數(shù)據(jù)庫課程設(shè)計(jì)---圖的存儲(chǔ)與遍歷

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)</p><p>　　設(shè)計(jì)題目： 圖的鄰接表存儲(chǔ)及其應(yīng)用 </p><p>　課題名稱圖的鄰接表存儲(chǔ)及其應(yīng)用</p><p>　院 系年級(jí)專業(yè)</p><p>　學(xué) 號(hào)</p><p>　課題設(shè)計(jì)目的與設(shè)計(jì)意義課題設(shè)計(jì)目的：一、是讓我們通過實(shí)習(xí)

2、掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識(shí)。對(duì)于《圖的遍歷》這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：圖的鄰接表存貯結(jié)構(gòu)、隊(duì)列的基本運(yùn)算實(shí)現(xiàn)、鄰接表的算法實(shí)現(xiàn)、圖的廣度優(yōu)先搜索、圖的深度優(yōu)先搜索算法實(shí)現(xiàn)。 二、是通過實(shí)習(xí)鞏固并提高實(shí)習(xí)者的C語言知識(shí)，并初步了解C++的知識(shí)，提高編程能力與專業(yè)水平。2、課題設(shè)計(jì)意義：一、通過對(duì)鄰接表表示圖及深廣度優(yōu)先遍歷程序的編寫，對(duì)數(shù)據(jù)結(jié)構(gòu)的理解更為加深。二、培養(yǎng)了我們獨(dú)立設(shè)計(jì)程序與解決問

3、題的能力，培養(yǎng)了我們團(tuán)隊(duì)協(xié)作集成程序模塊及調(diào)試能力。三、培養(yǎng)了學(xué)生初步的軟件設(shè)計(jì)及軟件測試的能力。指導(dǎo)教師：年 月 日</p><p><b>　　目 錄</b></p><p>　　第一章 課程設(shè)計(jì)目的１</p><p>　　第二章 課程設(shè)計(jì)內(nèi)容和要求１</p><p>　　2.1課程設(shè)計(jì)內(nèi)容１&l

4、t;/p><p>　　2.1.1圖的鄰接表的建立與輸出１</p><p>　　2.1.2 圖的遍歷的實(shí)現(xiàn)１</p><p>　　2.2 運(yùn)行環(huán)境１</p><p>　　第三章 課程設(shè)計(jì)分析２</p><p><b>　　3.1圖的存儲(chǔ)２</b></p><p>　　3

5、.2 圖的遍歷２</p><p>　　3.2.1 圖的深度優(yōu)先遍歷２</p><p>　　3.2.2 圖的廣度優(yōu)先遍歷２</p><p>　　第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述３</p><p>　　4.1 圖的存儲(chǔ)結(jié)構(gòu)的建立。３</p><p>　　4.1.1 定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型３</p

6、><p>　　4.1.2 初始化圖的鄰接表３</p><p>　　4.1.3 建立并輸出圖的鄰接表３</p><p>　　4.2 圖的遍歷５</p><p>　　4.2.1 深度優(yōu)先遍歷圖的鄰接表５</p><p>　　4.2.2 廣度優(yōu)先遍歷圖的鄰接表６</p><p><b>

7、;　　第五章 源代碼７</b></p><p>　　第六章 運(yùn)行結(jié)果分析１３</p><p>　　第七章 結(jié)束語１７</p><p>　　第八章 參考文獻(xiàn)１９</p><p>　　第一章 課程設(shè)計(jì)目的</p><p>　　本學(xué)期我們對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程進(jìn)行了學(xué)習(xí)。這門課程是一門實(shí)踐性非常強(qiáng)的課程，

8、為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)實(shí)習(xí)。這次課程設(shè)計(jì)不但要求實(shí)習(xí)者掌握《數(shù)據(jù)結(jié)構(gòu)》中的各方面知識(shí)，還要求實(shí)習(xí)者具備一定的C語言基礎(chǔ)和編程能力。</p><p>　　具體說來，這次課程設(shè)計(jì)主要有兩大方面目的。</p><p>　　一是讓實(shí)習(xí)者通過實(shí)習(xí)掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識(shí)。對(duì)于《圖的遍歷》這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：圖的鄰接表存貯結(jié)構(gòu)

