数据结构 向图的存储和遍历.doc

《数据结构 向图的存储和遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验报告◎实验题目:无向图的存储和遍历◎实验目的：1、掌握使用VisualC++6.0上机调试程序的基本方法；2、掌握图的邻接表存储结构和深度优先遍历的非递归算法。3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。◎实验内容：建立有10个顶点的无向图的邻接表存储结构，然后对其进行深度优先遍历，该无向图可以是无向连通图或无向非连通图。一、需求分析1、输入的形式和输入值的范围：根据提示，首先输入图的所有边建立邻接表存储结构，然后输入遍历的起始顶点对图或非连通图的某一连通分量进行遍历。2、输出的形式：输出对该图是连通图或非连通图

2、的判断结果，若是非连通图则输出各连通分量的顶点，之后输出队连通图或非连通图的某一连通分量的遍历结果。3、程序所能达到的功能：输入图的所有边后，建立图的邻接表存储结构，判断该图是连通图或非连通图，最后对图进行遍历。4、测试数据：输入10个顶点（空格分隔）:ABCDEFGHIJ输入边的信息（格式为xy）:ABACAFCEBDDCHGGIIJHJEH该图为连通图,请输入遍历的起始顶点:A遍历结果为:AFCDBEHJIG是否继续？（是,输入1;否,输入0）:1输入10个顶点（空格分隔）:ABCDEFGHIJ输入边的信息（格式为xy）:ABACCECAAFH

3、GHJIJIG该图为非连通图,各连通分量中的顶点为:输入第1个连通分量起始顶点:F第1个连通分量的遍历结果为:FACEB输入第2个连通分量起始顶点:I第2个连通分量的遍历结果为:IGHJ输入第3个连通分量起始顶点:D第3个连通分量的遍历结果为:D是否继续？（是,输入1;否,输入0）:0谢谢使用!Pressanykeytocontinue二概要设计1、邻接表是图的一种顺序存储与链式存储结构结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链

4、表就称为顶点Vi的邻接表，再将所有邻接表的表头放到数组中，就构成了图的邻接表，邻接表表示中的两种结点结构如下所示。一种顶点表的结点结构，它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成，另一种是边表（即邻接表）结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。2、无向图的建立输入顶点后，将顶点信息存入顶点表的顶点域。在输入边的信息后，如输入的一条边为XY，则生成新的边表结点，将其插入到顶点X的边表头部，同理，生成新的边表结点，将其插入到顶点Y的边表头部。最终完成图的建立。3、图的深度优先遍历

5、设p为指向边表结点的指针，首先访问图的指定的起始顶点V，从V出发访问一个与V邻接的p所指的顶点，并将其压入栈中，再从p所指定点出发，访问与p所指顶点邻接且未被访问的顶点，以后从该顶点出发。重复上述过程，知道找不到存在未访问过的邻接顶点为止。之后执行出栈操作，退回到尚有未访问过的邻接点的顶点，从该顶点出发，重复之前所述的操作，知道所有被访问过的顶点的邻接点都已被访问为止。下图中的深度优先遍历结果为ABDCEHJIGF，AFCEHGIJDB等。4、本程序的基本操作和模块：确定顶点所对应的下标的函数：locate(ALGraph&G,charch)建立图

6、的邻接表存储结构的函数：Create(ALGraph&G,SeqStack&s)深度优先遍历的函数：DFS(ALGraph&G,intv,SeqStack&s,intvisited[],inttag)判断图是否连通的函数：Judge(ALGraph&G,intvisited[],SeqStack&s)确定非连通图连通分量值的函数：Get(ALGraph&G,intvisited[],SeqStack&s)主函数：main()函数的调用关系如下图所示:三详细设计（一）元素类型、结点类型1、邻接表的表示形式描述typedefstructnode//边表

7、结点{intadjvex;//邻接点域structnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表结点{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[10];//AdjList是邻接表类型typedefstruct//以邻接表方式存储的图类型{AdjListadjlist;//邻接表inte;//图的边数}ALGraph;1、顺序栈的类型描述typedefstruct//存

8、放访问过的结点的栈{EdgeNode*pin[10];//存放边表结点的指针inttop;//栈顶指针}SeqStack;