数据结构实验---图的储存与遍历.doc

数据结构 课程实验报告　
学号：　
姓名:
实验日期: 2016、１、7
实验名称：　 图得存贮与遍历
一、实验目得
掌握图这种复杂得非线性结构得邻接矩阵与邻接表得存储表示，以及在此两种常用存储方式下深度优先遍历（ＤＦＳ）与广度优先遍历(BＦS）操作得实现。
二、实验内容与实验步骤
题目１：对以邻接矩阵为存储结构得图进行DFS与BＦS遍历
问题描述:以邻接矩阵为图得存储结构,实现图得DFS与BＦＳ遍历.
基本要求：建立一个图得邻接矩阵表示,输出顶点得一种DFＳ与BＦＳ序列。
测试数据：V0
V1
V4
V3
V2
如图所示
题目2：对以邻接表为存储结构得图进行DＦＳ与ＢFＳ遍历
问题描述：以邻接表为图得存储结构,实现图得DＦＳ与BFS遍历。
基本要求:建立一个图得邻接表存贮,输出顶点得一种ＤFS与ＢFS序列。
测试数据:如图所示
1 ∧∧∧
0
1
0 ∧
3 ∧
3 ∧
4 ∧

V０

V1

Ｖ2

V3

V4

三、附录:
在此贴上调试好得程序.
#ｉｎcluｄe〈sｔｄｉo、h>
#inｃlude＜malloｃ、h＞
＃ｉnclude<stｒiｎg、ｈ>
#defiｎｅ 　M 100 　 　　 　 　　 　 　 　 　 　 　　
ｔypｅｄｅｆ struｃt nｏdｅ　
｛
　ｃｈar　vex[M］［２］；　　 　 　 　
　inｔ ｅｄｇe[M　][　M　］; 　 　　 　 　
inｔ　n,e；　 　　 　　 　　 　
}Ｇraｐh；
inｔ ｖisｉtｅd［M]；
Ｇraph　*Create＿Grapｈ(）
{ Ｇraph *GＡ；
　　 ｉnt i，j,ｋ，ｗ;
GA＝(Ｇraph＊)malｌoc(siｚｅof(Grａph）);
prｉntf　（”请输入矩阵得顶点数与边数（用逗号隔开):\ｎ"）;
ﻩscanｆ（”％d，%d＂,&GA—>n，＆GＡ—＞e）；
printｆ　("请输入矩阵顶点信息：\ｎ");
　　 　 foｒ(ｉ = 0；i＜GA—〉n；i++)
　 　　 　 ｓcanｆ("％s",＆（ＧA-〉vex［ｉ］[0］），＆（GA—〉ｖex［i］[１］））；　 　　　 　 　
　 　foｒ （ｉ =　0；i〈GＡ-＞n;i+＋)
　　 　 for （ｊ　=　0;j<GＡ－〉ｎ;ｊ+＋)
　 　 GA－>edge[ｉ］［ｊ] = 0；
foｒ　(k　= 0；k＜GA-〉ｅ；k+＋)
　　 　{ printf　（"请输入第％ｄ条边得顶点位置（ｉ，j)与权值（用逗号隔开）:"，k+1);
　 　 　sｃanf　（"%ｄ，％d,％ｄ”，＆i，&j,＆w)；
　 GA－>eｄge［i][j］　=　ｗ;
　　 　 　}
ﻩ reｔurn（GA）;
｝
ｖｏid ｄfs(Gｒaph　＊GＡ， iｎt ｖ)
{ int ｉ；
ｐrintf(”％c％ｃ\ｎ”,GA－>vｅx[v］［0］，GA—〉vｅｘ[v］［１])； 　 　　 　
　visited［ｖ]=１;
for(ｉ=0; i<GA->n；　i++）
ｉf (GＡ－>ｅdgｅ[v］［i］==1 ＆＆ visiｔed[ｉ］＝=0） dfs（GA,　i)；
｝
voiｄ　travｅｒ(Grａph 　＊ＧA）
｛　 ｉnt i；
　　for(i＝0； i〈GA->n; i＋＋)　
ﻩ viｓiｔｅd[i]=０；
　 fｏｒ（i＝0； i〈ＧA-＞n;i++）
　 　 　if（ｖisitｅd［i］==0）
ﻩ dfs(ＧA， ｉ)；
｝
ｖoiｄ　bfs( Gｒaｐh ＊GA, int v)
{ int j，k，fronｔ＝—1,rear=-1；
　inｔ　Q［M］；
ｐｒｉｎｔf(”％c％c\ｎ"，GA-〉veｘ[v］[0］，GＡ->vex［v］［1]）;
visited［v］=1；
rｅar=rear+１;
　　 Ｑ［ｒear］=v；
wｈilｅ　(frｏnt!=rear)
　 　{　fronｔ=front+1；k=Q[fｒont］；
　　 　　for （j=0； j〈GＡ->n； j++)
　　 if （ＧＡ—＞ｅdｇe[k][ｊ］=＝1 ＆& visiｔed［j］＝=0）
　 { ｐｒiｎtf（＂％ｃ%ｃ＼n"，GA->ｖex[j］［0］，ＧA—＞ｖeｘ［j][1］)；
ﻩ visｉteｄ[j］=1；
　 　 　 rear=rear+1;
　Q［rｅar］=j；
　 　 　}
}
}
void trａver1(Ｇｒａph *ＧＡ)
｛ ｉnt i；
for (i=0； i〈GA－〉n;i++)　
ﻩ 　ｖisited[i]=0;
for （i=0； ｉ＜GA－>n; ｉ+＋）
　 ｉf (ｖiｓitｅd［i］＝=０)
　 　 bfs（GA， ｉ);
｝
tｙpｅｄeｆ strｕct　 NＯDE
｛　ｉnt　　adjveｘ;
　stｒuｃt ＮODＥ *ｎexｔ；
　}ENode；
typeｄef　ｓｔrｕｃt 　ＮODＥ1
｛ ｃhaｒ ｖex[2］;
ENodｅ　 ＊first；
｝　VexＮoｄe；
typedef ｓtrucｔ FS１
｛
ﻩVexNoｄｅ GＬ［M］;
ｉnt ｂｉan，tｏp；
｝FＳ；
ＦS ＊CｒeaｔeGＬ（ )
｛ FＳ　*kｋ=（FS *)maｌloc（sｉzeof(FＳ）)；
ﻩｉｎt i，j，k;
　 ＥNｏｄe　*s；
ｐrｉnｔｆ("请输入顶点数与边数（用逗号隔开）：\n＂)；
　 ｓcanf（"%d，％d”，&kｋ-〉top,　＆kk—＞ｂｉan);
　　　printｆ（＂请输入顶点信息：＼ｎ"）;
for　（ｉ=0; i〈kｋ->toｐ; i＋+)
　 {　scａnf("％s",kk—〉GＬ［i］、vex); 　 　　 　 　
　ｋk－〉GL[i]、fｉｒsｔ=NUＬL； ｝ 　 　 　 　 　　　 　　
　　 priｎtf(”请输入边得信息（ｉ,ｊ）：\n”）；
for　(k=0；k<kｋ－>ｂian；k++) 　 　 　 　 　 　
{　ｓcａｎf（”\n％d,％ｄ"，&i，&j）; 　 　 　　 　
　ｓ　=（ＥＮoｄe*）malloc（siｚeof（ＥNoｄe））; 　
　　 ｓ-＞adjvex=ｊ; 　 　 　 　 　 　 　 　 　
s->nexｔ=kk－>ＧL［ｉ］、first； 　　　 　
　 　kk－＞GL[ｉ］、ｆirst　＝s;
　 ｝
　returｎ kk;
｝
ｖoid DFS(FＳ　*kｋ, int ｖ）　
{ EＮode ＊w; 　int i;
　　ｐrｉntf（"％s＼n＂，kk－>GL［v］、veｘ）； 　 　 　 　　 　　　 　
vｉｓｉtｅd［v］=1； 　 　 　 　 　 　
w=kk－>GL[v]、firｓt　; 　 　 　　 　 　
　 　whilｅ （w！=NULL) 　　 　 　　 　
{ 　i=ｗ－〉adjvex；　 　 　
　　 　 if （visiｔed［i］＝＝0）　
ﻩﻩ　 DFＳ（kk，ｉ）；　 　
　 w=w—>nexｔ；
　 ｝
｝
voiｄ ＴRAＶER(FS ＊kk)　
｛ 　int ｉ;
　foｒ（i=０； i＜kk-＞toｐ;i＋+）
ﻩ vｉsｉted[i］=0; 　
ｆｏr(ｉ=０；　i＜ｋk－＞top; i+＋）
iｆ(ｖisitｅｄ［i］==0）
ﻩ ＤFS(kk， i);　
｝
ｖoid BFS(FS ＊kk, int　v）
{ ｉｎt Ｑ[M］, front=-1，reaｒ=—１;　 　　 　 　　
ENode ＊w;
　 int i, ｋ;
　 prｉntf（"%ｓ＼n"，ｋk->GL[v]、veｘ); 　　 　 　 　
　 ｖisited［v］=１；
ｒｅａｒ＝rｅar+１;　Q[rｅar]=v； 　 　 　 　
　ｗhｉlｅ (frｏnt！＝rear) 　 　 　 　 　　
　　 { froｎt=front+１；
　　　 ｋ=Q［froｎt］; 　
ｗ=ｋk-＞GＬ［ｋ］、ｆirst; 　　 　 　　 　
　 　ｗhile（w！＝NＵLＬ）
　 　 ｛　 i=w-〉adｊvex; 　　 　 　 　
　　　　 　 if（ viｓｉtｅd[i]==0)
　 　 {　　visiteｄ[ｉ］=1;　priｎｔf（"%s"，kk—>GL［ｉ］、vex）; 　
　 　 rear=reａr＋1； Q［reaｒ]=i；　　　
　 　 　　 　 }
　 　　 　 ｗ=w—>neｘt;
　 　 　 }
　 }
}
void TRAＶER1（FS ＊kk)
｛ int　ｉ；
for(i=０； i〈kk—>tｏp；ｉ++）　 ｖｉｓiｔed［ｉ]=０；　
　　 for(i=0； ｉ　〈ｋk—〉tｏｐ；i++）
　 if（visiｔed[i］＝=0) 　
ＢFS(kｋ,i）；　
｝
int maiｎ()
{
iｎt i=0；
Graｐh *p;
ＦＳ ＊ｑ; 　
　 whilｅ（i＝1）　
　｛
ﻩ/＊建立菜单＊／
ﻩ ｃhar jｚ［30]={＂1、创建邻接矩阵"}；
ﻩcｈａr jd[30]＝｛"２、邻接矩阵DFS遍历"｝；
ﻩｃhar jｂ[30］={＂3、邻接矩阵BＦS遍历”｝；
ﻩﻩchar bｇ［30]=｛"４、创建邻接表”｝；
ﻩ ｃhaｒ bd[3０]={＂5、邻接表DFS遍历”｝；
ﻩchaｒ bb［30］=｛”6、邻接表BFＳ遍历＂｝;
ﻩﻩchａr tc［３0]＝｛"7、退出”｝;
ﻩﻩchar mn[30］＝｛"菜单＂｝；
ﻩ ｉnt ｌ=strlｅn（jｄ)；
int o=strｌｅn(mn）；
inｔ　m,n；
ﻩ priｎtf(”＼n");
ﻩfor（ｍ=0;m＜=(2＊ｌ-o)/２;m++）
ﻩ priｎtf（” ");
ﻩﻩprintｆ（"％s”,ｍn）;
ﻩ fｏr（m＝0；m＜=(2*l－o）/2；ｍ+＋）
ﻩ printf(” "）；
ﻩpriｎｔf("\n")；
ﻩfoｒ(m=0;m<=2*l；m＋+）
ﻩﻩ printf（＂＊＂）；
ﻩprintf（”＼n＂）；
ｐrｉntｆ（"＊　 %ｓ ＊\n*　 　 　　%s 　 *\n*　 　%s　　 ＊＼n* %ｓ 　 　 ＊＼ｎ＊ 　 　 %s 　 　＊\ｎ＊ 　 　%s 　　 ＊\n＊ 　　 ％s　 　 　 　　 ＊\ｎ”，jｚ，jｄ，ｊb，bg，bd，ｂb，ｔc）；
ﻩfｏｒ(m=０；ｍ＜=2*l；m＋＋)
printｆ(”*"）;
ﻩprintf（"\n＂）；
ﻩ /＊选择功能*／
ﻩｐriｎtf（"请输入所需功能序号:")；
ﻩscanｆ("％d"，＆n）;
ﻩ switcｈ（ｎ)｛ﻩﻩ ﻩ
　 　 casｅ　１： ｐ=Crｅatｅ_Graph（);ｂreak;
　 casｅ 2： traver（p）;ｂreａk;
　　　 　 ｃase ３: trａver1(p）；break;
　 　 　ｃaｓe 4: ｑ＝ＣreaｔeGＬ（)；bｒｅａｋ;
　　 　 　　 ｃaｓe　5： ＴRAVER（ｑ）；break;　
　 　　 　 ｃase　6： TRＡVER1(q);ｂreak;
ﻩﻩ caｓe ７：　return　０;
ﻩﻩ defaulｔ：printf（”输入功能序号有误！\n"）； 　
　　　 　 　 ｝
ﻩ }
ｒetｕrｎ 0;
}
四、运行结果:
在此把运行结果从屏幕上拷下来贴在此

五、心得体会:
测试数据要注意现实中矩阵就是从1开始,而数组里就是从0开始。