专业课程设计任务书.doc

++专业课程设计任务书
D
课 程 设 计
课程设计名称： 数据结构
专 业 班 级 ：
学 生 姓 名 ：
学 号 ：
指 导 教 师 ：
课程设计时间：
一、需求分析
对任意给定的图（顶点数和边数自定义），建立它的邻接表输出，然后利用栈的五种基本运算（清空堆栈，压栈，弹出，取栈顶元素，判空栈）实现图的深度搜索遍历和广度优先搜素遍历算法
二、概要设计
Main()
创建邻接表存储图
输出邻接表
对图进行深度优先遍历
对图进行广度优先遍历
邻接表是图的一种链式存储结构为，类似于树的孩子链表表法。在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。对于无向图，第i个单链表中的结点表示依赖于顶点v
i的边。对于有向图是以顶点vi为尾的弧，这个单链表称为顶点vi的单链表(即Vi的邻接表)。单链表中每一个结点称为表结点，应包括两个域:邻接点域，用以存放与vi相邻接的顶点序号；链域用以指向民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域，将该结点链到邻接表的表头的Ｔ第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 20//最大顶点数
typedef struct node{
int adjvex;//弧指向顶点的位置
struct node *next;//指向下一条弧的指针
}edgenode;//表结点
typedef struct {//头结点
char vertex;//顶点信息
edgenode *link;//指向第一条依附该顶点的弧的指针
}vexnode,AdjList[maxvertex