数据结构课程设计报告《图的遍历》

数据结构

课程设计报告

班级：

姓名：

学号：

目录

一， 设计任务----------------------------------------3

二、 设计时间----------------------------------------3

三、 设计内容----------------------------------------3

1、需要分析----------------------------------------3

2、概要设计----------------------------------------3

3、详细设计----------------------------------------4

4、测试与分析--------------------------------------9

四、设计总结-----------------------------------------10

源程序清单--------------------------------------11

一．设计任务：

我选课程设计是自选题目《图的遍历》。

要求：设计一个程序，实现图的广度，深度优先遍历。

二、设计时间

2009年12月28日

三、设计内容

1、需求分析

本题目需要解决的问题是将一幅已知图，对图进行遍历，并完成：

（1） 输出它的邻接矩阵；

（2） 根据人工选择进行深度优先搜索（Depth_First Search）和广度

优先搜索（Breadth_First Search），将搜索结果放入一队列中；

（3） 将队列中的搜索结果输出。

2、 概要设计：

(1)抽象数据的类型定义

数据对象：V是图具有相同特性的数据元素的集合，称为定顶点集 数据关系：R

R={VR}

VR={<v,w>/v,w∈v且p(v,w)}

基本操作：CreateGraph(&G,V,VR)

初始条件：V是图的顶点集，VR是图中弧的集合

操作结果：按V和VR的定义构造图G

基本操作：DFSTraverse(G,Visit())

BFSTraverse(G,Visit())

（2）主程序的流程以及各程序模块之间的调用关系：

3、详细设计：

（1）定义图

typedef struct{

int V[M];

int R[M][M];

int vexnum;

}Graph;

（2）创建图

void creatgraph(Graph *g,int n)

{

int i,j,r1,r2;

g->vexnum=n;

/*顶点用i表示*/

for(i=1;i<=n;i++)

{

g->V[i]=i;

}

/*初始化R*/

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

g->R[i][j]=0;

}

/*输入R*/

printf("Please input R(0,0 END):\n");

scanf("%d,%d",&r1,&r2);

while(r1!=0&&r2!=0)

{

g->R[r1][r2]=1;

g->R[r2][r1]=1;

scanf("%d,%d",&r1,&r2);

}

}

（3）全局变量：访问标志数组

void printgraph(Graph *g)

{

int i,j;

for(i=1;i<=g->vexnum;i++)

{ for(j=1;j<=g->vexnum;j++)

{

printf("%2d ",g->R[i][j]);

}

printf("\n");

}

}

（4） 访问顶点

int visited[M];

void visitvex(Graph *g,int vex)

{

printf("%d ",g->V[vex]);

}

（5）获取第一个未被访问的邻接节点

int firstadjvex(Graph *g,int vex)

{

int w,i;

for(i=1;i<=g->vexnum;i++)

{

if(g->R[vex][i]==1&&visited[i]==0)

{

w=i;

break;

}

else

{

w=0;

}

}

return w;

}

/*获取下一个未被访问的邻接节点(深度遍历)*/

int nextadjvex(Graph *g,int vex,int w)

{

int t;

t=firstadjvex(g,w);

return t;

}

（6）深度递归遍历

void dfs(Graph *g,int vex)

{

int w;

visited[vex]=1;

visitvex(g,vex);

for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))

if(!visited[w])

{

dfs(g,w);

}

}

void dfstraverse(Graph *g)

{

int i;

for(i=1;i<=g->vexnum;i++)

visited[i]=0;

for(i=1;i<=g->vexnum;i++)

if(!visited[i])

{dfs(g,i);}

}

（7）定义队列

typedef struct{

int V[M];

int front;

int rear;

}Queue;

（8）初始化队列

initqueue(Queue *q)

{

q->front=0;

q->rear=0;

}

（9）判断队列是否为空

int quempty(Queue *q)

{

if(q->front==q->rear)

{

return 0;

}

else

{

return 1;

}

}

（10）入队操作

enqueue(Queue *q,int e)

{

if((q->rear+1)%M==q->front)

{

printf("The queue is overflow!\n");

return 0;

}

else

{

q->V[q->rear]=e;

q->rear=(q->rear+1)%M;

return 1;

}

}

（11）出队操作

dequeue(Queue *q)

{

int t;

if(q->front==q->rear)

{

printf("The queue is empty!\n");

return 0;

}

else

{

t=q->V[q->front];

q->front=(q->front+1)%M;

return t;

}

}

（12）广度遍历

void BESTraverse(Graph *g)

{

int i;

Queue *q=(Queue *)malloc(sizeof(Queue));

for(i=1;i<=g->vexnum;i++)

{

visited[i]=0;

}

initqueue(q);

for(i=1;i<=g->vexnum;i++)

{

if(!visited[i])

{

visited[i]=1;

visitvex(g,g->V[i]);

enqueue(q,g->V[i]);

while(!quempty(q))

{

int u,w;

u=dequeue(q);

for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))

{

if(!visited[w])

{

visited[w]=1;

visitvex(g,w);

enqueue(q,w);

}

}

}

}

}

}

4、测试与分析：

针对下图进行测试和分析：

由图已知有8个结点，根据提示“Please input the number of vertex:”输入“8”。再根据图输入邻接矩阵中有关系的两点，两点有关系只要输入一次即可。当输入完所有关系后输入“0，0”再输入回车，程序将输出该图邻接矩阵。再根据提示选择“b”，“d”或“q”。选“b”表示广度优先搜索（Breadth_First Search），“d”表示深度优先搜索（Depth_First Search），“q”表示退出。

Please input the number the number of vertex:

8

Please input R<0,0 END>:

1,2

2,4

4,8

5,8

2,5

1,3

3,6

3,7

0,0

This is the linjiejuzhen of graph:

0 1 1 0 0 0 0 0

1 0 0 1 1 0 0 0

1 0 0 0 0 1 1 0

0 1 0 0 0 0 0 1

0 1 0 0 0 0 0 1

0 0 1 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 1 0 0 0

Please input b or d or q,Breadth_first: b Depth_first: d quit: q b

Breadth_first:

1 2 3 4 5 6 7 8

Please input b or d or q,Breadth_first: b Depth_first: d quit: q d

Depth_fitst:

1 2 4 8 5 3 6 7

Please input b or d or q,Breadth_first: b Depth_first: d quit: q q

Press any key to contine

运行结果正确此程序可用

四、设计总结：

图的遍历是程序设计语言编译中的一个最基本问题。“图的遍历”是数据结构中主要的内容之一，也是重要的内容之一。它是树的遍历的拓展，但要比树的遍历复杂得多，是排序等的基础。它运用了深度优先遍历，广度优先遍历，入队，出队等多种运算，很有意义，是对数据结构一些基本操作的综合应用。

在做设计的开始就遇到了很多困难，比如，如何才能构造邻接矩阵，如何将邻接矩阵表示出来，如何将结果输出，以及深度优先搜索和广度优先搜索的用C语言表达等。在仔细研究教材寻找资料后，并和同学一同探讨最终将困难解决。

本次课程设计是学习数据结构后的一次具体的实践，体现了理论与实践的有效结合。在实践中体现出理论的思想，在实践中深入了解理论的具体实质，在实践中明白理论的精髓所在。同样也很好地锻炼了我自己动手动脑的的能力！

附录：源程序清单

#define M 20

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

typedef struct{

int V[M];

int R[M][M];

int vexnum;

}Graph;

void creatgraph(Graph *g,int n)

{

int i,j,r1,r2;

g->vexnum=n;

/*顶点用i表示*/

for(i=1;i<=n;i++)

{

g->V[i]=i;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

g->R[i][j]=0;

}

printf("Please input R(0,0 END):\n");

scanf("%d,%d",&r1,&r2);

while(r1!=0&&r2!=0)

{

g->R[r1][r2]=1;

g->R[r2][r1]=1;

scanf("%d,%d",&r1,&r2);

}

}

void printgraph(Graph *g)

{

int i,j;

for(i=1;i<=g->vexnum;i++)

{ for(j=1;j<=g->vexnum;j++)

{

printf("%2d ",g->R[i][j]);

}

printf("\n");

}

}

int visited[M];

void visitvex(Graph *g,int vex)

{

printf("%d ",g->V[vex]);

}

int firstadjvex(Graph *g,int vex)

{

int w,i;

for(i=1;i<=g->vexnum;i++)

{

if(g->R[vex][i]==1&&visited[i]==0)

{

w=i;

break;

}

else

{

w=0;

}

}

return w;

}

int nextadjvex(Graph *g,int vex,int w)

{

int t;

t=firstadjvex(g,w);

return t;

}

void dfs(Graph *g,int vex)

{

int w;

visited[vex]=1;

visitvex(g,vex);

for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))

if(!visited[w])

{

dfs(g,w);

}

}

void dfstraverse(Graph *g)

{

int i;

for(i=1;i<=g->vexnum;i++)

visited[i]=0;

for(i=1;i<=g->vexnum;i++)

if(!visited[i])

{dfs(g,i);}

}

typedef struct{

int V[M];

int front;

int rear;

}Queue;

initqueue(Queue *q)

{

q->front=0;

q->rear=0;

}

int quempty(Queue *q)

{

if(q->front==q->rear)

{

return 0;

}

else

{

return 1;

}

}

enqueue(Queue *q,int e)

{

if((q->rear+1)%M==q->front)

{

printf("The queue is overflow!\n");

return 0;

}

else

{

q->V[q->rear]=e;

q->rear=(q->rear+1)%M;

return 1;

}

}

dequeue(Queue *q)

{

int t;

if(q->front==q->rear)

{

printf("The queue is empty!\n");

return 0;

}

else

{

t=q->V[q->front];

q->front=(q->front+1)%M;

return t;

}

}

void BESTraverse(Graph *g)

{

int i;

Queue *q=(Queue *)malloc(sizeof(Queue));

for(i=1;i<=g->vexnum;i++)

{

visited[i]=0;

}

initqueue(q);

for(i=1;i<=g->vexnum;i++)

{

if(!visited[i])

{

visited[i]=1;

visitvex(g,g->V[i]);

enqueue(q,g->V[i]);

while(!quempty(q))

{

int u,w;

u=dequeue(q);

for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))

{

if(!visited[w])

{

visited[w]=1;

visitvex(g,w);

enqueue(q,w);

}

}

}

}

}

}

main()

{

int n;

Graph *g=(Graph *)malloc(sizeof(Graph));

char menu;

printf("Please input the number of vertex:\n");

scanf("%d",&n);

creatgraph(g,n);

printf("This is the linjiejuzhen of graph:\n");

printgraph(g);

input:

printf("Please input b or d or q ,Breadth_first: b Depth_first: d quit: q\n"); while((menu=getchar())=='\n');

if(menu=='b')

{

printf("Breadth_first:\n");

BESTraverse(g);

printf("\n");

goto input;

}

else if(menu=='d')

{

printf("Depth_first:\n");

dfstraverse(g);

printf("\n");

goto input;

}

else if(menu=='q')

{

exit(0);

}

else

{

printf("Input error!Please input b or d!\n");

}

}

本文来源：https://www.bwwdw.com/article/ijlm.html