课程设计报告---文章编辑、猴子选大王、建立二叉树、拓扑排序、各种排序.doc

课程设计2009 2010学年第二学期设计题目 文章编辑、猴子选大王、建立二叉树、拓扑排序、各种排序 目录1、目的与要求22、课程设计内容说明32.1主菜单界面：32.2项目一：文章编辑*32.3项目二：猴子选大王*42.4项目三：建立二叉树，层序、先序遍历*62.5项目四：拓扑排序82.6项目五：各种排序：插入排序和改进冒泡排序算法105、结论及体会146、附录14 1、 目的与要求1.1. 巩固和加深对常见数据结构的理解和掌握1.2. 掌握基于数据结构进行算法设计的基本方法1.3. 掌握用高级语言实现算法的基本技能1.4. 掌握书写程序设计说明文档的能力1.5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力2、 课程设计内容说明2.1 主菜单界面：2.2 项目一：文章编辑*（1）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共n行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；（2）程序的输入输出描述：进入应用程序：（1）输入文章：（2）查找：（3）删除：原文为：quying111，删除y后为:quing111（4）尚未解决的问题或改进方向这个文章编辑的缺点在于无法统计空格数，只能够统计大小写字母以及数字（5）对软件的使用说明在cfree4.0下打开软件，进行操作2.3 项目二：猴子选大王*2.4.1 对设计任务内容的概述一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。2.4.2 需求分析或功能描述输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。2.4.3 程序输入输出描述：a) 开始程序：b) 部分程序代码：#define maxsize 50 int houzi(int n,int m) int pmaxsize; int i,j,t; for(i=0;i=1;i-) t=(t+m-1)%i; printf(%d,pt); for(j=t+1;j=i-1;j+) pj-1=pj; printf(n); printf(n故编号 %d 的猴子是大王!n,pt); printf(n);2.4 项目三：建立二叉树，层序、先序遍历*（1）对设计任务内容的概述要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；（2）需求分析或功能描述程序功能包括，建立二叉树，输出二叉树，对二叉树进行层次遍历和先序遍历。（3）概要设计或程序流程图进入程序，选择菜单，1创建二叉树，在程序中进行构造二叉树，并输出创建好的二叉树，2层次遍历二叉树，输出二叉树的层次遍历序列，3先序遍历二叉树，输出二叉树的先序遍历序列。（4）详细设计或源代码说明创建二叉树createbtnode（*b，*str）。根据二叉树括号表示的字符串*str生成对应的二叉链存储结构，用ch扫描采用括号表示法表示二叉树的字符串。输出二叉树，以括号表示法输出一棵二叉树。先序遍历二叉树的过程是，访问根结点，先序遍历左子树，先序遍历右子树。层次遍历的过程是，先将根结点进队，在队不为空时循环，从队列中出列一个结点*p，访问它，若它有左孩子结点，如此操作直到队空为止。 （5）程序模块及其接口描述typedef char elemtype;typedef struct nodeelemtype data;/数据元素 struct node *lchild;/指向左孩子 struct node *rchild;/指向右孩子 btnode;void createbtnode(btnode *&b,char *str)/由str串创建二叉链void dispbtnode(btnode *b)/以括号表示法输出二叉树void travlevel(btnode *b)/层次遍历void preorder(btnode *b)/先序遍历的递归算法（6）程序的输入与输出描述输入界面：输出界面：（7）调试分析或程序测试（8）尚未解决的问题或改进方向因为本程序最终要与其他两个程序合并在一起，在主界面进行选择。所以在进入主界面时要在本程序的主函数处修改字符，否则在调用本程序时主函数会发生冲突。（9）对软件的使用说明在cfree4.0下打开软件，进行操作。2.5 项目四：拓扑排序(1) 对设计任务内容的概述编写函数，实现图的拓扑排序。(2) 需求分析或功能描述在一个有向图中找一个拓扑序列的过程称为拓扑排序，而每一个有向图的拓扑序列并不唯一，本程序的功能就是将用户输入的序列进行拓扑排序。(3) 概要设计或程序流程图在程序菜单中选择开始，输入有向图的结点数和边数，此时程序就会输出结点信息，如v1，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) /返回节点v在图中的位置void creategraph(graph &g) /建图 void topologicalsort(graph g) /拓扑排序函数(6) 程序的输入与输出描述输入界面：再输入结点数和边数，此时会输出顶点信息：排序结果输出界面：(7) 调试分析或程序测试(8) 对软件的使用说明在cfree4.0下打开软件，进行操作。2.6 项目五：各种排序：插入排序和改进冒泡排序算法(1) 对设计任务内容的概述用程序实现插入法排序、起泡法改进算法排序；利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。(2) 需求分析或功能描述插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到每次记录插入完成为止。本程序使用直接插入排序。交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。本程序使用改进的冒泡排序算法。(3) 概要设计或程序流程图直接插入排序：假设待排序的记录存放在数组r0.n-1中，排序过程的某一中间时刻，r被划分成两个子区间0.i-1和i.n-1（刚开始时i=1,有序区序号只有r0一个记录），其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第一个记录ri插入到有序区0.i-1中适当的位置上，使0.i变为新的有序区。 有序区 无序区rirn-1r0ri-1 一趟排序r0ri-1riri+1rn-1 有序区 无序区 直接插入排序的一趟排序过程冒泡排序：整个算法是从最下面的记录开始，对每两个相临的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序之后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。而在有些情况下，在第i（i0) printf(当前的文章为:); for(i=0;ip.length;i+) printf(%c,p.datai); if(i+1)%80=0) printf(n); int cout(sqstring p)/各种字符数量统计 int i=0;int a=0 ,b=0,c=0,d=0; for(i=0;i=a&p.datai=a&p.datai=0&p.datai=9)c+;if(p.datai=32)d+;printf(英文小写字母有：%d个n,a) ;printf(英文大写字母有：%d个n,b) ;printf(数字有：%d个n,c);printf(空格有：%d个n,d);return p.length;int findfind(sqstring p,sqstring q)/查找 int i=0;int j=0;int n=0;while(i=q.length) n+;j=0;printf(经查找个字符共有 %d 个n,n);sqstring dele(sqstring p,sqstring a)/删除 int i=0;int j=0;int n=0;int pos=0; while(i=a.length) pos=i-j+1; int k; sqstring b;b.length=0; if(pos=p.length|pos+a.lengthp.length+1) return b; for(k=0;kpos-1;k+) b.datak=p.datak; for(k=pos+j-1;kp.length;k+) b.datak-j=p.datak; b.length=p.length-a.length; return b; pos=0; j=0; *猴子选大王；#define maxsize 50 int houzi(int n,int m) int pmaxsize; int i,j,t; for(i=0;i=1;i-) t=(t+m-1)%i; printf(%d,pt); for(j=t+1;jdata=ch;p-lchild=p-rchild=null;if(b=null)/p指向二叉树的根结点 b=p;else/已建立二叉树根结点 switch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void dispbtnode(btnode *b)/以括号表示法输出二叉树 if(b!=null)printf(%c,b-data);if(b-lchild!=null|b-rchild!=null)printf();dispbtnode(b-lchild);if(b-rchild!=null) printf(,);dispbtnode(b-rchild);printf();void travlevel(btnode *b)/层次遍历 btnode *qumaxsize;int front,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-lchild!=null)printf(%c,b-lchild-data);rear=(rear+1)%maxsize;qurear=b-lchild;if(b-rchild!=null)printf(%c,b-rchild-data);rear=(rear+1)%maxsize;qurear=b-rchild;printf(n);void preorder(btnode *b)/先序遍历的递归算法 if(b!=null)printf(%c,b-data);/访问根结点 preorder(b-lchild);/先序遍历左子树 preorder(b-rchild);/先序遍历右子树 void menu8()btnode *b;char smaxsize;printf(请输入二叉树：);gets(s);createbtnode(b,s);printf(输出此二叉树:);dispbtnode(b);printf(n);printf(层序遍历序列：);travlevel(b);printf(先序遍历递归序列：);preorder(b);printf(n);#include #define maxe 20typedef int keytype;typedef char infotype10;typedef structkeytype key;infotype data;rectype;*拓扑排序：#define stacksize 100 /栈空间大小 #define stackincrement 20 /进栈栈增量 #define max 20 /邻接表数组的最大值 typedef struct int *base; /栈底 int *top; /栈顶 int stacksize; /栈空间 stack;int initstack(stack &s) /创建一个空栈 s.base=(int*)malloc(stacksize*sizeof(int); if(!s.base) return -1; s.top=s.base; s.stacksize=stacksize; return 1;int push(stack &s,int e) /进栈 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; return 1;bool empty(stack s) /查看栈是否为空 if(s.base=s.top) return true; else return false;int pop(stack &s) /出栈 int e; e=*-s.top; return e;typedef struct arcnode /头节点 int adjvex; /该边所指向的顶点的位置 struct arcnode *nextarc; /指向下一条边arcnode;typedef struct vnode /表节点 int data; /顶点信息 int indegree; /节点的入度 arcnode *firstarc; /指向第一条依附该节点的边的指针vnode,adjlistmax;typedef struct adjlist vertices; /表节点 int vexnum; /节点的个数 int arcnum; /边的条数graph;int locatevex(graph g,int v) /返回节点v在图中的位置 int i; for(i=0;ig.vexnum;+i) if(g.verticesi.data=v) break; else continue; if(ig.vexnum) return i; else return -1;void creategraph(graph &g) /建图 int m,n; printf(现在请输入dag的结点数: ); scanf(%d,&m); while(m0) printf(tttterror!nttttdag结点数不能小于1.n); printf(请重新输入dag的顶点数: ); /dag是有向无环图 scanf(%d,&m); printf(现在请输入dag的边数: ); scanf(%d,&n); while(n0) printf(tttterror!nttttdag的边数不能小于0.n); printf(请重新输入dag的边数: ); scanf(%d,&n); g.vexnum=m; /顶点数目 g.arcnum=n; /边的数目 int i,j,k; for(i=0;ig.vexnum;+i) /初始化图的信息 g.verticesi.data=i+1; /顶点信息 g.verticesi.firstarc=0; g.verticesi.indegree=0; /开始时入度都为0 /顶点信息 printf(现在输出顶点信息:n); for(i=0;ig.vexnum;+i) printf(v%dn,g.verticesi.data); int v1,v2,flag=0; for(k=0;k=0 & j=0) +flag; (g.verticesj.indegree)+; arcnode *p=(arcnode*)malloc(sizeof(arcnode); p-adjvex=j; p-nextarc=0; arcnode *p1; if(! g.verticesi.firstarc) g.verticesi.firstarc=p; else for(p1=g.verticesi.firstarc;p1-nextarc;p1=p1-nextarc); /求该顶点的最后一个邻接顶点 p1-nextarc=p; /将p插入到最后一个邻接顶点的后面 else /没有该弧，删除掉 printf(*); printf(没有该边!n); k=flag; printf(*); void topologicalsort(graph g) /拓扑排序函数 int i,j,k; int count=0; /用来统计顶点的个数 stack s; /定义一个栈，用来保存入度为0的顶点 initstack(s); /初始化栈 for(i=0;inextarc) /找与第j个顶点的邻接顶点，并将其入度减1 k=p-adjvex; -(g.verticesk.indegree); if(g.verticesk.indegree=0) /如果入度为0,就入栈 push(s,k); if(countg.vexnum) /count小于顶点的个数时候，说明有环，不符合拓扑排序的要求 printf(*); printf(tttterror!ntttt图中有环!该图不是dag!n); exit(0); /退出 /主函数的实现/*void tuopu()printf(tttt拓扑排序演示n);printf(tttt现在开始n); graph g; creategraph(g); printf(ntttt拓扑排序结果为: n); printf(*); topologicalsort(g); printf(n*); printf(ntttt演示完毕n);*/*各种排序void insertsort(rectype r,int n)/直接插入排序 int i,j,k;rectype temp;for(i=1;i=0&temp.keyrj.key)rj+1=rj;/将关键字大于ri.key的记录后移 j-;rj+1=temp; /在j+1处插入riprintf( i=%d ,i);for(k=0;kn;k+)printf(%3d,rk.key);printf(n);