數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告《圖的遍歷》

.../數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告班級(jí)：姓名：學(xué)號(hào)：目錄設(shè)計(jì)任務(wù)3設(shè)計(jì)時(shí)間3設(shè)計(jì)內(nèi)容31、需要分析32、概要設(shè)計(jì)33、詳細(xì)設(shè)計(jì)44、測(cè)試與分析9四、設(shè)計(jì)總結(jié)10源程序清單11一．設(shè)計(jì)任務(wù)：我選課程設(shè)計(jì)是自選題目《圖的遍歷》。要求：設(shè)計(jì)一個(gè)程序,實(shí)現(xiàn)圖的廣度,深度優(yōu)先遍歷。二、設(shè)計(jì)時(shí)間2009三、設(shè)計(jì)內(nèi)容1、需求分析本題目需要解決的問(wèn)題是將一幅已知圖,對(duì)圖進(jìn)行遍歷,并完成：〔1輸出它的鄰接矩陣；〔2根據(jù)人工選擇進(jìn)行深度優(yōu)先搜索〔Depth_FirstSearch和廣度優(yōu)先搜索〔Breadth_FirstSearch,將搜索結(jié)果放入一隊(duì)列中；〔3將隊(duì)列中的搜索結(jié)果輸出。2、概要設(shè)計(jì)：<1>抽象數(shù)據(jù)的類(lèi)型定義數(shù)據(jù)對(duì)象：V是圖具有相同特性的數(shù)據(jù)元素的集合,稱(chēng)為定頂點(diǎn)集數(shù)據(jù)關(guān)系：RR={VR}VR={<v,w>/v,w∈v且p<v,w>}基本操作：CreateGraph<&G,V,VR>初始條件：V是圖的頂點(diǎn)集,VR是圖中弧的集合操作結(jié)果：按V和VR的定義構(gòu)造圖G基本操作：DFSTraverse<G,Visit<>>BFSTraverse<G,Visit<>>〔2主程序的流程以及各程序模塊之間的調(diào)用關(guān)系：CreateGraph算法CreateGraph算法打印鄰接矩陣初始化成功選擇如何遍歷開(kāi)始深度優(yōu)先遍歷廣度優(yōu)先遍歷結(jié)束NYDB3、詳細(xì)設(shè)計(jì)：〔1定義圖

typedef

struct{

intV[M];

intR[M][M];

intvexnum;

}Graph;〔2創(chuàng)建圖

voidcreatgraph<Graph*g,intn>

{

inti,j,r1,r2;

g->vexnum=n;

/*頂點(diǎ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全局變量：訪問(wèn)標(biāo)志數(shù)組

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訪問(wèn)頂點(diǎn)

intvisited[M];

voidvisitvex<Graph*g,intvex>

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

}〔5獲取第一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)

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;

}

/*獲取下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)<深度遍歷>*/

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定義隊(duì)列

typedef

struct{

intV[M];

intfront;

intrear;

}Queue;

〔8初始化隊(duì)列

initqueue<Queue

*q>

{

q->front=0;

q->rear=0;

}

〔9判斷隊(duì)列是否為空

intquempty<Queue*q>

{

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

{

return0;

}

else

{

return1;

}

}

〔10入隊(duì)操作

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出隊(duì)操作

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、測(cè)試與分析：針對(duì)下圖進(jìn)行測(cè)試和分析：112345678由圖已知有8個(gè)結(jié)點(diǎn),根據(jù)提示"Pleaseinputthenumberofvertex:"輸入"8"。再根據(jù)圖輸入鄰接矩陣中有關(guān)系的兩點(diǎn),兩點(diǎn)有關(guān)系只要輸入一次即可。當(dāng)輸入完所有關(guān)系后輸入"0,0"再輸入回車(chē),程序?qū)⑤敵鲈搱D鄰接矩陣。再根據(jù)提示選擇"b","d"或"q"。選"b"表示廣度優(yōu)先搜索〔Breadth_FirstSearch,"d"表示深度優(yōu)先搜索〔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運(yùn)行結(jié)果正確此程序可用四、設(shè)計(jì)總結(jié)：圖的遍歷是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)最基本問(wèn)題。"圖的遍歷"是數(shù)據(jù)結(jié)構(gòu)中主要的內(nèi)容之一,也是重要的內(nèi)容之一。它是樹(shù)的遍歷的拓展,但要比樹(shù)的遍歷復(fù)雜得多,是排序等的基礎(chǔ)。它運(yùn)用了深度優(yōu)先遍歷,廣度優(yōu)先遍歷,入隊(duì),出隊(duì)等多種運(yùn)算,很有意義,是對(duì)數(shù)據(jù)結(jié)構(gòu)一些基本操作的綜合應(yīng)用。在做設(shè)計(jì)的開(kāi)始就遇到了很多困難,比如,如何才能構(gòu)造鄰接矩陣,如何將鄰接矩陣表示出來(lái),如何將結(jié)果輸出,以及深度優(yōu)先搜索和廣度優(yōu)先搜索的用C語(yǔ)言表達(dá)等。在仔細(xì)研究教材尋找資料后,并和同學(xué)一同探討最終將困難解決。本次課程設(shè)計(jì)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)后的一次具體的實(shí)踐,體現(xiàn)了理論與實(shí)踐的有效結(jié)合。在實(shí)踐中體現(xiàn)出理論的思想,在實(shí)踐中深入了解理論的具體實(shí)質(zhì),在實(shí)踐中明白理論的精髓所在。同樣也很好地鍛煉了我自己動(dòng)手動(dòng)腦的的能力！附錄：源程序清單#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;

/*頂點(diǎ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