9、、隊(duì)列的基本運(yùn)算實(shí)現(xiàn)、鄰接表的算法實(shí)現(xiàn)、圖的廣度優(yōu)先搜索周游算法實(shí)現(xiàn)、圖的深度優(yōu)先搜索周游算法實(shí)現(xiàn)。</p><p>　　二是通過實(shí)習(xí)鞏固并提高實(shí)習(xí)者的C語言知識(shí)，并初步了解Visual C++的知識(shí)，提高其編程能力與專業(yè)水平。</p><p>　　第二章 課程設(shè)計(jì)內(nèi)容和要求</p><p><b>　　2.1課程設(shè)計(jì)內(nèi)容</b></p&

10、gt;<p>　　該課題要求以鄰接表的方式存儲(chǔ)圖，輸出鄰接表，并要求實(shí)現(xiàn)圖的深度、廣度兩種遍歷。</p><p>　　2.1.1圖的鄰接表的建立與輸出</p><p>　　對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），并且對(duì)有向圖與無向圖都應(yīng)進(jìn)行討論，根據(jù)鄰接表的存儲(chǔ)結(jié)構(gòu)建立圖的鄰接表并輸出之。盡量用圖形化的方式輸出鄰接表。</p><p>　　2.1.2 圖的

11、遍歷的實(shí)現(xiàn)</p><p>　　圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對(duì)于廣度優(yōu)先遍歷應(yīng)利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）來實(shí)現(xiàn)。首先建立一空隊(duì)列，從初始點(diǎn)出發(fā)進(jìn)行訪問，當(dāng)被訪問時(shí)入隊(duì)，訪問完出隊(duì)。并以隊(duì)列是否為空作為循環(huán)控制條件。對(duì)于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來實(shí)現(xiàn)。</p><p><b>　　2.2 運(yùn)行環(huán)境</b>

12、</p><p>　　該程序的運(yùn)行環(huán)境為Windows xp系統(tǒng)，Microsoft Visual C++6.0版本。</p><p>　　第三章 課程設(shè)計(jì)分析</p><p><b>　　3.1圖的存儲(chǔ)</b></p><p>　　本課題要求采取鄰接表的存儲(chǔ)結(jié)構(gòu)。鄰接表是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建

13、立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（對(duì)有向圖是以頂點(diǎn)Vi為尾的在圖中的位置，鏈域（nextarc）指示下一條?。?。每個(gè)結(jié)點(diǎn)由3個(gè)域組成，其中鄰接點(diǎn)域（adjvex）指示與頂點(diǎn)Vi鄰接的點(diǎn)在圖中的位置，鏈域（nextarc）指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域（info）存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。</p><p>　　所以一開始必須先定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型，并對(duì)鄰接表進(jìn)行初始化

14、，然后根據(jù)所輸入的相關(guān)信息，包括圖的頂點(diǎn)數(shù)、邊數(shù)、是否為有向，以及各條邊的起點(diǎn)與終點(diǎn)序號(hào)，建立圖的鄰接表。此時(shí)要分兩種情況：有向圖與無向圖。對(duì)于無向圖，一條邊的兩的個(gè)頂點(diǎn)，互為鄰接點(diǎn)，所以在存儲(chǔ)時(shí)，應(yīng)向起點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即終點(diǎn)。同時(shí)將終點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即起點(diǎn)。對(duì)于有向圖，只能向起點(diǎn)的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)，即終點(diǎn)。但不能反過來。至于鄰接表的輸出，由于不了解C++中的繪圖操作，故采用for語句輸出各結(jié)點(diǎn)，并配合

15、一些符號(hào)完成鄰接表的輸出。</p><p><b>　　3.2 圖的遍歷</b></p><p>　　3.2.1 圖的深度優(yōu)先遍歷</p><p>　　假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪問初始點(diǎn)，然后依次從v未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)仍有頂點(diǎn)未被

16、訪問到，則從另一個(gè)未被訪問的頂點(diǎn)出發(fā)，重復(fù)上述過程，直至所有點(diǎn)都被訪問到為止。這是一個(gè)遞歸的過程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。</p><p>　　具體過程應(yīng)為：先訪問初始點(diǎn)Vi，并標(biāo)志其已被訪問。此時(shí)定義一指向邊結(jié)點(diǎn)的指針p，并建立一個(gè)while（）循環(huán)，以指針?biāo)笇?duì)象不為空為控制條件，當(dāng)Vi的鄰接點(diǎn)未被訪問時(shí)，遞歸調(diào)

