图结构的课程设计.doc

图结构的课程设计
全文16页4939字 叙述详尽
1前言
图(graph)是比线性表、树与二叉树更为复杂的一种数据结构。在图这种数据结构中，数据结点之间的联系是任意的，因此，图这种数据结构可以更广泛的表示数据之间的关系。可以说，线性表、二叉树是图的特例，也可以说，线性表、树与二叉树是最简单的图。
由于图的结构比较复杂，图中任意两个结点之间都有可能存在联系，无法用数据元素在存储空间中的物理位置来表示各数据元素之间的前后件关系。另外，图中各结点的度不相同，其最大度数与最小度数可能相差很大，用多重链表作为图的存储结构也是很不方便的。因此，在实际应用中，一般是根据对图的具体运算来选取合适的存储结构。
图有着极为广泛的应用。例如，用图可以表示有公共交通联系的一组城市，也可以描述化学结构式、交通网络等。
目 录
1前言 1
2 图的存储 1
3 图的遍历 1
3.1 图的深度优先遍历 1
3.2 图的广度优先遍历 2
4 算法描述 2
4.1 图的存储结构的建立 2
4.1.1 定义邻接表的边结点类型以及邻接表类型 2
4.1.2 初始化图的邻接表 3
4.1.3 建立并输出图的邻接表 3
4.2 图的遍历 4
4.2.1 深度优先遍历图的邻接表 4
4.2.2 广度优先遍历图的邻接表 5
5 程序流程图 5
6 图的遍历源程序 7
7 程序测试 13
8 总结与体会 14
参考文献 15
图(graph)是比线性表、树与二叉树更为复杂的一种数据结构。在图这种数据结构中，数据结点之间的联系是任意的，因此，图这种数据结构可以更广泛的表示数据之间的关系。可以说，线性表、二叉树是图的特例，也可以说，线性表、树与二叉树是最简单的图。
由于图的结构比较复杂，图中任意两个结点之间都有可能存在联系，无法用数据元素在存储空间中的物理位置来表示各数据元素之间的前后件关系。另外，图中各结点的度不相同，其最大度数与最小度数可能相差很大，用多重链表作为图的存储结构也是很不方便的。因此，在实际应用中，一般是根据对图的具体运算来选取合适的存储结构。
图有着极为广泛的应用。例如，用图可以表示有公共交通联系的一组城市，也可以描述化学结构式、交通网络等。
参考文献
[1] 徐士良.计算机软件技术基础[M].北京:清华大学出版社，2002
[2] 陈维钧.计算机软件基础[M].上海:上海交通大学出版社，1996
[3] 夏克俭.数据结构[M].北京:国防工业出版社，2007
[4] 李建学.数据结构课程设计案例精编[M].北京:清华大学出版社，2007
[5] 朱明方.机械工业出版社[M].北京:机械工业出版社,2007