河南工业大学实验报告实验二非线性结构（二）图.doc

PAGE 1 河南工业大学实验报告 课程名称 数据结构 实验项目 实验二 非线性结构(二)——图 院 系 信息学院计科系 专业班级 计科1401 姓 名 赵振 学 号 201416010121 指导老师 范艳峰 日 期 2013.5.17 批改日期 成 绩 一 实验目的 ? 1．掌握图的邻接矩阵和邻接链表存储结构。 ? 2．掌握图的建立、遍历、最小生成树等典型操作。 二 实验内容及要求 实验内容：（自选一题） 1．建立图的邻接矩阵或邻接链表存储结构，并在对应存储结构上实现图的递归遍历操作。 2．在邻接矩阵存储结构上，完成最小生成树的操作。 实验要求： 1. 根据所选题目，用C语言编写程序源代码。 2. 源程序须编译调试成功，独立完成。 三 实验过程及运行结果 本次试验是采用邻接表的方法建立图，然后进行深度优先遍历 具体实现结如下： //算法功能：采用邻接表存储结构建立无向图 #include stdio.h #include stdlib.h #define OK 1 #define NULL 0 #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef int Status; //函数的类型，其值是函数结果状态代码 typedef char VertexType; typedef int VRType; typedef int InforType; typedef struct ArcNode { int adjvex; //该边所指的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 int weight; //边的权 }ArcNode; //表的结点 typedef struct VNode { VertexType data; //顶点信息（如数据等） ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针 }VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct ALGraph { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //返回顶点v在顶点向量中的位置 int LocateVex(ALGraph G, char v) { int i; for(i = 0; v != G.vertices[i].data i G.vexnum; i++) ; if(i = G.vexnum) return -1; return i; } //构造邻接链表 Status CreateUDN(ALGraph G) { int j; 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.vertices[i].data); //构造顶点向量 G.vertices[i].firstarc = NULL; getchar(); } char v1, v2; for(int k = 0; k