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

数据结构实验报告实验题目:无向图的存储和遍历实验目的：1、掌握使用Visual C+6.0上机调试程序的基本方法；2、 掌握图的邻接表存储结构和深度优先遍历的非递归算法。3、 提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。实验内容：建立有10个顶点的无向图的邻接表存储结构，然后对其进行深度优先遍历，该无向图可以是无向连通图或无向非连通图。一、需求分析1、输入的形式和输入值的范围：根据提示，首先输入图的所有边建立邻接表存储结构，然后输入遍历的起始顶点对图或非连通图的某一连通分量进行遍历。2、输出的形式：输出对该图是连通图或非连通图的判断结果，若是非连通图则输出各连通分量的顶点，之后输出队连通图或非连通图的某一连通分量的遍历结果。3、程序所能达到的功能：输入图的所有边后，建立图的邻接表存储结构，判断该图是连通图或非连通图，最后对图进行遍历。4、测试数据：输入10个顶点（空格分隔）:A B C D E F G H I J输入边的信息（格式为x y）:AB AC AF CE BD DC HG GI IJ HJ EH该图为连通图,请输入遍历的起始顶点:A遍历结果为:A F C D B E H J I G是否继续？（是,输入1;否,输入0）:1输入10个顶点（空格分隔）:A B C D E F G H I J输入边的信息（格式为xy）:AB AC CE CA AF HG HJ IJ IG该图为非连通图,各连通分量中的顶点为: 输入第1个连通分量起始顶点:F第1个连通分量的遍历结果为:F A C E B输入第2个连通分量起始顶点:I第2个连通分量的遍历结果为:I G H J输入第3个连通分量起始顶点:D第3个连通分量的遍历结果为:D是否继续？（是,输入1;否,输入0）:0谢谢使用!Press any key to continue二 概要设计1、 邻接表是图的一种顺序存储与链式存储结构结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有邻接表的表头放到数组中，就构成了图的邻接表，邻接表表示中的两种结点结构如下所示。 一种顶点表的结点结构，它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成，另一种是边表（即邻接表）结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。2、 无向图的建立输入顶点后，将顶点信息存入顶点表的顶点域。在输入边的信息后，如输入的一条边为XY，则生成新的边表结点，将其插入到顶点X的边表头部，同理，生成新的边表结点，将其插入到顶点Y的边表头部。最终完成图的建立。3、 图的深度优先遍历设p为指向边表结点的指针，首先访问图的指定的起始顶点V，从V出发访问一个与V邻接的p所指的顶点，并将其压入栈中，再从p所指定点出发，访问与p所指顶点邻接且未被访问的顶点，以后从该顶点出发。重复上述过程，知道找不到存在未访问过的邻接顶点为止。之后执行出栈操作，退回到尚有未访问过的邻接点的顶点，从该顶点出发，重复之前所述的操作，知道所有被访问过的顶点的邻接点都已被访问为止。下图中的深度优先遍历结果为ABDCEHJIGF，AFCEHGIJDB等。4、本程序的基本操作和模块：确定顶点所对应的下标的函数：locate(ALGraph &G,char ch)建立图的邻接表存储结构的函数：Create(ALGraph &G,SeqStack &s)深度优先遍历的函数：DFS(ALGraph &G,int v,SeqStack &s,int visited,int tag) 判断图是否连通的函数：Judge(ALGraph &G,int visited,SeqStack &s)确定非连通图连通分量值的函数：Get(ALGraph &G,int visited,SeqStack &s)主函数：main( )函数的调用关系如下图所示: 三 详细设计（1） 元素类型、结点类型1、 邻接表的表示形式描述typedef struct node/边表结点int adjvex;/邻接点域struct node *next;/指向下一个邻接点的指针域EdgeNode;typedef struct vnode/顶点表结点char vertex;/顶点域EdgeNode *firstedge;/边表头指针VertexNode;typedef VertexNode AdjList10;/AdjList是邻接表类型typedef struct/以邻接表方式存储的图类型AdjList adjlist;/邻接表int e;/图的边数ALGraph;2、 顺序栈的类型描述typedef struct/存放访问过的结点的栈EdgeNode *pin10;/存放边表结点的指针int top;/栈顶指针SeqStack;（2） 每个模块的分析1、 主程序模块main()定义数组visited10,用于记录遍历过程中结点是否已访问过定义邻接表存储结构的图，定义栈while(1) 建立图的邻接表存储结构判断图是否连通如果图为连通图则执行以下操作输入图的遍历的起始顶点进行深度优先遍历 如果图为非连通图则执行以下操作确定非连通图连通分量值 for(j=0;jt;j+)当j小于连通分量值，对非连通图进行遍历输入某连通分量的遍历的起始顶点输出该连通分量的遍历的结果是否继续，若是则继续操作，若否则结束程序2、 确定顶点所对应的下标的函数 int locate(ALGraph &G,char ch)从下标0开始，执行循环操作，如果找到该顶点的下标则结束操作返回下标的值3、 建立图的邻接表存储结构的函数 void Create(ALGraph &G,SeqStack &s)定义指向边表结点的指针建立有10个顶点的顶点表，顶点的边表头指针设为空while(r!=n)/输入边的信息，建立边表，输入回车时结束输入边的信息在非连通图中，若边数为0，则输入0，结束将输入的边的顶点转换为相应的下标值 设第一个顶点对应下标i，第二个顶点对应下标j生成新的边表结点p 邻接点序号为j 将新边表结点p插入到下标为i的顶点的边表头部 将p赋给下标为i的顶点的边表头指针生成新的边表结点p 邻接点序号为i 将新边表结点p插入到下标为j的顶点的边表头部 将p赋给下标为j的顶点的边表头指针4、 深度优先遍历的函数 void DFS(ALGraph &G,int v,SeqStack &s,int visited,int tag) 定义指向边表结点的指针p则输出起始结点的值 p为该顶点的边表头指针所指的边表结点 访问过的顶点，则visited数组中的对应下标为赋为1while(栈非空，且指针p非空)while(p非空)若当前边表结点p已经访问过，则p指向下一个边表结点若未访问过，则执行以下操作若标记值为1，则输出结点的值访问过的顶点，则visited数组中的对应下标为赋为1指针p入栈令p为该顶点的边表头指针所指的边表结点if(p指针为空)退栈，取出栈顶元素赋给pp指向下一个边表结点5、 判断图是否连通的函数int Judge(ALGraph &G,int visited,SeqStack &s)初始时，t的值为0，visited数组中的值置0进行一次深度优先遍历，若结点已经访问则visited数组中的值置1 for(i=0;i10;i+) 如果仍有未访问的顶点，则t的值加1，继续深度优先遍历 若t未0，表示该图为连通图，若t不为0，表示该图为非连通图，返回相应的值6、 确定非连通图连通分量值的函数 int Get(ALGraph &G,int visited,SeqStack &s)/确定非连通图连通分量值的函数初始时，t的值为0，visited数组中的值置0深度优先遍历，输出该连通分量中的所有顶点for(i=0;i10;i+)如果仍有未访问的顶点，则t的值加1，继续深度优先遍历输出另外一个连通分量中的所有顶点返回连通分量的值t+1四 使用说明、测试分析及结果1、 程序使用说明：（1） 本程序运行环境为Visual C+ 6.0；（2） 根据界面提示进行操作：输入的10个顶点以空格分隔，按回车输入结束输入边的信息，格式为XY，以空格分隔，按回车结束，对于非连通图，当边的个数为0时输入0，按回车结束输入遍历的起始顶点时，输入字母后按回车结束2、 测试结果与分析：输入10个顶点（空格分隔）:A B C D E F G H I J输入边的信息（格式为x y）:AB AC AF CE BD DC HG GI IJ HJ EH该图为连通图,请输入遍历的起始顶点:A遍历结果为:A F C D B E H J I G是否继续？（是,输入1;否,输入0）:1输入10个顶点（空格分隔）:A B C D E F G H I J输入边的信息（格式为x y）:AB AC CE CA AF HG HJ IJ IG该图为非连通图,各连通分量中的顶点为: 输入第1个连通分量起始顶点:F第1个连通分量的遍历结果为:F A C E B输入第2个连通分量起始顶点:I第2个连通分量的遍历结果为:I G H J输入第3个连通分量起始顶点:D第3个连通分量的遍历结果为:D是否继续？（是,输入1;否,输入0）:0谢谢使用!Press any key to continue由上测试结果分析得，该程序功能满足题目要求。3、 调试过程中遇到的问题及解决方法本次实验的错误的主要发生在输入边的信息上，对于直接输入字符型的边的信息，出现过很多错误，在参考了C程序设计的教材后，对字符串的输入的部分进行了复习，最后修改正确。另外，因为程序修改后，对边或顶点的输入都为字符的形式，忽略了吸收回车，在运行过程中出现了错误，因为以前也犯过这样的错误，所以很快意识到并改正。还有在函数中将输入的顶点转化成字符，以及求非连通图的连通分量时，出现了相应的返回值与实际值相差1的情况，这个问题在认真地分析程序后修改正确。4、 运行界面五、实验总结本次实验提前作了预习，初次编写的程序由于照搬教材上的程序使运行界面显得很不人性化，在实验课上经过老师的指点后认识到