数据结构课程设计报告《图的遍历》.doc

数据结构课程设计报告班级： 姓名： 学号： 目录一， 设计任务-3二、 设计时间-3三、 设计内容-31、需要分析-32、概要设计-33、详细设计-44、测试与分析-9四、设计总结-10源程序清单-11一设计任务：我选课程设计是自选题目图的遍历。要求：设计一个程序，实现图的广度，深度优先遍历。二、设计时间 2009年12月28日三、设计内容 1、需求分析 本题目需要解决的问题是将一幅已知图，对图进行遍历，并完成：（1） 输出它的邻接矩阵；（2） 根据人工选择进行深度优先搜索（Depth_First Search）和广度优先搜索（Breadth_First Search），将搜索结果放入一队列中；（3） 将队列中的搜索结果输出。2、 概要设计： (1)抽象数据的类型定义数据对象：V是图具有相同特性的数据元素的集合，称为定顶点集 数据关系：R R=VR VR=/v,wv且p(v,w)基本操作：CreateGraph(&G,V,VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G 基本操作：DFSTraverse(G,Visit() BFSTraverse(G,Visit()（2）主程序的流程以及各程序模块之间的调用关系：CreateGraph算法打印邻接矩阵初始化成功选择如何遍历开始深度优先遍历广度优先遍历结束N Y D B3、详细设计：（1）定义图typedefstruct int VM; int RMM; int vexnum;Graph;（2）创建图void creatgraph(Graph *g,int n) int i,j,r1,r2; g-vexnum=n; /*顶点用i表示*/ for(i=1;iVi=i; /*初始化R*/ for(i=1;i=n;i+) for(j=1;jRij=0; /*输入R*/ printf(Please input R(0,0 END):n); scanf(%d,%d,&r1,&r2); while(r1!=0&r2!=0) g-Rr1r2=1; g-Rr2r1=1; scanf(%d,%d,&r1,&r2); （3）全局变量：访问标志数组void printgraph(Graph *g)int i,j;for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) printf(%2d ,g-Rij); printf(n); （4） 访问顶点 int visitedM;void visitvex(Graph *g,int vex) printf(%d ,g-Vvex);（5）获取第一个未被访问的邻接节点int firstadjvex(Graph *g,int vex)int w,i;for(i=1;ivexnum;i+) if(g-Rvexi=1&visitedi=0) w=i; break; else w=0; return w; /*获取下一个未被访问的邻接节点(深度遍历)*/ int nextadjvex(Graph *g,int vex,int w) int t; t=firstadjvex(g,w); return t; （6）深度递归遍历 void dfs(Graph *g,intvex) intw; visitedvex=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w0;w=nextadjvex(g,vex,w) if(!visitedw) dfs(g,w); voiddfstraverse(Graph *g) int i; for(i=1;ivexnum;i+) visitedi=0; for(i=1;ivexnum;i+) if(!visitedi) dfs(g,i); （7）定义队列 typedefstruct int VM; int front; int rear; Queue; （8）初始化队列 initqueue(Queue*q) q-front=0; q-rear=0; （9）判断队列是否为空 int quempty(Queue *q) if(q-front=q-rear) return 0; else return 1; （10）入队操作enqueue(Queue *q,int e) if(q-rear+1)%M=q-front) printf(Thequeue is overflow!n); return 0; else q-Vq-rear=e; q-rear=(q-rear+1)%M; return 1; （11）出队操作dequeue(Queue *q) int t; if(q-front=q-rear) printf(The queue is empty!n); return 0; else t=q-Vq-front; q-front=(q-front+1)%M; return t; （12）广度遍历void BESTraverse(Graph *g) int i; Queue*q=(Queue *)malloc(sizeof(Queue); for(i=1;ivexnum;i+) visitedi=0; initqueue(q); for(i=1;ivexnum;i+) if(!visitedi) visitedi=1; visitvex(g,g-Vi); enqueue(q,g-Vi); while(!quempty(q) int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w) if(!visitedw) visitedw=1; visitvex(g,w); enqueue(q,w); 4、测试与分析：针对下图进行测试和分析：12345678由图已知有8个结点，根据提示“Please input the number of vertex:”输入“8”。再根据图输入邻接矩阵中有关系的两点，两点有关系只要输入一次即可。当输入完所有关系后输入“0，0”再输入回车，程序将输出该图邻接矩阵。再根据提示选择“b”，“d”或“q”。选“b”表示广度优先搜索（Breadth_First Search），“d”表示深度优先搜索（Depth_First Search），“q”表示退出。Please input the number the number of vertex:8Please input R:1,22,44,85,82,51,33,63,70,0This is the linjiejuzhen of graph:0 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 1 1 00 1 0 0 0 0 0 10 1 0 0 0 0 0 10 0 1 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 1 0 0 0Please input b or d or q,Breadth_first: b Depth_first: d quit: qbBreadth_first:1 2 3 4 5 6 7 8Please input b or d or q,Breadth_first: b Depth_first: d quit: qdDepth_fitst:1 2 4 8 5 3 6 7Please input b or d or q,Breadth_first: b Depth_first: d quit: qq Press any key to contine运行结果正确此程序可用四、设计总结： 图的遍历是程序设计语言编译中的一个最基本问题。“图的遍历”是数据结构中主要的内容之一，也是重要的内容之一。它是树的遍历的拓展，但要比树的遍历复杂得多，是排序等的基础。它运用了深度优先遍历，广度优先遍历，入队，出队等多种运算，很有意义，是对数据结构一些基本操作的综合应用。在做设计的开始就遇到了很多困难，比如，如何才能构造邻接矩阵，如何将邻接矩阵表示出来，如何将结果输出，以及深度优先搜索和广度优先搜索的用C语言表达等。在仔细研究教材寻找资料后，并和同学一同探讨最终将困难解决。本次课程设计是学习数据结构后的一次具体的实践，体现了理论与实践的有效结合。在实践中体现出理论的思想，在实践中深入了解理论的具体实质，在实践中明白理论的精髓所在。同样也很好地锻炼了我自己动手动脑的的能力！ 附录：源程序清单#defineM 20#include #include #include typedefstruct int VM; int RMM; int vexnum;Graph;void creatgraph(Graph *g,int n) int i,j,r1,r2; g-vexnum=n; /*顶点用i表示*/ for(i=1;iVi=i; for(i=1;i=n;i+) for(j=1;jRij=0; printf(Please input R(0,0 END):n); scanf(%d,%d,&r1,&r2); while(r1!=0&r2!=0) g-Rr1r2=1; g-Rr2r1=1; scanf(%d,%d,&r1,&r2); void printgraph(Graph *g)int i,j;for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) printf(%2d ,g-Rij); printf(n); int visitedM;void visitvex(Graph *g,int vex)printf(%d ,g-Vvex);int firstadjvex(Graph *g,int vex)int w,i;for(i=1;ivexnum;i+) if(g-Rvexi=1&visitedi=0) w=i; break; else w=0; return w;int nextadjvex(Graph *g,int vex,int w) int t; t=firstadjvex(g,w); return t; void dfs(Graph *g,intvex) intw; visitedvex=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w0;w=nextadjvex(g,vex,w) if(!visitedw) dfs(g,w); voiddfstraverse(Graph *g) int i; for(i=1;ivexnum;i+) visitedi=0; for(i=1;ivexnum;i+) if(!visitedi) dfs(g,i); typedefstructint VM;int front;int rear;Queue;initqueue(Queue*q) q-front=0; q-rear=0;int quempty(Queue *q) if(q-front=q-rear) return 0; else return 1; enqueue(Queue *q,int e) if(q-rear+1)%M=q-front) printf(Thequeue is overflow!n); return 0; else q-Vq-rear=e; q-rear=(q-rear+1)%M; return 1; dequeue(Queue *q) int t; if(q-front=q-rear) printf(The queue is empty!n); return 0; else t=q-Vq-front; q-front=(q-front+1)%M; return t; void BESTraverse(Graph *g) int i; Queue*q=(Queue *)malloc(sizeof(Queue); for(i=1;ivexnum;i+) visitedi=0; initqueue(q); for(i=1;ivexnum;i+) if(!visitedi) visitedi=1; visitvex(g,g-Vi); enqueue(q,g-Vi); while(!quempty(q) int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w) if(!visitedw) visitedw=1; visitvex(g,w); enqueue(q,w); main() int n; Graph*g=(Graph *)malloc(sizeof(Graph); char menu; printf(Please input the number of vertex:n); scanf(%d,&n); creatgraph(g,n); printf(This is the linjiejuzhen of graph:n); printgraph(g); input: printf(Please input b or d or q ,Breadth_