版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、<p> 數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計</p><p> 設(shè)計題目: 圖的鄰接表存儲及其應(yīng)用 </p><p> 課題名稱圖的鄰接表存儲及其應(yīng)用</p><p> 院 系年級專業(yè)</p><p> 學 號</p><p> 課題設(shè)計目的與設(shè)計意義課題設(shè)計目的:一、是讓我們通過實習
2、掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識。對于《圖的遍歷》這一課題來說,所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識主要有:圖的鄰接表存貯結(jié)構(gòu)、隊列的基本運算實現(xiàn)、鄰接表的算法實現(xiàn)、圖的廣度優(yōu)先搜索、圖的深度優(yōu)先搜索算法實現(xiàn)。 二、是通過實習鞏固并提高實習者的C語言知識,并初步了解C++的知識,提高編程能力與專業(yè)水平。2、課題設(shè)計意義:一、通過對鄰接表表示圖及深廣度優(yōu)先遍歷程序的編寫,對數(shù)據(jù)結(jié)構(gòu)的理解更為加深。二、培養(yǎng)了我們獨立設(shè)計程序與解決問
3、題的能力,培養(yǎng)了我們團隊協(xié)作集成程序模塊及調(diào)試能力。三、培養(yǎng)了學生初步的軟件設(shè)計及軟件測試的能力。指導(dǎo)教師:年 月 日</p><p><b> 目 錄</b></p><p> 第一章 課程設(shè)計目的1</p><p> 第二章 課程設(shè)計內(nèi)容和要求1</p><p> 2.1課程設(shè)計內(nèi)容1&l
4、t;/p><p> 2.1.1圖的鄰接表的建立與輸出1</p><p> 2.1.2 圖的遍歷的實現(xiàn)1</p><p> 2.2 運行環(huán)境1</p><p> 第三章 課程設(shè)計分析2</p><p><b> 3.1圖的存儲2</b></p><p> 3
5、.2 圖的遍歷2</p><p> 3.2.1 圖的深度優(yōu)先遍歷2</p><p> 3.2.2 圖的廣度優(yōu)先遍歷2</p><p> 第四章 算法(數(shù)據(jù)結(jié)構(gòu))描述3</p><p> 4.1 圖的存儲結(jié)構(gòu)的建立。3</p><p> 4.1.1 定義鄰接表的邊結(jié)點類型以及鄰接表類型3</p
6、><p> 4.1.2 初始化圖的鄰接表3</p><p> 4.1.3 建立并輸出圖的鄰接表3</p><p> 4.2 圖的遍歷5</p><p> 4.2.1 深度優(yōu)先遍歷圖的鄰接表5</p><p> 4.2.2 廣度優(yōu)先遍歷圖的鄰接表6</p><p><b>
7、; 第五章 源代碼7</b></p><p> 第六章 運行結(jié)果分析13</p><p> 第七章 結(jié)束語17</p><p> 第八章 參考文獻19</p><p> 第一章 課程設(shè)計目的</p><p> 本學期我們對《數(shù)據(jù)結(jié)構(gòu)》這門課程進行了學習。這門課程是一門實踐性非常強的課程,
8、為了讓大家更好地理解與運用所學知識,提高動手能力,我們進行了此次課程設(shè)計實習。這次課程設(shè)計不但要求實習者掌握《數(shù)據(jù)結(jié)構(gòu)》中的各方面知識,還要求實習者具備一定的C語言基礎(chǔ)和編程能力。</p><p> 具體說來,這次課程設(shè)計主要有兩大方面目的。</p><p> 一是讓實習者通過實習掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識。對于《圖的遍歷》這一課題來說,所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識主要有:圖的鄰接表存貯結(jié)構(gòu)
9、、隊列的基本運算實現(xiàn)、鄰接表的算法實現(xiàn)、圖的廣度優(yōu)先搜索周游算法實現(xiàn)、圖的深度優(yōu)先搜索周游算法實現(xiàn)。</p><p> 二是通過實習鞏固并提高實習者的C語言知識,并初步了解Visual C++的知識,提高其編程能力與專業(yè)水平。</p><p> 第二章 課程設(shè)計內(nèi)容和要求</p><p><b> 2.1課程設(shè)計內(nèi)容</b></p&
10、gt;<p> 該課題要求以鄰接表的方式存儲圖,輸出鄰接表,并要求實現(xiàn)圖的深度、廣度兩種遍歷。</p><p> 2.1.1圖的鄰接表的建立與輸出</p><p> 對任意給定的圖(頂點數(shù)和邊數(shù)自定),并且對有向圖與無向圖都應(yīng)進行討論,根據(jù)鄰接表的存儲結(jié)構(gòu)建立圖的鄰接表并輸出之。盡量用圖形化的方式輸出鄰接表。</p><p> 2.1.2 圖的
11、遍歷的實現(xiàn)</p><p> 圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對于廣度優(yōu)先遍歷應(yīng)利用隊列的五種基本運算(置空隊列、進隊、出隊、取隊頭元素、判隊空)來實現(xiàn)。首先建立一空隊列,從初始點出發(fā)進行訪問,當被訪問時入隊,訪問完出隊。并以隊列是否為空作為循環(huán)控制條件。對于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來實現(xiàn)。</p><p><b> 2.2 運行環(huán)境</b>
12、</p><p> 該程序的運行環(huán)境為Windows xp系統(tǒng),Microsoft Visual C++6.0版本。</p><p> 第三章 課程設(shè)計分析</p><p><b> 3.1圖的存儲</b></p><p> 本課題要求采取鄰接表的存儲結(jié)構(gòu)。鄰接表是一種鏈式的存儲結(jié)構(gòu),在鄰接表中,對圖中每個頂點建
13、立一個單鏈表,第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊(對有向圖是以頂點Vi為尾的在圖中的位置,鏈域(nextarc)指示下一條?。C總€結(jié)點由3個域組成,其中鄰接點域(adjvex)指示與頂點Vi鄰接的點在圖中的位置,鏈域(nextarc)指示下一條邊或弧的結(jié)點;數(shù)據(jù)域(info)存儲和邊或弧相關(guān)的信息,如權(quán)值等。</p><p> 所以一開始必須先定義鄰接表的邊結(jié)點類型以及鄰接表類型,并對鄰接表進行初始化
14、,然后根據(jù)所輸入的相關(guān)信息,包括圖的頂點數(shù)、邊數(shù)、是否為有向,以及各條邊的起點與終點序號,建立圖的鄰接表。此時要分兩種情況:有向圖與無向圖。對于無向圖,一條邊的兩的個頂點,互為鄰接點,所以在存儲時,應(yīng)向起點的單鏈表表頭插入一邊結(jié)點,即終點。同時將終點的單鏈表表頭插入一邊結(jié)點,即起點。對于有向圖,只能向起點的單鏈表的表頭插入一個邊結(jié)點,即終點。但不能反過來。至于鄰接表的輸出,由于不了解C++中的繪圖操作,故采用for語句輸出各結(jié)點,并配合
15、一些符號完成鄰接表的輸出。</p><p><b> 3.2 圖的遍歷</b></p><p> 3.2.1 圖的深度優(yōu)先遍歷</p><p> 假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問,深度優(yōu)先遍歷可以從圖的初始點出發(fā),訪問初始點,然后依次從v未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖,直至圖中所有和v有路徑相通的頂點都被訪問到;若此時仍有頂點未被
16、訪問到,則從另一個未被訪問的頂點出發(fā),重復(fù)上述過程,直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標志數(shù)組以標記結(jié)點是否被訪問。</p><p> 具體過程應(yīng)為:先訪問初始點Vi,并標志其已被訪問。此時定義一指向邊結(jié)點的指針p,并建立一個while()循環(huán),以指針所指對象不為空為控制條件,當Vi的鄰接點未被訪問時,遞歸調(diào)
17、用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍歷了。</p><p> 3.2.2 圖的廣度優(yōu)先遍歷</p><p> 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點v出發(fā),在訪問了v之后訪問它們的鄰接點,并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問,直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖
18、中尙有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點,重復(fù)上述過程,直到圖中所有頂點都被訪問到為止。換句話說,廣度優(yōu)先搜索遍歷圖的過程是以v為起始點,由近及遠,依次訪問和v有路徑相通且路徑長度為1,2,……的頂點。</p><p> 所以要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列,并定義隊首與隊尾指針,同時也要定義一個標志數(shù)組以標記結(jié)點是否被訪問。同樣,也是從初始點出發(fā)開始訪問,訪問初始點,標志其已被
19、訪問,并將其入隊。當隊列非空時進行循環(huán)處理。當結(jié)點被訪問時對其進行標志,并入隊列。通過while()循環(huán),并以是否被訪問為控制條件,訪問所有結(jié)點,完成圖的廣度優(yōu)先遍歷。</p><p> 第四章 算法(數(shù)據(jù)結(jié)構(gòu))描述</p><p> 4.1 圖的存儲結(jié)構(gòu)的建立。</p><p> 4.1.1 定義鄰接表的邊結(jié)點類型以及鄰接表類型</p><
20、;p> struct edgenode{</p><p> int adjvex; //該弧所指向的頂點的位置</p><p> 4.1.2 初始化圖的鄰接表</p><p> 需建立一個鄰接表初始化函數(shù)對圖的鄰接表進行初始化。即建立一個所有邊結(jié)點都為空的鄰#include<stdio.h></p>
21、<p> 4.1.3 建立并輸出圖的鄰接表</p><p> 首先必須輸入圖的相關(guān)信息,包括圖的頂點數(shù)、邊數(shù)。圖分為有向圖和無向圖。對于無向圖,各條邊的起點和終點互為鄰接點。所以必須把起點添加到終點的鄰接點域中,并把終點添加到起點的鄰接點域中。而對于有向圖,只能是將弧頭添加到弧尾的鄰接點域中。最后是輸出鄰接表,即對于每個頂點,輸出其鄰接點。由于不了解C++中繪圖函數(shù)的用法,所以利用一些符號來達到圖
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請輸入%d個頂點的元素:",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請輸入要鄰接的倆個頂點的下標:\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)是圖中所有頂點未曾被訪問,深度優(yōu)先遍歷可以從圖的初始點出發(fā),訪問初始點,然后依次從v未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖,直至圖中所有和v有路徑相通的頂點都被訪問到;若此時仍有頂點未被訪問到,
32、則從另一個未被訪問的頂點出發(fā),重復(fù)上述過程,直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標志數(shù)組以標記結(jié)點是否被訪問。</p><p> 具體過程應(yīng)為:先訪問初始點Vi,并標志其已被訪問。此時定義一指向邊結(jié)點的指針p,并建立一個while()循環(huán),以指針所指對象不為空為控制條件,當Vi的鄰接點未被訪問時,遞歸調(diào)用深度優(yōu)
33、先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(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)先遍歷是從初始點出發(fā),訪問初始點,再訪問初始點的鄰接點。當初始點的所有鄰接點都被訪問過時,再依次訪問各鄰接點的鄰接點。如此循環(huán)下去。算法的實現(xiàn)必須依靠輔助隊列,結(jié)點被訪問后,對其進行標記,并將結(jié)點入隊列。<
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> 程序 圖的存儲與遍歷</p><p> #include<
43、;stdio.h></p><p> #include<stdlib.h></p><p> typedef int datatype; //datatype可為任何類型,這里假設(shè)為int</p><p> typedef char vextype; //頂點的數(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類型定義隊頭和隊尾</p><p> }linkqueue;</p><p> linkqueue *q; //q是鏈
46、隊列指針</p><p> ypedef struct node</p><p><b> {</b></p><p> int adjvex; //鄰接點域</p><p> truct node *next; //鏈域</p><p> }edgenode; //邊表結(jié)點
47、</p><p> typedef struct</p><p><b> {</b></p><p> vextype topvex; //頂點信息</p><p> edgenode *link; //邊表頭指針</p><p> }topnode; //頂點表結(jié)點<
48、/p><p> topnode gl[20];</p><p> void setnull(linkqueue *q)//建立一個空隊列</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)//判斷隊列是否為空</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("隊為空!&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請輸入%d個頂點的元素:",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請輸入要鄰接的倆個頂點的下標:\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請輸入%d個頂點的元素:",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請輸入要鄰接的倆個頂點的下標:\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請選擇你需要操作的菜單序號:");</p><p> scanf("%d",&i);</p><p><b> switch(i)
81、</b></p><p><b> {</b></p><p> case 1://無向圖的基本運算</p><p><b> while(k)</b></p><p><b> { </b></p><p> printf(
82、"\n1:無向圖鄰接表的建立\n2:無向圖鄰接表的輸出\n3:無向圖鄰接表的深度遍歷 \n4:無向圖鄰接表的廣度遍歷\n\n請選擇你需要操作無向圖的序號:");</p><p> scanf("%d",&k);</p><p><b> switch(k)</b></p><p><b&
83、gt; {</b></p><p> case 1:printf("\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請輸入要遍歷的起始位置:"); scanf("%d",&j);</p><p> printf("\n鄰接表深度遍歷后的結(jié)果為:");</p><p&
85、gt; DFSL(&gl,j); break;</p><p> case 4:printf("\n請輸入要遍歷的起始位置:"); 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://有向圖的基本運算</p><p><b> while(l)</b></p><p> { printf("\n1:有向圖鄰接表的建立\n2:有向圖鄰接表的輸出\n3:有向圖鄰接表的深度遍歷\n4:有向圖鄰接表的廣度遍歷\n\n請選擇你需要操作有向圖的序號:");</p
88、><p> scanf("%d",&l);</p><p><b> switch(l)</b></p><p><b> {</b></p><p> case 1:printf("\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請輸入要遍歷的起始位置:");</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請輸入要遍歷的起始位置:");</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> 第六章 運行結(jié)果分析</p><p> 當然在編譯程序的過程中出現(xiàn)了一些錯誤,經(jīng)過對程序的反復(fù)檢查,最后一一的找出了錯誤的地方,并予以改正。下面就是無向圖G1和有向圖G2為例的程序運行結(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 無向鄰接圖的深度和廣度遍歷的運行結(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è)計實習即將結(jié)束了。在這次實習中,自己的C語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固,編程能力也有了一定的提高。同時也
98、學會了解決問題的方法。總結(jié)起來,自己主要有以下幾點體會:</p><p> 1.必須牢固掌握基礎(chǔ)知識。由于C語言是大一所學知識,有所遺忘,且未掌握好這學期所學的《數(shù)據(jù)結(jié)構(gòu)》這門課,所以在實習之初感到棘手。不知如何下手,但在后來的實習過程中自己通過看書和課外資料,并請教其他同學,慢慢地對C語言和數(shù)據(jù)結(jié)構(gòu)知識有所熟悉。這時才逐漸有了思路。所以,這次實習之后,我告誡自己:今后一定要牢固掌握好專業(yè)基礎(chǔ)知識。</p
99、><p> 2.必須培養(yǎng)嚴謹?shù)目茖W態(tài)度。自己在編程時經(jīng)常因為一些類似于“少了分號”的小錯誤而導(dǎo)致錯誤,不夠認真細致,這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑?,容不得馬虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)目茖W態(tài)度。我想這不僅是對于程序設(shè)計,做任何事都應(yīng)如此。</p><p> 3.這次課程設(shè)計也讓我充分認識到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個思想和大綱,讓我們在編程時容易找到思路
100、,不至于無章可循。同時它也有廣泛的實際應(yīng)用。</p><p> 總之,在這次實習中,自己的C語言以及數(shù)據(jù)結(jié)構(gòu)知識得到提高,編程能力也得到了提高。</p><p><b> 第八章 參考文獻</b></p><p> 譚浩強 .C程序設(shè)計 . 北京:清華大學出版社,2006.</p><p> 徐孝凱 . 數(shù)據(jù)結(jié)構(gòu)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)庫課程設(shè)計---數(shù)據(jù)庫
- 數(shù)據(jù)庫課程設(shè)計--學生課程數(shù)據(jù)庫的設(shè)計與實現(xiàn)
- 數(shù)據(jù)庫課程設(shè)計--數(shù)據(jù)庫設(shè)計
- 數(shù)據(jù)庫課程設(shè)計--數(shù)據(jù)庫原理及應(yīng)用課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計---學生選題數(shù)據(jù)庫的設(shè)計與實現(xiàn)
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計---網(wǎng)上拍賣數(shù)據(jù)庫設(shè)計
- 數(shù)據(jù)庫課程設(shè)計--bbs系統(tǒng)數(shù)據(jù)庫設(shè)計
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計--學生選題數(shù)據(jù)庫的設(shè)計與實現(xiàn)
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計
- 數(shù)據(jù)庫課程設(shè)計--cd唱片數(shù)據(jù)庫設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷
- 數(shù)據(jù)庫原理課程設(shè)計---個人事物管理數(shù)據(jù)庫課程設(shè)計
- 《圖的建立與遍歷》數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
評論
0/150
提交評論