计算机工程学院 数据结构课程 设计报告
题 目： 图的建立与输出 姓 名： 学 号： 专业班级： 指导教师： 设计时间：
目录
1 课题任务与计划………………………………………3 2 设计方案及原理………………………………………3
2.1 图有两种主要的存储结构
………………………………3
2.2 图的邻接表存储表示……………………………………4 2.3 有向图的十字链表存储表示法……………………………5 2.4无向图的邻接多重表存储表示……………………………5 2.5 邻接矩阵表示法 2.6 邻接表表示法
………………………………………6
…………………………………………9
3 各功能的程序流程……………………………………10
3.1函数功能的实现 3.2变量的定义
………………………………………10
…………………………………………12
4 主函数程序流程………………………………………12 5 实验数据分析…………………………………………13 6 附源代码………………………………………………16 7 参考书目………………………………………………19
2
一 课题任务与计划
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
数据结构课程设计是学习数据结构课程的一个重要环节。能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。
通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。
除了广义表和树以外，都可以有两类不同的存储结构，它们是由不同的映像方法（顺序映像和链式映像）得到的。由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映像结构，即以一数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针，如图所示，有向图G1和无向图G2的多重链表。但是，由于图中各个结点的度数不同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元；反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。因此，和树类似，在实现应用中不宜采用这种结构，而应该根据具体的图的需要进行的操作，设计恰当的结点结构和表结构。常用的就有我们熟悉的邻接表、邻接多重表和十字链表。所以，我们打算采用邻接表的方法设计图的存储结构，包括图的建立与存储。
二 设计方案及工作原理
1． 图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图 A
3
(完整word版)数据结构图的建立与输出课程设计
