西安石油大学：《数据结构》精品课程资源_设计大纲

《数据结构课程设计》教学大纲 课程设计中文名称:数据结构课程设计适合专业:计算机科学与技术,软件工程 设计周数:2周 学分:2学分 开课学期:第4学期 开课单位:计算机学院 课程设计的教学目的和任务 通过本课程设计教学所要达到的目的是:1、使学生进一步理解和掌握课堂上所学各种基本抽象 数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。Σ、使学生掌握软 件设计的基本内容和设计方法,并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计 算机资料和有关参考资料,提高学生的基本设计能力。 本课程设计的任务是:学生应该完成指导教师布置的课程设计题目,并按照规范提交课程设计报 告 二、课程设计的主要内容 数据结构课程设计包含以下主要内容 1.分析课题,查阅相关资料; 2.方案论证、数据结构设计; 3.编写代码并调试 4.数据课程设计报告。 三、课程设计的基本教学要求 1.巩固和加深对数据结构基本知识的理解,提高综合运用课程知识的能力。 2.培养学生根据课程需要自学参考书籍,查阅手册、图表和文献资料的能力, 3.通过实际课程设计,初步掌握简单实用软件的分析方法和设计方法。 4.了解与课程有关的工程技术规范,按课程设计任务书的要求编写设计说明书,能正确反映设 计的实验结果。 5.选题具有足够的工作量,学生具有足够的自学能力和独立工作能力。 四、课程设计报告的规范 课程设计报告要求规范书写。应当包括如下八个部分 1.问题描述:描述要求编程解决的问题。 2.基本要求:给出程序要达到的具体的要求。 3.测试数据:设计测试数据,或具体给出测试数据。要求测试数据能全面地测试所设计程序的 功能 4.算法思想:描述解决相应问题算法的设计思想 5.模块划分:描述所设计程序的各个模块(即函数)功能。 6.数据结构:给出所使用的基本抽象数据类型所定义的具体问题的数据类型 Data Type,以及 新定义的抽象数据类型。 7.源程序:给出所有源程序清单,要求程序有充分的注释语句,至少要注释毎个函数参数的含 义和函数返回值的含义 8.测试情况:给出程序的测试情况说明。 五、成绩评定标准 学生成绩以优、良、中、及格和不及格5个等级评定 1.以学生制作的实物为依据,占总成绩60% 2.设计报告,占总成绩30% 3.教师提问,占总成绩10% 六、参考文献 1.《数据结构-使用C语言》,西安交通大学出版社,朱站立编著; 2.《数据结构-C语言描述》,清华大学岀版社,严蔚敏编著 3.http://realcourse.grids.cn/ 4.http://student.zjzk.cn/courseware_/data_structure/web/main.htm

《数据结构课程设计》教学大纲 课程设计中文名称：数据结构课程设计 适合专业：计算机科学与技术，软件工程 设计周数：2周 学 分：2学分 开课学期：第4学期 开课单位：计算机学院 一、课程设计的教学目的和任务 通过本课程设计教学所要达到的目的是：1、使学生进一步理解和掌握课堂上所学各种基本抽象 数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软 件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计 算机资料和有关参考资料，提高学生的基本设计能力。 本课程设计的任务是：学生应该完成指导教师布置的课程设计题目，并按照规范提交课程设计报 告。 二、课程设计的主要内容 数据结构课程设计包含以下主要内容： 1. 分析课题，查阅相关资料； 2. 方案论证、数据结构设计； 3. 编写代码并调试； 4. 数据课程设计报告。 三、课程设计的基本教学要求 1. 巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。 2. 培养学生根据课程需要自学参考书籍，查阅手册、图表和文献资料的能力。 3. 通过实际课程设计，初步掌握简单实用软件的分析方法和设计方法。 4. 了解与课程有关的工程技术规范，按课程设计任务书的要求编写设计说明书，能正确反映设 计的实验结果。 5. 选题具有足够的工作量，学生具有足够的自学能力和独立工作能力。 四、课程设计报告的规范 课程设计报告要求规范书写。应当包括如下八个部分： 1. 问题描述：描述要求编程解决的问题。 2. 基本要求：给出程序要达到的具体的要求。 3. 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的 功能。 4. 算法思想：描述解决相应问题算法的设计思想。 5. 模块划分：描述所设计程序的各个模块（即函数）功能。 6. 数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型DataType,以及 新定义的抽象数据类型。 7. 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含 义和函数返回值的含义。 8. 测试情况：给出程序的测试情况说明。 五、成绩评定标准 学生成绩以优、良、中、及格和不及格5个等级评定。 1．以学生制作的实物为依据，占总成绩60% 2．设计报告，占总成绩30% 3．教师提问，占总成绩10% 六、参考文献 1．《数据结构-使用C语言》，西安交通大学出版社，朱站立编著； 2．《数据结构-C 语言描述》，清华大学出版社，严蔚敏编著； 3．http://realcourse.grids.cn/ 4．http://student.zjzk.cn/course_ware/data_structure/web/main.htm

