图的遍历实现优秀课程设计数据结构程序图.doc

数据结构课程设计
设计说明书

图遍历实现

学生姓名
英 茜
学 号

班 级
网络1101班
成 绩

指导老师
申 静

数学和计算机科学学院
1 月 4日
课程设计任务书
—第一学期
课程设计名称：
数据结构课程设计
课程设计题目：
图遍历实现
完 成 期 限：
自 12 月23日至 1 月 4 日共 2 周
设计内容：
1. 任务说明
(1) 采取邻接表存放结构创建一个图；
(2) 编程实现图深度优先搜索（或广度优先搜索）遍历算法；
(3) 输出遍历结果；
(4) 给定具体数据调试程序。
2. 要求
1）问题分析和任务定义：依据设计题目标要求，充足地分析和了解问题，明确问题要求做什么？
2）逻辑设计：写出抽象数据类型定义，各个关键模块算法，并画出模块之间调用关系图；
3）具体设计：定义对应存放结构并写出各函数伪码算法。
4）程序编码：把具体设计结果深入求精为程序设计语言程序。
5）程序调试和测试：采取自底向上，分模块进行，即先调试低层函数。
6）结果分析：程序运行结果包含正确输入及其输出结果和含有错误输入及其输出结果。算法时间、空间复杂性分析；
7）编写课程设计汇报。
3. 参考资料
指导老师：申静 教研室责任人：余冬梅
课程设计评阅
评语：

指导老师署名：
年 月 日

摘 要
针对图问题中怎样愈加好地实现图遍历问题，以无向图为例，分别采取广度优先遍历和深度优先遍历算法实现对各节点遍历，以VC++为开发环境进行系统设计和实现，其运行结果表明，系统能很好地完成遍历后节点输出，实现了遍历目标，系统界面友好，可操作性强。
关键词：数据结构；存放结构；邻接矩阵

目 录

一 课题描述 1
二 设计目标和任务 2
2.1课程设计目标 2
2.2课程设计任务 2
三 设计方案和实施 3
3.1总体设计 3
3.2基础操作 3
3.3具体设计 4
四 运行调试结果 6
五 结论和致谢 9
六 附录 11

一 课题描述
数据结构是一门专业基础课，它对学习者要求很明确：学会分析、研究计算机加工数据结构特征，方便为应用设计所需数据选择合适逻辑结构、存放结构及其对应算法，并初步掌握算法时间分析和空间分析技术。其次，该课程学习过程也是复杂程序设计训练过程，要求学习者编写程序结构或设计程序结构体清楚、正确、易读，符合软件工程规范。
图是一个较为复杂且关键数据结构，其特殊性在于图形结构中结点之间关系能够是任意，图中任意两个数据元素之间全部有可能相关。就本课程设计而言应用图论知识讨论怎样在计算机上实现图遍历操作，关键处理图遍历多个方法实现。
本设计采取现在最通用程序设计语言之一—C语言作为数据结构和算法描述语言。

二 设计目标和任务
2.1课程设计目标
深入了解图遍历问题，图DFS,BFS递归和非递归算法实现， 用无向图来实现图遍历。
初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基础方法和技能。
训练学生灵活应用所学数据结构基础知识，熟练完成问题分析、算法设计、编写程序，求解出指定问题。
训练用系统见解和软件开发通常规范进行软件开发，巩固、深化学生理论知识，提升编程水平，并在此过程中培养严谨科学态度和良好工作作风。
提升综合利用所学理论知识和方法独立分析和处理问题能力。
2.2课程设计任务
1）任务说明
用C/C++编写一个程序实现图遍历算法。
从键盘上输入一个图基础信息（图用邻矩阵表示）。图DFS,BFS递归和非递归算法实现;用有向图实现图遍历；用无向图实现图遍历；用邻接矩阵存放图；用邻接表存放图。
2）要求
1>首先输入图结点数；
2>依次输入图各条边（数据之间用空格隔开）；
3>输出形式：按用户选择遍历方法给出遍历次序，各字符间用->分隔；
4>程序所能达成功效：能够按要求输出所要结果。

三 设计方案和实施
3.1总体设计
采取邻接矩阵作为图存放结构。程序中关键用到以下抽象数据类型：
抽象数据类型定义
typedef struct{
char *vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图目前顶点数和弧数
}Graph;
3.2基础操作
CreateUDN(Graph &G)
操作结果：用邻接矩阵创建带权无向网图。
DFS(Graph G,int k)
操作结果：对已存在图进行深度优先遍历。
BFS(Graph G)
操作结果：对已存在图进行广度优先遍历。
choose(Graph G)
操作结果：对将要实现操作步骤进行选择。
程序包含两个模块
主程序模块，其中主函数为
int main{
输入信息；
依据输入要求进行选择操作和输出；
输出结果；
}
选择操作模块—实现具体选择对应操作及输出操作。
两模块之间关系以下图3.1所表示

图3.1 模块关系图
3.3具体设计
程序步骤图图3.2所表示

图3.2 程序步骤图

函数设计程序设计中关键包含下列函数用邻接矩阵创建一个图：
void CreateUDN(Graph &G){

用邻接矩阵创建一个带权无向网图;
输入顶点数和弧数;
输入各个顶点及各条弧;
}
递归方法实现图遍历：
void DFS(Graph G, int k)
{
用递归方法访问图中结点;
对图进行深度优先遍历;
}
非递归方法实现图遍历：
void BFS(Graph G)
{
用队列辅助访问图中结点;
对图进行广度优先遍历;
}
选择输出需要遍历方法：
void choose(Graph G)
{
给出程序运行选项;
对对应输入选项调用对应函数以实施操作；
}

四 运行调试结果
例：遍历以下无向图（图 4.1）(a,b,c,d,e分别表示V1 V2 V3 V4 V5五个顶点)

以图4.1为例

步骤一：
运行程序，按提醒首先输入顶点数和弧数。

图4.2输入顶点数和弧数
步骤二：
输入顶点和弧
（1） 输入顶点

图4.3 输入各顶点
（2）输入弧

图4.3 输入各条弧
步骤三：
选择便利方法和选择后结果

选择1操作显示广度优先编历结果

图4.4 广度优先结果

选2操作显示深度优先遍历

图4.4深度优先遍历结果
五 结论和致谢
在程序设计中我关键是处理是给出一个图怎样用多个方法完成图遍历问题，也包含怎样创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归方法实现图遍历。程序最终经过调试运行，初步实现了设计目标。
图是一个较为复杂且关键数据结构，其特殊性在于图形结构中结点之间关系能够是任意，图中任意两个数据元素之间全部有可能相关。用邻接矩阵作为图数据存放结构很好地处理了图结构难点， 借助于邻接矩阵轻易判定任意两个顶点之间是否有边(或弧)相连，并轻易求得各个顶点度。该程序通俗易懂且实用性强，而且该程序清单具体具体、全方面、含有很强可读性；系统整体上比较完美，能够从键盘获取输入元素，而且能够依据用户输入进行选择性地输出；整体输出画面效果整齐、大方。
这次课程设计也让我充足认识到《数据结构》这门课关键性。它给我们一个思想和纲领，让我们在编程时轻易找到思绪，不至于无章可循。同时它也有广泛实际应用。
最终，我还要尤其感谢我们教导老师申静老师，在她精心教导和帮助下，我设计才得以顺利完成。对她为我们设计所提出宝贵意见表示忠心感谢！

参考文件
[1]谭浩强. C程序设计[第三版]. 北京:清华大学出版社.
[2]罗宇等. 数据结构[M ]. 北京邮电大学出版社.
[3]严藯敏. 数据结构[C语言版]. 北京:清华大学出版社.
[4]杨路明. C语言程序设计教程. 北京邮电大学出版社.
[5]徐孝凯. 数据结构课程试验. 清华大学出版社.

六 附录
源程序代码
// 程序功效：采取递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多个结构存放实现图遍历。
// 程序作者：英茜
// 最终修改日期：-1-3

#include"stdio.h"
#include"stdlib.h"
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
bool *visited; //访问标志数组
int z=1; //图邻接矩阵存放结构
typedef struct{
char *vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图目前顶点数和弧数
}Graph;
class Queue{ //队列类
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
int *base;
int front;
int rear;
};
int Locate(Graph G,char c){ //图G中查找元素c位置
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
void CreateUDN(Graph &G){ //创建无向网
int i,j,w,s1,s2;
char a,b,c,temp;
printf("输入顶点数和弧数(顶点数和弧数之间以空格隔开) : ");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化顶点
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("输入弧%d: ",i);
scanf("%c %c %d%c",&a,&b,&w,&c); //输入一条边依附顶点和权值
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
int FirstVex(Graph G,int k){ //图G中顶点k第一个邻接顶点
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//图G中顶点i第j个邻接顶点下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次实施DFS时,k为-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //对还未访问顶点调用DFS
}
else{
visited[k]=true;
if(z==1)
printf("%c",G.vexs[k]);
else printf(" -> %c",G.vexs[k]); ++z; //访问第k个顶点
if((z-1)%G.vexnum==0) z=1;
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k还未访问邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i还未访问
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k还未访问邻接顶点
visited[w]=true;
printf("-> %c ",G.vexs[w]);
Q.EnQueue(w);
}
}
} printf("\n 请继续选择:\n");
}
void choose(Graph G){ //对输入选项调用对应函数实施操作
int i,m;
visited=(bool *)malloc(G.vexnum*sizeof(bool));
scanf("%d",&m);
switch(m){
case 1:
printf("广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G); choose(G); printf("\n");break;
case 2:
printf("深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n 请继续选择:\n");choose(G);break;
case 3:printf("程序结束."); break;
default : printf(" 输入错误!\n请在1-3中选择:\n"); choose(G);
}
}
//主函数
void main(){
int i,m;
Graph G;
CreateUDN(G);
printf("有以下选项供选择：\n");
printf("\n");
printf("|*| 1:广度优先遍历 2:深度优先遍历 3:退出本程序！|*|\n");
printf("\n");
printf("请选择(1--3):\n");
choose(G);
}