数据结构中图的建立及算法实现.doc

南京工程学院通信工程学院实 验 报 告课程名称 数 据 结 构 实验项目名称 图的建立及遍历算法的实现 实验学生班级 实验学生姓名 实验时间 2014.5.29 实验地点 信 息 楼 C207 实验成绩评定 指导教师签字 年 月 日一、实验目的：1掌握图的定义及图的存储结构。2掌握图的遍历算法二、实验内容：1定义图的数据结构。2编写函数，用邻接表实现图的存储结构，求图的顶点的度数。3编写函数，输出图的遍历序列。三、实验要求：1数据结构定义正确，程序编码规范。2撰写实验报告，写出程序运行结果。3分析算法，写出本次实验总结。四、实现提示1数据结构定义#define MAX_VERTEX_NUM 100 /*最大顶点数为100*/int visitedMAX_VERTEX_NUM;typedef int VertexType;/*表结点*/typedef struct ArcNodeint adjvex; struct ArcNode * nextarc; ArcNode;/*头结点*/typedef struct VNode VertexType data; ArcNode * firstarc; VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum; ALGraph;2图的存储（邻接表存储）void CreateALGraph(ALGraph &G)int i,j,k;ArcNode *s;printf(input data:顶点数,边数：n);scanf(%d,%d,&G.vexnum,&G.arcnum); printf(nplease v data:);for(i=0;iG.vexnum;i+) scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL; for(k=0;kG.arcnum;k+) printf(please input arc );scanf(%d,%d,&i,&j); s=(ArcNode*)malloc(sizeof(ArcNode); s-adjvex=j; s-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=s;五关键算法流程图图的构造流程图开始开始输入vexnum，arcnumIncInfo选择图的类型构造图ii+1输入顶点ivexnumY深度遍历广度遍历jj+1N初始化邻接矩阵ivexnum结束YjvexnumNYii+1N主程序流程图karcnumkk+1输入弧的信息设置邻接矩阵YN结束六测试结果 1.主菜单页面2.输入显示3.遍历结果4.邻接矩阵七.分析与总结 通过一学期对数据结构的学习，我初步掌握了数据结构的设计流程，和处理一些基本问题的算法的设计，以及如何对算法进行初步评估分析。在此基础上我完成了此次课程设计。我所做的题目是图的建立及输出，我完成的是无向图和无向网的构造，深度优先搜索遍历，广度优先搜索遍历，和相应邻接矩阵的输出。在这课程设计是我认真复习了书中关于图的一章的内容，并在网上查找了一些资料，进一步学习，总结了他人经验，并请教了同学。确定基本算法，主程序的结构，然后具体实施