17、用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個(gè)邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。</p><p>　　3.2.2 圖的廣度優(yōu)先遍歷</p><p>　　廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖

18、中尙有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點(diǎn)，由近及遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1，2，……的頂點(diǎn)。</p><p>　　所以要實(shí)現(xiàn)算法必須先建立一個(gè)元素類型為整形的空隊(duì)列，并定義隊(duì)首與隊(duì)尾指針，同時(shí)也要定義一個(gè)標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。同樣，也是從初始點(diǎn)出發(fā)開始訪問，訪問初始點(diǎn)，標(biāo)志其已被

19、訪問，并將其入隊(duì)。當(dāng)隊(duì)列非空時(shí)進(jìn)行循環(huán)處理。當(dāng)結(jié)點(diǎn)被訪問時(shí)對(duì)其進(jìn)行標(biāo)志，并入隊(duì)列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷。</p><p>　　第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述</p><p>　　4.1 圖的存儲(chǔ)結(jié)構(gòu)的建立。</p><p>　　4.1.1 定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型</p><

20、;p>　　struct edgenode{</p><p>　　int adjvex; //該弧所指向的頂點(diǎn)的位置</p><p>　　4.1.2 初始化圖的鄰接表</p><p>　　需建立一個(gè)鄰接表初始化函數(shù)對(duì)圖的鄰接表進(jìn)行初始化。即建立一個(gè)所有邊結(jié)點(diǎn)都為空的鄰#include<stdio.h></p>

21、<p>　　4.1.3 建立并輸出圖的鄰接表</p><p>　　首先必須輸入圖的相關(guān)信息，包括圖的頂點(diǎn)數(shù)、邊數(shù)。圖分為有向圖和無向圖。對(duì)于無向圖，各條邊的起點(diǎn)和終點(diǎn)互為鄰接點(diǎn)。所以必須把起點(diǎn)添加到終點(diǎn)的鄰接點(diǎn)域中，并把終點(diǎn)添加到起點(diǎn)的鄰接點(diǎn)域中。而對(duì)于有向圖，只能是將弧頭添加到弧尾的鄰接點(diǎn)域中。最后是輸出鄰接表，即對(duì)于每個(gè)頂點(diǎn)，輸出其鄰接點(diǎn)。由于不了解C++中繪圖函數(shù)的用法，所以利用一些符號(hào)來達(dá)到圖

22、形化的效果。鄰接表建立和輸出的程序如下：</p><p>　　void creat_ljbiao(topnode gl[],int n,int e)//無向圖鄰接表的建立</p><p><b>　　{</b></p><p>　　int i,j,k;</p><p>　　edgenode *p;</p>

23、<p>　　getchar();</p><p>　　printf("\n請(qǐng)輸入%d個(gè)頂點(diǎn)的元素:",n);</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　scanf("%c",&gl[i]

24、.topvex);</p><p>　　gl[i].link=NULL;</p><p><b>　　}</b></p><p>　　printf("\n請(qǐng)輸入要鄰接的倆個(gè)頂點(diǎn)的下標(biāo):\n");</p><p>　　for(k=0;k<e;k++)</p><p><

25、;b>　　{</b></p><p>　　scanf("%d%d",&i,&j);</p><p>　　p=(edgenode *)malloc(sizeof(edgenode));</p><p>　　p->adjvex=j;</p><p>　　p->next=gl[i].

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

27、p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void print_ljbiao(topnode gl[],int n)//鄰接表的輸出</p><p><b>　　{</b></p><p>

28、<b>　　int i;</b></p><p>　　edgenode *p;</p><p>　　printf("\n建立后的鄰接表為:\n");</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><

29、p>　　printf("%c\t",gl[i].topvex);</p><p>　　p=gl[i].link;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　printf("%d\t"

30、,p->adjvex);</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}<

31、/b></p><p><b>　　4.2 圖的遍歷</b></p><p>　　4.2.1 深度優(yōu)先遍歷圖的鄰接表</p><p>　　假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪問初始點(diǎn)，然后依次從v未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)仍有頂點(diǎn)未被訪問到，

