数据结构实验报告无向图

1、数据结构实验报告实验标题3360全向图的建立和遍历实验目的：了解无向图的相邻链表存储，熟悉无向图的宽度和深度。实验内容：对与无向图相邻的链表存储分别重复深度、宽度、非递归输出。一、需求分析1.在牙齿演示中，首先输入无方向图的相邻链表格式，其中输入无方向图的顶点数和面数、顶点信息以及每个边的顶点对应数。牙齿无向图以深度、宽度优先级通过输出。3.牙齿程序可以实现无向图的相邻链表存储，并且可以重复深度、宽度、范围、非递归输出。4.程序发出的命令是：(1)设置无向图的相邻链表存储(2)以深度优先级遍历输出(3)以宽度优先遍历输出(4)结束5.测试数据：abfdce顶点和面数：6，5顶点信息：a b c

2、 d e F边的顶点相应编号：0，10，20，32，43，4深度优先级横向输出：A d e c bf宽度优先遍历输出：A d c b ef2概述设计要执行这些操作，必须将相邻链表用作存储结构。1.基本任务：Void createalgraph(algraph g)创建无向图的相邻链表存储Void dfstraverseal (algraph g，int v)以深度优先级遍历输出Void bfstraverseal (algraph g，int v)按宽度优先级遍历输出牙齿程序包含四个模块。(1)主节目模块(2)全向图的相邻链表箱(3)深度优先级通过输出模块(4)宽度优先遍历输出模块3.模块调用

3、图：主节目模块深度优先级通过输出模块宽度优先遍历输出模块无向图的相邻链表存储模块三茄子详图设计1.元素类型、节点类型和指针类型：Typedef struct nodeInt adjvexStruct node * next edgenodeTypedef struct vnodeChar vertexEdgenode * firstedge vertxnodeTypedef vertxnode adj list 最大vernum；Typedef structAdjlist adjlistInt n、e； algraphedge node * s；Edge node * stack 最大vern

4、um，* p；2.每个模块的分析：(1)主节目模块Int main()int v=0；al graph g；createal graph(g)；Printf(“以深度优先级通过输出 n”)；Dfstraverseal(g，v):Printf(“宽度优先遍历输出 n”)；Bfstraverseal(g，v)；getchar()；getchar()；return 0；(2)全向图的相邻链表箱Void createalgraph(algraph g)Int i、j、k；edge node * s；Printf(输入顶点数和面数(输入格式为：顶点数，面数): n )；scanf(“%d”、“% d”、

5、(g.n)、(g . e)；/*导入的顶点和面数*/getchar()；Printf(输入顶点信息(输入格式为：(顶点编号(Cr): n )；for(I=0)；iadj vex=j；/*相邻点序号为j*/S-next=g.adjlisti。firstedge/*将新边节点s插入顶点VI的边头*/G.adjlisti。first edge=s；s=(edge node *)malloc(size of(edge node)；/*创建新边表节点s*/s-adj vex=I；/*相邻点序号为i*/S-next=g.adjlistj。firstedge/*将新边节点s插入顶点VJ的边头*/G.adjl

6、istj。first edge=s；(3)深度优先级通过输出模块Void dfstraverseal (algraph g，int v)int j=0；Edge node * stack 最大vernum，* p；Int visitedmaxvernum，top=-1，I；for(I=0)；I=0|p！=NULL)While(p)！=NULL)If(visitedp-adjvex=1)p=p-next；ElsePrintf (%c ，g. adjlist p-adjvex)。vertex)；/*访问v中与v相邻的p指向的顶点*/j；visitedp-adj vex=1；塔；塔。stacktop

7、=p；/*将p指向的顶点放入堆栈*/P=g. adjlist p-adjvex。firstedge/*从p指向的顶点开始*/If(top=0)p=stacktop；/*在堆栈后面，回溯访问节点的未访问邻近点。*/顶部-；p=p-next；printf(“ n”)；(4)宽度优先通过输出模块Void bfstraverseal (algraph g，int v)Int i、front=-1、rear=-1、j=0；edge node * p；for(I=0)；iadj vex=0)visitedp-adj vex=1；Printf (%c ，g. adjlist p-adjvex)。vertex

8、)；j；rear=rear 1；queuerear=p-adj vex；p=p-next；printf(“ n”)；3.函数调用图：Int main()Void dfstraverseal (algraph g，int v)Void bfstraverseal (algraph g，int v)Void createalgraph(algraph g)完整步骤： (请参见源档案)。4茄子使用指南、测试分析和结果1.使用节目的准则(1)牙齿程序的操作环境是VC6.0。(2)进入演示程序后，您将看到以下消息：输入顶点数和面数(输入格式为：顶点数，面数):输入顶点信息(输入格式为：(顶点编号(CR)

9、:输入边信息(输入格式：i，j):2.测试数据：abfdce顶点和面数：6，5顶点信息：a b c d e F边的顶点相应编号：0，10，20，32，43，4深度优先级横向输出：A d e c bf宽度优先遍历输出：A d c b ef3.运行界面。五、实验摘要这次节目书上有相关节目，写起来比较方便。通过这次编程，为无向图的相邻链表存储奠定了基础，熟练掌握了无向图的深度和宽度优先遍历输出。中间要存储无向不连续性，所以出现了一些问题，在自己的努力和同学的帮助下，通过无向不痛度的存储和这次实验，对无向度有了更深的了解，就能更好地掌握它的建立和巡回输出。教师意见：#include#include#d

10、efine maxvernum 100Typedef struct nodeInt adjvexStruct node * next edgenodeTypedef struct vnodeChar vertexEdgenode * firstedge vertxnodeTypedef vertxnode adj list 最大vernum；Typedef structAdjlist adjlistInt n、e； algraphint visitedmax vernum；int queuemax vernum；/创建无方向图Void createalgraph(algraph g)Int i

11、、j、k；edge node * s；Printf(输入顶点数和面数(输入格式为：顶点数，面数): n )；scanf(“%d”、“% d”、(g.n)、(g . e)；/*导入的顶点和面数*/getchar()；Printf(输入顶点信息(输入格式为：(顶点编号(Cr): n )；for(I=0)；iadj vex=j；/*相邻点序号为j*/S-next=g.adjlisti。firstedge/*将新边节点s插入顶点VI的边头*/G.adjlisti。first edge=s；s=(edge node *)malloc(size of(edge node)；/*创建新边表节点s*/s-adj vex=I；/*相邻点序号为i*/S-next=g.adjlis