《数据结构课程设计-图的遍历.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-图的遍历.doc（24页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上2012级计算机科学与技术专业数据结构课程设计文档设计题目 图的遍历班 级 12网路工程 组长学号 姓名 庄俊坤 学 号 姓名 林捷 学 号 姓名 周柏煌 学 号 姓名 赵云鹏 学 号 姓名 谢国印 完成日期 2014.1 前言图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。一、 设计题目 图遍历的演示二、 实验目的： 本课程设计是数据结构课程的组成之一，也是它的继续和延伸。采用集中学习方法，分组完成
2、一个小型应用系统。开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；同时培养学生的创新能力和创新意识，锻炼他们的团队协作精神。三、问题描述：由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面： 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。 在图结构中，一个顶
3、点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。四、功能要求（1）以邻接表作为存储结构；（2）由用户指定遍历的起点；（3）实现深度优先和广度优先遍历；（4）输出深度优先遍历和广度优先遍历的结点访问序列；（5）并给出相应生成树的边集。（6）给出至少3组测试数据，其中图顶点的个数大于10小于30。较高要求：建立深度和广度生成树，按凹入表或树形打印生成树。五、相关原理(1)深度优先搜索法深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问
4、的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visitedMAX_VERTEX_NUM; /访问标志数组Status (*VisitFunc)(int v); /VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G, Status(*Visit)(int v)VisitFunc = Visit;for(v=0; vG.vexnum; +v)visitedv
5、 = FALSE; /访问标志数组初始化for(v=0; v=0; w=NextAdjVex(G,v,w)/FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。/若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。/若w是v的最后一个邻接点，则返回空（0）。if(!visitedw)DFS(G, w); /对v的尚未访问的邻接顶点w调用DFS (2)广度优先搜索法图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, vi t，并均标记已
6、访问过，然后再按照vi1,vi2, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：Boolean visitedMAX_VERTEX_NUM; /访问标志数组Status (*VisitFunc)(int v); /VisitFunc是访问函数，对图的每个顶点调用该函数void BFSTraverse (Graph G, Status(*Visit)(int v)VisitFunc = Visit;for(v=0; vG.vexnum, +v)visitedv = FALSE;in
7、itQueue(Q); /置空辅助队列Qfor(v=0; v=0; w=NextAdjVex(G,u,w)if(!Visitedw) /w为u的尚未访问的邻接顶点Visitedw=TRUE; VisitFunc(w);EnQueue(Q, w);六、设计方案通过结合教材和网络资料，先分析各个算法的基本实现的方法，然后将基本算法列出，之后根据需要，将各个算法进行整合、使用。七、详细设计1.邻接表的存储表示int visited30;# define MAX_VERTEX_NUM 30# define OK 1/typedef int VertexType;typedef int InfoType
8、;/表节点typedef struct ArcNode /弧 int adjvex; struct ArcNode *nextarc;ArcNode;/头节点typedef struct VNode/表头 int data; ArcNode *firstarc;/指向第一条依附该定点的弧的指针VNode,AdjListMAX_VERTEX_NUM;2.图的构建typedef struct/图 AdjList vertices; int vexnum,arcnum;/顶点数，弧数 int kind;/图的种类标志ALGraph;/邻接表存储表示/图的创建void CreateDG(ALGraph
9、 &G) int k,i,v1; coutendlG.vexnum;/节点数 coutG.arcnum; /弧数 for(i=1;i=G.vexnum;i+)/初使化表头 G.verticesi.data=i; /初始化顶点值 G.verticesi.firstarc=NULL;/初始化指针 for(k=1;k=G.vexnum;k+) /输入边 int v2; cout请输入与结点kv2; cout请输入与第kv1; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) exit(-1); p-adjvex=v1; p-nextarc=
10、NULL; G.verticesk.firstarc=p; for(int i=1;iv2;i+) int m; cout请输入与第km; ArcNode *q; q=(ArcNode *)malloc(sizeof(ArcNode);/动态指针 if(!q) exit(-1); q-adjvex=m; /顶点给P q-nextarc=NULL; p-nextarc=q; p=q; /free(q); /free(p); 3.深度优先遍历void DFS (ALGraph G,int v )/深度搜索 visitedv=1; coutG.verticesv.datanextarc) w=x-a
11、djvex; if(visitedw=0) DFS(G,w); void DFSB (ALGraph G,int v)/深度搜索的边集 visitedv=1; ArcNode *y; y=(ArcNode*)malloc(sizeof(ArcNode); if(!y) exit(-1); y=G.verticesv.firstarc; int u=G.verticesv.data; int w; for(;y;y=y-nextarc) w=y-adjvex; if(visitedw=0) coutuwendl; DFSB(G,w); typedef struct QNode int data;
12、 QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;4.广度优先遍历void BFS(ALGraph G,int v)/广度搜索 int u; LinkQueue Q; InitQueue(Q); if(visitedv=0) visitedv=1; coutG.verticesv.datanextarc) w=z-adjvex; if(visitedw=0) visitedw=1; coutwnextarc) w=r-adjvex; if(visitedw=0) visited
13、w=1; coutuwendl; EnQueue(Q,w); 5.主函数int main() int i; ALGraph G; CreateDG(G); int x; coutx; cout邻接表为：endl; for(int j=1;j=x;j+) coutG.verticesj.data ; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) exit(-1); p=G.verticesj.firstarc; while(p) coutadjvexnextarc; coutendl; cout请输入第一个要访问的结点序号：n; f
14、or( i=0;i30;i+) visitedi=0; cout广度搜索：endl; BFS(G,n); for( i=0;i30;i+) visitedi=0; coutendl; cout边集：endl; BFSB(G,n); for( i=0;i30;i+) visitedi=0; cout深度搜索：endl; DFS(G,n); for( i=0;i30;i+) visitedi=0; coutendl; cout边集：endl; DFSB(G,n); /system(pause); return 0;八、测试结果（分析Test_1）主界面输入结点个数以及边数，构建图。（如上图，节点个
15、数10，边数11）功能模块Test_1(10节点，11条边)邻接表为：如图，左列110分别为结点编号。横表分别为对应结点相邻点的结点编号（如结点1与结点2、3、4相邻）广度优先遍历为：如图，以用户指定的“1”结点为顶点进行广度优先遍历。所经路径及其顺序如图边集所示。（搜索原理参照本报告“五、相关原理”）深度优先遍历为：如图，以用户指定的“1”结点为顶点进行深度优先遍历。所经路径及其顺序如图边集所示。（搜索原理参照本报告“五、相关原理”）Test_2邻接表为：广度优先遍历为：深度优先遍历为：Test_3邻接表为：广度优先遍历为：深度优先遍历为：九、总结通过本次课程设计，使我更深刻的理解数据结构及
16、其重要作用,对数据结构有了一个新的认识,深刻的认识到数据结构对于我们学习计算机的重要性和其深远但是意义.同时,通过这次课程设计,也加强我的动手能力和思维能力,可以将自己所学的知识用于实践,这不仅对自己是一次锻炼机会, 而且让自己有一种成就感和自豪感，觉得自己终于可以做出一点有用的东西了。当遇到一个算法问题时，首先要知道自己以前有没有处理过这种问题，如果见过，那么你一般会做出来；如果没见过，那么考虑以下问题： 1、问题是否是建立在某种已知的熟悉的数据结构（例如，选择、深度优先遍历、广度优先遍历等） 上？如果不是，则要自己设计数据结构。 答是。此次课程设计的算法都建立在我们课本所学的内容。 2、问
17、题所要求编写的算法属于以下哪种类型？（建立数据结构，修改数据结 构，遍历，查找，排序） 答问题所要求编写的算法属于遍历。3、确认你的思路可行，然后开始编写程序，在编写代码的过程中，尽可能把 各种问题考虑的详细，周密，程序应该具有良好的结构，并且在关键的地方配有 注释。 更重要的是对VC+有了更深的认识，基本掌握了图的遍历。同时在课程设计的过程中也深深地感到了自己专业知识的匮乏。动手能力极差。在今后的学习中加强动手能力的培养，加强实践十、使用教材与参考资料1 数据结构（c语言描述），严蔚敏编著，清华大学出版社2数据结构题集，严蔚敏编著，清华大学出版社十一、小组成员分工：组长：庄俊坤(算法分析、编
18、程、后期修改)副组长：赵云鹏(算法分析、调试、文档)组员：林捷，周柏煌，谢国印(调试、后期修改、侧视图的制作附录：(程序代码)#include# include # include # include using namespace std;/邻接表存储表示int visited30;# define MAX_VERTEX_NUM 30# define OK 1/typedef int VertexType;typedef int InfoType;/表节点typedef struct ArcNode /弧 int adjvex; struct ArcNode *nextarc;ArcNode
19、;/头节点typedef struct VNode/表头 int data; ArcNode *firstarc;/指向第一条依附该定点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/typedef struct/图 AdjList vertices; int vexnum,arcnum;/顶点数，弧数 int kind;/图的种类标志ALGraph;/邻接表存储表示/图的创建void CreateDG(ALGraph &G) int k,i,v1; coutendlG.vexnum;/节点数 coutG.arcnum; /弧数 for(i=1;i=G.vexnum;i+)
20、/初使化表头 G.verticesi.data=i; /初始化顶点值 G.verticesi.firstarc=NULL;/初始化指针 for(k=1;k=G.vexnum;k+) /输入边 int v2; cout请输入与结点kv2; cout请输入与第kv1; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) exit(-1); p-adjvex=v1; p-nextarc=NULL; G.verticesk.firstarc=p; for(int i=1;iv2;i+) int m; cout请输入与第km; ArcNode *
21、q; q=(ArcNode *)malloc(sizeof(ArcNode);/动态指针 if(!q) exit(-1); q-adjvex=m; /顶点给P q-nextarc=NULL; p-nextarc=q; p=q; /free(q); /free(p); /深度优先遍历void DFS (ALGraph G,int v )/深度搜索 visitedv=1; coutG.verticesv.datanextarc) w=x-adjvex; if(visitedw=0) DFS(G,w); void DFSB (ALGraph G,int v)/深度搜索的边集 visitedv=1;
22、ArcNode *y; y=(ArcNode*)malloc(sizeof(ArcNode); if(!y) exit(-1); y=G.verticesv.firstarc; int u=G.verticesv.data; int w; for(;y;y=y-nextarc) w=y-adjvex; if(visitedw=0) coutuwnext=NULL;void EnQueue (LinkQueue &Q,int e)/进队 QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p-data=e; p-next=NULL
23、; Q.rear-next=p; Q.rear=p; /free(p);int DeQueue (LinkQueue &Q,int &e)/出队 if(Q.front=Q.rear) return -1; QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return e;int QueueEmpty (LinkQueue Q)/判断队列是否为空 if(Q.f
24、ront=Q.rear) return 1; return 0; void BFS(ALGraph G,int v)/广度搜索 int u; LinkQueue Q; InitQueue(Q); if(visitedv=0) visitedv=1; coutG.verticesv.dataadjvex;w=0;w=z-nextarc-adjvex) if(visitedw=0) visitedw=1; coutwnextarc) w=z-adjvex; if(visitedw=0) visitedw=1; coutwnextarc) w=r-adjvex; if(visitedw=0) vis
25、itedw=1; coutuwendl; EnQueue(Q,w); int main() int i; ALGraph G; CreateDG(G); int x; coutx; cout邻接表为：endl; for(int j=1;j=x;j+) coutG.verticesj.data ; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) exit(-1); p=G.verticesj.firstarc; while(p) coutadjvexnextarc; coutendl; cout请输入第一个要访问的结点序号：n; for( i=0;i30;i+) visitedi=0; cout广度搜索：endl; BFS(G,n); for( i=0;i30;i+) visitedi=0; coutendl; cout边集：endl; BFSB(G,n); for( i=0;i30;i+) visitedi=0; cout深度搜索：endl; DFS(G,n); for( i=0;i30;i+) visitedi=0; coutendl; cout边集：endl; DFSB(G,n); /system(pause); return 0;专心-专注-专业
