河南工业大学实验报告_实验二 非线性结构(二)——图.docx

1、河南工业大学实验报告 实验目的1. 掌握图的邻接矩阵和邻接链表存储结构。2. 掌握图的建立、遍历、最小生成树等典型操作。二 实验内容及要求实验内容：（自选一题）1. 建立图的邻接矩阵或邻接链表存储结构，并在对应存储结构上实现图的递归遍历操作。2. 在邻接矩阵存储结构上，完成最小生成树的操作。实验要求：1. 根据所选题目，用 C 语言编写程序源代码。2. 源程序须编译调试成功，独立完成。三 实验过程及运行结果本次试验是采用邻接表的方法建立图，然后进行深度优先遍历具体实现结如下：/算法功能：采用邻接表存储结构建立无向图#include #include #define OK 1#define NU

2、LL 01 数据结构图的邻接表存储#define MAX_VERTEX_NUM 20 / 最大顶点数typedef int Status;/函数的类型，其值是函数结果状态代码typedef char VertexType; typedef int VRType; typedef int InforType;typedef struct ArcNodeint adjvex;/该边所指的顶点的位置struct ArcNode *nextarc;/指向下一条边的指针int weight;/边的权ArcNode;/表的结点typedef struct VNodeVertexType data;/顶点信

3、息（如数据等）ArcNode *firstarc;/指向第一条依附该顶点的边的弧指针VNode, AdjListMAX_VERTEX_NUM;/头结点typedef struct ALGraphAdjList vertices;int vexnum, arcnum;/图的当前顶点数和弧数ALGraph;/返回顶点 v 在顶点向量中的位置int LocateVex(ALGraph G, char v)6int i;for(i = 0; v != G.verticesi.data & i = G.vexnum)return -1; return i;/构造邻接链表Status CreateUDN(

4、ALGraph &G)intj;ArcNode *s, *t;printf(输入无向图顶点数: ); scanf(%d, &G.vexnum);printf(输入无向图边数: );scanf(%d, &G.arcnum); getchar();for(int i = 0; i G.vexnum; i+)printf(输入第%d 个顶点信息:, i+1);scanf(%c, &G.verticesi.data);/构造顶点向量G.verticesi.firstarc = NULL;getchar();char v1, v2;for(int k = 0; k adjvex = j;/该边所指向的顶

5、点的位置为 j s-nextarc = G.verticesi.firstarc; G.verticesi.firstarc =s;t-adjvex = i;/该边所指向的顶点的位置为 j t-nextarc = G.verticesj.firstarc; G.verticesj.firstarc =t;return OK;Status PrintAdjList(ALGraph &G)ArcNode *p;printf(%4s%6s%12sn, 编号, 顶点, 相邻边编号);for(int i = 0; i nextarc) printf(%4d, p-adjvex);printf(n);re

6、turn OK;int main()ALGraph G; CreateUDN(G); PrintAdjList(G); return 0;运行结果如下：四 调试情况、设计技巧及体会图的邻接表表示不唯一，这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序，另外对于有 N 个顶点和 E 条边的无向图，其邻接表有 N 个顶点节点和 2e 个边节点。显然， 在总的边数远小于 n（n-1）/2 的情况下，邻接表比邻接矩阵要节省空间；而邻接矩阵是唯一的；邻接表在建立时要比邻接矩阵麻烦的多；在邻接表的深度优先遍历时，对建立的概念模糊，在实验时浪费了很长时间；