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

目 录
1 课题任务与计划………………………………………2
2 设计方案及原理………………………………………3
2.1 图有两种主要的存储结构 ………………………………3
2.2 图的邻接表存储表示……………………………………4
2.3 有向图的十字链表存储表示法……………………………4
2.4无向图的邻接多重表存储表示……………………………4
2.5 邻接矩阵表示法 ………………………………………5
2.6 邻接表表示法 …………………………………………7
3 各功能的程序流程……………………………………8
3.1函数功能的实现 ………………………………………8
3.2变量的定义 …………………………………………9
4 主函数程序流程………………………………………9
5 实验数据分析…………………………………………10
6 附源代码………………………………………………13
7 参考书目………………………………………………17
一 课题任务与计划
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
设计方案及工作原理
1． 图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edge[n][n]，　　用来存放顶点的信息和边或弧的信息。
（1） 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
（2） 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点j 的入度。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i的度。
图的邻接表（Adjacency List）存储表示法
邻接表是图的一种链式存储结构，它对图中每个顶点建立一个单链表，第i个单链表中的结　点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧），每个结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点，数据　域（info）存储和边或弧相关的信息（如权值）。每个链表上附设一个表头结点,包含数据域（data）和链域(firstarc)指向链表中的第一个结点，这些表头结点通常以顺序结构的形式存储，
以便随机访问任一顶点的链表。
　　在无向图的邻接表中，顶点vi的度等于第i个链表中的结点数；在有向图的邻接表中，顶点vi的出度等于第i个链表中的结点数，求入度必须遍历整个邻接表，为便于求vi的入度需建立有　向图的逆邻接表（是以顶点vi为头的弧所建立的邻接表）。