1、 数据结构课程设计数据结构课程设计 题目：图的建立与输出图的建立与输出 院 系： 电子与信息工程学院 学生姓名： 学 号： 专 业： 电子信息工程 班 级： 09 级（1）班 指导教师： 职称 教授 完成时间： 2011-6-23 - 2 - 目目 录录 一 课程设计目的3 二 课程设计内容3 三 算法和思想3 四 源代码4 五 课程设计心得6 六 参考文献7 - 3 - 图的建立与输出图的建立与输出 摘要摘要：运用数组类型来表示元素之间的关系，还采用多重链表示图，运用邻 接矩阵来输出图。 关键字：关键字：邻接矩阵，多重链表，时间复杂度，数据域，指针域，邻接表。 一一、程序设计目的程序设计目的
2、 巩固和加深课堂教学内容，提高学生实际工作能力，使学生熟练掌握数据结 构课程中所学的理论知识， 通过综合运用数据结构的基本知识来解决实际问题加 强学生分析和解决问题的能力。 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学 生可以任选两种类型） ，能够输入图的顶点和边的信息，并存储到相应存储结构 中，而后输出图的邻接矩阵。 二二、课程设计内容课程设计内容 建立图的存储结构，并能输出图的顶点和边的信息，并存储到相应的存储结 构中，同时并能输出图的邻接矩阵， （图可以是有向图，无向图，有向网，无向 网， ） 图的建立比较复杂，任意两个顶点之间都有可能存在联系，因此无法以数据元 素
3、在存储区中的物理位置来表示元素之间的关系， 因此图没有顺序影像的存储结 构，但可以借助数组的数据类型来表示元素之间的关系。 三三、 算法和思想算法和思想 首先是图的存储结构，用多重链表表示图是自然的事，它是一种最简单的链 式影像结构，以一个由一个数据域和多个指针域组成的结点表示图的一个顶点， 其中数据域存储该结点的信息，指针域存储指向其临界点的指针。 数组表示法，用两个数组分别别存储顶点的信息和数据元素之间的关系的信 息。邻接表，在邻接表中对图中的每一个顶点建立一个单链表，第 I 个单链表中 的结点表示依附于顶点 VI 的边。每个结点由三个域组成，其中邻接点域指示与顶点 VI 邻接的点在图中
4、的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息。每个 链表上依附一个表结点。在表头结点中除了设有链域指针链表中第一个结点之 外，还设有存储顶点 VI 的名或其他信息的数据域。 图的遍历，图中任一都有可能和其余顶点相邻接，所以在访问了某个定点之 后，可能沿着某条路径搜索之后，又回到该顶点上。深度优先搜索，假设初始状 态是图中所有顶点未曾被访问，则深度优先搜索可以从图中某个顶点 V 出发，访 问此顶点，然后依次从 V 的未被访问的邻接点出发深度优先遍历图，直到图中所 有和 V 有路径相通的顶点都被访问到，若此时图中还有顶点未被访问，则另选图 中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问 - 4 -
