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

上海应用技术学院课程设计报告课程名称 数据结构课程设计 设计题目猴子选大王;建立二叉树；各种排序；有序表得合并;成绩管理系统； 院系 计算机科学与信息工程 专业计算机科学与技术 班级 姓名 学号 指导教师 日期 一. 目得与要求1. 巩固与加深对常见数据结构得理解与掌握2. 掌握基于数据结构进行算法设计得基本方法3. 掌握用高级语言实现算法得基本技能4. 掌握书写程序设计说明文档得能力5. 提高运用数据结构知识及高级语言解决非数值实际问题得能力二. 课程设计内容说明1. 项目一(1) 对设计任务内容得概述学生成绩管理*任务：要求实现对学生资料得录入、浏览、插入与删除等功能.输入:设学生成绩以记录形式存储，每个学生记录包含得信息有:学号与各门课程得成绩,设学生成绩至少3门以上。存储结构：采用线性链式结构。(2) 详细设计LnkLt reate()：输入学生成绩记录函数；void print(Links had）：显示全部记录函数LinListele(LikList hea):删除记录函数LList Inst(Linkist*hea):插入记录函数voi mnu_selct（）：菜单选择ocoreMnage（）:函数界面(3) 程序流程图3.删除学生记录4.插入学生记录1.输入学生记录输入n(0n6)主界面2.输出学生记录退出学生成绩管理系统5.退出判断nn=5n=1、2、3、4(4) 程序模块及其接口描述该程序可以分为以下几个模块:、菜单选择：void enu_sel()； 提供五种可以选择得操作，在main函数中通过switch语句调用菜单mnueect(）函数，进入不同得功能函数中完成相关操作。2、输入功能:inkLs *cete（）; 通过一个or循环语句得控制，可以一次完成无数条记录得输入。并将其存入链表. 、输出功能:idprit(LinkList hed）; 通过一个wile得循环控制语句，在指针p!=NLL时，完成全部学生记录得显示。知道不满足循环语句，程序再次回到菜单选择功能界面.4、删除功能：LnkList *Dele（Linist *head）； 按想要删除得学生得学号首先进行查找,通过指针所指向结点得下移来完成，如果找到该记录，则完成前后结点得连接，同时对以查找到得结点进行空间得释放,最后完成对某个学生记录进行删除,并重新存储。、插入功能：inkLtnsert（LnkLit head)；输入您想插入得位置,通过指针所指向结点得下移,找到该位置，将该新得学生记录插入到该结点，并对该结点后面得指针下移。链表长度加一,重新存储。(5) 程序得输入与输出描述输入：调用LinListreate(）函数，输入学生得姓名、学号、三门功课得成绩;输出：调用vod prnt（LinkListhd）函数，输出学生得记录。(6) 程序测试主菜单：成绩管理系统得主界面：学生成绩记录得输入:输出学生成绩记录:学生成绩记录得删除（删除学号就是1101得学生记录）插入新得学生成绩记录（插入学号为1得学生记录)(7) 尚未解决得问题或改进方向尚未解决得问题:该成绩管理系统还存在不少缺陷,而且它提供得功能也就是有限得，只能实现学生成绩得输入、输出、删除、插入。对于，学生成绩记录得文件保存以及按学号、姓名等得查询也就是缺少得。还有就就是,对于多个学生成绩得操作也就是不够得。改进得方向:在时间许可得条件下，尽量得完善该系统得各种功能，同时也应修改系统,让它更为人性化、简单化,被广大用户所接受.(8) 对软件得使用说明该软件就是属于比较低级得软件,只就是包含了课程设计得要求得几个功能：输入、输出、删除、插入。所以用户在使用得过程中肯定会受到一定得局限性、不方便性,但由于时间得缘故，无法将软件做到尽善尽美.2. 项目二(1) 对设计任务内容得概述各种排序任务:用程序实现插入法排序、选择法排序、起泡法改进算法排序;利用插入排序、选择法排序与冒泡法得改进算法,将用户随机输入得一列数按递增得顺序排好。输入得数据形式为任何一个正整数，大小不限。输出得形式:数字大小逐个递增得数列.(2) 功能描述该函数有以下几个功能:1) 对R0、n1按递增有序进行直接插入排序2) 对R、n1按递增有序进行冒泡排序3) 对0、n1按递增有序进行直接选择排序4) 排序后得输出5）调用所有排序,实现排序(3) 程序流程图直接插入排序InsertSort()退出排序Sort()直接选择排序SelectSort()冒泡排序BubbleSort()(4) 详细设计voi Ierot（RecTyp R，it n）:对R0、n-按递增有序进行直接插入排序void Bubbleor(RTypeR，int n):对R0、n1按递增有序进行冒泡排序oidSecort（RcTye R，intn）:对R0、-1按递增有序进行直接选择排序vod isp（RecTyp R，int n）:排序后得输出od Sort()：调用所有排序,实现排序(5) 程序模块及其接口描述该程序分为五个模块:、输入功能:oi Sot() 建立一个数组存放用户在键盘上输入得关键字，在分别调用各种排序得函数,对关键字进行排序。2、直接插入排序功能：voi nsertSr（RecTp R,it n)将后一个数与前一个数比较,将其插入到第一个比它大得大得数前面，其余数字往后移一个位置.每次从无序表中取出第一个元素,把它插入到有序表得合适位置，使有序表仍然有序。、冒泡排序功能:d BubbeSort(Recpe R,ntn） 在排序过程中，执行完最后得排序后，虽然数据已全部排序完备，但程序无法判断就是否完成排序,为了解决这一不足,可设置一个标志位excge,将其初始值设置为非0,表示被排序得表就是一个无序得表，每一次排序开始前设置hnge值为0，在进行数据交换时，修改change为非0.在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据,则结束排序;否则进行排序。、直接选择排序功能:vi SlectSor（Rcy R，n） 在无序区里找最小得数，第i小得数字放在第i个位置上，与原来第个位置上得数字交换。5、输出功能：voiddip（cTypR，int n）(6) 程序得输入与输出描述输入:要求就是10个为数字得关键字；输出：排序后新得序列。(7) 程序测试输入关键字，调用各种排序函数(8) 尚未解决得问题或改进方向改进方向:虽然给出了它得各种排序得结果,但就是没有它得箱子过程,这就是我得改进得方向，希望能将每种排序得过程也能展示给用户，来体现它们得不同。(9) 对软件得使用说明用户只需根据提示，在键盘上输入要排序得0个关键字.3. 项目三(1) 对设计任务内容得概述有序表得合并要求输入有序表得数据，利用顺序表与链表结构分布完成两个有序表合并功能,并输出合并后得信息。(2) 功能描述该程序有如下几个功能：1) 初始化顺序表2) 初始化链表3) 建立顺序表4) 尾插法建表5) 输出合并后得顺序表6) 输出合并后得单链表7) 合并顺序表8) 合并单链表9) 调用以上得函数,实现有序表得合并(3) 概要设计或程序流程图开始初始化链表初始化顺序表建立顺序表尾插法建表合并顺序表合并单链表输出结束(4) 详细设计void Iniis（qListL）:初始化顺序表od Lis1(ikLit1 *&）：初始化链表id CreatList(qLst L,EleTpea，nt）:建立顺序表dCreateLisR（Linkis1 &，lmype ，t n）：尾插法建表oi DspL（Lst L):输出合并后得顺序表vo spList1（inLis1 L）：输出合并后得单链表voi nonList(qLt LA，SqstLB,SqLiLC）：合并顺序表voidnnLst1（LinkList1 *L,kistLB，Linist1 *L）：合并单链表oi Uon(）:调用以上得函数,实现有序表得合并。(5) 程序模块及其接口描述程序有以下几个模块:1) 初始化、建立顺序表2) 初始化、建立链表3) 输出合并后得表4) 合并表(6) 调试分析或程序测试有序表得合并：(7) 尚未解决得问题或改进方向不足：不能重复使用程序。(8) 对软件得使用说明用户只需根据界面得提示，采用对应得操作。4。项目四(1)对设计任务内容得概述建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归得方法都可以）*任务：要求能够输入树得各个结点,并能够输出用不同方法遍历得遍历序列;分别建立二叉树存储结构得得输入函数、输出层序遍历序列得函数、输出先序遍历序列得函数、输出中序遍历序列得函数、输出后序遍历序列得函数;（)功能描述1) 建立二叉树2) 输出二叉树3) 先序遍历非递归算法：不为空时,访问根-左右，采用递归得方法.4) 中序遍历非递归算法：不为空时，访问左-根-右,采用递归得方法。5) 后序遍历非递归算法：不为空时,访问左右根,采用递归得方法。6) 层序遍历：运用队列,队列不空时,有左孩子将其入队,有右孩子将其入队，同时出队.7） 调用以上函数实现二叉树得各种遍历（3）概要设计或程序流程图开始输入二叉树得按层结点值层次遍历后序遍历中序遍历先序遍历结束(4)详细设计oid reatBoe（BTode ，char st）:建立二叉树od DispTNode(BTNodeb):输出二叉树voiPeOrder（BTNode*）:先序遍历非递归算法vodInOde(BTode b）：中序遍历非递归算法void PosOrder(TNo *）:后序遍历非递归算法vd LevelOder（BTode b）:层序遍历（5）程序模块及其接口描述(6)程序得输入与输出描述输入二叉树得按层结点值;输出二叉树先序遍历访问结点得顺序;输出二叉树中序遍历访问结点得顺序;输出二叉树后序遍历访问结点得顺序；输出二叉树层次遍历访问结点得顺序；（）调试分析或程序测试用户从键盘上输入要创建得二叉树结点：(8）尚未解决得问题或改进方向改进方向:希望能将系统改进得更为人性化，让界面更舒适，操作更简单。()对软件得使用说明用户只需按照界面得提示,采取相应得措施，到时界面会提醒用户键盘输入。5。项目五（1)对设计任务内容得概述猴子选大王*任务:一堆猴子都有编号,编号就是1，2，3 、m ,这群猴子(m个)按照m得顺序围坐一圈，从第1开始数，每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子，则该猴子为大王。要求:输入数据：输入，nm, 为整数，n输出形式:中文提示按照m个猴子，数 个数得方法,输出为大王得猴子就是几号 ，建立一个函数来实现此功能（2）需求分析或功能描述为猴子编号ou,编号out=pas（p为密码值），该猴子离圈，次数se+。剩下得猴子继续次操作，直到次数step猴子onky时结束.（3)概要设计或程序流程图开始输入猴子得数量与密码值编号=密码值,猴子出列,次数自增N次数=猴子数Y结束（4)详细设计或源代码说明为猴子编号u,编号out=pa(pass为密码值）,该猴子离圈,次数step+。剩下得猴子继续次操作，直到次数ste猴子money时结束.函数nt Mokey（）实现了这一功能。()程序模块及其接口描述运用队列（环形队列)，编号=密码值 入队;为猴子编号ot，编号out=ass（pass为密码值）,该猴子离圈,次数st+.剩下得猴子继续次操作,直到次数step=猴子monk时结束。函数intMokey（）实现了这一功能。（)程序得输入与输出描述输入数据:输入m，n，n 为整数，ninclud malloc、hnuesring、hiludeistream#nludedefeLEN sizeo（inkList）#fine Maie 50/*/成绩管理系统typefstructLNde/*定义单链表结点类型*/hr nae10; /姓名char num10；/学号 nsor3； sruct LNodenxt; Linkst;nkLit nit（)return ULL； 返回空指针*/inkLit crete（)in,k；nt j=0；LikL heNUL,p； / 定义函数、此函数带回一个指向链表头得指针/syse(”cls”)； print(请输入您想输入得学生个数:）；scnf（”d”，）；or(j=0;jk;+)p=（Linkist*）mlloc(LE）; /*开辟一个新得单元/if（p=NLL) /如果指针p为空/pinf（输出内存溢出、）； 输出内存溢出/reurn （ea)； 返回头指针,下同/rnt（输入学号：”）; af（”%”,um)；prntf（输入姓名：”）；canf(%s”，pname）;pritf（请分别输入语文、数学、英语得分数 cresn”，3）;/*开始输入*/fo（i0;3；+） *3门课程循环3次printf（scoe%d:,i1）；sanf(”%d”,&p-scor）；f（-orei -scoei00) /*确保成绩在01之间/pt（”Daa ro，leaseeter agi、n”)；hie（p-score0 pscori00);pxhad； 将头结点做为新输入结点得后继结点*/had=p; /新输入结点为新得头结点*/retrn(ea)； /* 显示全部记录函数*/void int(LinList head)ikLs *p； ytem(cls”)； p=hea； /*初值为头指针ptf（n*inkList*n”）；intf（”-n）；pritf（学号 | 姓名 语文 数学 | 英语 | n）;pinf(-n)；whil(p！=NU) rintf(| %4 | -4s | %3d | 3d | %d n， nu,pame，pscr0,score1,sco2); p=pnext；rint（-n”）；rtf（*END*n)；/*删除记录函数*/LinList*eete（ikit hd)LiLs *p1,*p2; /p1为查找到要删除得结点指针，p2为其前驱指针har c，s6； /6用来存放学号，c用来输入字母*/ssem(cs”);printf（请输入要删除得学生得学号: ）；sf（，s)；1=p2=ed； /*给p1与p赋初值头指针*/while(strcmp（nm，s) p1！= NUL） /当记录得学号不就是要找得,或指针不为空时/pp1; /*将p1指针值赋给2作为p1得前驱指针*1=p1-et; *将1指针指向下一条记录*i（srcmp(p1-um,s)=） /学号找到了*/pritf（*FOUND*n”）；rint（-n”）；prif（ 学号 姓名 | 语文 | 数学 英语n）；printf（”-n);prnt（ %4s | | %3 | %3d 3d n，p1um，p1ame，p1ce，pore1，p1sco2);print(-n”)；pintf（”*END*)；prntf（您确定要删除该学生得记录吗 Y/ ？);/*提示就是否要删除,输入Y删除,N则退出f(；;)scnf（”%c，c）;i(=n=N） brk； /如果不删除,则跳出本循环/（c=y|cY)if（=head） /若p1=had,说明被删结点就是首结点*/hd=p-net； /把第二个结点地址赋予hed*/lse2-nxtpext; re（1）;否则将一下结点地址赋给前一结点地址*prntf（”n学号为s 得学生记录已被删除、n，);brak； /*删除后就跳出循环*/ elseprintf(找不到学号为 s得学生记录、n,s）; /*找不到该结点/etr(ead);/插入 LiList *sert(LiListhea)ik；/在表中第k个位置插入rint（”请输入插入得位置：）；sanf（d，k); intj0,i=0；LinkLst*p1,*p2； *p1为查找到要删除得结点指针,p2为其前驱指针/chaN10，s10; s0用来存放姓名，N10用来存放学号nt sco3; syte(”cls”）; printf(”输入学号：”）；saf（%s,N）；int(输入姓名:）；scan(”，s）；pritf（请分别输入语文、数学、英语得分数 d scosn,3)；/*开始输入/for（0；i3；i+） /门课程循环3次/doprtf（sce:，i+1）;cnf（”%d，&corei）;if(scre0 |cei100) /*确保成绩在0100之间*/prntf（ata error，ple ente aain、);whil(scoi100);p=had; /给p赋初值头指针/whl（jnext； 将p指针指向下一条记录*/if(p=U) tun 0; ep2（nkList ）mllo（szef（Linkst）)；strcp(p2num,N）;sry(2name,s）；for（i=0；i3；i+） pscorei=si;2-nex=p1ne；p1-ext=p2；id menu_slec()pintf(”nnn）;prntf(*n”)；intf（”t Wee to n）;ritf（” The ud sc manae sstem ）;rif（*MEN*n”)；prinf(1、 输入学生记录）; /输入学生成绩记录/prinf(”t2、 输出学生记录n）; *显示/rint（tt3、 删除学生记录n）； /删除*/ritf（tt、 插入一个新得学生记录n）； *插入*/rinf（tt5、 退出n”)； /退出*/printf（*n)；/主函数界面*/void ScreMag(）Liks *head，N;it i,；head=init（）； /链表初始化,使hea得值为ULL/me_slec(); o pi(”nt输入您得选择(15):”）； cn(”d”，&n);wle（n1n5);or（；;） 循环无限次*swtc（） case ：head=reate（）;brak; se 2:rnt（ha);brea; case ：ea=eete（ead)；bea; cse 4:hea=Inet（he）；beak； case5：retu; /如菜单返回值为9则程序结束*/nselect()；pintf（”nttt输入您得选择(15）：”）； scaf(”%d，n）；/*/各种排序typd itKeyType; /定义关键字类型/tpeef ch InfoType1；ypedf struct *记录类型KeyType ky; /关键字项/InfoType data； /其她数据项，类型为nfoType RecType;/*排序得记录类型定义*/voi nseSot（ReTpeR，in ） *对R0、n-1按递增有序进行直接插入排序n,j；ReType tmp；fr (i=1;i0 & tm、key、ey) Rj+=Rj; /将关键字大于Ri、key得记录后移/-;R1tp; *在j+处插入Ri/od ubleort(RecTye R,n n）it，j,xhange；RTpe tmp；for(i=0;ii；j-）（、key1、k)mp=R；RjRj;Rjtm；echange=1;i(xcange=） turn ;void SelctSrt（Reye R,t )nt i,j,k；RecTyp tp；for（i=;in1；i+）;fr（=i1；jn；j+)if(R、keRk、）;if(k!i）mR；i=R;Rk=tmp;void disp（RecType R，nt n)ini;for （=0；i；i+)prn（”d,Ri、ke）;vod Sor(）int i，n1,;RecTye RMiz；KeyTyea0;rintf(”请输入排序得关键字(10个数字）n）；fr （i=；i+)scnf(%d”，&a）;or(i=;in;+)Ri、keyai;printf（”nn直接插入排序 :）；InsertSort（R,n）；disp（,）;rint（”nn冒泡排序 :”）;BuleSort(R,n）;disp（R，n);pif（”n直接选择排序 :”);Selecort(R,n)；dsp(R,n);/*/建立二叉树typdef ha ElemType;tpedef struct nod Elmpe dta；/*数据元素*/struct ne*lchild；指向左孩子结点/trut noch；*指向右孩子结点/BTNde；vi CreateNode（BTe * ，c *tr）BTode Staxize，*pNLL；it to=1，k,j0;char ch；b=NULL；/建立得二叉树初始时为空strj;while （h！=0） /st未扫描完时循环* switch(ch) c （：t+;Stop=p;k1; brek;/*为左孩子结点/cas ):top-;brek；as ,：k2; a； 为孩子结点右结点/fault：p=（BTode *)mallo(sieof（BT