數(shù)據(jù)結(jié)構(gòu)-鄰接表存儲(chǔ)及遍歷-課程設(shè)計(jì)-實(shí)驗(yàn)報(bào)告

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)</p><p>　　設(shè)計(jì)題目： 鄰接表存儲(chǔ)及遍歷 </p><p>　　學(xué)生姓名： </p><p>　　專業(yè)班級(jí)： </p><p>　　指導(dǎo)教師： </p><p>

2、　　完成時(shí)間： </p><p>　課題名稱鄰接表存儲(chǔ)及遍歷</p><p>　院 系年級(jí)專業(yè)</p><p>　學(xué) 號(hào)姓 名成 績</p><p>　課題設(shè)計(jì)目的與設(shè)計(jì)意義1、課題設(shè)計(jì)目的：①通過實(shí)習(xí)掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識(shí)。對(duì)于本課題所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：圖的鄰接表儲(chǔ)存結(jié)構(gòu)、鄰接表的算法

3、實(shí)現(xiàn)、圖的廣度優(yōu)先搜索遍歷、圖的深度優(yōu)先搜索遍歷。2、課題設(shè)計(jì)意義：①培養(yǎng)學(xué)生運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)解決實(shí)際編程中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和設(shè)計(jì)問題。②培養(yǎng)學(xué)生獨(dú)立設(shè)計(jì)程序與解決問題的能力，培養(yǎng)學(xué)生團(tuán)隊(duì)協(xié)作集成程序模塊及調(diào)試能力。指導(dǎo)教師：年 月 日</p><p><b>　　目 錄</b></p><p>　　第一章 需求分析4</p><

4、p><b>　　1.1 圖4</b></p><p>　　1.2 鄰接表的概念4</p><p>　　1.3鄰接表的表示法4</p><p>　　第二章 概要分析5</p><p>　　2.1 無向圖5</p><p><b>　　2.2 有相圖5</b&g

5、t;</p><p>　　2.3 無向圖5</p><p><b>　　2.4有向圖5</b></p><p>　　第三章 詳細(xì)分析6</p><p>　　3.1 鄰接表的建立6</p><p>　　3.2 鄰接表的建立過程如下：6</p><p>　　3.2

6、.1無向圖鄰接表的建立6</p><p>　　3.2.2 有向圖鄰接表的建立7</p><p>　　3.3 鄰接表的輸出過程如下：7</p><p>　　3.4 鄰接表的遍歷8</p><p>　　3.4.1 連通圖的深度優(yōu)先搜索遍歷8</p><p>　　3.4.2 有向圖的廣度優(yōu)先搜索遍歷9&l

7、t;/p><p>　　3.5 流程圖10</p><p>　　3.5.1 主流程圖10</p><p>　　3.5.2 無向圖鄰接表的流程圖10</p><p>　　3.5.3 有向圖鄰接表的流程圖12</p><p>　　第四章 測(cè)試分析14</p><p>　　4.1 無向圖

8、14</p><p>　　4.1.1 主程序main()編寫如下：14</p><p>　　4.1.2 運(yùn)行步驟16</p><p>　　4.2 有向圖18</p><p>　　第五章 心得體會(huì)20</p><p>　　第六章、參考文獻(xiàn)20</p><p><b>　

9、　第一章 需求分析</b></p><p><b>　　1.1 圖</b></p><p>　　①若圖1.1中每一條邊都是有方向的，則為有相圖。 </p><p>　?、谌魣D1.1中每一條邊都是沒有方向的，則為無向圖。v2</p><p><b>　　圖1.1</b></

10、p><p>　　1.2 鄰接表的概念</p><p>　　對(duì)于圖1.1中的每個(gè)頂點(diǎn)vi，該方法把所有鄰接于vi </p><p>　　的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。</p><p>　　1.3鄰接表的表示法</p><p>　　鄰接表中每個(gè)表結(jié)點(diǎn)均有2個(gè)域，其一是鄰接點(diǎn)域（adjvex），

11、用以存放與vi相鄰接的頂點(diǎn)vj的序號(hào)；其二是鏈域（next），用來將鄰接表的所有表結(jié)點(diǎn)鏈在一起。</p><p>　　并且為每個(gè)頂點(diǎn)vi的鄰接表設(shè)置一個(gè)具有2個(gè)域的表頭結(jié)點(diǎn)：一個(gè)是頂點(diǎn)域（vertex），用來存放頂點(diǎn)vi的信息；另一個(gè)是指針域（link），用于存入指向vi的鄰接表中第一個(gè)表結(jié)點(diǎn)的頭指針。</p><p><b>　　第二章 概要分析</b></

