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

.../数据结构课程设计报告班级：姓名：学号：目录设计任务3设计时间3设计内容31、需要分析32、概要设计33、详细设计44、测试与分析9四、设计总结10源程序清单11一．设计任务：我选课程设计是自选题目《图的遍历》。要求：设计一个程序,实现图的广度,深度优先遍历。二、设计时间2009三、设计内容1、需求分析本题目需要解决的问题是将一幅已知图,对图进行遍历,并完成：〔1输出它的邻接矩阵；〔2根据人工选择进行深度优先搜索〔Depth_FirstSearch和广度优先搜索〔Breadth_FirstSearch,将搜索结果放入一队列中；〔3将队列中的搜索结果输出。2、概要设计：<1>抽象数据的类型定义数据对象：V是图具有相同特性的数据元素的集合,称为定顶点集数据关系：RR={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主程序的流程以及各程序模块之间的调用关系：CreateGraph算法CreateGraph算法打印邻接矩阵初始化成功选择如何遍历开始深度优先遍历广度优先遍历结束NYDB3、详细设计：〔1定义图

typedef

struct{

intV[M];

intR[M][M];

intvexnum;

}Graph;〔2创建图

voidcreatgraph<Graph*g,intn>

{

inti,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<"PleaseinputR<0,0END>:\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全局变量：访问标志数组

voidprintgraph<Graph*g>

{

inti,j;

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

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

{

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

}

printf<"\n">;

}

}

〔4访问顶点

intvisited[M];

voidvisitvex<Graph*g,intvex>

{printf<"%d",g->V[vex]>;

}〔5获取第一个未被访问的邻接节点

intfirstadjvex<Graph*g,intvex>

{

intw,i;

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

{

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

{

w=i;

break;

}

else

{

w=0;

}

}

returnw;

}

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

intnextadjvex<Graph*g,intvex,intw>

{

intt;

t=firstadjvex<g,w>;

returnt;

}

〔6深度递归遍历

voiddfs<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>

{

inti;

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{

intV[M];

intfront;

intrear;

}Queue;

〔8初始化队列

initqueue<Queue

*q>

{

q->front=0;

q->rear=0;

}

〔9判断队列是否为空

intquempty<Queue*q>

{

if<q->front==q->rear>

{

return0;

}

else

{

return1;

}

}

〔10入队操作

enqueue<Queue*q,inte>

{

if<<q->rear+1>%M==q->front>

{

printf<"The

queueisoverflow!\n">;

return0;

}

else

{

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

q->rear=<q->rear+1>%M;

return1;

}

}

〔11出队操作

dequeue<Queue*q>

{

intt;

if<q->front==q->rear>

{

printf<"Thequeueisempty!\n">;

return0;

}

else

{

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

q->front=<q->front+1>%M;

returnt;

}

}

〔12广度遍历

voidBESTraverse<Graph*g>

{

inti;

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>>

{

intu,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、测试与分析：针对下图进行测试和分析：112345678由图已知有8个结点,根据提示"Pleaseinputthenumberofvertex:"输入"8"。再根据图输入邻接矩阵中有关系的两点,两点有关系只要输入一次即可。当输入完所有关系后输入"0,0"再输入回车,程序将输出该图邻接矩阵。再根据提示选择"b","d"或"q"。选"b"表示广度优先搜索〔Breadth_FirstSearch,"d"表示深度优先搜索〔Depth_FirstSearch,"q"表示退出。Pleaseinputthenumberthenumberofvertex:8PleaseinputR<0,0END>:1,22,44,85,82,51,33,63,70,0Thisisthelinjiejuzhenofgraph:0110000010011000100001100100000101000001001000000010000000011000Pleaseinputbordorq,Breadth_first:bDepth_first:dquit:qbBreadth_first:12345678Pleaseinputbordorq,Breadth_first:bDepth_first:dquit:qdDepth_fitst:12485367Pleaseinputbordorq,Breadth_first:bDepth_first:dquit:qqPressanykeytocontine运行结果正确此程序可用四、设计总结：图的遍历是程序设计语言编译中的一个最基本问题。"图的遍历"是数据结构中主要的内容之一,也是重要的内容之一。它是树的遍历的拓展,但要比树的遍历复杂得多,是排序等的基础。它运用了深度优先遍历,广度优先遍历,入队,出队等多种运算,很有意义,是对数据结构一些基本操作的综合应用。在做设计的开始就遇到了很多困难,比如,如何才能构造邻接矩阵,如何将邻接矩阵表示出来,如何将结果输出,以及深度优先搜索和广度优先搜索的用C语言表达等。在仔细研究教材寻找资料后,并和同学一同探讨最终将困难解决。本次课程设计是学习数据结构后的一次具体的实践,体现了理论与实践的有效结合。在实践中体现出理论的思想,在实践中深入了解理论的具体实质,在实践中明白理论的精髓所在。同样也很好地锻炼了我自己动手动脑的的能力！附录：源程序清单#define

M20

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedef

struct{

intV[M];

intR[M][M];

intvexnum;

}Graph;voidcreatgraph<Graph*g,intn>

{

inti,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<"PleaseinputR<0,0END>:\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>;

}

}

voidprintgraph<Graph*g>

{

inti,j;

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

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

{

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

}

printf<"\n">;

}

}

intvisited[M];

voidvisitvex<Graph*g,intvex>

{

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

}

intfirstadjvex<Graph*g,intvex>

{

intw,i;

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

{

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

{

w=i;

break;

}

else

{

w=0;

}

}

returnw;

}

intnextadjvex<Graph*g,intvex,intw>

{

intt;

t=firstadjvex<g,w>;

returnt;

}

voiddfs<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>

{

inti;

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{

intV[M];

intfront;

intrear;

}Queue;

initqueue<Queue

*q>

{

q->front=0;

q->rear=0;

}

intquempty<Queue*q>

{

if<q->front==q->rear>

{

return0;

}

else

{

return1;

}

}

enqueue<Queue*q,inte>

{

if<<q->rear+1>%M==q->front>

{

printf<"The

queueisoverflow!\n">;

return0;

}

else

{

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

q->rear=<q->rear+1>%M;

return1;

}

}

dequeue<Queue*q>

{

intt;

if<q->front==q->rear>

{

printf<"Thequeueisempty!\n">;

return0;

}

else

{

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

q->front=<q->front+1>%M;

returnt;

}

}

voidBESTraverse<Graph*g>

{

inti;

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>>

{

intu,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>;

en