《数据结构课程设计——图的存储与遍历》由会员分享，可在线阅读，更多相关《数据结构课程设计——图的存储与遍历（17页珍藏版）》请在金锄头文库上搜索。
1、中南大学数据结构课程设计题 目 图的存储和遍历 学生姓名 指导教师 学 院 信息科学与工程 专业班级 完成时间 2008.01.23 第一章 课程设计目的1.1 掌握图的邻接表存贮结构。1.2 掌握队列的基本运算实现。1.3 掌握图的邻接表的算法实现。1.4 掌握图的广度优先搜索周游算法实现。1.5 掌握图的深度优先搜索周游算法实现第二章 设计内容和要求对任意给定的图（顶点数和边数自定） ，建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度、深度优先搜索周游。第三章 运行环境Turber c/c+集成实验与学习环境第四章 课程设计分析我的设
2、计思路是,先通过给定的顶点和边的信息构造出图，用邻接表存储该图，然后用 DFS 或 BFS 进行遍历.下面是我设计过程的结构图:图 4.1 设计过程的结构图输入图的顶点数和边数主函数 main()输入顶点和边的信息根据信息创建图用邻接表存储图图的遍历深度优先遍历 广度优先遍历无向图 有向图通过自己对图的存储与遍历的算法了解和实践，进一步加深了图的邻接表存储，其特点有：1.存储表示，不惟一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序；空间复杂度 S(n，e) ，S(n，e)=O(n+e)。稀疏图用邻接表表示比用邻接矩阵表示节省存储空间；2.求顶点的度，无向图：顶点 vi 的度则是第
3、 i 个边表中的结点个数；3.判定 (Vi，Vj)或是否是图的一条边 ；在邻接表表示中，需扫描第 i 个边表最坏情况下要耗费 O(n)时间 ；4.求边的数目，与 e 的大小无关 只要对每个边表的结点个数计数即可求得e，所耗费的时间，是 O(e+n)。当 en2 时，采用邻接表表示更节省空间。至于两种遍历，在计算机科学中，经常会遇到图的遍历问题。解决这一问题的经典算法就是所谓深度优先搜索和广度优先搜索，理论证明两套算法的性能是等效的。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处在于对顶点访问的顺序不同而已.第五章 算法（数据结
4、构）描述实现图的存储和遍历其思路总体分二个大步骤：1.1 图的存储采用邻接表对图进行存储，并输出存储结果，为实现邻接表的建立附设连个指向图相关边的指针*p,*q.再用 for(k=1;k|v,w 属于集合 V 且 P(v,w),表示从 v 到 w的弧,谓词 P(v,w)定义了弧的意义或信息 基本操作 P:CreateGraph(初始条件:V 是图的顶点集,VR 是图中弧的集合.操作结果:按 V 和 VR 的定义构造图 G.DFSTraverse(G,Visit();初始条件:图 G 存在,Visit 是顶点的应用函数.操作结果:对图进行深度优先遍历.在遍历过程中对每个顶点调用函数 Visit
5、一次且仅一次.一旦 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)操作结果:构造一个空队
6、列 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 Ar
7、cNode 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
8、.2 图的深度优先遍历Boolean visitedMAX; /访问标志数组Status (*VisitFuc) (int v); /函数变量void DFSTraverse(Graph G, Status (*Visit) (int v) /对图 G 作深度优先遍历VisitFuc = Visit; /使用全局变量 VisitFuc,使 DFS 不必设函数指针参数for (v=0;v = 0; w = NextAdjVex(G,u,w)if (! Visitedw) /w 为尚未访问的邻接顶点Visitedw = TRUE; Visit(w);EnQueue(Q,w);/if/while/i
9、f/BFSTraverse第六章 源代码#include #include #define QueueSize 50 #define MaxVertexNum 50 #define NULL 0typedef int datatype; typedef struct /定义存放顶点的队列int front; int rear; datatype dataQueueSize; /顶点信息CirQueue; typedef int VertexType; typedef struct node /定义表结点int adjvex; /邻接点struct node *next; /指向下一个邻接点的指
10、针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 InitQueu
11、e(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;
12、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), getchar(); printf(请输入所有顶点的信息，如 01234:n); for (i=0;in;i+) /依次读入图的顶点G-adjlisti.vertex=getchar(); G-adjlisti.firstedge=NULL; getchar();
