数据结构课程设计

1、上海应用技术学院课程设计报告课程名称数据结构课程设计设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级_姓名学号指导教师日期一. 目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二. 课程设计内容说明1.项目一(1) 对设计任务内容的概述学生成绩管理*任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储，每个学生记

2、录包含的信息有：学号和各 门课程的成绩，设学生成绩至少 3门以上。存储结构：采用线性链式结构。(2) 详细设计LinkList *create():输入学生成绩记录函数；void print(LinkList *head) :显示全部记录函数LinkList *Delete(LinkList *head):删除记录函数LinkList *lnsert(LinkList *head):插入记录函数void menu_select():菜单选择void ScoreManage():函数界面程序流程图学生成绩管理系统4 插入学牛记录输入学生记录(4) 程序模块及其接口描述 该程序可以分为以下几个模块

3、：1、菜单选择：void menu _select();提供五种可以选择的操作，在main函数中通过switch 语句调用菜单 menu_select()函数，进入不同的功能函数中完成相关操作。2、输入功能：Li nkList *create();通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链3、输出功能：void prin t(L in kList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。 知道不满足循环语句，程序再次回到菜单选择功能界面。4、删除功能:Li nkList *Delete(Li nkList *

4、head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释 放，最后完成对某个学生记录进行删除，并重新存储。5、 插入功能：Li nkList *ln sert(L in kList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置， 将该新的学生 记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。(5) 程序的输入与输出描述输入：调用Lin kList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList

5、 *head)函数，输出学生的记录。(6) 程序测试主菜单：成绩管理系统的主界面:料耳N耳M港The-F：l主科庁.e*i：录1G 学1CD1X 二 二 XX 二 X 二蜀蚩何 uent盟率一 亦站人出除入出U2输入您的运择=学生成绩记录的输入:输出学生成绩记录:-F: l主科庁.ej且貝:M JtJCJHKJBKKK Kit ! H KU jKJtJtL lnkLlSt学号丨窪g I悟文:数学英语!11R2!hr!S2：9211 Bl!uan91BSI7fi二二* nhl c * _诸 二 己 a卄 i 二 Tl n g-录录录的 0 *己己己折 nt;盟孟Z于一 de+ 入出学生成绩记录的

6、删除（删除学号是 1101的学生记录）1101勺学号；.101且貝 W J* JC JH J( JM 扯 K K JCJI! :M 理 KU M： JI.R 0 |J klD 宾 X 宾 JC JI J JI JC Jt ：M Kit 何 Jt J H K H XU KW Xlt悟丈教学vjcui-y78您确定蓦删除该学绘的记录吗S ?,字号为111的学生记录己械別除.Ueleone toThe student score manage svsten耳uitB弭xsKitat jfjtx涯icxiot插:k kjc acHIFNII *0*并墓梵11兴1耳1寰贰耳*1*1*:廉址蔦疋鳶:連退出

7、的学生记議插入新的学生成绩记录（插入学号为 1103的学生记录）-F：l主科庁.CJ且貝:M JtJCJHKJBKKK Kit ! H KU jKJtJtL lnkLlSt学号丨窪g I悟文:数学英语!11R2!hr!S2：92:nm:sit77:as输入爺的选择门为:二y *二* nhl C * _诸 二 己 a卄 i n g-录录录的 0 *己己己折 nt;盟孟Z于一 de+ 入出(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是 有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的 文件保存以及按学号、姓名等的查询也是缺少

8、的。还有就是，对于多个学生成绩的操作也是不够的。改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也 应修改系统，让它更为人性化、简单化，被广大用户所接受。(8) 对软件的使用说明该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能： 输 人输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不 方便性，但由于时间的缘故，无法将软件做到尽善尽美。2.项目二(1) 对设计任务内容的概述各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法 ，将用户随机输入的一列数 按递增的顺序排好。输入的数据形式为任何一

9、个正整数，大小不限。输出的形式：数字大小逐个递增的数列。(2) 功能描述该函数有以下几个功能：1) 对R0.n-1按递增有序进行直接插入排序2) 对R0.n-1按递增有序进行冒泡排序3) 对R0.n-1按递增有序进行直接选择排序4) 排序后的输出5) 调用所有排序，实现排序(3)程序流程图直接插入排序直接选择排序b 冒泡排序 创bleSort()排序Sort ()1L.(4)详细设计voidIn sertSort(RecTypeR,i ntn):对 R0.n-1插入排序voidBubbleSort(RecTypeR,i ntn):对 R0.n-1排序voidSelectSort(RecType

10、R,i ntn):对 R0.n-1选择排序void disp(RecType R,i nt n):排序后的输出void Sort():调用所有排序，实现排序按递增有序进行直接按递增有序进行冒泡按递增有序进行直接(5) 程序模块及其接口描述 该程序分为五个模块 :1. 输入功能： void Sort()建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数， 对关键字进行排序。2. 直接插入排序功能： void InsertSort(RecType R,int n) 将后一个数与前一个数比较， 将其插入到第一个比它大的大的数前面， 其余数 字往后移一个位置。 每次从无序表中取出第一个

