数据结构与算法实验

1、任课教师： 数据结构与算法（2011-2012学年第2学期）实验报告学号：姓名： 班级： 实验3 图的邻接表表示一、实验目的和要求 在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。二、实验内容 完成下图的邻接表表示，并计算每个顶点的度。三、实验提示类型定义（邻接表存储） #define MAX_VERTEX_NUM 8 /顶点最大个数 typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int weight; /边的权ArcNode

2、; /表结点 #define VertexType char /顶点元素类型typedef struct VNodeint degree;/顶点的度，入度 VertexType data;ArcNode *firstarc;VNode/*头结点*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices;int vexnum,arcnum;/顶点的实际数，边的实际数ALGraph;2实验步骤1）输入图中顶点信息，完成邻接表的VNode内容的初始化。2）根据图中边的信息，把各边的信息链到firstarc指针链上，同时统计degree3）输出邻

3、接表。 四、程序源码：#include using namespace std;#include #include #define OK 1#define NULL 0#define MAX_VERTEX_NUM 20 / 最大顶点数typedef char VertexType;typedef int VRType;typedef int InforType;typedef struct ArcNode int adjvex; /该边所指的顶点的位置 struct ArcNode *nextarc; /指向下一条边的指针 int weight; /边的权ArcNode; /表的结点typed

4、ef struct VNode VertexType data; /顶点信息（如数据等） ArcNode *firstarc; /指向第一条依附该顶点的边的弧指针VNode, AdjListMAX_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.verticesi.data & i = G.vexnum)

5、return -1; return i;/增加节点void add_vex(ALGraph &G) cout输入无向图顶点数: G.vexnum; /getchar(); /吃回车 cout输入顶点信息:endl; for(int i = 0; i G.verticesi.data; /构造顶点向量 G.verticesi.firstarc = NULL; /getchar(); /增加边void add_arc(ALGraph &G) ArcNode *s, *t; cout输入无向图边数: G.arcnum; char v1, v2; cout输入边信息:endl; for(int k =

6、 0; k v1v2; int i = LocateVex(G, v1); int j = LocateVex(G, v2); /确定v1 , v2在G中的位置 s = (ArcNode*) malloc (sizeof(ArcNode); t = (ArcNode*) malloc (sizeof(ArcNode); s-adjvex = j; /该边所指向的顶点的位置为j s-nextarc = G.verticesi.firstarc; G.verticesi.firstarc =s; t-adjvex = i; /该边所指向的顶点的位置为j t-nextarc = G.verticesj.firstarc; G.verticesj.firstarc =t; /构造邻接链表void CreateUDN(ALGraph &G) add_vex(G); /增加节点 add_arc(G); /增加边 void PrintAdjList(ALGraph &G) int i; ArcNode *p; cout编号 顶点 邻点编号endl; for(i = 0; i G.vexnum; i+) cout i G.verticesi.datanextarc)