数据结构实验报告无向图.doc

《数据结构实验报告无向图.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》实验报告◎实验题目:无向图的建立与遍历◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。一、需求分析1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。2.该无向图以深度、广度优先遍历输出。3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先

2、遍历输出（3）以广度优先遍历输出（4）结束5.测试数据：abfdce顶点数和边数：6,5顶点信息：abcdef边的顶点对应序号：0,10,20,32,43,4深度优先遍历输出：adecbf广度优先遍历输出：adcbef二概要设计为了实现上述操作，应以邻接链表为存储结构。1.基本操作：voidcreatealgraph(algraph&g)创建无向图的邻接链表存储voiddfstraverseal(algraph&g,intv)以深度优先遍历输出voidbfstraverseal(algraph&g,intv)以广度优先

3、遍历输出2.本程序包含四个模块：（1）主程序模块（2）无向图的邻接链表存储模块（3）深度优先遍历输出模块（4）广度优先遍历输出模块3.模块调用图：主程序模块深度优先遍历输出模块广度优先遍历输出模块无向图的邻接链表存储模块三详细设计1.元素类型，结点类型和指针类型：typedefstructnode{intadjvex;structnode*next;}edgenode;typedefstructvnode{charvertex;edgenode*firstedge;}vertxnode;typedefvertxnode

4、Adjlist[maxvernum];typedefstruct{Adjlistadjlist;intn,e;}algraph;edgenode*s;edgenode*stack[maxvernum],*p;2.每个模块的分析：（1）主程序模块intmain(){intv=0;algraphg;createalgraph(g);printf("以深度优先遍历输出");dfstraverseal(g,v);printf("以广度优先遍历输出");bfstraverseal(g,v);getchar();getch

5、ar();return0;}（2）无向图的邻接链表存储模块voidcreatealgraph(algraph&g){inti,j,k;edgenode*s;printf("请输入顶点数和边数(输入格式为:顶点数,边数):");scanf("%d,%d",&(g.n),&(g.e));/*读入顶点数和边数*/getchar();printf("请输入顶点信息(输入格式为:(顶点号(CR))):");for(i=0;i

6、].vertex));/*读入顶点信息*/getchar();g.adjlist[i].firstedge=NULL;/*顶点的边表头指针设为空*/}printf("请输入边的信息(输入格式为:i,j):");for(k=0;kadjvex=j;/*邻接点序号为j*/s->next=g.adj

7、list[i].firstedge;/*将新边表节点s插入到顶点vi的边表头部*/g.adjlist[i].firstedge=s;s=(edgenode*)malloc(sizeof(edgenode));/*生成新边表节点s*/s->adjvex=i;/*邻接点序号为i*/s->next=g.adjlist[j].firstedge;/*将新边表节点s插入到顶点vj的边表头部*/g.adjlist[j].firstedge=s;}}（3）深度优先遍历输出模块voiddfstraverseal(algraph&g,i

8、ntv){intj=0;edgenode*stack[maxvernum],*p;intvisited[maxvernum],top=-1,i;for(i=0;i