11、元素， 把它插入到有序表的合适 位置，使有序表仍然有序。3. 冒泡排序功能： void BubbleSort(RecType R,int n)在排序过程中， 执行完最后的排序后，虽然数据已全部排序完备，但程序无法 判断是否完成排序，为了解决这一不足，可设置一个标志位exchange,将其初始值设置为非 0，表示被排序的表是一个无序的表，每一次排序开始前设置 exchange 值为 0,在进行数据交换时,修改 exchange 为非 0。在新一轮排序开 始时, 检查此标志, 若此标志为 0,表示上一次没有做过交换数据, 则结束排序； 否则进行排序。4. 直接选择排序功能： void Select

12、Sort(RecType R,int n)在无序区里找最小的数, 第 i 小的数字放在第 i 个位置上, 与原来第 i 个位置 上的数字交换。5. 输出功能： void disp(RecType R,int n)(6) 程序的输入与输出描述 输入：要求是 10 个为数字的关键字； 输出：排序后新的序列。(7) 程序测试输入关键字,调用各种排序函数EE-F: l主科庁.eji 34 砧 is2 3 7 ft 1055 5t It?冒泡琳序=1 2 17 S lfi 34 跖 EG S9圭粟鱼统 并 系树合 理序A的 靠二表ac k* kx KXKXFHXiw at XH* kkxkk aexiM

13、K nxaoeiorxiMwx输入您的选择CL5、=(8) 尚未解决的问题或改进方向改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它们的不同。(9) 对软件的使用说明用户只需根据提示，在键盘上输入要排序的10个关键字。3.项目三(1) 对设计任务内容的概述有序表的合并要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功 能，并输出合并后的信息。(2) 功能描述该程序有如下几个功能：1) 初始化顺序表2) 初始化链表3) 建立顺序表4) 尾插法建表5) 输出合并后的顺序表6) 输出合并后的单链表7) 合

14、并顺序表8) 合并单链表9)调用以上的函数，实现有序表的合并 (3)概要设计或程序流程图(4) 详细设计void In itList(SqList *&L):初始化顺序表void Ini tList1(Li nkListl *&L):初始化链表void CreateList(SqList *&L,ElemType a,i nt n):建立顺序表void CreateListR(Li nkList1 *&L,ElemType a,i nt n):尾插法建表void DispList(SqList *L):输出合并后的顺序表void DispList1(L in kListl *L):输出合并后的

15、单链表void Union List(SqList *LA,SqList *LB,SqList *&LC):合并顺序表void Union List1(Li nkListl *LA ,L i nkListl *LB ,L i nkListl *&LC):合并单链表void Union():调用以上的函数，实现有序表的合并。(5) 程序模块及其接口描述程序有以下几个模块：1) 初始化、建立顺序表2) 初始化、建立链表3) 输出合并后的表4) 合并表(6)调试分析或程序测试(7) 尚未解决的问题或改进方向 不足：不能重复使用程序。(8) 对软件的使用说明用户只需根据界面的提示，采用对应的操作4 .

16、项目四(1)对设计任务内容的概述建立二叉树，层序、先序、中序、后序遍历(用递归或非递归的方法都可以)*任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列； 分别 建立二叉树存储结构的的输入函数、 输出层序遍历序列的函数、输出先序遍历序 列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；(2)功能描述1) 建立二叉树2) 输出二叉树3) 先序遍历非递归算法:不为空时，访问根-左-右，采用递归的方法。4) 中序遍历非递归算法：不为空时，访问左-根-右，采用递归的方法。5) 后序遍历非递归算法：不为空时，访问左-右-根，采用递归的方法。6) 层序遍历：运用队列，队列不空时，有

17、左孩子将其入队，有右孩子将其入队，同时出队7) 调用以上函数实现二叉树的各种遍历(3)概要设计或程序流程图(4) 详细设计void CreateBTNode(BTNode * & b,char *str):建立二叉树void DispBTNode(BTNode *b):输出二叉树void PreOrder(BTNode *b):先序遍历非递归算法void In Order(BTNode *b):中序遍历非递归算法void PostOrder(BTNode *b):后序遍历非递归算法void LevelOrder(BTNode *b):层序遍历(5) 程序模块及其接口描述(6) 程序的输入与输出

