文档介绍：计算机科学与技术专业课程设计任务书
学生姓名
专业班级
学号
题目
图的遍历
课题性质
其他
课题来源
自拟课题
指导教师
同组姓名
主要内容
建立图的存储结构输出两种遍历
任务要求
对任意给定的图(顶点数和边数自定义),建立它的邻接表输出,然后利用栈的五种基本运算(清空堆栈,压栈,弹出,取栈顶元素,判空栈)实现图的深度搜索遍历和广度优先搜素遍历算法
参考文献
[1] 谭浩强,《C程序设计(第二版)》,北京,清华大学出版社,2005年1月
[2] 严蔚敏,吴伟民,《数据结构(C语言版)》,北京,清华大学出版社,2005年10月
[3] 许卓群,杨冬青等,《数据结构与算法》,高等教育出版社,2004
[4] 朱战立, 《数据结构》,西安电子科技大学出版社,2003
审查意见
指导教师签字:
教研室主任签字: 年月日
说明:本表由指导教师填写,由教研室主任审核后下达给选题学生,装订在设计(论文)首页
课程设计
课程设计名称: 数据结构
专业班级:
学生姓名:
学号:
指导教师:
课程设计时间:
一、需求分析
对任意给定的图(顶点数和边数自定义),建立它的邻接表输出,然后利用栈的五种基本运算(清空堆栈,压栈,弹出,取栈顶元素,判空栈)实现图的深度搜索遍历和广度优先搜素遍历算法
二、概要设计
Main()
创建邻接表存储图
输出邻接表
对图进行深度优先遍历
对图进行广度优先遍历
邻接表是图的一种链式存储结构为,类似于树的孩子链表表法。在邻接表中,对图中每个顶点建立一个单链表,n个顶点,就要建n个链表。对于无向图,第i个单链表中的结点表示依赖于顶点vi的边。对于有向图是以顶点vi为尾的弧,这个单链表称为顶点vi的单链表(即Vi的邻接表)。单链表中每一个结点称为表结点,应包括两个域:邻接点域,用以存放与v
i相邻接的顶点序号;链域用以指向民vi邻接的下一个结点。另外,每一个单链表设一个表头结点。每一个表头结点有两个域,一个用来存放顶点vi的信息;另一个域用来指向vi的邻接表中的第一个结点。为了便于管理和随机访问任一顶点的单链表,将所有单链表的头结点组织成一个一维数组。
vertex
link
adjvex
next
顶点
链头
顶点地址
链针
邻接表的表头和表结点形式
typedef struct node{
int adjvex;//弧指向顶点的位置
struct node *next;//指向下一条弧的指针
}edgenode;//表结点
typedef struct {//头结点
char vertex;//顶点信息
edgenode *link;//指向第一条依附该顶点的弧的指针
}vexnode,AdjList[maxvertexnum];
建立邻接表的方法是:首先将邻接表表头数组初始化,第i个表头的vertex初始化为i,;link初始化为NULL。然后读入顶点对<>,产生一个表结点,将j放入到该结点的adjvex域,将该结点链到邻接表的表头的T第i个表头的link域上。
深度优先遍历算法
,同时置起始顶点已访问的标记
a取当前栈顶顶点
b若栈顶顶点存在未被访问的邻接结点,则选择一个顶点进行一下步骤:
输出该顶点
置该顶点已访问标记
将该顶点进栈
c否测当前顶点退栈
存储结构
typedef struct{//栈
int *data;//栈底指针
int *top;//栈顶指针
}seqstack;
广度优先遍历算法
,并将该顶点入队
a取对头顶点
b依次访问与顶点相邻的未被访问的顶点
访问该顶点
置该顶点为已被访问的标记,并将它入队
c当前对头元素顶点出队
d重复进行直到对空时结束
三、运行环境(软、硬件环境)
++
四、开发工具和编程语言
开发工具和编程语言:(数据结构)C语言
数据结构(c语言)
五、详细设计
#include<>
#include<>
#include <>
#define False 0
#define True 1
#define Null 0
#define maxsize 20//队列的最大空间
#define maxvertexnum 2