数据结构课程设计-图的遍历和生成树求解问题的研究与实现.doc

数据结构课程设计
设计说明书
图的遍历和生成树求解问题的研究与实现
学生姓名
学号
班级
信管061
成绩
指导教师
计算机科学与技术系
2008年3月8日
数据结构课程设计评阅书
题目
图的遍历和生成树求解问题的研究与实现
学生姓名
秦洁
学号
0621024014
指导教师评语及成绩
指导教师签名:
年月日
答辩评语及成绩
答辩教师签名:
年月日
教研室意见
总成绩:
室主任签名:
年月日
课程设计任务书
2007—2008学年第一学期
专业: 信息管理与信息系统学号: 0621024014
姓名: 秦洁
课程设计名称: 数据结构课程设计
设计题目: 图的遍历和生成树求解问题的研究与实现
完成期限:自 2008 年 2 月 25 日至 2008 年 3 月 7 日共 2 周
设计依据、要求及主要内容(可另加附页):
设计依据:数据结构算法设计
要求:先任意创建一个图;
图的DFS,BFS的递归和非递归算法的实现最小生成树(两个算法)的实现,求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。
主要内容:对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储,并完成图的DFS和BFS操作。
指导教师(签字): 教研室主任(签字):
批准日期: 年月日
摘要
图是一种较线形表和树更为复杂的数据结构。在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法,邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。
关键词: 图;存储;遍历;深度;广度

目录
1 课题描述……………………………………………………………………………1
2 设计过程……………………………………………………………………………2
设计思路……………………………………………………………………2
设计流程图…………………………………………………………………3
程序源代码…………………………………………………………………4
3 编译运行………………………………………………………………………… 17
总结………………………………………………………………………………… 19
参考文献…………………………………………………………………………… 20
1 课题描述
图是一种较线形表和树更为复杂的数据结构。在线形表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子节点)相关,但只能和上一层中一个元素(即其双亲节点)相关;而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。因此,图的应用极为广泛,特别是近年来的迅速发展,已深入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。
开发工具:Visual C++
2设计过程
本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。
设计思路
这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识,结合起来才完成了这个程序。
因为图是一种较线形表和树更为复杂的数据结构。在线形表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继,并且在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。因此,本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法,邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。
设计流程图
开始
创建图G
用邻接表存储图
If y=’y’
N
Y
显示图的邻接矩阵
KRUSCAL算法
显示图的邻接表
深度优先遍历
广度优先遍历
最小生成树PRIM
输入字母
If y=’y’
结束
N
Y
图的连通分量
输入一个数
2
0
1
3
4
5
6
程序源代码
#include <iostream>
#include <>
using namespace std;
#define int_max 10