图的存储结构算法.doc

信息工程学院计算机系 《数据结构与算法》实验报告 姓名 学号 实验成绩 班级 实验日期 项目号、实验名称 5、图的存储结构算法 实 验 要 求 （任课 教 师 提 供） 该实验要求掌握邻接矩阵、邻接表等存储结构的相关算法； 2、验证性实验要求在实验前认真研读相关教材，作好充分的预习准备工作，写出实验预习报告； 3、学生必须在规定时间内独立完成，对实验过程中出现的问题，要求尽量做到独立思考，独立解决； 4、每次实验的结果必须经过教师认可后，实验方可结束； 5、要求学生必须认真对待每一个实验，不得缺席、迟到、早退； 6、要求实验中认真做好实验记录，实验后认真完成实验报告； 实 验 内 容 （由学 生 填 写） 1. 图的存储结构算法代码： #includestdio.h #includestdlib.h #define Max 20 typedef struct ArcNode { int adjvex; // 弧的邻接顶点 char info; struct ArcNode *nextarc; }ArcNode; typedef struct Vnode { char data; ArcNode *link; }Vnode,AdjList[Max+1]; typedef struct { AdjList vertices; int vexnum; //顶点数 int arcnum; //边数 }ALGraph; typedef struct { int n; char vexs[Max+1]; int arcs[Max+1][Max+1]; }AdjMatrix; void AdjListToAdjMatrix(AdjList gl,AdjMatrix gm,int n) { int i,j; ArcNode *p; for(i=1;i=Max;i++) { for(j=1;j=Max;j++) gm.arcs[i][j]=0; } for(i=1;i=n;i++) { p=gl[i].link; while(p!=NULL) { gm.arcs[i][p-adjvex]=1; p=p-nextarc; } } } void outputGraph(ALGraph G) { int i; ArcNode *p; printf(图的邻接表如下:\n); for(i=1;i=G.vexnum;i++) { printf([%c],G.vertices[i].data); p=G.vertices[i].link; while(p!=NULL) { printf(---(%d %c),p-adjvex,p-info); p=p-nextarc; } printf(\n); } } void outputAdjMatrix(AdjMatrix gm,int n) { int i,j; printf(邻接矩阵如下:\n); for(i=1;i=n;i++) { for(j=1;j=n;j++) { printf(%d ,gm.arcs[i][j]); } printf(\n); } } void CreatGraph(ALGraph G) { int i,s,d; ArcNode *p; for(i=1;i=G.vexnum;i++) { getchar(); printf(第%d个节点的信息:,i); scanf(%c,G.vertices[i].data); G.vertices[i].link=NULL; } for(i=1;i=G.arcnum;i++) { printf(第%d条边———起点序号,终点序号:,i); scanf(%d %d,s,d); p=(ArcNode *)malloc(sizeof(ArcNode)); p-adjvex=d; p-info=G.vertices[d].data; p-nextarc=G.vertices[s].link; G.vertices[s].link=p; } } int main() { ALGraph G; AdjMatrix gm; printf(输入节点数和边:); scanf(%d %d,G.vexnum,G.arcnum); CreatGraph(G); AdjListToAdjMatrix(G.vertices,gm,G.vexnum); outputGraph(G); outputAdjMatrix(gm,G.