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

上海应用技术学院课程设计报告课程名称 数据结构课程设计 设计题目 猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统； 院系 计算机科学与信息工程 专业计算机科学与技术 班级 姓名 学号 指导教师 日期 一. 目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二. 课程设计内容说明1. 项目一(1) 对设计任务内容的概述学生成绩管理*任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。(2) 详细设计LinkList *create()：输入学生成绩记录函数；void print(LinkList *head)：显示全部记录函数LinkList *Delete(LinkList *head)：删除记录函数LinkList *Insert(LinkList *head)：插入记录函数void menu_select()：菜单选择void ScoreManage()：函数界面(3) 程序流程图3删除学生记录4插入学生记录1输入学生记录输入n（0n6）主界面2输出学生记录退出学生成绩管理系统5退出判断nn=5n=1、2、3、4(4) 程序模块及其接口描述该程序可以分为以下几个模块：1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。2、输入功能：LinkList *create(); 通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链表。 3、输出功能：void print(LinkList *head); 通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。知道不满足循环语句，程序再次回到菜单选择功能界面。4、删除功能：LinkList *Delete(LinkList *head); 按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的文件保存以及按学号、姓名等的查询也是缺少的。还有就是，对于多个学生成绩的操作也是不够的。改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也应修改系统，让它更为人性化、简单化，被广大用户所接受。(8) 对软件的使用说明该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不方便性，但由于时间的缘故，无法将软件做到尽善尽美。2. 项目二(1) 对设计任务内容的概述各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。(2) 功能描述该函数有以下几个功能：1) 对R0.n-1按递增有序进行直接插入排序2) 对R0.n-1按递增有序进行冒泡排序3) 对R0.n-1按递增有序进行直接选择排序4) 排序后的输出5)调用所有排序，实现排序(3) 程序流程图直接插入排序InsertSort()退出排序Sort（）直接选择排序SelectSort()冒泡排序BubbleSort()(4) 详细设计void InsertSort(RecType R,int n)：对R0.n-1按递增有序进行直接插入排序void BubbleSort(RecType R,int n)：对R0.n-1按递增有序进行冒泡排序void SelectSort(RecType R,int n)：对R0.n-1按递增有序进行直接选择排序void disp(RecType R,int n)：排序后的输出void Sort()：调用所有排序，实现排序(5) 程序模块及其接口描述该程序分为五个模块:1.输入功能：void Sort() 建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数，对关键字进行排序。2.直接插入排序功能：void InsertSort(RecType R,int n)将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。3.冒泡排序功能：void BubbleSort(RecType R,int n) 在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位exchange，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置exchange值为0，在进行数据交换时，修改exchange为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序。4.直接选择排序功能：void SelectSort(RecType R,int n) 在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置上的数字交换。5.输出功能：void disp(RecType R,int n)(6) 程序的输入与输出描述输入：要求是10个为数字的关键字；输出：排序后新的序列。(7) 程序测试输入关键字，调用各种排序函数(8) 尚未解决的问题或改进方向改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它们的不同。(9) 对软件的使用说明用户只需根据提示，在键盘上输入要排序的10个关键字。3. 项目三(1) 对设计任务内容的概述有序表的合并要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功能，并输出合并后的信息。(2) 功能描述该程序有如下几个功能：1) 初始化顺序表2) 初始化链表3) 建立顺序表4) 尾插法建表5) 输出合并后的顺序表6) 输出合并后的单链表7) 合并顺序表8) 合并单链表9) 调用以上的函数，实现有序表的合并(3) 概要设计或程序流程图开始初始化链表初始化顺序表建立顺序表尾插法建表合并顺序表合并单链表输出结束(4) 详细设计void InitList(SqList *&L)：初始化顺序表void InitList1(LinkList1 *&L)：初始化链表void CreateList(SqList *&L,ElemType a,int n)：建立顺序表void CreateListR(LinkList1 *&L,ElemType a,int n)：尾插法建表void DispList(SqList *L)：输出合并后的顺序表void DispList1(LinkList1 *L)：输出合并后的单链表void UnionList(SqList *LA,SqList *LB,SqList *&LC)：合并顺序表void UnionList1(LinkList1 *LA,LinkList1 *LB,LinkList1 *&LC)：合并单链表void Union()：调用以上的函数，实现有序表的合并。(5) 程序模块及其接口描述程序有以下几个模块：1) 初始化、建立顺序表2) 初始化、建立链表3) 输出合并后的表4) 合并表(6) 调试分析或程序测试有序表的合并：(7) 尚未解决的问题或改进方向不足：不能重复使用程序。(8) 对软件的使用说明用户只需根据界面的提示，采用对应的操作。4项目四(1)对设计任务内容的概述建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法都可以）*任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；(2)功能描述1) 建立二叉树2) 输出二叉树3) 先序遍历非递归算法：不为空时，访问根-左-右，采用递归的方法。4) 中序遍历非递归算法：不为空时，访问左-根-右，采用递归的方法。5) 后序遍历非递归算法：不为空时，访问左-右-根，采用递归的方法。6) 层序遍历：运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。7） 调用以上函数实现二叉树的各种遍历(3)概要设计或程序流程图开始输入二叉树的按层结点值层次遍历后序遍历中序遍历先序遍历结束(4)详细设计void CreateBTNode(BTNode * &b,char *str)：建立二叉树void DispBTNode(BTNode *b)：输出二叉树void PreOrder(BTNode *b)：先序遍历非递归算法void InOrder(BTNode *b)：中序遍历非递归算法void PostOrder(BTNode *b)：后序遍历非递归算法void LevelOrder(BTNode *b)：层序遍历(5)程序模块及其接口描述(6)程序的输入与输出描述输入二叉树的按层结点值；输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序；输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序；(7)调试分析或程序测试用户从键盘上输入要创建的二叉树结点：(8)尚未解决的问题或改进方向改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。(9)对软件的使用说明用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。5项目五（1）对设计任务内容的概述猴子选大王*任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能（2）需求分析或功能描述为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step+。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。（3）概要设计或程序流程图开始输入猴子的数量和密码值编号=密码值，猴子出列，次数自增N次数=猴子数Y结束（4）详细设计或源代码说明为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step+。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数int Monkey()实现了这一功能。（5）程序模块及其接口描述运用队列（环形队列），编号=密码值 入队；为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step+。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数int Monkey()实现了这一功能。（6）程序的输入与输出描述输入数据：输入m,n m,n 为整数，n密码值）（8）尚未解决的问题或改进方向不足：不能重复使用程序，如果数字大的话，输出繁琐。（9）对软件的使用说明用户只需根据软件界面的提示进行相关操作。三 结论及体会本学期，我学会了常用数据结构：数组（连续空间），栈（先进后出），队列（先进先出），链表（指针），树（前驱、后继，根、叶子），图（点、边），堆（特殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存储，常用的排序算法。在这一周里，自己用了CFree做了一个程序，分别实现了学生成绩管理系统、各种排序、有序表的合并、二叉树的建立及遍历以及猴子选大王，通过本次数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、链表等知识。在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、图书馆查阅资料、问老师的方式，最终还是解决多数，虽然最后的程序不是很完美，但是因为是通过自己的努力完成的，还是感觉很满意，也收获很大东西。经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高，其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。总之，通过这次的课程设计，我们收获匪浅，首先由衷感谢老师提供这样的一个机会锻炼自己，感受到学来的知识不只是用来完成试卷的。一向习惯独立思考的自己学会了积极的与别人交流，取长补短，共同进步。课程设计使自己发现考试不是最重要的，最重要的是能运用所学的知识。在整个课程设计的学习过程中，不再是学到知识解题，而是在实际运用时遇到什么学什么，重在把知识应用于实际。附录1：参考文献1 数据结构教程（第3版），李春葆，清华大学出版社，20102数据结构，杨剑，清华大学出版社，20113数据结构(C语言版)，严蔚敏 吴伟民，清华大学出版社，19974Data Structures Using C数据结构（C语言版），R Krishnamoorthy、G Indirani Kumaravel，清华大学出版社，2009-95C+数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译， 清华大学出版社，2004 6计算机算法设计与分析（第2版），王晓东， 电子工业出版社， 2004附录2：部分源代码清单#include #include #include#include #include #define LEN sizeof(LinkList)#define MaxSize 50/*/成绩管理系统typedef struct LNode/*定义单链表结点类型*/char name10; /姓名 char num10;/学号 int score3; struct LNode *next; LinkList;LinkList *init()return NULL; /*返回空指针*/LinkList *create()int i,s,k;int j=0;LinkList *head=NULL,*p; /* 定义函数.此函数带回一个指向链表头的指针*/system(cls); printf(n请输入您想输入的学生个数：);scanf(%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); /* 显示全部记录函数*/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);/*删除记录函数*/LinkList *Delete(LinkList *head)LinkList *p1,*p2; /*p1为查找到要删除的结点指针，p2为其前驱指针*/char c,s6; /*s6用来存放学号,c用来输入字母*/system(cls); printf(请输入要删除的学生的学号: );scanf(%s,s);p1=p2=head; /*给p1和p2赋初值头指针*/while(strcmp(p1-num,s) & p1 != NULL) /*当记录的学号不是要找的，或指针不为空时*/p2=p1; /*将p1指针值赋给p2作为p1的前驱指针*/p1=p1-next; /*将p1指针指向下一条记录*/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 ?); /*提示是否要删除,输入Y删除,N则退出*/for(;)scanf(%c,&c);if(c=n|c=N) break; /*如果不删除,则跳出本循环*/if(c=y|c=Y)if(p1=head) /*若p1=head，说明被删结点是首结点*/head=p1-next; /*把第二个结点地址赋予head*/elsep2-next=p1-next; free(p1);/*否则将一下结点地址赋给前一结点地址*/printf(n学号为 %s 的学生记录已被删除.n,s);break; /*删除后就跳出循环*/ else printf(n找不到学号为 %s 的学生记录.n,s); /*找不到该结点*/return(head);/插入 LinkList *Insert(LinkList *head)int k;/在表中第k个位置插入printf(请输入插入的位置：);scanf(%d,&k); int j=0,i=0;LinkList *p1,*p2; /*p1为查找到要删除的结点指针，p2为其前驱指针*/char N10,s10; /*s10用来存放姓名,N10用来存放学号*/int score3; system(cls); printf(输入学号:); scanf(%s,N);printf(输入姓名:);scanf(%s,s);printf(请分别输入语文、数学、英语的分数 %d scoresn,3);/*开始输入*/for(i=0;i3;i+) /*3门课程循环3次*/doprintf(score%d:,i+1);scanf(%d,&scorei);if(scorei100) /*确保成绩在0100之间*/printf(Data error,please enter again.n);while(scorei100);p1=head; /*给p1赋初值头指针*/while(jnext; /*将p1指针指向下一条记录*/if(p1=NULL) return 0; elsep2=(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(*n);printf(t Welcome to n);printf(t The student score manage system n);printf(*MENU*n);printf(tt1. 输入学生记录n); /*输入学生成绩记录*/printf(tt2. 输出学生记录n); /*显示*/printf(tt3. 删除学生记录n); /*删除*/printf(tt4. 插入一个新的学生记录n); /*插入*/printf(tt5. 退出n); /*退出*/printf(*n);/*主函数界面*/void ScoreManage()LinkList *head,New;int i,n;head=init(); /*链表初始化,使head的值为NULL*/menu_select(); do printf(ntt输入您的选择(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; /*如菜单返回值为9则程序结束*/menu_select();printf(nttt输入您的选择(15):); scanf(%d,&n); /*/各种排序typedef int KeyType; /*定义关键字类型*/typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/InfoType data; /*其他数据项,类型为InfoType*/ RecType;/*排序的记录类型定义*/void InsertSort(RecType R,int n) /*对R0.n-1按递增有序进行直接插入排序*/int i,j;RecType tmp;for (i=1;i=0 & tmp.keyRj.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-)if(Rj.keyRj-1.key)tmp=Rj;Rj=Rj-1;Rj-1=tmp;exchange=1;if(exchange=0) return ;void SelectSort(RecType R,int n)int i,j,k;RecType tmp;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(Rj.keyRk.key)k=j;if(k!=i)tmp=Ri;Ri=Rk;Rk=tmp;void disp(RecType R,int n)int i;for (i=0;in;i+)printf(%d ,Ri.key);void Sort()int i,n=10,k;RecType RMaxSize;KeyType a10;printf(请输入排序的关键字(10个数字)n); for (i=0;in;i+)scanf(%d,&ai);for (i=0;in;i+)Ri.key=ai;printf(nn直接插入排序 :); InsertSort(R,n);disp(R,n);printf(nn冒泡排序 :);BubbleSort(R,n);disp(R,n);printf(nn直接选择排序 :);SelectSort(R,n);disp(R,n);/*/建立二叉树typedef char ElemType;typedef struct node ElemType data;/*数据元素*/struct node *lchild;/*指向左孩子结点*/struct node *rchild;/*指向右孩子结点*/ BTNode;void CreateBTNode(BTNode * &b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (