专业课程设计图的遍历.doc

专业课程设计图的遍历

目录
一、课题的主要功能 2
1.1设计内容 2
1.2对课程设计功能的需求分析 2
二、课题的功能模块的划分 2
2.1模块划分 2
2.2系统的概要设计 3
三、主要功能的实现 4
3.1算法思想 4
1.图的邻接矩阵的建立 4
2.图的遍历的实现 4
3.2数据结构 4
3.3主函数流程图 5
3.4深度优先遍历流程图 6
3.5深度优先遍历递归 7
3.6深度优先遍历流程图 9
3.7广度优先遍历递归流程图 10
四、程序调试 11
4.1程序的调试分析 11
4.2程序的测试结果 11
五、总结 16
六、附件 16
6.1源程序 16
一、课题的主要功能
1.1设计内容
演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。
1.2对课程设计功能的需求分析
图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下：
1.用户可以随时建立一个有向图或无向图；
2.用户可以根据自己的需要，对图进行深度遍历或广度遍历；
3.用户可以根据自己的需要对图进行修改；
4.在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号；
二、课题的功能模块的划分
2.1模块划分
1.队列的初始化、进队、出队、队列空、队列满的函数
void InitQueue(CirQueue *Q) //初始化队列
int QueueEmpty(CirQueue *Q)//队列是否为空
int QueueFull(CirQueue *Q)//队列满
Void EnQueue(CirQueue *Q,int x)//将队员进队
int DeQueue(CirQueue *Q)//将队员出队
2.创建图的函数
void CreateMGraph(MGraph *G)//根据用户需要创建一个图
3.图的深度优先遍历递归
void DFSM(MGraph *G,int i)/*含有输出已访问的顶点的语句*/
4.图的广度优先遍历递归
void BFSM(MGraph *G,int k) /*含有输出已访问的顶点的语句*/
5.深度优先遍历
void DFSTraverseM(MGraph *G)/*调用DFSM函数*/
6.广度优先遍历
void BFSTraverseM(MGraph *G) /*调用BFSM函数*/
7.主函数
main() /*包含一些调用和控制语句*/
2.2系统的概要设计
开 始
信息录入
菜单选择
深度优先
修改信息

广度优先
退出程序

三、主要功能的实现
3.1算法思想
本课题所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。
1.图的邻接矩阵的建立
对任意给定的图（顶点数和边数自定），根据邻接矩阵的存储结构建立图的邻接距阵。
2.图的遍历的实现
图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。
3.2数据结构
#define Max 10
#define FALSE 0
#define TRUE 1
#define Error printf
#define QueueSize 30

typedef struct
{
char vexs[Max];
int edges[Max][Max];
int n,e;
}MGraph;

int visited[Max];

typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;

3.3主函数流程图

输入ch2
登陆开始

CreateMGraph(G);
Ch1=’y’
Ch1=’y’

真

假
Ch2

B r e a k
Ch1=’n’
0
CreateMGraph(G)
1
DFSTraverseM(G) BFSTraverseM(G)BFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G)DFSTraverseM(G)
2
BFSTraverseM(G)
3
结束程序

3.4深度优先遍历流程图

DFSTraverseM(MGraph *G)

i=0

i<G->n

visited[i]=FALSE

i++

i=0

i<G->n

真
!visited[i]

i++
非零 零

DFSM(G,i)

结束程序

3.5深度优先遍历递归

DFSM(MGraph *G,int i)

输出G->vexs[i]

visited[i]=TRUE

j=0

j<G->n

真

G->edges[i][j]==1&&!visited[j]

DFSM(G,i)

J++

结束程序

3.6深度优先遍历流程图
BFSTraverseM(MGraph *G)

i=0

i<G->n

visited[i]=FALSE

i++

i=0

i<G->n

真
!visited[i]

i++
非零 零

BFS(G,i)

结束程序

3.7广度优先遍历递归流程图
i=DeQueue(&Q)
j=0
!QueueEmpty(&Q)
EnQueue(&Q,k)
visited[i]=TRUE
输出G->vexs[k]
InitQueue(&Q)
BFSM(MGraph *G,int k)

j<G->n

真
!visited[i]

DFSM(G,i)

i++

结束程序

四、程序调试
4.1程序的调试分析
在调试过程中，程序中出现了许多的错误，有错误的调用,一些变量没有定义等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：
1.在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函数名、变量没有被定义等问题；
2.在编写程序的过程中数组的大小写没有被确定；
3.在编写程序的过程中一些变量没有被定义，导致程序出错；
4.数组visited[Max]应定义为全局变量，若不是则会出错；
5.函数的返回类型要确定，是void还是其他类型要十分注意；
6.在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，
4.2程序的测试结果

初始进入程序时，程序提示按格式输入图的顶点个数和边数。

输入顶点数和边数后，程序提示输入顶点的序号，为各顶点依次进行编号。

将各顶点进行编号后，程序提示按格式输入边的顶点序号。

按格式依次输入边的顶点序号后，按enter键程序会出现“选择菜单”，用户根据需要进行选择。

用户选择2进入深度优先搜索，并输出深度优先遍历后的序列，再次输出菜单栏，进行选择。

用户再次选择3进入广度优先搜索，并输出广度优先遍历后的序列，再次输出菜单栏，进行选择。

用户选择1后进入更改数据，重新创建一个图。

用户选择0，则退出程序。

五、总结
通过这次数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：
1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好上学期所学的《数据结构》这门课，所以在实践之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉，这时才逐渐有了思路。所以今后一定要牢固掌握好专业基础知识。
2.必须培养严谨的态度。自己在编程时经常因为一些小错误而导致出现问题，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。
3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。
在实践过程中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，我会继续努力思考，完善程序，做到最好。
总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，这次课程设计为我以后更好的学习和使用c语言打下了基础。
六、附件
6.1源程序
#include<stdio.h>
#include<stdlib.h>
#define Max 10
#define FALSE 0
#define TRUE 1
#define Error printf
#define QueueSize 30

typedef struct
{
char vexs[Max];
int edges[Max][Max];
int n,e;
}MGraph;/*以邻接矩阵作为图的存储结构*/

int visited[Max];/*将visited[Max]定义为全局变量并分配最大空间*/

typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;/*定义队列的数据结构*/

//初始化队列
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0;
}

//队列空
int QueueEmpty(CirQueue *Q)
{
return Q->count=QueueSize;/*返回队列的最大长度*/
}

//队列满
int QueueFull(CirQueue *Q)
{
return Q->count==QueueSize;/*返回队列的最大长度*/
}

