数据结构课程设计2.doc

数 据 结 构课程设计报告书班级 计算机121 学号 1208010128 姓名 指导老师 目录一课程设计的目的和任务3二、课程设计名称：迷宫的求解问题31、 问题的描述32、 基本要求33、 算法思想34、 需要解决的问题35、 模块划分36、 源程序为37、 测试结果为4三、课程设计名称：生死者游戏71、 问题的描述72、 问题的解决方法73、 模块划分84、 函数之间的调用关系85、 程序包含的函数86、 源程序为87、 程序的运行结果为10四、课程设计的名称：二叉树基本操作的实现101、 问题的描述102、 源程序为103、 测试结果为14五、课程设计的名称：图的基本操作的实现151、 问题的描述为152、 源程序为153、 测试结果为19六、二叉排序树的设计与实现以及快速排序算法的实现201、 问题的描述为202、 源程序为203、 测试结果为25一、课程设计的目的和任务：1、 使学生进一步理解和掌握课程上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法2、 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力3、 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本技能二、课程设计名称：迷宫的求解问题1、 问题的描述：迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。2、 基本要求：（1） 建立一个大小为m*n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2） 找出一条通路的二元组（i，j)数据序列，（i,j）表示通路上某一点的坐标（3） 在屏幕上输出迷宫和通路3、 算法思想：采用回溯法，回溯法是一种不断试探且及时纠正错误的搜索方法。本问题可从入口出发，按某一方向向未走过的前方探索，若能走通，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。这也是一种“穷举求解”的方法。4、 需要解决的问题：（1） 表示迷宫的数据结构（2） 试探方向（3）栈的设计（4）防止重复到达某点，避免发生死循环5、模块划分：（1) 表示一个m行n列迷宫用mazemn表示，0=im,0=jnmazeij=0; 通路mazeij=1; 不通迷宫的定义：#define m 8 /*迷宫的实际行*/#define n 8/*迷宫的实际列*/int maze m+2n+2;（2） 试探方向表示位置的类型postype定义如下：typedef structint x, y;postype;试探顺序规定为：从正东衍顺时针方向与点(x,y)相邻的4个点及坐标 (x-1,y) (x,y-1) (x,y) (x,y+1) (x+1,y) （3） 栈中设计栈中每个元素的组成通道块在路径上的序号坐标位置前进方向（东为1，南为2，西为3，北为4）栈元素的类型定义：typedef struct int ord;postype seat;int di;selemtype;（4）防止重复到达某点走过不通之处要加以标记（markprint操作）6、 源程序为：#include#include#define n1 10#define n2 10typedef struct nodeint x;int y;int c;linkstack;linkstack top100;int mazen1n2=1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,;int i,j,k,m=0;void main()for(i=0;in1*n2;i+)topi.c=1;printf(the maze is:n);for(i=0;in1;i+)for(j=0;jn2;j+)printf(mazeij?*: );printf(n);i=0;topi.x=1;topi.y=0;maze10=2;doif(topi.c5)if(topi.x=5 & topi.y=9)printf(the way &d is:n,m+);for(j=0;j,topj.x,topj.y);printf(n);for(j=0;jn1;j+)for(k=0;k1）（3） 在链表的首结点开始从1计数，计到m-1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到m-1，再将其下一个结点从单循环链表删除，直到剩下一半结点为止。3、模块划分：（1） 建立一个头指针head指示的有n个结点的约瑟夫单循环链表initring（2） 生者与死者的选择： p指向链表的第一个结点，初始化i为1； while (idata； （3）输出所有生者的编号4、函数间的调用关系： main output deletedeath initring5、 程序包含的函数：（1） linklist initring(int n, linklist r)：初始化一个约瑟夫环（2） linklist deletedeath(int n,int k,linklist r)：寻找被扔入大海的人（3） void output(linklist r)：输出所有生存者函数6、 源程序为：#include#includetypedef struct nodeint num;struct node *next;node,*linklist;linklist initring(int n,linklist r)node *q,*p;int i;r=q=(node*)malloc(sizeof(node); for(i=1;inum =i;q-next=p;q=p; p-num =n;p-next =r;return r;linklist deletedeath(int n,int k,linklist r) int i,j;node *p,*q;p=r;for(i=1;i=n/2;i+)for(j=1;jnext; q=p-next ;p-next =q-next ;printf(%4d,q-num);free(q);p=p-next;return p;/*输出所有生存者函数*/void output(linklist r)node *p;p=r;doprintf(%4d,p-num);p=p-next;while(p!=r);void main() linklist r; int n,m; printf(总人数n，报数上限m（用，分隔开）：); scanf(%d,%d,&n,&m); r=initring(n,r); output(r); printf(n被抛入大海的人有：); r=deletedeath(n,m,r); printf(n生存下来的人有：); output(r); printf(n);7、 程序运行结果为：四、课程设计名称：二叉树的基本操作的实现1、 问题的描述：在主程序中编写一个简单的菜单，将有关二叉树的操作（建立一棵二叉树的存储结构、遍历一棵二叉树、统计二叉树叶子结点的个数，求二叉树的深度）等整合在一起，包括递归算法和非递归算法。2、 源程序为：/*头文件bitnode.h*/#include #include #include #define max 20#define ok 1#define error 0#define null 0#define overflow 0typedef char telemtype;typedef int status;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;/*先序遍历构造二叉树*/bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=#) t=null;else t=(bitnode*)malloc(sizeof(bitnode);if(!t) exit(overflow); t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t;void levelorder(bitree t)bitree queuemax,b;int front,rear;front=rear=0;if(t)queuerear+=t;while(front!=rear)b=queuefront+;printf(%2c,b-data);if(b-lchild!=null) queuerear+=b-lchild;if(b-rchild!=null) queuerear+=b-rchild;（1）构造二叉树：#include bitnode.hvoid main ()bitree t=null;printf(*采用递归函数构造一棵二叉树*n);printf(请读入构造二叉树的字符序列：);if(t=createbitree(t)printf(二叉树建立成功！并以层序遍历出构造的二叉树n);levelorder(t);printf(n);elseprintf(很遗憾，不能成功建立二叉树！n);（2） 二叉树的遍历：#include #include bitnode.hstatus printelement(telemtype e)printf(%2c,e);return ok;status preordertraverse(bitree t,status(*visit)(telemtype)int i,j,k;if(t=null)return ok;elsei=visit(t-data);if(i)j=preordertraverse(t-lchild ,visit);if(j)k=preordertraverse(t-rchild ,visit);if(k) return ok;/if(j)/if(i)else return error;/elsestatus inordertraverse(bitree t,status(*visit)(telemtype)/*中序遍历*/if(t)if(inordertraverse(t-lchild ,visit)if(visit(t-data )if(inordertraverse(t-rchild ,visit) return ok;return error;else return ok;status postordertraverse(bitree t,status(*visit)(telemtype)/*后序遍历*/if(t)if(postordertraverse(t-lchild,visit)if(postordertraverse(t-rchild,visit)if(visit(t-data)return ok;return error;else return ok;void main()bitree t=null,b=null;printf(*构造一颗二叉树并对其进行遍历*n);printf(请读入构造二叉树的字符序列:);b = createbitree(t);if(b)printf(二叉树建立成功!);printf(n该二叉树的先序遍历是:);preordertraverse(b,printelement);printf(n该二叉树的中序遍历是:);inordertraverse(b,printelement);printf(n该二叉树的后序遍历:);postordertraverse(b,printelement);printf(n该二叉树的层次遍历是:);levelorder(b);printf(n);elseprintf(二叉树建立不成功!n);（3） 叶子结点的统计#include #include bitnode.hint leafcount(bitree bt)int n;if(bt=null) n=0;else if(bt-lchild=null&bt-rchild=null) n=1; else n=leafcount(bt-lchild)+leafcount(bt-rchild); return n;void main ()bitree t=null;int m;printf(*构造一棵二叉树并求其结点数和深度*n);printf(请输入所构造的二叉树的结点序列:);t=createbitree(t);if(t)printf(二叉树建立成功！以层序遍历输出构造的二叉树n);levelorder(t);m=leafcount(t);printf(n该二叉树的叶子结点数是:%dn,m);else printf(二叉树建立不成功！n);（4） 二叉树的深度统计：#include #include bitnode.hint depth(bitree t)/*求二叉树的深度*/int dep1,dep2;if(t=null)return error;elsedep1=depth(t-lchild);dep2=depth(t-rchild);return dep1dep2?dep1+1:dep2+1;/elsevoid main ()bitree t=null;printf(*构造一棵二叉树并求对其进行深度统计*n);printf(请输入所构造的二叉树的结点序列:);t=createbitree(t);if(t)printf(二叉树建立成功！并以层序遍历输出构造的二叉树n);levelorder(t); printf(n二叉树的深度是:%dn,depth(t);else printf(二叉树建立不成功！n);3、 测试结果为：（1）二叉树的建立的程序运行结果为：（2） 二叉树的遍历的运行结果：（3）叶子结点的统计的程序运行结果为：（4） 二叉树的深度统计的程序的运行结果为：五、课程设计名称：图的基本操作的实现1、 问题的描述：在主程序中建立一个菜单，实现图的基本操作，包括：建立图的存储结构，实现图的深度优先搜索遍历，广度优先搜索遍历以及利用图的拓扑排序验证图中是否存在环2、 源程序为：头文件graph的内容为：typedef int infotype;#define maxv 100/*以下定义邻接矩阵类型*/typedef structint no;infotype info;vertextype;typedef structint edgesmaxvmaxv;int vexnum,arcnum;vertextype vexsmaxv;mgraph;/*以下定义邻接表类型*/typedef struct anodeint adjvex;struct anode*nextarc;infotype info;arcnode;typedef int vertex;typedef struct vnodevertex data;arcnode *firstarc;vnode;typedef vnode adjlistmaxv;typedef structadjlist adjlist;int n,e;algraph;（1）实现图的遍历算法的主程序为：#include #include #include graph.hint visitedmaxv; algraph*mattolist(mgraph g)/*将邻接矩阵g转换成邻接表g*/int i,j,n=g.vexnum;arcnode*p;algraph*g;g=(algraph*)malloc(sizeof(algraph);for(i=0;iadjlisti.firstarc=null;for(i=0;i=0;j-)if(g.edgesij!=0)p=(arcnode*)malloc(sizeof(arcnode);p-adjvex=j;p-info=g.edgesij;p-nextarc=g-adjlisti.firstarc;g-adjlisti.firstarc=p;g-n=n;g-e=g.arcnum;return g;void dispadj(algraph*g)/*输出邻接表g*/int i;arcnode*p;for(i=0;in;i+)p=g-adjlisti.firstarc;if(p!=null)printf(%3d:,i);while(p!=null)printf(%3d,p-adjvex);p=p-nextarc;printf(n);void dfs(algraph*g,int v)arcnode*p;visitedv=1;printf(%3d,v);p=g-adjlistv.firstarc;while(p!=null)if(visitedp-adjvex=0)dfs(g,p-adjvex);p=p-nextarc;void dfs1(algraph*g,int v)int i,visitedmaxv,stmaxv,top=-1;arcnode*p;for(i=0;in;i+)visitedi=0;printf(%3d,v);top+;sttop=v;visitedv=1;while(top-1)v=sttop;p=g-adjlistv.firstarc;while(p!=null & visitedp-adjvex=1)p=p-nextarc;if(p=null)top-;elsev=p-adjvex;printf(%3d,v);visitedv=1;top+;sttop=v;printf(n);void bfs(algraph*g,int v)arcnode*p;int queuemaxv,front=0,rear=0;int visitedmaxv;int w,i;for(i=0;in;i+) visitedi=0;printf(%3d,v);visitedv=1;rear=(rear+1)%maxv;queuerear=v;while(front!=rear)front=(front+1)%maxv;w=queuefront;p=g-adjlistw.firstarc;while(p!=null)if(visitedp-adjvex=0)printf(%3d,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%maxv;queuerear=p-adjvex;p=p-nextarc;printf(n);void main()int i,j;mgraph g;algraph *g;int amaxv5=0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,;g.vexnum=5;g.arcnum=4;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.edgesij=aij;g=mattolist(g);printf(图g的邻接表:n);dispadj(g);printf(从顶点0开始的dfs（递归算法）:n);dfs(g,0);printf(n);printf(从顶点0开始的dfs（非递归算法）:n);dfs1(g,0);printf(从顶点0开始的bfs（递归算法）:n);bfs(g,0); 3、 测试结果为： 六、课程设计名称：二叉排序树的设计与实现以及快速排序算法的实现1、问题的描述：（1）编写一个程序实现二叉树的基本运算，并在此基础上完成如下功能：a、由4,9,0,1,8,6,3,5,2,7,创建一棵bt并以括号表示法输出；b、判断bt是否为一棵二叉排序树c、采用递归和非递归两种方法查询关键字为6的结点，并输出其查找路径；d、分别删除bt中的关键字4和5的结点，并输出删除后的二叉排序树。（2)编写一个程序，实现对某一张顺序表的快速排序算法2、源程序：（1）二叉树的设计与实现：#include #include #define maxsize 100typedef int keytype;typedef char infotype;typedef struct nodekeytype key;infotype data;struct node *lchild,*rchild;bstnode;int pathmaxsize;void dispbst(bstnode *b);int insertbst(bstnode *p,keytype k)if(p=null)p=(bstnode *)malloc(sizeof(bstnode);p-key=k;p-lchild=p-rchild=null;return 1;else if(k=p-key)return 0;else if(kkey )return insertbst(p-lchild ,k);else return insertbst(p-rchild ,k);bstnode*creatbst(keytype a,int n)bstnode *bt=null;int i=0;while(irchild!=null)delete1(p,r-rchild );elsep-key=r-key ;q=r;r=r-lchild;free(q);void delete(bstnode *p)bstnode*q;if(p-rchild=null)q=p;p=p-lchild;free(q);else if(p-lchild=null)q=p;p=p-rchild;free(q);else delete1(p,p-lchild);int deletebst(bstnode*bt,keytype k)if(bt=null)return 0;elseif(kkey )return deletebst(bt-lchild,k);else if(kbt-key )return deletebst(bt-rchild,k);elsedelete(bt);return 1;void searchbst1(bstnode *bt,keytype k,keytype path,int i)int j;if(bt=null)return;else if(k=bt-key)pathi+1=bt-key;for(j=0;jkey;if(kkey)searchbst1(bt-lchild,k,path,i+1);elsesearchbst1(bt-rchild,k,path,i+1);int searchbst2(bstnode*bt,keytype k)if(bt=null)return 0;else if(k=bt-key )printf(%3d,bt-key );return 1;else if(kkey )searchbst2(bt-lchild ,k);else searchbst2(bt-rchild ,k);printf(%3d,bt-key );void dispbst(bstnode *bt)if(bt!=null)printf(%d,bt-key );if(bt-lchild!=null|bt-rchild!=null)printf();dispbst(bt-lchild);if(bt-rchild!=null)printf(,);dispbst(bt-rchild );printf();keytype predt=-32767;int judgebst(bstnode*bt)int b1,b2;if(bt=null)return 1;elseb1=judgebst(bt-lchild);if(b1=0|predt=bt-k