32、則從另一個(gè)未被訪問的頂點(diǎn)出發(fā)，重復(fù)上述過程，直至所有點(diǎn)都被訪問到為止。這是一個(gè)遞歸的過程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。</p><p>　　具體過程應(yīng)為：先訪問初始點(diǎn)Vi，并標(biāo)志其已被訪問。此時(shí)定義一指向邊結(jié)點(diǎn)的指針p，并建立一個(gè)while（）循環(huán)，以指針?biāo)笇?duì)象不為空為控制條件，當(dāng)Vi的鄰接點(diǎn)未被訪問時(shí)，遞歸調(diào)用深度優(yōu)

33、先遍歷函數(shù)訪問之。然后將p指針指向下一個(gè)邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。</p><p>　　深度優(yōu)先遍歷的相關(guān)算法如下：</p><p>　　int visited_lj[20]={0};</p><p>　　void DFSL(topnode gl[],int i) //鄰接表的深度優(yōu)先遍歷</p><p><b&

34、gt;　　{</b></p><p>　　edgenode *p;</p><p>　　printf("%c",gl[i].topvex);</p><p>　　visited_lj[i]=1;</p><p>　　p=gl[i].link;</p><p>　　while(p!=NUL

35、L)</p><p><b>　　{</b></p><p>　　if(visited_lj[p->adjvex]==0)</p><p>　　DFSL(gl,p->adjvex);</p><p>　　p=p->next;</p><p><b>　　}</b&

36、gt;</p><p><b>　　}</b></p><p>　　4.2.2 廣度優(yōu)先遍歷圖的鄰接表</p><p>　　圖的廣度優(yōu)先遍歷是從初始點(diǎn)出發(fā)，訪問初始點(diǎn)，再訪問初始點(diǎn)的鄰接點(diǎn)。當(dāng)初始點(diǎn)的所有鄰接點(diǎn)都被訪問過時(shí)，再依次訪問各鄰接點(diǎn)的鄰接點(diǎn)。如此循環(huán)下去。算法的實(shí)現(xiàn)必須依靠輔助隊(duì)列，結(jié)點(diǎn)被訪問后，對(duì)其進(jìn)行標(biāo)記，并將結(jié)點(diǎn)入隊(duì)列。<

37、/p><p>　　廣度優(yōu)先遍歷的相關(guān)代碼如下：</p><p>　　int visited_ljb[20]={0};</p><p>　　void BFSL(topnode gl[],int k)//鄰接表的廣度遍歷</p><p><b>　　{</b></p><p><b>　　int

38、 i;</b></p><p>　　edgenode *p;</p><p>　　linkqueue Q;</p><p>　　setnull(&Q);</p><p>　　printf("%c",gl[k].topvex);</p><p>　　visited_ljb[k]=1

39、;</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;</p>&l

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

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

42、>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　第五章 源代碼</b></p><p>　　程序 圖的存儲(chǔ)與遍歷</p><p>　　#include<

43、;stdio.h></p><p>　　#include<stdlib.h></p><p>　　typedef int datatype; //datatype可為任何類型，這里假設(shè)為int</p><p>　　typedef char vextype; //頂點(diǎn)的數(shù)據(jù)類型，vextype可為任何類型，這里假設(shè)為char</p>

44、;<p>　　typedef struct pnode</p><p><b>　　{</b></p><p>　　datatype data; //定義鏈表的數(shù)據(jù)域</p><p>　　struct pnode *next; //定義鏈表的指針域</p><p>　　}linklist;</p

45、><p>　　typedef struct</p><p><b>　　{</b></p><p>　　linklist *front,*rear; //用linklist類型定義隊(duì)頭和隊(duì)尾</p><p>　　}linkqueue;</p><p>　　linkqueue *q; //q是鏈

46、隊(duì)列指針</p><p>　　ypedef struct node</p><p><b>　　{</b></p><p>　　int adjvex; //鄰接點(diǎn)域</p><p>　　truct node *next; //鏈域</p><p>　　}edgenode; //邊表結(jié)點(diǎn)

47、</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　vextype topvex; //頂點(diǎn)信息</p><p>　　edgenode *link; //邊表頭指針</p><p>　　}topnode; //頂點(diǎn)表結(jié)點(diǎn)<

48、/p><p>　　topnode gl[20];</p><p>　　void setnull(linkqueue *q)//建立一個(gè)空隊(duì)列</p><p><b>　　{</b></p><p>　　q->front=(linklist *)malloc(sizeof(linklist));</p>&

49、lt;p>　　q->front->next=NULL;</p><p>　　q->rear=q->front;</p><p><b>　　}</b></p><p>　　int empty(linkqueue *q)//判斷隊(duì)列是否為空</p><p><b>　　{</b

50、></p><p>　　if(q->front==q->rear)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p&

51、gt;<b>　　}</b></p><p>　　void enqueue(linkqueue *q,datatype x)//讓元素入棧</p><p><b>　　{</b></p><p>　　q->rear->next=(linklist *)malloc(sizeof(linklist));</

52、p><p>　　q->rear=q->rear->next;</p><p>　　q->rear->data=x;</p><p>　　q->rear->next=NULL;</p><p><b>　　}</b></p><p>　　int dequeue(

53、linkqueue *q)//讓元素出棧</p><p><b>　　{</b></p><p>　　linkqueue *s;</p><p>　　if(empty(q))</p><p><b>　　{</b></p><p>　　printf("隊(duì)為空!&qu