//进队
void EnQueue(CirQueue *Q,int x)
{
if(QueueFull(Q))/*队列满则出错*/
{
Error("Queue overflow");
}
else
{
Q->count++;/*否则count++，将x进队*/
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
}

//出队
int DeQueue(CirQueue *Q)
{
int temp;/*定义整型的变量*/
if(QueueEmpty(Q))/*若为真则出错*/
{
Error("Queue underflow");
}
else/*为假则count--，将队员出队*/
{
temp=Q->data[Q->front];/*用temp返回其值*/
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;/*返回出队元素值*/
}
}

//建立一个图
void CreateMGraph(MGraph *G)
{
int i,j,k;/*定义整型变量*/
char ch1,ch2;/*定义字符型变量*/
printf("\n请输入顶点数，边数（格式：3，4）:");
scanf("%d,%d",&(G->n),&(G->e));/*输入图的顶点数和边数*/
for(i=0;i<G->n;i++)
{
getchar();
printf("\n请输入第%d个顶点序号",i+1);
scanf("%c",&(G->vexs[i]));/*输入顶点的序号*/
}
for(i=0;i<G->n;i++)
{
for(j=0;j<G->n;j++)
{
G->edges[i][j]=0;/*初始化矩阵*/
}
}
for(k=0;k<G->e;k++)
{
getchar();
printf("\n请输入第%d条边的顶点序号（格式：i，j）:",k+1);
scanf("%c,%c",&ch1,&ch2);/*输入边的顶点序号*/
for(i=0;ch1!=G->vexs[i];i++);
for(j=0;ch2!=G->vexs[j];j++);
G->edges[i][j]=1;/*有边则赋值为1*/
}
}

//深度优先遍历递归
void DFSM(MGraph *G,int i)
{
int j;
printf("%c ",G->vexs[i]);
visited[i]=TRUE;/*标记visited[i]*/
/*依次优先搜索访问visited[i]的每个邻接点*/
for(j=0;j<G->n;j++)
/*若visited[i]的一个有效邻接点visited[j]未被访问过，则从visited[j]出发进行递归调用*/
if(G->edges[i][j]==1&&!visited[j])
DFSM(G,j);
}

//广度优先遍历递归
void BFSM(MGraph *G,int k)
{
int i,j;
CirQueue Q;/*定义一个队列Q，初始化队列为空*/
InitQueue(&Q);
printf("%c ",G->vexs[k]);/*访问初始点，并将其标记已访问过*/
visited[k]=TRUE;
EnQueue(&Q,k);/*将以访问过的初始点序号k入队*/
while(!QueueEmpty(&Q))/*队列非空进行循环处理*/
{
i=DeQueue(&Q);/*将队首元素出队*/
for(j=0;j<G->n;j++)/*依次搜索vexs[k]的每一个可能的邻接点*/
{
if(G->edges[i][j]==1 &&! visited[j])
{
visited[j]=TRUE;/*标记vexs[j]已访问过*/
EnQueue(&Q,j);/*顶点序号j入队*/
}
}
}
}

//深度优先遍历
void DFSTraverseM(MGraph *G)
{
int i;
printf("\n 深度优先遍历序列:");
for(i=0;i<G->n;i++)
{
visited[i]=FALSE;/*访问标志数组初始化*/
}
for(i=0;i<G->n;i++)
{
if(!visited[i])/*对尚未访问的顶点调用DFSM*/
{
DFSM(G,i);
}
}
}

//广度优先遍历
void BFSTraverseM(MGraph *G)
{
int i;

printf("\n 广度优先遍历序列:");
for(i=0;i<G->n;i++)
{
visited[i]=FALSE;/*访问标志数组初始化*/
}
for(i=0;i<G->n;i++)
{
if(!visited[i])/*对尚未访问的顶点调用BFSM*/
{
BFSM(G,i);
}
}
}

main()
{
MGraph *G,a;
char ch1;
int i,j,ch2;
G=&a;
printf("\n\t\t 深度优先搜索和广度优先搜索 \n");
CreateMGraph(G);/*调用创建图矩阵的函数*/

getchar();
ch1='y';/*设置控制语句标志*/
while(ch1=='y'||ch1=='Y')
{ /*菜单栏*/
printf("\n");
printf(" 选择菜单");
printf("\n\t\t******************************************\n");
printf("\t\t* 更改数据请按:1 *\n");
printf("\t\t* 深度优先搜索请按:2 *\n");
printf("\t\t* 广度优先搜索请按:3 *\n");
printf("\t\t* 退出搜索请按:0 *\n");
printf("\t\t******************************************\n");
printf("\n\t\t请选择菜单号（0-3）：");
scanf("%d",&ch2);
getchar();
switch(ch2)
{
case 1:
CreateMGraph(G);/*选1创建一个新的图矩阵*/
break;
case 2:
DFSTraverseM(G);/*选2进入深度优先搜索*/
break;
case 3:
BFSTraverseM(G);/*选3进入广度优先搜索*/
break;
case 0:/*选0结束搜索，退出程序*/
ch1='n';
break;
default:
system("cls");
printf("\n\t\t输入有误！\n");
break;
}
if(ch2==1||ch2==2||ch2==3)
printf("\n\n\t\t ");/*控制格式*/
}
}

计算机与通信学院课程设计评分表

课程名称：

项 目
评 价
设计方案的合理性与创造性

设计与调试结果

设计说明书的质量

答辩陈述与回答问题情况

课程设计周表现情况

综合成绩

教师签名：
日 期：

（注：1．此页附在课程设计报告之后；2．综合成绩按优、良、中、及格和不及格五级评定。）

27