排序算法课程设计报告.docx

课程设计20092010学年第二学期设计题目文章编辑、猴子选大王、建立二叉树、拓扑排序、各种排序目录1、目的与要求22、课程设计内容说明32.1 主菜单界面：32.2 工程一：文章编辑*32.3 工程二：猴子选大王*42.4 工程三：建立二叉树，层序、先序遍历*62.5 工程四：拓扑排序82.6 工程五：各种排序：插入排序和改良冒泡排序算法105、 结论及体会146、 附录141、目的与要求1.1. 稳固和加深对常见数据结构的理解和掌握1.2. 掌握基于数据结构进行算法设计的根本方法1.3. 掌握用高级语言实现算法的根本技能1.4. 掌握书写程序设计说明文档的能力1.5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力2、课程设计内容说明2.1 主菜单界面：MM1、运动会分数统计e2、一元多项式计算MM.3、订票系统4、迷宫求解MX5、文章编辑*6、Joseph环MMa?、猴子选大王©8、二叉树的遍历X9、哈夫曼树的建立工0、纸牌游戏-M-M11、图的建立及输出工2、拓扑排序MS13、各种排序Q0、退出M*-M-M-目前有效选项为：5、？、8、12、13?请选择：2.2 工程一：文章编辑*（1）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；12）程序的输入输出描述：进入应用程序：目前有效选项为：5、8、12.13?请选择：5* 1、输入文章J2、查找字符* 3、删除字符* 0、返回主菜单(1)输入文章:(2)查找:箜当英FE* 9 .1 4 2 Finuy .僧有有 f 曾为母母 F qs星X子3404 f:1文文写写： 决E择入的÷K有有 选地刖文文格v±r¼>1.啕选择：23l三三11请选择:2三1l三1(3)删除：原文为：QUYinglII,删除丫后为:QuinglllXxMXXXxxXXXXX“x*XxxX请选择：3谓地筮蒯除的字符串：V当BU的文早为：Quinglll(4)尚未解决的问题或改良方向这个文章编辑的缺点在于无法统计空格数，只能够统计大小写字母以及数字(5)对软件的使用说明在CFree4.0下翻开软件，进行操作2.3工程二：猴子选大王*2.4.1 对设计任务内容的概述一堆猴子都有编号，编号是1,2,3.m,这群猴子(m个)按照l-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，那么该猴子为大王。2.4.2 需求分析或功能描述输入数据：输入m,nm,n为整数，n<m输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。2.4.3 程序输入输出描述：目前有效选项为：5、7、8、12、13? 请选择菜单71、开始选大王。、返回主菜单请诜a）开始程序:情选择情输入架子数目：8请输入猿子数到所需出列的数：3出列顺序:36152847故编号?的很子是大王？b）局部程序代码:#defineMaxSize50inthouzi(intn,intm)intpMaxSize;inti,j,t;for(i=0;i<n;i+)pi=i+l;t=0;printf(z,n出列顺序:");for(i=n;i>=l;i)(t=(t+m-l)%i;printf(*%d*,t);for(j=t+l;j<=i-l;j+)pj-l=pj;printfn*);Printf("n故编号%d的猴子是大王！n",pl);Printf("n");2.4.4 三：建立二叉树，层序、先序遍历*(1)对设计任务内容的概述要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；(2)需求分析或功能描述程序功能包括，建立二叉树，输出二叉树，对二叉树进行层次遍历和先序遍历。13)概要设计或程序流程图进入程序，选择菜单，1创立二叉树，在程序中进行构造二叉树，并输出创立好的二叉树，2层次遍历二叉树，输出二叉树的层次遍历序列，3先序遍历二叉树，输出二叉树的先序遍历序列。14)详细设计或源代码说明创立二叉树CrealeBTNode(*b,*str)。根据二叉树括号表示的字符串*slr生成对应的二叉链存储结构，用Ch扫描采用括号表示法表示二叉树的字符串。输出二叉树，以括号表示法输出一棵二叉树。先序遍历二叉树的过程是，访问根结点，先序遍历左子树，先序遍历右子树。层次遍历的过程是，先将根结点进队，在队不为空时循环，从队列中出列一个结点*p,访问它，假设它有左孩子结点，如此操作直到队空为止。(5)程序模块及其接口描述typedefcharElemType;typedefstructnode(ElemTypedata;数据元素structnode*1Chik1;指向左孩子structnode*rchild;指向右孩子BTNode;voidCreateBTNode(BTNode*&b,Char*str)由str串创立二叉链voidDispBTNodeCBTNode*b)以括号表示法输出二叉树voidTravLevel(BTNode*b)层次遍历voidPreOrderCBTNode*b)先序遍历的递归算法(6)程序的输入与输出描述输入界面：翼翼8* 1、创建二叉树* 2、层序遍历二叉树* 3、先序遍历二叉树* 0、返回主菜单鬲选择:灵叉:1二二此 选电 胃请输输出界面:：a<b,b<c,c<e,g>>>清选接：2：a<b,b<c,c<e,g>>>层序遍历序列：abbcceg星序:历递归序列：abbcceg(7)调试分析或程序测试1、创建二叉树2、层序遍历二叉树3、先序遍历二叉树0、返回主菜单请选隹：2层序遍历序列：abbcceg菜单81、创建二叉树2、层序遍历二叉树3、先序遍历二叉树0、返回主菜单猊序遍历递归序列：abbcCeg18)尚未解决的问题或改良方向因为本程序最终要与其他两个程序合并在一起，在主界面进行选择。所以在进入主界面时要在本程序的主函数处修改字符，否那么在调用本程序时主函数会发生冲突。(9)对软件的使用说明在CFree4.0下翻开软件，进行操作。2.5工程四：拓扑排序(1)对设计任务内容的概述编写函数，实现图的拓扑排序。(2)需求分析或功能描述在一个有向图中找一个拓扑序列的过程称为拓扑排序，而每一个有向图的拓扑序列并不唯一，本程序的功能就是将用户输入的序列进行拓扑排序。(3)概要设计或程序流程图在程序菜单中选择开始，输入有向图的结点数和边数，此时程序就会输出结点信息，如vl,v2,v3等，接下来会要求用户输入第一条边的起点和终点，通过程序运行就可以输出拓扑排序结果。(4)详细设计或源代码说明对于给定的有向图，采用邻接表作为存储结构，为每个顶点设置一个链表，每个链表有一个表头结点，这些表头结点构成一个数组，表头结点中增加一个存放顶点入度的域count,在执行拓扑排序的过程中，当某个顶点的入度为0(没有前驱结点时)，就将此顶点输出，同时将该顶点的所有后继结点的入度减1,为了防止重复检测入度为0的顶点，设立一个栈St,以存放入度为0的顶点。(5)程序模块及其接口描述 typedef struct(int *base;int *top;int stacksize;)Stack;int InitStack(Stack &s)int Push(Stack &s,int e)bool Empty(Stack s)int Pop(Stack &s)int LocateVex(Graph G,int v) void CreateGraph(Graph &G)/栈底/栈顶/栈空间创立一个空栈进栈查看栈是否为空出栈返回节点V在图中的位置建图voidTopologicalSortCGraphG)拓扑排序函数(6)程序的输入与输出描述输入界面：拓扑排用黄示*1、开始*2、退出*现在开始清选择;12清选择：1再输入结点数和边数，此时会输出顶点信息:请选择"排序结果输出界面:3447566513222744>>>>>>>> 22222222 <<<<< 点点点点点点点点 终终终终终终终终 口口口口口口口口 点点点点点点点点 氾-氾-氾-汜-氾-氾-沼-巳_ ;此 tf tf ;比二乂 二乂 ;比 fffl I(I 一 IJLyI(二Is】If二f二 边边边边边边边边 、TA、TA %T、TA、T、TA 12345678 a7g>a>gpapapa>g> HEH 殳 H5FR5fR5FH5FH3fH5f -入入- 主OE主DE主DE主OlHiliE主IIE主OE主QE 段现套遣族入结点数：7奥现隹遗输入边藜：.8现在输出顶点信息：拓扑排序结果为:XXXXXXXXXXXxXMXXXXXMXXXXXXXXXXXXXXXXXXXXXU2u7ulu3u4u5u6X*M*XXXXXXxXXXXXXXX)O<XXXXXXXXXXXXXXXXXXXX(7)调试分析或程序测试<<<<<<<< 点点点点点点点点 终终终终终终终终 DODDnUDDnU VA 士不为，方，本士 ”.»方 点点点点点点点点 立Z金氾-殳殳巳_堂 +tt 二二二A'H 二乂 二H -r TT *r j*t . rT 边边边由边边 ¼T*TA*T¼TATAT%TA¼T 12345678 7pgp7gRgpgpg4 4axx0u7j 主OE主星QE至星星R至H青 、IK > k、 IK、Tk、Ik、Tk、Tk Iv7现在输出顶点信息: lm2m3u4m32： 1 32: 3 42： 2 42： 2 52： 2 72： 7 62: 4 52： 4 6XXXXXXM X*M*X“ Gg购程序设计课程设计主菜单.exe嘉磁典示*1、苏希*2、退出*(8)对软件的使用说明在CFree4.0下翻开软件，进行操作。2.6工程五：各种排序：插入排序和改良冒泡排序算法(1)对设计任务内容的概述用程序实现插入法排序、起泡法改良算法排序；利用插入排序和冒泡法的改良算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。(2)需求分析或功能描述插入排序的根本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到每次记录插入完成为止。本程序使用直接插入排序。交换排序的根本思想是：两两比拟待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。本程序使用改良的冒泡排序算法。(3)概要设计或程序流程图直接插入排序：假设待排序的记录存放在数组R0n-l中，排序过程的某一中间时刻，R被划分成两个子区间。E和i.n-l(刚开始时i=l,有序区序号只有R0一个记录)，其中：前一个子区间是已排好序的有序区，后一个子区间那么是当前未排序的局部，不妨称其为无序区。直接插入排序的根本操作是将当前无序区的第一个记录Ri插入到有序区0.iJ中适当的位置上，使0.i变为新的有序区。有序区无序区R0Ri-1RiRn-1)一趟排序R0Ri-lRiRi+IRn-l有序区无序区直接插入排序的一趟排序过程冒泡排序：整个算法是从最下面的记录开始，对每两个相临的关键字进行比拟，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序之后，关键字最小的记录到达最上端，接着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。而在有些情况下，在第i(i<n-l)趟时己排好序了，但仍执行后面几趟的比拟。实际上，一旦酸法中某一趟比拟时不出现任何记录交换,说明已经排好序了，就可以结束本算法。为此，改良了冒泡排序算法。有序一趟排序区R0Ri-URi无序区Ri+1Rn-1(4)程序模块及其接口描述/定义关键字类型为inttypedefintKeyType;typedefcharInfoTypej10|;记录类型typedefstructKeyTypekey;关键字类型InfoType data;其他数据项，类型为InfoType RecType，排序的记录类型定义voidInsertSort(RecTypeR,intn)/直接插入排序voidBubbleSort(RecTypeRjnln)改良冒泡排序(5)程序的输入与输出描述：目前看茹方虹”5、8、12、13?菜单131、直接插入排序MMM2、冒泡排序WM*0、返回主菜单M*请选窗3、直接插入排序:输入:请选择式请施入个数：10请输入1。个整数：115849341215522输出:请输入10个整数门15849341215522初始关键字115849341215522i=l511849341215522i=2581149341215522i=3458119341215522i=4458911341215522i=5345891141215522i=6345891141215522i=7345891121415522i=8345891121415522i=9345891121224155最后结果3458911212241554、冒泡排序:输入：输出:初始关键字1251623210840194320i=08125162321019402043i=l8101251623219204043i=28101219516232204043i=38101219205162324043i=48101219203251624043i=58101219203240516243i=68101219203240435162最后结果8101219203240435162(6)调试分析或程序测试直接插入排序：El,数构程序设计修改文件主菜单.6乂6.88188555555151855444444115544333333 1异 123456789 卷 VP =予 建 i i i i i i i i i洁49342215522493422155224934221552249342215522119342215522911342215522891142215522891142215522891121425522891121425522891121224255891121224255菜单131、直接插入排序2、冒泡排序0、返回主菜单冒泡排序:H数构程序设计修改文件主菜单.exe请选择;2请揄入个数：10请输入10个整数：1251623210840194320初始关键字1251623210840194320i=08125162321019402043i=l8101251623219204043i=28101219516232204043i=38101219205162324043i=48101219203251624043i=58101219203240516243i=68101219203240435162最后结果8101219203240435162(7)尚未解决的问题或改良方向在算法的定义中，一开始就定义数组长度为10,如果用户操作中输入了大于10个数时将只对前10个数进行操作，而后面的数不会参加运算。(8)对软件的使用说明在CFree4.0下翻开软件，进行操作。5、结论及体会在这次的数据结构程序设计中，从十三个题目中选了五个自己比拟感兴趣的题目进行编程，因为许多算法可以在书上找到类似的类型，加上自己的想法，做的可以说比拟顺利。和平时上机所做的不同，这次需要一个程序的主界面，用来调用所设计的五个工程，而且分别对五个工程的程序设计从构思，到算法，再到输入输出和调试，进行了比拟充分的说明，使用起来也比拟方便。6、附录附录1：参考文献1李春葆.数据结构学习指导.清华大学出版社,20102张晓莉等.数据结构与算法.机械工业出版社,2002引李春葆.数据结构教程上机实验指导.清华大学出版社,2010.附录2:局部源代码清单*¾#defineMAX3000typedefstructchardataMAX;intlength;)SqString;voidStrAssign(SqString&str,charcstr)建立串(inti;for(i=0;cstri!='0'i+)str.da(ai)=cstri;str.length=i;)voidDispStr(SqStringp)(inti;if(p.length>O)Printf("当前的文章为:")；for(i=0;i<p.length;i+)printf("%c,',p.datai);if(i+l)%80=0)printf("n,');intcout(SqStringp)各种字符数量统计(inti=0;inta=0,b=0,c=0,d=0;for(i=0;i<p.length;i+)if(p.datai>='a'&&p.datai<='z')a+;if(p.datai>='A'&&p.datai<='Z')b+;if(p.datai>=,0'<fe<fep.datai<='9')c+;if(p.datai=32)d+;)Printf("英文小写字母有：d个n”,a);Prinlf("英文大写字母有：%d个nb);Printf("数字有：d个r,c);Printf(”空格有：%d个nd);returnp.length;intFindFind(SqStringp,SqStringq)查找(inti=O;intj=O;intn=0;while(i<=p.length)if(p.datai=q.dataj)<fe(q.dataj!=O,)i÷÷U+;)elsei+；if(j>=q.length)n+y=O;)Printf("经查找个字符共有%d个SqStringDele(SqStringp,SqStringa)删除(inti=O;intj=O;intn=O;intpos=0;while(i<=p.length)(if(p.datai=a.dataj)&&(a.dataj!='O,)i+÷U+;)elsei+；if(j>=a.length)pos=i-j+l;intk;SqStringb;b.length=O;if(pos<=Opos>=p.lengthpos+a.length>p.length+1)returnb;fbr(k=0;k<pos-I;k+)b.datak=p.datak;for(k=pos+j-l;k<p.length;k+)b.datak-j=p.datak;b.length=p.length-a.length;returnb;pos=0;j=0;#defineMaxSize50inthouzi(intn,intm)(intpMaxSize;inti,j,t;fbr(i=0;i<n;i+)pi=i+l;t=0;printf("n出列顺序fbr(i=n;i>=l;i)(t=(t+m-l)%i;printf("%d'pt);for(j=t+l;j<=i-l;j+)pU-11=pU1;)printf(',n');Prin情("矫故编号%d的猴子是大王!n",pt);printf(,n);1 -*包2:#defineMaxSize100typedefcharElemType;typedefstructnode(ElemTypedata;/数据元素structnode*1Chik1;指向左孩子structnode*rchild;指向右孩子BTNode;voidCreateBTNode(BTNode*&b,char*slr)由str串创立二叉链(BTNode*StMaxSize,*p=NULL;inttop=-l,k,j=;charch;b=NULL;建立的二叉树初始时为空ch=strj;while(ch!='O')str未扫描完时循环(switch(ch)(case'C：top+;Sttop=p;k=l;break;为左结点case,),rtop-ibreak;case?:k=2;break;为右结点default:p=(BTNode*)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if(b=NULL)p指向二叉树的根结点b=p;else己建立二叉树根结点(switch(k)(case1:Sttop->lchild=p;break;case2:Sttop->rchild=p;break;)j+;ch=strj;1voidDispBTNode(BTNode*b)以括号表示法输出二叉树(if(b!=NULL)(printf("%c",b->data);if(b->lchiIcl!=NULLb->rchild!=NULL)(printf("C');DispBTNode(b->Ichild);if(b->rchild!=NULL)printf(,',");DispBTNode(b->rchild);printf(")");voidTravLevel(BTNode*b)层次遍历(BTNode*QuMaxSize;intfront,rear;front=rear=0;if(b!=NULL)printf("%c',b->data);rear+;Qurear=b;while(rear!=front)(front=(front+1)%MaxSize;b=Qufront;if(b->Ichild!=NULL)(printf("%c',b->lchild->data);rear=(rear+l)%MaxSize;Qurear=b->lchild;)if(b->rchild!=NULL)(printf("%c,b->rchild->data);rear=(rear+1)%MaxSize;Qurearl=b->rchild;(printf("n,');voidPreOrderCBTNode*b)先序遍历的递归算法(if(b!=NULL)(Printf("%c"b>data);访问根结点PreOrder(b->lchild);先序遍历左子树Preorder(b->rchild);先序遍历右子树voidmenu8()(BTNode*b;charsMaxSize;Printf("请输入二叉树：");gets(s);CreateBTNode(b,s);Printf("输出此二叉树:")；DispBTNode(b);printf("n");Printf(”层J遍历序列:");TravLevel(b);Printfr先序遍历递归序列：")；Prerder(b);printf("n");)#include<stdio.h>#defineMAXE20typedefintKeyType;typedefcharInfoTypej10);typedefstruct(KeyTypekey;InfbTypedata;RecType;*引、料FJ手:#defineSTACKSIZE100#defineSTACKINCREMENT20#defineMAX20typedefstruct栈空间大小进栈栈增量/邻接表数组的最大值int*base;int*top;intstacksize;(Stack;intInitStack(Stack&s)栈底/栈顶栈空间创立一个空栈s.base=(int*)malloc(STACKSIZE*sizeof(int);if(!s.base)return-1;s.top=s.base;s.stacksize=STACKSIZE;return1;1intPush(Stack&s,inte)进栈if(s.top-s.base)>s.stacksize)s.base=(int*)realloc(s.base,(STACKSIZE+STACKINCREMENT)*sizeof(int);if(!s.base)return-1;s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return1;boolEmpty(Stacks)I查看栈是否为空if(s.base=s.top)retumtrue;elsereturnfalse;)intPop(Stack&s)inte;e=*-s.top;returne;I出栈/typedefstructArcNode(intadjvex;structArcNode*nextarc;/头节点该边所指向的顶点的位置指向下一条边IArcNode;typedefstructVNodeintdata;intindegree;ArcNode*firstarc;)VNode,AListMAX;表节点顶点信息节点的入度/指向第一条依附该节点的边的指针typedefstruct(AcljLislvertices;表节点intvexnum;节点的个数intarcnum;边的条数(Graph;intLocateVex(GraphG,intv)(inti;返回节点V在图中的位置for(i=0;i<G.vexnum;+i)(if(G.verticesi.data=v)break;elsecontinue;)if(i<Gvexnum)retumi;elsereturn-1;voidCreateGraph(Grah&G)建图intm,n;Printfr现在请输入DAG的结点数:,);scanf(,%d",<fem);while(m<0)printf(,ttttError!nttttDAG 结点数不能小于 l.n);Printf("请重新输入DAG的顶点数:");/DAG是有向无环图 scanf("%d",(fcm);PrintfC现在请输入DAG的边数:");scanf("%d",<fen);while(n<0)(printf(,ttttEor!nttttDAG 的边数不能小于 OAn");Printf("请重新输入DAG的边数:");scanf("%d",&n);G.vexnum=m;G.arcnum=n;int i,j,k;fbr(i=O;i<Gvexnum;+i)(G. verticesi .data=i+1;G. vertices i.fi rstarc=0;G.verticesi.indegree=O;顶点信息顶点数目边的数目初始化图的信息顶点信息开始时入度都为0PrimfC现在输出顶点信息:n")；for(i=0;i<Gvexnum;+i)printf("v%dn,',Gverticesl i .data);int vl,v2,flag=0;for(k=0;k<G.arcnum;+k)(Printf("请输入第d边的起点和终点(样例:1 2),注意其中分隔符为一个空格:,k+l);scanf(',%d%d,vl ,&v2);i=LocateVex(G,v 1);顶点Vl在图中的位置j=LocateVex(G,v2);顶点v2在图中的位置if(i >=0 && j>=0)(+flag;(Gverticesj.indegree)+;ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=j;p->nextarc=O;ArcNode *pl;if(! Gverticesi.firstarc)Gverticesi.firstarc=p;elsefor(p 1 =GverticesI i .firstarc;p 1 ->nextarc;p l=p I ->nextarc); /求该顶点的最后一个邻接顶点pl->nextarc=p;将p插入到最后一个邻接顶点的后面else没有该弧，删除掉Printn*”)Printf("没有该边!n")；k=flag;PrintR'*