5.=n时,C=X1,y1,X2y nini 当n>m时,C=y1,X1,y2,X2…Ym,Xm…,yn 输出线形表C (5)用直接插入排序法对C进行升序排序,生成链表D,并输出链表D 测试数据 (1)A表(30,41,15,12,56,80)

5．《Data Structures and Program Design in C++》Robert L. Kruse,Alexandeer J. Ryba编，高等教育出版社2002（影印版） 6．《DATA STRUCTURES AND ALGORITHM ANALYSIS》CLIFFORD A. SHAFFER编， PRENTICE HALL出版公司1996出版 七、编写大纲的执笔人和审定人 执笔人：韩家新 审定人：朱战立 附件一 部分课程设计题目 1．排序算法比较 利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、 归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 2．图的深度周游 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算 （清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索周游 3．图的广度周游 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算 （置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。 4．二叉树的周游 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空 栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游 的结果。 5．链表操作 利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表 的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后 的结果。 6．设计一元稀疏多项式简单计数器 （1） 输入并建立多项式 （2） 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项 数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。 （3） 多项式a和b相加，建立多项式a+b，输出相加的多项式。 （4） 多项式a和b相减，建立多项式a-b，输出相减的多项式。 用带表头结点的单链表存储多项式。 测试数据： （1）(2x+5x8-3.1x11)+(7-5x8+11x9) （2） (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) （3）(x+x2+x3)+0 （4）(x+x3)-(-x-x -3) 7．实现两个链表的合并 基本功能要求： （1）建立两个链表A和B，链表元素个数分别为m和n个。 （2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得： 当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm 当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn 输出线形表C （5） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。 测试数据： （1） A表（30，41，15，12，56，80）