18、描述输入二叉树的按层结点值；输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序; 输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序;(7) 调试分析或程序测试用户从键盘上输入要创建的二叉树结点:山P注主程序ab,c(e-f二貝树甜；1先序遍历序列alxtErcef一一殳树h的中尸遍巧序列曲1 nu二叉树h的后底遍历序列gdbEf ca一叉餐fit的层庆遍厉呼列abcdef畅 并 系树合 理序X的 工01二表 咸各建有退(8) 尚未解决的问题或改进方向改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。(9) 对软件的使用说明用户只需按照界面的提示

19、，采取相应的措施，到时界面会提醒用户键盘输入。 5项目五(1)对设计任务内容的概述猴子选大王*任务：一堆猴子都有编号，编号是 1, 2, 3 .m ,这群猴子(m个)按照 1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这 样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n为整数，*m输出形式：中文提示按照 m个猴子，数n个数的方法，输出为大王的猴子 是几号，建立一个函数来实现此功能(2) 需求分析或功能描述为猴子编号out，编号out=pass (pass为密码值)，该猴子离圈，次数step+ 剩下的猴子继续次操作，直到次数 st

20、ep=猴子monkey时结束。（3）概要设计或程序流程图（4）详细设计或源代码说明为猴子编号out，编号out=pass （pass为密码值），该猴子离圈，次数step+。 剩下的猴子继续次操作，直到次数 step=猴子mon key时结束。函数int Monkey（）实现了这一功能。（5）程序模块及其接口描述运用队列（环形队列），编号二密码值 入队；为猴子编号out，编号out=pass （pass为密码值），该猴子离圈，次数step+。剩下的猴子继续次操作，直到次 数 step=猴子 monkey时结束。函数int Monkey（）实现了这一功能。（6）程序的输入与输出描述输入数据：输入m

21、,n m,n为整数，*m输出形式：中文提示按照 m个猴子，数n个数的方法，输出为大王的猴子 是几号，建立一个函数来实现此功能。（7）调试分析或程序测试猴子数量8,密码值9 （猴子数密码值）.1 DULt .3 out.6 out -4 out .5 out.2 out.,? out,-8 out,主菜单ithmm at: atiffKwratKnu wkacuatla-畴管理系统*3 建立二叉树*1-有序禹騎答并（8）尚未解决的问题或改进方向不足：不能重复使用程序，如果数字大的话，输出繁琐。（9）对软件的使用说明用户只需根据软件界面的提示进行相关操作。三. 结论及体会本学期，我学会了常用数据结

22、构：数组（连续空间），栈（先进后出），队列 （先进先出），链表（指针），树（前驱、后继，根、叶子），图（点、边），堆（特 殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存 储，常用的排序算法。在这一周里，自己用了 C Free做了一个程序，分别实现了学生成绩管理系 统、各种排序、有序表的合并、二叉树的建立及遍历以及猴子选大王，通过本次 数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、 链表等知识。在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、 图书馆查阅资料、问老师的方式，最终还是解决多数，虽然最后的程序不是很完 美，但是因为是

23、通过自己的努力完成的，还是感觉很满意，也收获很大东西。 经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很 是开心。 在这一段努力学习的过程中， 我的编程设计有了明显的提高， 其实现在 想起来， 收获还真是不少， 虽然说以前非常不懂这门语言， 在它上面花费了好多 心血，觉得它很难， 是需用花费了大量的时间编写出来的。 现在真正的明白了一 些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力 去学习，就会灵活的去应用它。总之，通过这次的课程设计，我们收获匪浅，首先由衷感谢老师提供这样的 一

24、个机会锻炼自己， 感受到学来的知识不只是用来完成试卷的。 一向习惯独立思 考的自己学会了积极的与别人交流，取长补短， 共同进步。 课程设计使自己发现 考试不是最重要的， 最重要的是能运用所学的知识。 在整个课程设计的学习过程 中，不再是学到知识解题， 而是在实际运用时遇到什么学什么， 重在把知识应用 于实际。附录 1：参考文献1 数据结构教程（第 3 版），李春葆，清华大学出版社， 20102 数据结构 ，杨剑，清华大学出版社， 20113 数据结构 （C 语言版 ） ，严蔚敏 吴伟民，清华大学出版社， 19974 Data Structures Using C数据结构（C 语言版）R Kri

25、shnamoorthy、G IndiraniKumaravel ，清华大学出版社， 2009-9 C+数据结构与程序设计（美）Robert Alexander着/钱丽萍译，清华大学出版社， 20046 计算机算法设计与分析（第 2 版），王晓东， 电子工业出版社， 2004附录 2：部分源代码清单#include #include #include#include #include #define LEN sizeof(LinkList)#define MaxSize 50函数带回一个指向链表头的指针 */system(cls);printf(n 请输入您想输入的学生个数： ); scanf(

26、%d,&k);for(j=0;jnum);printf( 输入姓名 :);scanf(%s,p-name);printf( 请分别输入语文、数学、英语的分数 %d scoresn,3);/* 开始输入*/for(i=0;iscorei);if(p-scoreiscorei100) /*确保成绩在 0100之间*/printf(Data error,please enter again.n); while(p-scoreiscorei100);*/p-next=head;/*将头结点做为新输入结点的后继结点head=p;/*新输入结点为新的头结点 */return(head);/* 显示全部记录

27、函数 */ void print(LinkList *head)LinkList *p;system(cls);p=head; /* 初值为头指针 */printf(n*LinkList*n);printf(n);printf(| 学号 | 姓名 | 语文 | 数学 | 英语 | n);printf(n);while(p!=NULL)printf(| %4s | %-4s | %3d | %3d | %3d |n, p-num,p-name,p-score0,p-score1,p-score2); p=p-next;printf(n);printf(*END*n);/* 删除记录函数 */Li