54、ot;);</p><p>　　return NULL;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　s=q->front;</p>

55、<p>　　q->front=q->front->next;</p><p><b>　　free(s);</b></p><p>　　return(q->front->data);</p><p><b>　　}</b></p><p>　　}void c

56、reat_ljbiao(topnode gl[],int n,int e)//無向圖鄰接表的建立</p><p><b>　　{</b></p><p>　　int i,j,k;</p><p>　　edgenode *p;</p><p>　　getchar();</p><p>　　print

57、f("\n請(qǐng)輸入%d個(gè)頂點(diǎn)的元素:",n);</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　scanf("%c",&gl[i].topvex);</p><p>　　gl[i].link=NULL;&

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

59、quot;%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&

60、gt;<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><

61、;/p><p><b>　　}</b></p><p>　　void print_ljbiao(topnode gl[],int n)//鄰接表的輸出</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>

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

63、;/p><p>　　p=gl[i].link;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　printf("%d\t",p->adjvex);</p><p>　　p=p->ne

64、xt;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int visited_lj[20]=

65、{0};</p><p>　　void DFSL(topnode gl[],int i)//鄰接表的深度遍歷</p><p><b>　　{</b></p><p>　　edgenode *p;</p><p>　　printf("%c",gl[i].topvex);</p><p

66、>　　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->adjvex]==0)</p><p>　　DFSL(

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

68、[20]={0};</p><p>　　void BFSL(topnode gl[],int k)//鄰接表的廣度遍歷</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　edgenode *p;</p><p>　　

69、linkqueue Q;</p><p>　　setnull(&Q);</p><p>　　printf("%c",gl[k].topvex);</p><p>　　visited_ljb[k]=1;</p><p>　　enqueue(&Q,k);</p><p>　　while(

70、!empty(&Q))</p><p><b>　　{</b></p><p>　　i=dequeue(&Q);</p><p>　　p=gl[i].link;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></

71、p><p>　　if(!visited_ljb[p->adjvex])</p><p><b>　　{</b></p><p>　　printf("%c",gl[p->adjvex].topvex);</p><p>　　visited_ljb[p->adjvex]=1;</p&g

72、t;<p>　　enqueue(&Q,p->adjve </p><p><b>　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p>

73、<p><b>　　}</b></p><p>　　int visited_jz[20]={0};</p><p>　　void creat_yljbiao(topnode gl[],int n,int e)//有向圖鄰接表的建立</p><p><b>　　{</b></p><p>　

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

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

76、t;<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>

77、;　　p->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>　　void main()&

78、lt;/p><p><b>　　{</b></p><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>

79、<p>　　printf("*****************************鄰接表表示圖的基本操作*****************************\n");</p><p><b>　　while(i)</b></p><p>　　{ printf("\n\t\t\t\t\t菜單:\n");&l

80、t;/p><p>　　printf("\n\t\t\t\t1: 無向圖的操作\n\n\t\t\t\t2: 有向圖的操作\n\n\t\t\t\t0: 結(jié)束圖的操作\n\n請(qǐng)選擇你需要操作的菜單序號(hào):");</p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)

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

82、"\n1:無向圖鄰接表的建立\n2:無向圖鄰接表的輸出\n3:無向圖鄰接表的深度遍歷 \n4:無向圖鄰接表的廣度遍歷\n\n請(qǐng)選擇你需要操作無向圖的序號(hào):");</p><p>　　scanf("%d",&k);</p><p><b>　　switch(k)</b></p><p><b&

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

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

85、gt;　　DFSL(&gl,j); break;</p><p>　　case 4:printf("\n請(qǐng)輸入要遍歷的起始位置:"); scanf("%d",&j);</p><p>　　printf("\n鄰接表廣度遍歷后的結(jié)果為:");</p><p>　　BFSL(&am

86、p;gl,j); break;</p><p><b>　　}</b></p><p>　　printf("\n\n0:結(jié)束無向圖的操作\n1:繼續(xù)無向圖的操作\n");</p><p>　　scanf("%d",&k);</p><p>　　} break;&l

87、t;/p><p>　　case 2://有向圖的基本運(yùn)算</p><p><b>　　while(l)</b></p><p>　　{ printf("\n1:有向圖鄰接表的建立\n2:有向圖鄰接表的輸出\n3:有向圖鄰接表的深度遍歷\n4:有向圖鄰接表的廣度遍歷\n\n請(qǐng)選擇你需要操作有向圖的序號(hào):");</p

88、><p>　　scanf("%d",&l);</p><p><b>　　switch(l)</b></p><p><b>　　{</b></p><p>　　case 1:printf("\n請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):");</p><p

89、>　　scanf("%d%d",&n,&e);</p><p>　　creat_yljbiao(&gl,n,e);</p><p><b>　　break;</b></p><p>　　case 2:print_ljbiao(&gl,n);</p><p><

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

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

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

93、ot;);</p><p>　　scanf("%d",&l);</p><p><b>　　}break;</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><