B表(23,56,78,23,12,33,79,90,55) (2)A表(30,41,15,12,56,80,23,12,34) B表(23,56,78,23,12) 附件二课程设计报告范例 约瑟夫环问题。 问题描述:设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈,每人持有一个正整数密码。开始时 任意给出一个报数上限值m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,抱m 的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人起重新自1起顺序报数;如此 下去,直到所有人全部出列为止。要求设计一个程序模拟此过程,并给出出列人的编号序列 基本要求 (1)初始报数上限值m和测试数据在程序中确定; (2)用带头结点的单循环链表作数据元素的存储结构 (3)把带头结点的单循环链表作为抽象数据类型设计 测试数据 n=7,七个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20 算法思想 Jeseph Ring()函数是实现问题要求的主要函数,其算法思想是:从1至m对带头结点的单循环链表 循环计数,到m时,输出该结点的编号值,将该结点的密码作为新的m值,再从该结点的下一个结 点起重新自1起循环计数;如此下去,直到单循环链表空时循环过程结束。 模块划分 1)带头结点的单循环链表抽象数据类型 SCLinList,其中包括基本操作的函数有:初始化操作函 数、插入一个结点操作函数、删除_个结点操作函数、取一个结点数据操作函数和判表是否非空拶 作函数。该抽象数据类型文件名为 SCLinList. h。 2) void scLLDelete After( SCLNode*p),其功能是删除带头结点的单循环链表中指针p所指 结点的下一个结点。这是对带头结点的单循环链表抽象数据类型 SCLinList,补充本问题需要的一个 操作函数。 (3) void Jeseph Ring( SCLNode*head,intm),其功能是对带头结点的单循环链表head,以m 为初始报数上限值实现问题要求 (4) void main(void),主函数,功能是给出测试数据值,建立测试数据值的带头结点单循环链 表,调用] esephRing(函数实现问题要求 数据结构 (1)数据类型 DataType定义如下: typedef struct int number It cipher; s DataType (2)带头结点单循环链表抽象数据类型 SCLinList。 (3)带头结点单循环链表抽象数据类型的结点结构定义如下: typedef struct node DataType data struct node *next. SCLNode 源程序

B表（23，56，78，23，12，33，79，90，55） （2） A表（30，41，15，12，56，80，23，12，34） B表（23，56，78，23，12） 附件二 课程设计报告范例 约瑟夫环问题。 问题描述：设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时 任意给出一个报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，抱m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此 下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 基本要求： （1）初始报数上限值m和测试数据在程序中确定； （2）用带头结点的单循环链表作数据元素的存储结构； （3）把带头结点的单循环链表作为抽象数据类型设计。 测试数据： n = 7，七个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m = 20 算法思想： JesephRing()函数是实现问题要求的主要函数，其算法思想是：从1至m对带头结点的单循环链表 循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结 点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。 模块划分： （1）带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函 数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操 作函数。该抽象数据类型文件名为SCLinList.h。 （2）void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指 结点的下一个结点。这是对带头结点的单循环链表抽象数据类型SCLinList，补充本问题需要的一个 操作函数。 （3）void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m 为初始报数上限值实现问题要求。 （4）void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链 表，调用JesephRing()函数实现问题要求。 数据结构： （1）数据类型DataType定义如下： typedef struct { int number; int cipher; } DataType; （2）带头结点单循环链表抽象数据类型SCLinList。 （3）带头结点单循环链表抽象数据类型的结点结构定义如下： typedef struct node { DataType data; struct node *next; } SCLNode; 源程序：

源程序存放在两个文件中,文件 SCLinlist.h是带头结点单循环链表抽象数据类型,文件Exam3· 9.c是主程序。 文件 SCLinList h typedef struct node Data Type data; struct node *next 1 SCLNode /*结点结构定义*/ void SCLLInitiate(sCLNode **head) /*初始化*/ if(head =(SCLNode *)malloc(sizeof(SCLNode ))== NULL) exit(1); head)->next =*head nt scllinsert( SCLNode*head,inti, Data Type x)/*插入一个结点*/ SCLNode p, *g: p= head->next: j=1 while(p!= head &&jnext:J+ ifG 1&&i!=1) printf(("插入位置参数错!"); return o } if((q =(SCLNode *)malloc(sizeof(sSCLNode)))== NULL) exit(1); q->data =X q->next= p->next p->next q; return 1 } nt sclldelete( SCLNode*head,inti, DataType*x)/*删除一个结点* { SCLNode *, *g: p= head;j= 0; while(p->next!= head &&jnext: j++i printf(("删除位置参数错!"); return o

源程序存放在两个文件中，文件SCLinList.h是带头结点单循环链表抽象数据类型，文件Exam3- 9.c是主程序。 文件SCLinList.h： typedef struct node { DataType data; struct node *next; } SCLNode; /*结点结构定义*/ void SCLLInitiate(SCLNode **head) /*初始化*/ { if((*head = (SCLNode *)malloc(sizeof(SCLNode))) == NULL) exit(1); (*head)->next = *head; } int SCLLInsert(SCLNode *head, int i, DataType x) /*插入一个结点*/ { SCLNode *p, *q; int j; p = head->next; j = 1; while(p != head && j next; j++; } if(j != i - 1 && i != 1) { printf("插入位置参数错！"); return 0; } if((q = (SCLNode *)malloc(sizeof(SCLNode))) == NULL) exit(1); q->data = x; q->next = p->next; p->next = q; return 1; } int SCLLDelete(SCLNode *head, int i, DataType *x) /*删除一个结点*/ { SCLNode *p, *q; int j; p = head; j = 0; while(p->next != head && j next; j++; } if(j != i - 1) { printf("删除位置参数错！"); return 0;

} q= p->next: p->next p->next->next: *X=g->data free(g) return li } nt sallet( SCLNode*head,inti, DataType*x)/*取一个结点数据元素值*/ SCLNode * p: p= head;j=0 while(p->next!= head &&jnext: j++ if(j!=i) printf(("取元素位置参数错!"); return o *x= p->data return 1 int SCLLNotEmpty (sCLNode *head) /*链表非空否*/ if(head->next = head return 0 else return 1 文件Exam3-9c #include #include typedef struct t number, nt cipher s DataType /*定义具体的数据类型 Data Type*/ #include " SCLinList h /*包含 SCLinlist抽象数据类型*/ void sclldelete After( SCLNode*p)/*删除p指针所指结点的下一个结点*/ SCLNode *q= p->next p->next p->next->next: free(g)

} q = p->next; p->next = p->next->next; *x = q->data; free(q); return 1; } int SCLLGet(SCLNode *head, int i, DataType *x) /*取一个结点数据元素值*/ { SCLNode *p; int j; p = head; j = 0; while(p->next != head && j next; j++; } if(j != i) { printf("取元素位置参数错！"); return 0; } *x = p->data; return 1; } int SCLLNotEmpty(SCLNode *head) /*链表非空否*/ { if(head->next == head) return 0; else return 1; } 文件Exam3-9.c： #include #include typedef struct { int number; int cipher; } DataType; /*定义具体的数据类型DataType*/ #include "SCLinList.h" /*包含SCLinList抽象数据类型*/ void SCLLDeleteAfter(SCLNode *p) /*删除p指针所指结点的下一个结点*/ { SCLNode *q = p->next; p->next = p->next->next; free(q); }

void JesephRing(sCLNode *head, int m) /*对带头结点单循环链表head,初始值为m的约瑟夫环问题函数*/ SCLNode *pre, *curr int i. pre= head curr head->next. while (sCllNotempty (head)== 1) for(=1;inext if(curr = head) pre curri curr curr->next. printf(" %od,curr->data number) m= curr->data cipher curr curr->next. if(curr = head) curr curr->next: SCLLDelete After(pre) void main(void) DataType test[7]={{1,3},{2,1},{3,7}{4,2},{5,4},{6,8}{74}}; ntn=7,m=20,i; SCLNode *head SCLLInitiate(head) /*初始化*/ for (i= l; /*循环插入建立单循环链表链表*/ SCLLInsert(head, i, test[i-1D) JesephRing(head, m) /*约瑟夫环问题函数*/ 测试情况 程序输出为 6147235

void JesephRing(SCLNode *head, int m) /*对带头结点单循环链表head，初始值为m的约瑟夫环问题函数*/ { SCLNode *pre, *curr; int i; pre = head; curr = head->next; while(SCLLNotEmpty(head) == 1) { for(i = 1; i next; if(curr == head) { pre = curr; curr = curr->next; } } printf(" %d ", curr->data.number); m = curr->data.cipher; curr = curr->next; if(curr == head) curr = curr->next; SCLLDeleteAfter(pre); } } void main(void) { DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}}; int n = 7, m = 20, i; SCLNode *head; SCLLInitiate(&head); /*初始化*/ for(i = 1; i <= n; i++) /*循环插入建立单循环链表链表*/ SCLLInsert(head, i, test[i-1]); JesephRing(head, m); /*约瑟夫环问题函数*/ } 测试情况： 程序输出为： 6 1 4 7 2 3 5