数据结构课程设计(附代码)

第1页上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1.巩固和加深对常见数据结构的理解和掌握2.掌握基于数据结构进行算法设计的基本方法3.掌握用高级语言实现算法的基本技能4.掌握书写程序设计说明文档的能力5.提高运用数据结构知识及高级语言解决非数值实际问题的能力二.课程设计内容说明1.项目一(1)对设计任务内容的概述学生成绩管理**任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。(2)详细设计LinkList*create()：输入学生成绩记录函数；voidprint(LinkList*head)：显示全部记录函数LinkList*Delete(LinkList*head)：删除记录函数LinkList*Insert(LinkList*head)：插入记录函数voidmenu_select()：菜单选择voidScoreManage()：函数界面(3)程序流程图第2页(4)程序模块及其接口描述该程序可以分为以下几个模块：1、菜单选择：voidmenu_select();提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。2、输入功能：LinkList*create();通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链3．删除学生记录4．插入学生记录1．输入学生记录输入n（0n6）主界面2．输出学生记录退出学生成绩管理系统5．退出判断nn=5n=1、2、3、4第3页表。3、输出功能：voidprint(LinkList*head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。知道不满足循环语句，程序再次回到菜单选择功能界面。4、删除功能：LinkList*Delete(LinkList*head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。5、插入功能：LinkList*Insert(LinkList*head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。(5)程序的输入与输出描述输入：调用LinkList*create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用voidprint(LinkList*head)函数，输出学生的记录。(6)程序测试主菜单：第4页成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：第5页学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）第6页(7)尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的文件保存以及按学号、姓名等的查询也是缺少的。还有就是，对于多个学生成绩的操作也是不够的。改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也应修改系统，让它更为人性化、简单化，被广大用户所接受。(8)对软件的使用说明该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不方便性，但由于时间的缘故，无法将软件做到尽善尽美。2.项目二(1)对设计任务内容的概述各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。第7页(2)功能描述该函数有以下几个功能：1)对R[0..n-1]按递增有序进行直接插入排序2)对R[0..n-1]按递增有序进行冒泡排序3)对R[0..n-1]按递增有序进行直接选择排序4)排序后的输出5)调用所有排序，实现排序(3)程序流程图(4)详细设计voidInsertSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行直接插入排序voidBubbleSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行冒泡排序voidSelectSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行直接选择排序voiddisp(RecTypeR[],intn)：排序后的输出voidSort()：调用所有排序，实现排序直接插入排序InsertSort()退出排序Sort（）直接选择排序SelectSort()冒泡排序BubbleSort()第8页(5)程序模块及其接口描述该程序分为五个模块:1.输入功能：voidSort()建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数，对关键字进行排序。2.直接插入排序功能：voidInsertSort(RecTypeR[],intn)将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。3.冒泡排序功能：voidBubbleSort(RecTypeR[],intn)在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位exchange，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置exchange值为0，在进行数据交换时，修改exchange为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序。4.直接选择排序功能：voidSelectSort(RecTypeR[],intn)在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置上的数字交换。5.输出功能：voiddisp(RecTypeR[],intn)(6)程序的输入与输出描述输入：要求是10个为数字的关键字；输出：排序后新的序列。(7)程序测试输入关键字，调用各种排序函数第9页(8)尚未解决的问题或改进方向改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它们的不同。(9)对软件的使用说明用户只需根据提示，在键盘上输入要排序的10个关键字。3.项目三(1)对设计任务内容的概述有序表的合并要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功能，并输出合并后的信息。(2)功能描述该程序有如下几个功能：1)初始化顺序表2)初始化链表3)建立顺序表4)尾插法建表5)输出合并后的顺序表6)输出合并后的单链表7)合并顺序表第10页8)合并单链表9)调用以上的函数，实现有序表的合并(3)概要设计或程序流程图(4)详细设计voidInitList(SqList*&L)：初始化顺序表voidInitList1(LinkList1*&L)：初始化链表voidCreateList(SqList*&L,ElemTypea[],intn)：建立顺序表voidCreateListR(LinkList1*&L,ElemTypea[],intn)：尾插法建表voidDispList(SqList*L)：输出合并后的顺序表voidDispList1(LinkList1*L)：输出合并后的单链表voidUnionList(SqList*LA,SqList*LB,SqList*&LC)：合并顺序表voidUnionList1(LinkList1*LA,LinkList1*LB,LinkList1*&LC)：合并单链表voidUnion()：调用以上的函数，实现有序表的合并。(5)程序模块及其接口描述程序有以下几个模块：开始初始化顺序表初始化链表建立顺序表尾插法建表合并顺序表合并单链表输出结束第11页1)初始化、建立顺序表2)初始化、建立链表3)输出合并后的表4)合并表(6)调试分析或程序测试有序表的合并：(7)尚未解决的问题或改进方向不足：不能重复使用程序。(8)对软件的使用说明用户只需根据界面的提示，采用对应的操作。4．项目四(1)对设计任务内容的概述建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法都可以）**任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；(2)功能描述第12页1)建立二叉树2)输出二叉树3)先序遍历非递归算法：不为空时，访问根--左--右，采用递归的方法。4)中序遍历非递归算法：不为空时，访问左--根--右，采用递归的方法。5)后序遍历非递归算法：不为空时，访问左--右--根，采用递归的方法。6)层序遍历：运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。7）调用以上函数实现二叉树的各种遍历(3)概要设计或程序流程图(4)详细设计voidCreateBTNode(BTNode*&b,char*str)：建立二叉树voidDispBTNode(BTNode*b)：输出二叉树voidPreOrder(BTNode*b)：先序遍历非递归算法voidInOrder(BTNode*b)：中序遍历非递归算法voidPostOrder(BTNode*b)：后序遍历非递归算法voidLevelOrder(BTNode*b)：层序遍历(5)程序模块及其接口描述开始输入二叉树的按层结点值先序遍历中序遍历层次遍历后序遍历结束第13页(6)程序的输入与输出描述输入二叉树的按层结点值；输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序；输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序；(7)调试分析或程序测试用户从键盘上输入要创建的二叉树结点：(8)尚未解决的问题或改进方向改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。(9)对软件的使用说明用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。5．项目五（1）对设计任务内容的概述猴子选大王**任务：一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,nm,n为整数，nm输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能第14页（2）需求分析或功能描述为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。（3）概要设计或程序流程图（4）详细设计或源代码说明为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数intMonkey()实现了这一功能。（5）程序模块及其接口描述运用队列（环形队列），编号=密码值入队；为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数intM