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

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

1、z/〔据结构课程设计报告题目：图的建立与输出姓名：学号：专业班级：指导教师：设计时间目录1课题任务与计划32设计方案及原理32.1图有两种主要的存储结构32.2图的邻接表存储表示42.3有向阁的十字链表存储表示法52.4无向图的邻接多重表存储表示52.5邻接矩陈表示法62.6邻接表表示法93各功能的程序流程103.1函数功能的实现103.2变量的定义124主函数程序流程125实验数据分析136附源代码167参考书目19一课题任务与计划建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到

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

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

4、当的结点结构和表结构。常用的就有我们熟悉的邻接表、邻接多重表和十字链表。所以，我们打算采用邻接表的方法设计图的存储结构，包括图的建立与存储。二设计方案及工作原理1.图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图A=（V，E）是一个有n个顶点的图，图的邻接矩阵是一个二维数组A.edge[n][n],用來存放顶点的信息和边或弧的信息。（1）无向图的邻接矩阵是对称的;奋向图的邻接矩阵可能是不对称的。（2）在有向图中，统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。在无向图中，统计第i行（列）1的个数可得顶点i的度。图的邻接

5、表（AdjacencyList）存储表示法邻接表是图的-种链式存储结构，它对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点xd的边（对有向图是以顶点vi为尾的弧），每个结点由三个域组成：邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点，数据域（info）存储和边或弧相关的信息（如权值）。每个链表上附设一个表头结点，包含数据域（data）和链域（firstarc）指向链表中的第一个结点，这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。在无向图的邻接表中，顶点vi的度等于第

6、i个链表中的结点数；在有向图的邻接表中，顶点vi的出度等于第i个链表中的结点数，求入度必须遍历整个邻接表，为便于求vi的入度需建立有向图的逆邻接表（是以顶点vi为头的弧所建立的邻接表）。1.图的邻接表存储表示：#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNodenextarc;//指向下一条弧的指针InfoTypeinfo;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNo

7、defirstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;2.有向图的十字链表存储表示法十字链表(OrthogonalList)是有向图的另一种链式存储结构，可以看成是将右向图的邻接表和逆邻接表结合起来得到的一种链表。#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;

8、//该弧的尾和久•顶点的位置structArcBox