排序算法课程设计报告.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 6XXX