12、p><p><b>　　2.1 無向圖</b></p><p>　　無向圖鄰接表的建立，無向圖鄰接表的輸出，無向圖鄰接表的深度優(yōu)先搜索遍歷，無向圖鄰接表的廣度優(yōu)先搜索遍歷。</p><p><b>　　2.2 有相圖</b></p><p>　　有向圖鄰接表的建立，有向圖鄰接表的輸出，有向圖鄰接表的深

13、度優(yōu)先搜索遍歷，有向圖鄰接表的廣度優(yōu)先搜索遍歷。</p><p><b>　　2.3 無向圖</b></p><p><b>　　2.4有向圖</b></p><p><b>　　第三章 詳細(xì)分析</b></p><p>　　3.1 鄰接表的建立</p><

14、;p>　　鄰接表是把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表。其次還需要一個(gè)順序表來儲(chǔ)存頂點(diǎn)信息。其具體C語言代碼如下：</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　int adjvex;/*鄰接點(diǎn)域*/</p><p>　　struct n

15、ode *next;/*鏈域*/</p><p>　　}edgenode;/*邊表結(jié)點(diǎn)*/</p><p>　　3.2 鄰接表的建立過程如下：</p><p>　　3.2.1無向圖鄰接表的建立</p><p>　　void creat_ljb(topnode gl[],int n,int e) /*無向圖鄰接表的建立*/</p&

16、gt;<p><b>　　{</b></p><p>　　int i,j,k;</p><p>　　edgenode *p;</p><p>　　getchar();</p><p>　　printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的元素:",n);</p><p>　　fo

17、r(i=0;i<n;i++)/*讀入頂點(diǎn)信息*/</p><p><b>　　{</b></p><p>　　scanf("%c",&gl[i].topvex)；</p><p>　　gl[i].link=NULL; /*邊表頭指針初始化*/</p><p>&

18、lt;b>　　}</b></p><p>　　printf("請(qǐng)輸入要鄰接的倆個(gè)頂點(diǎn)的下標(biāo):\n");</p><p>　　for(k=0;k<e;k++) /*建立邊表*/</p><p><b>　　{</b></p><p>　　scanf(&qu

19、ot;%d%d",&i,&j);</p><p>　　p=(edgenode *)malloc(sizeof(edgenode));</p><p>　　p->adjvex=j;</p><p>　　p->next=gl[i].link;</p><p>　　gl[i].link=p;</p>

20、<p>　　p=(edgenode *)malloc(sizeof(edgenode));</p><p>　　p->adjvex=i;</p><p>　　p->next=gl[j].link;</p><p>　　gl[j].link=p;</p><p><b>　　}</b></p

21、><p><b>　　}</b></p><p>　　3.2.2 有向圖鄰接表的建立</p><p>　　void creat_yljb(topnode gl[],int n,int e)/*有向圖鄰接表的建立*/</p><p><b>　　{</b></p><p>　　in

22、t i,j,k;</p><p>　　edgenode *p;</p><p>　　getchar();</p><p>　　printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的元素:",n);</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b>&

23、lt;/p><p>　　scanf("%c",&gl[i].topvex);</p><p>　　gl[i].link=NULL;</p><p><b>　　}</b></p><p>　　printf("請(qǐng)輸入要鄰接的倆個(gè)頂點(diǎn)的下標(biāo):\n");</p><

24、;p>　　for(k=0;k<e;k++)</p><p><b>　　{</b></p><p>　　scanf("%d%d",&i,&j);</p><p>　　p=(edgenode *)malloc(sizeof(edgenode));</p><p>　　p-&g

25、t;adjvex=j;</p><p>　　p->next=gl[i].link;</p><p>　　gl[i].link=p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.3 鄰接表的輸出過程如下：<

26、;/p><p>　　void print_ljb(topnode gl[],int n)/*鄰接表的輸出*/</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　edgenode *p;</p><p>　　printf(

27、"建立后的鄰接表為:\n");</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　printf("%c\t",gl[i].topvex);</p><p>　　p=gl[i].link;</p>&

28、lt;p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　printf("%d\t",p->adjvex);</p><p>　　p=p->next;</p><p><b>　　}</b>

29、</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.4 鄰接表的遍歷</p><p>　　對(duì)于圖的遍歷，和樹的遍歷類似，也是從某個(gè)頂點(diǎn)出發(fā)，沿著搜索路徑

30、對(duì)圖中所有頂點(diǎn)做一次訪問。若給定的圖是連通圖，則從圖中人一頂點(diǎn)出發(fā)順著邊可以訪問到該圖的所有頂點(diǎn)。又因?yàn)閳D中任一頂點(diǎn)都可能和其余頂點(diǎn)相鄰接，故在訪問了某個(gè)頂點(diǎn)之后，可能順著某條路又反回到了該頂點(diǎn)。為避免重復(fù)訪問同頂點(diǎn)，必須記住每個(gè)頂點(diǎn)是否被訪問過。為此，我們已經(jīng)在前面設(shè)置了向量int visited[vexnum]={0}來標(biāo)示，他的初始值為0。</p><p>　　3.4.1 連通圖的深度優(yōu)先搜索遍歷<