94、b>　　}</b></p><p>　　第六章 運(yùn)行結(jié)果分析</p><p>　　當(dāng)然在編譯程序的過程中出現(xiàn)了一些錯(cuò)誤，經(jīng)過對(duì)程序的反復(fù)檢查，最后一一的找出了錯(cuò)誤的地方，并予以改正。下面就是無向圖G1和有向圖G2為例的程序運(yùn)行結(jié)果。</p><p>　　圖 1 G 1

95、 圖2 G 2</p><p>　　1 無向圖的建立如 圖1.1 所示</p><p>　　圖1.1無向圖的建立</p><p>　　2 無向圖的輸出如 圖1.2 所示</p><p>　　圖 1.2 無向圖的輸出</p><p>　　3 無向鄰接圖的深度和廣度遍歷的運(yùn)行結(jié)果如 圖 1.3 所示</p

96、><p>　　圖1.3 無向鄰接圖的深度和廣度遍歷</p><p>　　4 有向圖的建立如 圖 2.1 所示</p><p>　　圖 2.1 有向圖的建立</p><p>　　5 有向圖鄰接表的輸出結(jié)果如 圖 2.2 所示</p><p>　　圖 2.2有向圖鄰接表的輸出</p><p>

97、　　6 有向圖鄰接表的深度遍歷和廣度遍歷結(jié)果如 圖2.3 所示</p><p>　　圖 2.3 有向圖鄰接表的深度遍歷和廣度遍歷</p><p><b>　　第七章 結(jié)束語</b></p><p>　　轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(xí)中，自己的C語言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也

98、學(xué)會(huì)了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點(diǎn)體會(huì)：</p><p>　　1.必須牢固掌握基礎(chǔ)知識(shí)。由于C語言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好這學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實(shí)習(xí)之初感到棘手。不知如何下手，但在后來的實(shí)習(xí)過程中自己通過看書和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì)C語言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉。這時(shí)才逐漸有了思路。所以，這次實(shí)習(xí)之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識(shí)。</p

99、><p>　　2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍╊愃朴凇吧倭朔痔?hào)”的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(yīng)如此。</p><p>　　3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路

100、，不至于無章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。</p><p>　　總之，在這次實(shí)習(xí)中，自己的C語言以及數(shù)據(jù)結(jié)構(gòu)知識(shí)得到提高，編程能力也得到了提高。</p><p><b>　　第八章 參考文獻(xiàn)</b></p><p>　　譚浩強(qiáng) .C程序設(shè)計(jì) . 北京：清華大學(xué)出版社，2006.</p><p>　　徐孝凱 . 數(shù)據(jù)結(jié)構(gòu)