《数据结构 实验五.doc》由会员分享，可在线阅读，更多相关《数据结构 实验五.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验报告课程名称： 数据结构 实验项目： 图的有关操作 专业班级： 计算机科学与技术1303班 姓 名： 宁相如 学 号： 实验室号： 信息220 实验组号： 24 实验时间： 2015.5.25 批阅时间： 指导教师： 王宏生 成 绩： 沈阳工业大学实验报告（适用计算机程序设计类）专业班级： 计算机1303班 学号： 姓名： 宁相如 实验名称：图的有关操作1.实验目的（1）掌握图的存储思想及其存储实现；（2）掌握图的深度、广度优先遍历算法思想及其程序实现；（3）熟悉求图的最小生成树的普利姆算法。2.实验内容（1）键盘输入数据，建立一个无向图的邻接表。（2）采用邻接表存储实现无向图的深度优先非
2、递归遍历。（3）采用邻接表存储实现无向图的广度优先遍历。（4）采用邻接矩阵存储一个无向图。（5）采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。（6）编写一个主函数,调试上述算法。3.实验方案（程序设计说明）（1）类型定义（邻接表存储）#define MAX_VERTEX_NUM 8 /顶点最大个数typedef struct ArcNodeint adjvex; struct ArcNode *nextarc; int weight; /边的权ArcNode; /表结点 #define VertexType int /顶点元素类型typedef struct VNodeint degr
3、ee,indegree;/顶点的度，入度 VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/顶点的实际数，边的实际数 ALGraph; （2）上述类型定义可以根据实际情况适当调整。4.实验程序（见附件A） 附件A 沈阳工业大学实验报告（适用计算机程序设计类）专业班级： 计算机1303班 学号： 姓名： 宁相如 实验程序：#include#define MAX_VERTEX_NUM 10 /顶点最大个数 typed
4、ef struct ArcNode /定义边表结点int adjvex; /邻接点域 struct ArcNode *nextarc; int weight; /边的权ArcNode; /表结点 typedef struct VNode /定义顶点表结点int degree,indegree; /顶点的度，入度int data; ArcNode *firstarc;VNode/*头结点*/,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/顶点的实际数，边的实际数ALGraph;/建立图的邻接表vo
5、id creat_link(ALGraph *G)int i,j;ArcNode *s;coutG-vexnumG-arcnum;for (i=0;ivexnum;i+)G-verticesi.data=A+i;G-verticesi.firstarc=NULL;coutInput the adjvexs of arcsn;for (i=0;iarcnum;i+)cinij;s=new ArcNode;s-adjvex=j;s-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=s;/*输出邻接表 */void visit(ALGraph G)i
6、nt i;ArcNode *p;coutNO data adjvexs of arcsn;for (i=0;iiG.verticesi.data;for(p=G.verticesi.firstarc;p;p=p-nextarc)coutadjvex;coutendl;void cacu(ALGraph *G)ArcNode *p;int i;for (i=0;ivexnum;i+)G-verticesi.degree=0;G-verticesi.indegree=0;for (i=0;ivexnum;i+) for(p=G-verticesi.firstarc;p;p=p-nextarc)G-verticesi.degree+;G-verticesp-adjvex.degree+;G-verticesp-adjvex.indegree+;void print_degree(ALGraph G)int i;for (i=0;iG.vexnum;i+)coutiG.verticesi.dataG.verticesi.degreeG.verticesi.indegree;int main()ALGraph g;creat_link(&g);visit(g);cacu(&g);print_degree(g);return 0;