31、/p><p>　　int visited_lj[20]={0};</p><p>　　void DFSL(topnode gl[],int i)/*鄰接表的深度遍歷*/</p><p><b>　　{</b></p><p>　　edgenode *p;</p><p>　　printf("

32、%c",gl[i].topvex);</p><p>　　visited_lj[i]=1;</p><p>　　p=gl[i].link;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　if(visited_lj[p->

33、;adjvex]==0)</p><p>　　DFSL(gl,p->adjvex);</p><p>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int visited[20]={0

34、};</p><p>　　3.4.2 有向圖的廣度優(yōu)先搜索遍歷</p><p>　　int visited_ljb[20]={0};</p><p>　　void BFSL(topnode gl[],int k)/*鄰接表的廣度遍歷*/</p><p><b>　　{</b></p><p>&

35、lt;b>　　int i;</b></p><p>　　edgenode *p;</p><p>　　linkqueue Q;</p><p>　　setnull(&Q);</p><p>　　printf("%c",gl[k].topvex);</p><p>　　vis

36、ited_ljb[k]=1;</p><p>　　enqueue(&Q,k);</p><p>　　while(!empty(&Q))</p><p><b>　　{</b></p><p>　　i=dequeue(&Q);</p><p>　　p=gl[i].link;&

37、lt;/p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　if(!visited_ljb[p->adjvex])</p><p><b>　　{</b></p><p>　　printf("%c",

38、gl[p->adjvex].topvex);</p><p>　　visited_ljb[p->adjvex]=1;</p><p>　　enqueue(&Q,p->adjvex);</p><p><b>　　}</b></p><p>　　p=p->next;</p>&

39、lt;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int visited_jz[20]={0};</p><p><b>　　3.5 流程圖</b></p&g

40、t;<p>　　3.5.1 主流程圖</p><p>　　3.5.2 無向圖鄰接表的流程圖 </p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p>&

41、lt;b>　　是</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b&

42、gt;　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p>　　3.5.3 有向圖鄰接表的流程圖 </p><p><b>　　否

43、</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p><b>　　是否</b></p><p><b>　　是</b></p><p><b>　　否<

44、;/b></p><p><b>　　是</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p><b>　　是</b&g

45、t;</p><p><b>　　第四章 測(cè)試分析</b></p><p>　　運(yùn)行環(huán)境：Microsoft Visual C++</p><p><b>　　程序語言：C語言</b></p><p>　　下面，我們來檢驗(yàn)一下程序能否正確運(yùn)行。</p><p><b&g

46、t;　　4.1 無向圖</b></p><p><b>　　01頂點(diǎn)信息</b></p><p><b>　　序號(hào) 元素</b></p><p><b>　　0a</b></p><p><b>　　1b</b></p>

47、;<p><b>　　2 c</b></p><p>　　3 3 </p><p>　　4.1.1 主程序main()編寫如下：</p><p>　　void main()</p><p><b>　　{</b></p&g

48、t;<p>　　int i=1,j,n,e;</p><p>　　int k=1,m=1,l=1,t=1;</p><p><b>　　graph ga;</b></p><p>　　topnode *gl;</p><p>　　printf("\t\t\t鄰接表表示圖及深廣度優(yōu)先遍歷\n&quo

49、t;);</p><p><b>　　while(i)</b></p><p><b>　　{</b></p><p>　　printf("\n1:無向圖\n2:有向圖\n");</p><p>　　scanf("%d",&i);</p>

50、<p><b>　　switch(i)</b></p><p><b>　　{</b></p><p>　　case 1://無向圖的基本運(yùn)算</p><p><b>　　while(k)</b></p><p><b>　　{</b><

51、/p><p>　　printf("\n1:無向圖鄰接表的建立\n2:無向圖鄰接表的輸出\n3:無向圖鄰接表的深度遍歷\n4:無向圖鄰接表的廣度遍歷\n");</p><p>　　scanf("%d",&k);</p><p><b>　　switch(k)</b></p><p&g

52、t;<b>　　{</b></p><p>　　case 1:printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):");</p><p>　　scanf("%d%d",&n,&e);</p><p>　　creat_ljb(&gl,n,e);</p><p><b&g

53、t;　　break;</b></p><p>　　case 2:print_ljb(&gl,n);</p><p><b>　　break;</b></p><p>　　case 3:printf("請(qǐng)輸入要遍歷的起始位置:");</p><p>　　scanf("%d&

54、quot;,&j);</p><p>　　printf("鄰接表深度遍歷后的結(jié)果為:") </p><p>　　DFSL(&gl,j);</p><p><b>　　break;</b></p><p>　　case 4:printf("請(qǐng)輸入要遍歷的起始位

55、置:");</p><p>　　scanf("%d",&j);</p><p>　　printf("鄰接表廣度遍歷后的結(jié)果為:");</p><p>　　BFSL(&gl,j);</p><p><b>　　break;</b></p>&l

56、t;p><b>　　}</b></p><p>　　printf("\n0:結(jié)束\n1:繼續(xù)\n");</p><p>　　scanf("%d",&k);</p><p><b>　　}</b></p><p><b>　　break;

57、</b></p><p>　　case 2://有向圖的基本運(yùn)算</p><p><b>　　while(l)</b></p><p><b>　　{</b></p><p>　　printf("\n1:有向圖鄰接表的建立\n2:有向圖鄰接表的輸出\n3:有向圖鄰接表的深度遍歷

58、\n4:有向圖鄰接表的廣度遍歷\n");</p><p>　　scanf("%d",&l);</p><p><b>　　switch(l)</b></p><p><b>　　{</b></p><p>　　case 1:printf("請(qǐng)輸入頂點(diǎn)數(shù)

59、和邊數(shù):");</p><p>　　scanf("%d%d",&n,&e);</p><p>　　creat_yljb(&gl,n,e);</p><p><b>　　break;</b></p><p>　　case 2:print_ljb(&gl,n);&

60、lt;/p><p><b>　　break;</b></p><p>　　case 3:printf("請(qǐng)輸入要遍歷的起始位置:");</p><p>　　scanf("%d",&l);</p><p>　　printf("鄰接表深度遍歷后的結(jié)果為:");&

61、lt;/p><p>　　DFSL(&gl,l);</p><p><b>　　break;</b></p><p>　　case 4:printf("請(qǐng)輸入要遍歷的起始位置:");</p><p>　　scanf("%d",&l);</p><p&g

62、t;　　printf("鄰接表廣度遍歷后的結(jié)果為:");</p><p>　　BFSL(&gl,l);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　printf("\n0:結(jié)束\n1:繼續(xù)\n&q

63、uot;);</p><p>　　scanf("%d",&l);</p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　print

64、f("\n0:結(jié)束無向圖的運(yùn)算1:繼續(xù)無向圖的運(yùn)算\n"); </p><p>　　scanf("%d",&i);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.1.2 運(yùn)行步驟</p

65、><p>　　1 無向圖鄰接表建立與輸出</p><p><b>　　2 廣度與深度遍歷</b></p><p><b>　　4.2 有向圖</b></p><p>　　01 頂點(diǎn)信息</p><p><b>　　序號(hào) 元素<

66、;/b></p><p><b>　　0a</b></p><p><b>　　1b</b></p><p><b>　　2c</b></p><p><b>　　3d</b></p><p><b>　　2

67、3</b></p><p>　　其主函數(shù)于無向圖相圖</p><p><b>　　運(yùn)行步驟</b></p><p>　　1 有向圖的建立與輸出</p><p>　　2有向圖鄰接表的深度與廣度遍歷</p><p><b>　　第五章 心得體會(huì)</b></p&

68、gt;<p>　　數(shù)據(jù)結(jié)構(gòu)交給我們了許多關(guān)于電腦的知識(shí)，開闊了我們的視野，讓我們更加喜愛計(jì)算機(jī)，同時(shí)教給我們?cè)S多不足，讓我們充分了解了計(jì)算機(jī)的樂趣及其重要性，本章的學(xué)習(xí)，讓我們了解了許多，也懂得了許多……</p><p><b>　　第六章、參考文獻(xiàn) </b></p><p>　　徐德民.最新C語言程序設(shè)計(jì).電子工業(yè)出版社，1992</p>