数据结构课程设计——图的存储与遍历.doc

中南大学数据结构课程设计题 目 图的存储和遍历 学生姓名 指导教师 学 院 信息科学与工程 专业班级 完成时间 2008.01.23 第一章 课程设计目的1.1掌握图的邻接表存贮结构。1.2掌握队列的基本运算实现。1.3掌握图的邻接表的算法实现。1.4掌握图的广度优先搜索周游算法实现。1.5掌握图的深度优先搜索周游算法实现第二章 设计内容和要求对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度、深度优先搜索周游。第三章 运行环境Turber c/c+集成实验与学习环境第四章 课程设计分析我的设计思路是,先通过给定的顶点和边的信息构造出图，用邻接表存储该图，然后用DFS或BFS进行遍历.下面是我设计过程的结构图:有向图无向图深度优先遍历图的遍历用邻接表存储图根据信息创建图输入顶点和边的信息主函数main()输入图的顶点数和边数广度优先遍历图4.1 设计过程的结构图通过自己对图的存储与遍历的算法了解和实践，进一步加深了图的邻接表存储，其特点有：1.存储表示，不惟一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序；空间复杂度S(n，e)，S(n，e)=O(n+e)。稀疏图用邻接表表示比用邻接矩阵表示节省存储空间；2.求顶点的度，无向图：顶点vi的度则是第i个边表中的结点个数；3.判定(Vi，Vj)或是否是图的一条边；在邻接表表示中，需扫描第i个边表最坏情况下要耗费O(n)时间；4.求边的数目，与e的大小无关 只要对每个边表的结点个数计数即可求得e，所耗费的时间，是O(e+n)。当en2时，采用邻接表表示更节省空间。至于两种遍历，在计算机科学中，经常会遇到图的遍历问题。解决这一问题的经典算法就是所谓深度优先搜索和广度优先搜索，理论证明两套算法的性能是等效的。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处在于对顶点访问的顺序不同而已.第五章 算法（数据结构）描述实现图的存储和遍历其思路总体分二个大步骤：1.1图的存储采用邻接表对图进行存储，并输出存储结果，为实现邻接表的建立附设连个指向图相关边的指针*p,*q.再用for(k=1;k=e;k+)同时*p，*q移动，给每条边分配内存，再利用函数print(g,n)将建立好的邻接表输出。1.2图的遍历图的遍历是指从某个顶点出发，沿着某条搜索路径对图中所有的顶点进行访问且仅访问一次的过程。1.2.1 深度优先搜索（DFS）深度优先搜索类似于树的前序遍历，也是一遇到顶点就进行访问。其特点是尽可能先对纵深方向进行搜索，因此很容易用递归算法实现。如果将遍历过程中走过的边连接起来，即可得到深度优先遍历生成树。深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3。依次类推，直到一个所有邻接顶点都被访问过为止。1.2.2 广度优先搜索（BFS）广度优先搜索类似于树的按层次遍历。首先访问指定的起始点v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2， wk，然后再依次从w1，w2， wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。广度优先遍历的特点是尽可能进行横向搜索，即最先访问的顶点其邻接点也被先访问。因此，借助一个队列来保存已被访问过的顶点序列。访问一个顶点vi时（出队），同时将vi相邻的其余结点入队。每个顶点只能入队一次。图是一种数据结构,加上一组基本操作,就构成了抽象数据类型.图的抽象数据类型定义如下:ADT Graph 数据对象 V: V是具有相同特性的数据元素的集合,称为顶点集. 数据关系 R: R = VR VR = |v,w属于集合V且P(v,w),表示从v到w的弧,谓词P(v,w)定义了弧的意义或信息 基本操作 P: CreateGraph(&G,V,VR); 初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR的定义构造图G. DFSTraverse(G,Visit(); 初始条件:图G存在,Visit是顶点的应用函数. 操作结果:对图进行深度优先遍历.在遍历过程中对每个顶点调用函数Visit一次且仅一次.一旦visit()失败,则操作失败. BFSTraverse(G,Visit(); 初始条件:图G存在,Visit是顶点的应用函数. 操作结果:对图进行广度优先遍历.在遍历过程中对每个顶点调用函数Visit一次且仅一次.一旦visit()失败,则操作失败. ADT Graph由于设计过程中也用到了队列,下面给出队列抽象数据类型的定义: ADT Queue 数据对象:D = ai|ai是队列中的元素,i=1,2,n 数据关系:R1 = |ai-1,ai属于D,i=1,2,n 约定其中a1端为队列头,an端为队列尾. 基本操作: InitQueue(&Q) 操作结果:构造一个空队列Q. QueueEmpty(Q) 初始条件:队列Q已经存在. 操作结果:若Q为空队列,则返回TRUE,否则返回FALSE. QueueFull(Q) 初始条件:队列Q已经存在. 操作结果:若队列Q已满,则返回TRUE,否则返回FALSE. EnQueue(&Q,e) 初始条件:队列Q已经存在. 操作结果:插入元素e为Q的新的队尾元素. DeQueue(&Q,&e) 初始条件:Q为非空队列. 操作结果:删除Q的队头元素,并用e返回其值. ADT Queue算法5.1 图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType *info; /该弧相关信息的指针 ArcNode;typedef struct VNode VertexType date; /顶点信息 ArcNode *firstarc; /指向第一条依附顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数 int kind; /图的种类标志 ALGraph;算法5.2 图的深度优先遍历Boolean visitedMAX; /访问标志数组Status (*VisitFuc) (int v); /函数变量void DFSTraverse(Graph G, Status (*Visit) (int v) /对图G作深度优先遍历 VisitFuc = Visit; /使用全局变量VisitFuc,使DFS不必设函数指针参数 for (v=0;vG.vexnum;+v) visitedv = FALSE; /访问标志数组初始化 for (v=0;vG.vexnum;+v) if(! visitedv) DFS(G,v); /对尚未访问的顶点调用DFS 算法5.3图的广度优先遍历Boolean visitedMAX; /访问标志数组void BFSTraverse(Graph G, Status (*Visit)(int v) /按广度优先非递归遍历图G.使用辅助队列Q和访问标志数组visited. for (v = 0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q) /置空的辅助队列Q for (v = 0; v = 0; w = NextAdjVex(G,u,w) if (! Visitedw) /w为尚未访问的邻接顶点 Visitedw = TRUE; Visit(w); EnQueue(Q,w); /if /while /if /BFSTraverse第六章 源代码#include #include #define QueueSize 50 #define MaxVertexNum 50 #define NULL 0 typedef int datatype; typedef struct /定义存放顶点的队列 int front; int rear; datatype dataQueueSize; /顶点信息 CirQueue; typedef int VertexType; typedef struct node /定义表结点 int adjvex; /邻接点 struct node *next; /指向下一个邻接点的指针 EdgeNode; typedef struct vnode /定义顶点 VertexType vertex; EdgeNode *firstedge; /指向第一条依附该顶点的边的指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /邻接表 typedef struct /定义图 AdjList adjlist; int n,e; ALGraph; typedef enumFALSE,TRUE Boolean; /说明真假二值 Boolean visitedMaxVertexNum; /辅助数组标志顶点是否已被访问 void InitQueue(CirQueue *q) /构造一个空队列 q-front=q-rear=0; int QueueEmpty(CirQueue *q) /判断队列是否为空 return(q-front=q-rear); int QueueFull(CirQueue *q) /判断队列是否已满 return(q-rear+1)%QueueSize=q-front); void EnQueue(CirQueue *q, datatype x) /插入新的队尾元素 if (!QueueFull(q) q-data(q-rear)%QueueSize=x;q-rear=(q-rear+1)%QueueSize; else printf(Queue overflow);exit(0); datatype DeQueue(CirQueue *q) /删除队头元素 datatype x; if (!QueueEmpty(q) x=q-dataq-front; q-front=(q-front+1)%QueueSize; return(x); else printf(Queue is Empty); exit(0); void QueueFront(CirQueue *q) printf(%d,q-dataq-front); void CreateALGraph(ALGraph *G,int option) /创建图 int i,j,k; EdgeNode *s; printf(请输入图的顶点数和边数，如 (4,5):n); scanf(%d,%d),&G-n,&G-e); getchar(); printf(请输入所有顶点的信息，如 01234:n); for (i=0;in;i+) /依次读入图的顶点 G-adjlisti.vertex=getchar(); G-adjlisti.firstedge=NULL; getchar(); /清除回车符 printf(请输入所有边的信息, 如 (2,5).etc:); for (k=0;ke;k+) /依次读入图的边 scanf(%d,%d),&i,&j); s=(EdgeNode *)malloc(sizeof(EdgeNode); /分配存储 s-adjvex=j; s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /指针后移 if (!option) s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; getchar(); void DFS(ALGraph *G,int i) /深度优先访问G中第i个顶点 EdgeNode *p; printf(visit vertex:%cn,G-adjlisti.vertex); visitedi=TRUE; /标记该顶点已被访问 p=G-adjlisti.firstedge; while(p) /依次对尚未访问的邻接点递归调用DFS if (!visitedp-adjvex) DFS(G,p-adjvex); p=p-next; void DFSTraverse(ALGraph *G) /深度优先遍历图G int i; for (i=0;in;i+) /初始化辅助数组 visitedi=FALSE; for (i=0;in;i+) /依次对尚未访问的顶点递归调用DFS if (!visitedi) DFS(G,i); void BFS(ALGraph *G,int k) /广度优先访问G中第k个顶点 int i; CirQueue Q; /构造一个循环队列 EdgeNode *p; InitQueue(&Q); /初始化队列 printf(visit vertex: %cn,G-adjlistk.vertex); visitedk=TRUE; /标记该顶点已被访问 EnQueue(&Q,k); /把已被访问的顶点插入队尾 while(!QueueEmpty(&Q) /依次对尚未访问的邻接点进行访问 i=DeQueue(&Q); p=G-adjlisti.firstedge; while(p) if (!visitedp-adjvex) printf(visit vertex: %cn,G-adjlistp-adjvex.vertex); visitedp-adjvex=TRUE; EnQueue(&Q,p-adjvex); p=p-next; void BFSTraverse(ALGraph *G,int j)/从第j个顶点开始广度优先遍历图G int i; for (i=0;in;i+) /初始化辅助数组 visitedi=FALSE; for (i=j;i!=j-1;i=(i+1)%G-n) /依次对尚未访问的顶点递归调用BFS if (!visitedi) BFS(G,i); main() int i,j; EdgeNode *p; int option; /option用来决定创建无向图或有向图 ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph); /给图分配存储 printf(选择创建哪一种图？ 无向图(0) or 有向图(1):); scanf(%d,&option); getchar(); CreateALGraph(G,option); printf(图的邻接表如下 : n); for (i=0;in;i+) /依次创建各顶点的邻接表 printf(%d) %c ,i,G-adjlisti.vertex); p=G-adjlisti.firstedge; while(p) printf( %d ,p-adjvex); p=p-next; printf(n); printf(选择进行哪种遍历:n); printf( 1.深度优先遍历n); printf( 2.广度优先遍历n); scanf(%d,&i); switch (i) /选择进行图的遍历 case 1:printf(深度优先遍历图的结果如下:n); DFSTraverse(G);break; case 2:printf(选择开始遍历的结点:);scanf(%d,&j); printf(广度优先遍历图的结果如下:n); BFSTraverse(G,j);break; 第七章 运行结果分析4132043120 图7.1 5个顶点7条边的无向图 图7.2 5个顶点7条弧的有向图7.1 无向图的深度优先遍历创建无向图,如图7.1,并进行深度优先遍历.运行结果如下:7.2 无向图的广度优先遍历 创建无向图,如图7.1,并进行广度优先遍历.运行结果如下:7.3 有向图的深度优先遍历创建无向图,如图7.2,并进行深度优先遍历.运行结果如下:7.4 有向图的广度优先遍历创建无向图,如图7.2,并进行广度优先遍历.运行结果如下:第八章 结束语课程设计总结:数据结构课程设计是在我们学完了数据结构的全部课程以及C和C+语言之后进行的.这是我们在学完数据结构课程后的一次深入的综合性的总复习,也是一次理论联系实际的训练,因此,它在我们四年的大学生活中占有重要的地位。 就我个人而言，我希望能通过这次课程设计对自己的过去半年的大学生活做出总结,同时为将来工作进行一次适应性训练，从中锻炼自己分析问题、解决问题的能力，为今后自己的学习生活打下一个良好的基础。但是这次课程设计的确显得有点心有余而力不足:首先,就是自己的心态问题,轻视这次课程设计,以为可以像以前一样轻轻松松地通过,这次由于要接受学校的教学评估,学校会对我们这次的课程设计报告进行抽样检查,所以指导老师对我们也特别严格要求.其次,就是基础知识问题,由于数据结构课听不太懂,老师讲得又比较快,加上自己的学习态度不是很好,课后没有去复习和做一些习题来巩固知识,结果就落下了很大一截.自己很想好好的把它补充上来,但一直没补充上来,说起这事情自己心里不免有些惭愧!从而就这样,自己面对课程设计困难重重,在一次又次的打击与挫折下,自己心里不免有点不满起来,然而现实就是现实,没办法,课程设计是必须完成的.虽然自己心里有这样的失败感,但在外人看来,我就是行,结果自