图的实验报告

1、数据结构实验报告标题：图1.存储图的邻接矩阵和邻接表(a)需求分析对于下图所示的有向图g，编写一个程序来完成以下功能：1.建立g的邻接矩阵并输出2.从g的邻接矩阵生成一个邻接表并输出3.然后从2的邻接表中生成相应的邻接矩阵并输出(2)系统设计1.此程序中使用的所有抽象数据类型的定义；typedef结构 int no信息类型信息； vertextype/顶点类型typedef结构/图形的定义 int edgesmaxvmaxv；int vexnum，arcnumvextype vexmaxv； mgraph/图的邻接矩阵类型typedef结构阳极/弧的节点结构类型 int adjvexstruc

2、t阳极* nextarc信息类型信息； arcnode顶点类型定义；typedef结构vnode /与标头相邻的节点类型顶点数据；arcnode * firstarc/指向第一个弧 vnodetypedef vnode adjlistmaxv；/adjlist是邻接表类型typedef结构 adjlist adjlist/邻接表int n，e； algraph/图的相邻表类型2.主程序流程，各程序模块间的层次调用关系，函数调用关系图：主()dispadj(g)；输出邻接表gdispmat(g)；输出邻接矩阵gmattolist(g，g)；将邻接矩阵g转换成邻接表g3.列出各功能模块的主要功能和

3、输入输出参数空matto列表(图g，算法g)将邻接矩阵g转换成邻接表g。void dispmat(mgraph g)输出邻接矩阵g。空dispadj(代数* g)输出邻接表g。int out度(代数* g，int v)找出图中每个顶点的度(3)调试分析调试过程中仍有一些拼写错误，经过检查可以及时纠正。有些是语法设计中的小错误，比如一些参数的初始值设置错误，使得程序调试出错。经过小组讨论和分析，这些结果得到了修正，算法的性能得到了提高，时间复杂度也尽可能地降低了。将邻接矩阵g转化为邻接表g并输出邻接表g的算法时间复杂度为o (n 2)。通过这次实验，我们对图形的存储方法有了更深的印象。(4)测试

4、结果测试结果：(1)有向图g的邻接矩阵是0 1 0 40 0 9 23 5 8 00 0 6 0(2)由图g的邻接矩阵转换而来的邻接表是：0:1 31:2 32:0 1 23:2(5)用户手册不需要输入参数(6)附录源程序#包括#包括# define xv 100/最大顶点数#定义inf 32767 /inf意味着typedef int infotypetypedef结构int no/顶点数信息类型信息；/顶点其他信息 vertextype/顶点类型typedef结构/图形的定义整数边maxvmaxv；/邻接矩阵int vexnum，arcnum/顶点数，弧数vextype vexmaxv；/

5、存储顶点信息 mgraph/图的邻接矩阵类型typedef结构阳极/弧的节点结构类型int adjvex/弧的结束位置struct阳极* nextarc/指向下一个弧的指针信息类型信息；/用于存储重量的弧线信息 arcnode顶点类型定义；typedef结构vnode /与标头相邻的节点类型顶点数据；/顶点信息arcnode * firstarc/指向第一个弧 vnodetypedef vnode adjlistmaxv；/adjlist是邻接表类型typedef结构adjlist adjlist/邻接表int n，e；/图中的顶点数n和边数e algraph/图的相邻表类型空matto列表(

6、m图g，算法* g)/将邻接矩阵g转换为邻接表 i，j，n=g . vex num；/n是顶点的数量arcnode *p。g=(algraph *)malloc(sizeof(algraph)；对于(i=0；iadjlisti。第一个弧=空；对于(i=0；i=0；j -)if (g.edgesij！=0)/邻接矩阵的当前元素不是0p=(arcnode *)malloc(sizeof(arcnode)；/创建节点*pp-adj vex=j；p-info=g . edgesij；p-nextarc=g-adjlisti.firstarc/将*p链到链表后g-adjlisti.第一弧=p；

7、g-n=n .g-e=g弧数；void dispmat(管理图形g)/输出邻接矩阵gint i，j；对于(i=0；在；在p=g-adjlisti.firstarcif (p！=空)打印格式(=: ，1)；而(p！=空)printf(=，p-adj vex)；p=p-下一个弧；printf( n )；int outender(algraph * g，int v)/求图中每个顶点的出度arcnode *p .int n=0；p=g-adjlistv.firstarc同时(p！=空) n；p=p-下一个弧；返回n；void main()int i，j；g1格拉夫；代数* g；int amaxv4=0，1，0，4，0，0，9，2，3，5，8，0，0，0，6，0，；g .vex num=4；g . arc num=8；对于(i=0；在德国)；/输入顶点数和边数scanf(% c ，