28、nkList *Delete(LinkList *head)LinkList *p1,*p2; /*p1 为查找到要删除的结点指针， p2 为其前驱指针 */ char c,s6;/*s6用来存放学号,c用来输入字母*/system(cls);printf( 请输入要删除的学生的学号 : );scanf(%s,s);p仁p2=head; /* 给pl和p2赋初值头指针*/while(strcmp(p1-num,s) & p1 != NULL) /*当记录的学号不是要找的，或指针不为空时 */p2=p1;/*将pl指针值赋给p2作为pl的前驱指针*/p1=p1-next;/*将 p1 指针指向下

29、一条记录 */if(strcmp(p1-num,s)=0) /*学号找到了 */printf(*FOUND*n);printf(-n);printf(| 学号 | 姓名 | 语文 | 数学 | 英语 |n);printf(n);printf(| %4s |%4s|%3d|%3d|%3d|n,p1-num,p1-name,p1-score0,p1-score1,p1-score2);printf(n)printf(*END*n ）;printf（ 您确定要删除该学生的记录吗 Y/N ?）; /* 提示是否要删除输入丫删除,N则退出*/for(;)scanf(%c,&c);if(c=n|c=N)

30、break; /*if(C=y|c=Y)如果不删除 , 则跳出本循环 */if(p1=head) /*若p仁=head,说明被删结点是首结点*/head=p1-next; /* 把第二个结点地址赋予 head*/ elsep2-next=p1-next;free(p1);/* 否则将一下结点地址赋给前一结点地址*/printf(n 学号为 %s 的学生记录已被删除 .n,s); break; /* 删除后就跳出循环 */elseprintf(n 找不到学号为 %s 的学生记录 .n,s); /* 找不到该结点 */ return(head);n);while(scorei100);p1=hea

31、d; /* 给 p1 赋初值头指针 */while(jnext; /*将 p1 指针指向下一条记录 */if(p1=NULL) return 0;else p2=(LinkList *)malloc(sizeof(LinkList);strcpy(p2-num,N);strcpy(p2-name,s); for(i=0;iscorei=scorei;p2-next=p1-next;p1-next=p2;void menu_select() printf(nnn);printf(f*n);printf(t Welcome to n);printf(t The student score mana

32、ge system n);printf(tt1.输入学生记录 n);/*输入学生成绩记录 */printf(tt2.输出学生记录 n);/*显示*/printf(tt3.删除学生记录 n);/*删除*/printf(tt4.插入一个新的学生记录n);/*插入*/printf(tt5.退出n);/*退出 */printf(*MENU*n);printf(f*n);/* 主函数界面 */ void ScoreManage() LinkList *head,New;int i,n;链表初始化,使head的值为NULL*/head=init(); /* menu_select();doprintf(n

33、tt 输入您的选择 (15):); scanf(%d,&n);while(n5);for(;) /* 循环无限次 */ switch(n)case 1:head=create();break;case 2:print(head);break;case 3:head=Delete(head);break;case 4:head=Insert(head);break;case 5:return; /* 如菜单返回值为 menu_select();printf(nttt 输入您的选择 (15):); scanf(%d,&n);n-1 按递增有序进行直接插入排序 */int i,j;RecType tmp;for (i=1;i=0 & Rj.key)的记录后移 */Rj+1=Rj; /* 将关键字大于 Ri.key j-;Rj+1=tmp; /* 在 j+1 处插入 Ri*/void BubbleSort(RecType R,int n) int i,j,exchange;RecType tmp;for(i=0;ii;j