数据结构图的建立与输出课程设计

《数据结构图的建立与输出课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机工程学院数据结构课程设计报告题目：图的建立与输出姓名：学号：专业班级：指导教师：设计时间：19目录1课题任务与计划………………………………………32设计方案及原理………………………………………32.1图有两种主要的存储结构………………………………32.2图的邻接表存储表示……………………………………42.3有向图的十字链表存储表示法……………………………52.4无向图的邻接多重表存储表示……………………………52.5邻接矩阵表示法………………………………………62.6邻接表表示法………………………………………

2、…93各功能的程序流程……………………………………103.1函数功能的实现………………………………………103.2变量的定义…………………………………………124主函数程序流程………………………………………125实验数据分析…………………………………………136附源代码………………………………………………167参考书目………………………………………………1919一课题任务与计划建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，

3、而后输出图的邻接矩阵。数据结构课程设计是学习数据结构课程的一个重要环节。能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。除了广义表和树以外，都可以有两类不同的存储结构，它们是由不同的映像方法（顺序映像和链式映像）得到的。由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元

4、素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映像结构，即以一数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针，如图所示，有向图G1和无向图G2的多重链表。但是，由于图中各个结点的度数不同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元；反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。因此，和树类似，在

5、实现应用中不宜采用这种结构，而应该根据具体的图的需要进行的操作，设计恰当的结点结构和表结构。常用的就有我们熟悉的邻接表、邻接多重表和十字链表。所以，我们打算采用邻接表的方法设计图的存储结构，包括图的建立与存储。二设计方案及工作原理1．图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组19A.edge[n][n]，　　用来存放顶点的信息和边或弧的信息。（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（2）在有向图中,统计第i行

6、1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。图的邻接表（AdjacencyList）存储表示法邻接表是图的一种链式存储结构，它对图中每个顶点建立一个单链表，第i个单链表中的结　点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧），每个结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点，数据　域（info）存储和边或弧相关的信息（如权值）。每个链表上附设一个表头结点,包含数

7、据域（data）和链域(firstarc)指向链表中的第一个结点，这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。　　在无向图的邻接表中，顶点vi的度等于第i个链表中的结点数；在有向图的邻接表中，顶点vi的出度等于第i个链表中的结点数，求入度必须遍历整个邻接表，为便于求vi的入度需建立有　向图的逆邻接表（是以顶点vi为头的弧所建立的邻接表）。2．图的邻接表存储表示：#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置

8、structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstru