數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-圖的鄰接矩陣

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　設(shè)計(jì)題目： 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)</p><p>　　院 系 計(jì)算機(jī)學(xué)院 </p><p>　　年 級 x 級 </p><p&

2、gt;　　學(xué) 生 xxxx </p><p>　　學(xué) 號 xxxxxxxxxx </p><p>　　指導(dǎo)教師 xxxxxxxxx </p><p>　　起止時(shí)間 10-6/10-10 </p><p>　　2013年10月10日</p><p><b&g

3、t;　　目 錄 </b></p><p><b>　　1 需求分析4</b></p><p><b>　　2 概要設(shè)計(jì)4</b></p><p>　　2.1 ADT描述4</p><p>　　2.2程序模塊結(jié)構(gòu)5</p><p>　　2.3　各功能模塊

4、6</p><p><b>　　3　詳細(xì)設(shè)計(jì)7</b></p><p><b>　　3.1類的定義7</b></p><p><b>　　3.2 初始化8</b></p><p>　　3.3 圖的構(gòu)建操作8</p><p>　　3.4 輸出操作

5、9</p><p>　　3.5 get操作9</p><p>　　3.6 插入操作10</p><p>　　3.7 刪除操作10</p><p>　　3.8 求頂點(diǎn)的度操作11</p><p>　　3.9 深度遍歷作……………………………………………………………………………...11</p>&

6、lt;p>　　3.10 判斷連通操作12</p><p>　　3.11 主函數(shù)13</p><p><b>　　4 調(diào)試分析16</b></p><p>　　4.1調(diào)試問題16</p><p>　　4.2 算法時(shí)間復(fù)雜度16</p><p><b>　　5　用戶手冊16

7、</b></p><p><b>　　5.1主界面16</b></p><p>　　5.2 創(chuàng)建圖17</p><p>　　5.3插入節(jié)點(diǎn)17</p><p>　　5.4 深度優(yōu)先遍歷17</p><p>　　5.5 求各頂點(diǎn)的度18</p><p>

8、　　5.6 輸出圖18</p><p>　　5.7 判斷是否連通19</p><p>　　5.8 求邊的權(quán)值19</p><p>　　5.9 插入邊19</p><p>　　5.10 刪除邊20</p><p><b>　　結(jié) 論20</b></p><p>

9、　　參考文獻(xiàn)……………………………………………………………………………………………………………………………………..20</p><p><b>　　摘 要 </b></p><p>　　隨著計(jì)算機(jī)的普及，涉及計(jì)算機(jī)相關(guān)的科目也越來越普遍，其中數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，為適應(yīng)我國計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展和應(yīng)用，學(xué)好數(shù)據(jù)結(jié)構(gòu)非常必要，然而要掌

10、握數(shù)據(jù)結(jié)構(gòu)的知識非常難，所以對“數(shù)據(jù)結(jié)構(gòu)”的課程設(shè)計(jì)比不可少。本說明書是對“無向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)”課程設(shè)計(jì)的說明。</p><p>　　首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務(wù)和相應(yīng)的分析，并給出測試數(shù)據(jù)。其次是概要設(shè)計(jì)，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關(guān)系，以及ADT描述。然后是詳細(xì)設(shè)計(jì)，描述實(shí)現(xiàn)概要設(shè)計(jì)中定義的基本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實(shí)現(xiàn)。再次

11、是對系統(tǒng)的調(diào)試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測試的數(shù)據(jù)和結(jié)果的分析，最后是對本次課程設(shè)計(jì)的結(jié)論。</p><p>　　關(guān)鍵詞：網(wǎng)絡(luò)化；計(jì)算機(jī)；對策；圖；儲(chǔ)存。 </p><p><b>　　1 需求分析 </b></p><p>　　隨著計(jì)算機(jī)的普及,信息的存儲(chǔ)逐漸和我們的日常生活變得密切起來，

12、而數(shù)據(jù)的存儲(chǔ)方式也多種多樣，比如樹、鏈表、數(shù)組、圖等等。</p><p>　　為了充分體現(xiàn)圖的矩陣儲(chǔ)存結(jié)構(gòu)的優(yōu)勢與功能，要求本系統(tǒng)應(yīng)達(dá)到以下要求：</p><p><b>　　圖是無向帶權(quán)圖</b></p><p>　　能從鍵盤上輸入各條邊和邊上的權(quán)值；</p><p>　　構(gòu)造圖的鄰接矩陣和頂點(diǎn)集。</p>

13、<p>　　輸出圖的各頂點(diǎn)和鄰接矩陣</p><p><b>　　插入一條邊</b></p><p><b>　　刪除一條邊</b></p><p><b>　　求出各頂點(diǎn)的度</b></p><p>　　判斷該圖是否是連通圖，若是，返回1；否則返回0.</

14、p><p>　　使用深度遍歷算法，輸出遍歷序列。</p><p><b>　　2 概要設(shè)計(jì) </b></p><p><b>　　2.1 ADT描述</b></p><p>　　ADT Glist </p><p><b>　　{</b></p&g

15、t;<p>　　{VR}={圖的頂點(diǎn)和邊}</p><p>　　VR={<v,w> | v,w∈V, <v,w>表示頂點(diǎn)v和w間的邊；}</p><p><b>　　基本操作：</b></p><p><b>　　初始化空圖；</b></p><p><

16、b>　　輸入建立圖；</b></p><p><b>　　深度優(yōu)先遍歷圖；</b></p><p>　　確定圖中的頂點(diǎn)數(shù)目；</p><p><b>　　確定圖中邊的數(shù)目；</b></p><p>　　在圖中插入一個(gè)頂點(diǎn)；</p><p><b>

17、　　在圖中插入一條邊；</b></p><p><b>　　刪除圖中一個(gè)頂點(diǎn)</b></p><p><b>　　刪除圖中的一條邊；</b></p><p><b>　　求頂點(diǎn)的度；</b></p><p><b>　　求最小生成樹；</b>&

18、lt;/p><p>　　} ADT Graph;</p><p>　　2.2程序模塊結(jié)構(gòu) </p><p><b>　　圖2.1：模塊結(jié)構(gòu)</b></p><p>　　2.2.1　結(jié)構(gòu)體定義</p><p>　　本系統(tǒng)未采用結(jié)構(gòu)體方法，類的定義如下：</p><p>　　定義

19、頂點(diǎn): nodecount，edgecount 邊：已經(jīng)分別存放頂點(diǎn)和邊的兩個(gè)數(shù)組： a[MaxNode]和 b[MaxNode][MaxNode];其余成員函數(shù)均以public形式聲明。在鄰接矩陣表示的圖中，頂點(diǎn)信息用一維數(shù)組表示a[]。在簡單情況下可省略，僅以下標(biāo)值代表頂點(diǎn)序號。若需要，頂點(diǎn)信息更加豐富。邊（或?。┬畔⒂枚S數(shù)組表示b[ ][ ]，這也是鄰接矩陣。包含邊的權(quán)值。在類中數(shù)據(jù)成員有4個(gè)，重要的是鄰接矩陣Edge[ ][

20、]、總邊數(shù)edgecount和頂點(diǎn)數(shù)nodecount。</p><p>　　class Graph1 </p><p><b>　　{</b></p><p><b>　　private:</b></p><p>　　int nodecount;//節(jié)點(diǎn)</p><p>

21、　　int edgecount;//邊</p><p>　　int a[MaxNode];//頂點(diǎn)信息組</p><p>　　//set<int> a;</p><p>　　int b[MaxNode][MaxNode];//權(quán)值信息組</p><p><b>　　public:</b></p>

22、<p>　　Graph1(int);//構(gòu)造函數(shù)</p><p>　　int getNodeCount();//當(dāng)前的節(jié)點(diǎn)數(shù)</p><p>　　int getEdgeCount();//當(dāng)前的邊數(shù)</p><p>　　void insertNode(int);//插入一個(gè)節(jié)點(diǎn)</p><p>　　void isertEdge(i

23、nt ,int ,int);//插入一條邊</p><p>　　void deleteEdge(int,int);//刪除一條邊</p><p>　　bool isliantong();//判斷是否連通</p><p>　　int getWeight(int,int);//獲得某條邊的權(quán)值</p><p>　　int Depth(int );

24、//深度遍歷準(zhǔn)備，用于建立頂點(diǎn)訪問數(shù)組和記錄所訪問頂點(diǎn)個(gè)數(shù)</p><p>　　void Depth(int v,int visited[],int &n);//深度遍歷</p><p>　　void outDu(Graph1 G);//輸出節(jié)點(diǎn)個(gè)數(shù)</p><p>　　void PrintOut(Graph1 G) ;//輸出圖</p>&

25、lt;p>　　void CreatG(int n,int e);//建立圖</p><p><b>　　};</b></p><p><b>　　2.3　各功能模塊</b></p><p>　　以下將以注釋形式為每個(gè)函數(shù)的功能進(jìn)行聲明：</p><p>　　構(gòu)造函數(shù)：Graph1(int)

26、 用于初始化圖 </p><p>　　get函數(shù)：int getNodeCount();得到當(dāng)前的節(jié)點(diǎn)數(shù)</p><p>　　get函數(shù)：int getWeight(int,int);獲得某條邊的權(quán)值</p><p>　　get函數(shù)：int getEdgeCount();得到當(dāng)前的邊數(shù)</p><p>　　插入函數(shù)：void insertN

27、ode(int);插入一個(gè)節(jié)點(diǎn)</p><p>　　插入函數(shù)：void isertEdge(int ,int ,int);插入一條邊</p><p>　　刪除函數(shù)：void deleteEdge(int,int);刪除一條邊</p><p>　　判斷函數(shù)：bool isliantong();判斷是否連通</p><p>　　遍歷函數(shù)1：int

28、 Depth(int );//深度遍歷準(zhǔn)備，用于建立頂點(diǎn)訪問數(shù)組和記錄所訪問頂點(diǎn)個(gè)數(shù)</p><p>　　遍歷函數(shù)2：void Depth(int v,int visited[],int &n);//深度遍歷</p><p>　　求度函數(shù)：void outDu(Graph1 G);輸出節(jié)點(diǎn)個(gè)數(shù)</p><p>　　輸出函數(shù)：void PrintOut(Gr

29、aph1 G) ;輸出圖</p><p>　　構(gòu)建函數(shù)：void CreatG(int n,int e);建立圖</p><p><b>　　3　詳細(xì)設(shè)計(jì)</b></p><p><b>　　3.1類的定義</b></p><p>　　class Graph1 </p><p

30、><b>　　{</b></p><p><b>　　private:</b></p><p>　　int nodecount;//節(jié)點(diǎn)</p><p>　　int edgecount;//邊</p><p>　　int a[MaxNode];//頂點(diǎn)信息組</p><p&

31、gt;　　//set<int> a;</p><p>　　int b[MaxNode][MaxNode];//權(quán)值信息組</p><p><b>　　public:</b></p><p>　　Graph1(int);//構(gòu)造函數(shù)</p><p>　　int getNodeCount();//當(dāng)前的節(jié)點(diǎn)數(shù)&l

32、t;/p><p>　　int getEdgeCount();//當(dāng)前的邊數(shù)</p><p>　　void insertNode(int);//插入一個(gè)節(jié)點(diǎn)</p><p>　　void isertEdge(int ,int ,int);//插入一條邊</p><p>　　void deleteEdge(int,int);//刪除一條邊</p

33、><p>　　void prim(int);//生成最小樹</p><p>　　bool isliantong();//判斷是否連通</p><p>　　int getWeight(int,int);//獲得某條邊的權(quán)值</p><p>　　int Depth(int );//深度遍歷準(zhǔn)備，用于建立頂點(diǎn)訪問數(shù)組和記錄所訪問頂點(diǎn)個(gè)數(shù)</p&g

34、t;<p>　　void Depth(int v,int visited[],int &n);//深度遍歷</p><p>　　void outDu(Graph1 G);//輸出節(jié)點(diǎn)個(gè)數(shù)</p><p>　　void PrintOut(Graph1 G) ;//輸出圖</p><p>　　void CreatG(int n,int e);

35、//建立圖</p><p><b>　　};</b></p><p><b>　　3.2 初始化</b></p><p>　　初始化鄰接矩陣以及有關(guān)參數(shù)，通過for循環(huán)將數(shù)組的值都初始化為0，使之成為一個(gè)空圖。</p><p>　　Graph1::Graph1(int s=MaxNode)//構(gòu)造函

36、數(shù)</p><p><b>　　{</b></p><p>　　for(int i=0;i<=s-1;i++)</p><p>　　for(int j=0;j<=s-1;j++)</p><p>　　b[i][j]=0;</p><p>　　nodecount=0;</p>

37、<p>　　for(int k=0;k<=s-1;k++)</p><p><b>　　a[k]=-1;</b></p><p><b>　　}</b></p><p>　　3.3 圖的構(gòu)建操作</p><p>　　在主函數(shù)中要求輸入需要構(gòu)建的圖的頂點(diǎn)數(shù)和邊數(shù)，調(diào)用構(gòu)建函數(shù)，分別

38、用兩個(gè)for語句來構(gòu)建圖（即輸入頂點(diǎn)的值和邊的權(quán)值），此處要求輸入有一定的順序，不能隨意輸入。</p><p>　　void Graph1::CreatG(int n,int e) </p><p>　　{ int i,vi,vj,w; </p><p>　　edgecount=e;

39、 </p><p>　　nodecount=n;</p><p>　　cout<<endl<<" 輸入頂點(diǎn)的信息（暫設(shè)為整型）：" ;</p><p>　　for ( i=0; i<nodecount; i++ ) </p><p>　　{ cout<<

40、;"\n "<<i+1<<": "; cin>>a[i]; }</p><p>　　for ( i=0; i<edgecount; i++ ) //輸入兩個(gè)頂點(diǎn)編號和邊權(quán)值</p><p>　　{ cout<<endl<<" 輸入邊的信息（vi,vj,

41、w）："<<endl;; </p><p>　　cin>>vi>>vj>>w;</p><p>　　b[vi-1][vj-1]=w; </p><p>　　b[vj-1][vi-1]=w; }</p><p><b>　　}</b>&

42、lt;/p><p><b>　　3.4 輸出操作</b></p><p>　　本函數(shù)通過傳過來的對象G得到相關(guān)數(shù)組，通過for循環(huán)來分別輸出頂點(diǎn)數(shù)組和邊的權(quán)值數(shù)組（鄰接矩陣）。</p><p>　　void Graph1::PrintOut(Graph1 G) </p><p><b&g

43、t;　　{ int i;</b></p><p>　　cout<<"\n 輸出頂點(diǎn)的信息："<<endl;</p><p>　　for ( i=0; i<G.getNodeCount(); i++ ) cout<<G.a[i]<<" ";</p><p&g

44、t;　　cout<<endl<<"\n 輸出鄰接矩陣：" ;</p><p>　　for ( i=0; i<G.getNodeCount(); i++ )</p><p>　　{ cout<<endl<<i+1<<": ";</p><p>　　for (

45、 int j=0; j<G.getNodeCount() ;j++ ) cout<<G.b[i][j]<<" ";</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p>

46、<p><b>　　3.5 get操作</b></p><p>　　用于得到圖的頂點(diǎn)數(shù)、邊數(shù)、權(quán)值</p><p>　　int Graph1::getNodeCount()//當(dāng)前的節(jié)點(diǎn)數(shù)</p><p><b>　　{</b></p><p>　　return nodecount;&l

47、t;/p><p><b>　　}</b></p><p>　　int Graph1::getEdgeCount()//當(dāng)前的邊數(shù)</p><p><b>　　{</b></p><p>　　return edgecount;</p><p><b>　　} </b

48、></p><p>　　int Graph1::getWeight(int x,int y)//獲得某條邊的權(quán)值</p><p><b>　　{</b></p><p>　　return b[x-1][y-1];</p><p><b>　　}</b></p><p>

49、<b>　　3.6 插入操作</b></p><p>　　插入頂點(diǎn)：通過將傳來的值（頂點(diǎn)值）賦到一個(gè)當(dāng)前頂點(diǎn)數(shù)下一個(gè)的數(shù)組元素中實(shí)現(xiàn)插入功能，此時(shí)頂點(diǎn)樹加1。</p><p>　　插入邊：原理與插入頂點(diǎn)相同，通過傳過來的兩個(gè)頂點(diǎn)信息與權(quán)值進(jìn)行相應(yīng)賦值，不過此時(shí)應(yīng)該注意表示同一條邊的兩個(gè)數(shù)組都該賦值。</p><p>　　void Graph1:

50、:insertNode(int it)//插入一個(gè)節(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　a[nodecount++]=it;</p><p>　　cout<<"當(dāng)前節(jié)點(diǎn)數(shù)為："<<nodecount<<endl;</p><p><

51、b>　　}</b></p><p>　　void Graph1::isertEdge(int x,int y,int w)//插入一條邊</p><p><b>　　{</b></p><p>　　b[x-1][y-1]=w;</p><p>　　b[y-1][x-1]=w;</p>&l

52、t;p>　　cout<<"該邊插入成功! "<<endl;</p><p>　　edgecount++;</p><p><b>　　}</b></p><p><b>　　3.7 刪除操作</b></p><p>　　將相應(yīng)的數(shù)組值賦為0從而達(dá)到刪

53、除目的。</p><p>　　void Graph1::deleteEdge(int x ,int y)//刪除一條邊</p><p><b>　　{</b></p><p>　　b[x-1][y-1]=0;</p><p>　　b[y-1][x-1]=0;</p><p>　　cout<&

54、lt;"邊("<<x<<","<<y<<")已經(jīng)成功刪除!";</p><p>　　edgecount--;</p><p><b>　　}</b></p><p>　　3.8 求頂點(diǎn)的度操作</p><p>　　

55、通過兩個(gè)for循環(huán)來查找各頂點(diǎn)，判斷其是否有邊（權(quán)值），有邊的話又有幾條邊，每找到一條邊則度數(shù)加一，記錄到存放頂點(diǎn)的度數(shù)的數(shù)組M[]中，搜索完成后輸出各頂點(diǎn)的度。</p><p>　　void Graph1::outDu(Graph1 G)//輸出各點(diǎn)的度</p><p><b>　　{</b></p><p>　　int m[Max]={0}

56、,k,i;</p><p>　　for(k=0;k<G.getNodeCount();k++)</p><p>　　for(i=0;i<G.getNodeCount();i++)</p><p><b>　　{</b></p><p>　　if(G.b[k][i]!=0)</p><p&g

57、t;<b>　　m[k]++;</b></p><p><b>　　}</b></p><p>　　cout<<"各點(diǎn)的度："<<endl;</p><p>　　for(i=0;i<G.getNodeCount();i++)</p><p><

58、b>　　{</b></p><p>　　cout<<"頂點(diǎn)"<<i<<"的度："<<m[i]<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p>

59、<p>　　3.9 深度遍歷操作</p><p>　　圖的深度優(yōu)先遍歷DFS算法是沿著某初始頂點(diǎn)出發(fā)的一條路徑，盡可能深入地前進(jìn)，即每次在訪問完當(dāng)前頂點(diǎn)后，首先訪問當(dāng)前頂點(diǎn)的一個(gè)未被訪問過的鄰接頂點(diǎn)，然后去訪問這個(gè)鄰接點(diǎn)的一個(gè)未被訪問過的鄰接點(diǎn)，這是一個(gè)遞歸算法。</p><p>　　其中第一個(gè)遍歷函數(shù)Depth(int node)其主要作用是構(gòu)建訪問數(shù)組int v[]，以及

60、調(diào)用核心遍歷函數(shù)Depth(int v,int visited[],int &n)，其中的n是用來記錄訪問的頂點(diǎn)數(shù)目，用于判斷圖的連通性。</p><p>　　int Graph1::Depth(int node)</p><p><b>　　{</b></p><p><b>　　int n=0;</b><

61、/p><p>　　int v[MaxNode];</p><p>　　for(int i=0;i<=nodecount-1;i++)</p><p><b>　　v[i]=0;</b></p><p>　　Depth(node,v,n);</p><p>　　return n;//n記錄訪問節(jié)點(diǎn)

62、數(shù)，用于判斷是否連通</p><p><b>　　}</b></p><p>　　void Graph1::Depth(int v,int visited[],int &n)</p><p>　　{ cout<<" "<<v+1<<" " ;//訪問頂點(diǎn)v&l

63、t;/p><p>　　visited[v]=1; //標(biāo)記頂點(diǎn)v已訪問</p><p>　　n++;//n記錄訪問節(jié)點(diǎn)數(shù)</p><p>　　for (int col=0; col<nodecount; col++)</p><p>　　{ if (b[v][col]==0||b[v][col]==Max) </p><

64、;p>　　continue; //找v一個(gè)鄰接點(diǎn)col</p><p>　　if (!visited[col]) Depth(col, visited,n); </p><p>　　//調(diào)用深度遞歸遍歷</p><p><b>　　}</b></p><p><b>　　}</b>&

65、lt;/p><p>　　3.10 判斷連通操作</p><p>　　通過調(diào)用遍歷函數(shù)得到所能訪問的頂點(diǎn)數(shù)n，然后判斷n與當(dāng)前頂點(diǎn)數(shù)是否相等來確認(rèn)是否連通。</p><p>　　bool Graph1::isliantong()//判斷是否連通</p><p><b>　　{</b></p><p>&

66、lt;b>　　int n=0;</b></p><p>　　n=Depth(0);</p><p>　　cout<<"該圖的總節(jié)點(diǎn)數(shù)為:"<<nodecount<<"!"<<endl;</p><p>　　cout<<"其中一個(gè)連通分量連通

67、的節(jié)點(diǎn)數(shù)為:"<<n<<"!"<<endl;</p><p>　　if(n==nodecount)//訪問到的節(jié)點(diǎn)數(shù)與頂點(diǎn)數(shù)是否相等</p><p><b>　　return 1;</b></p><p>　　else return 0;</p><p>

68、<b>　　}</b></p><p><b>　　3.11 主函數(shù)</b></p><p>　　主函數(shù)的主要功能是引導(dǎo)構(gòu)建新圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，并且制作菜單、調(diào)用各個(gè)相應(yīng)的功能函數(shù)。</p><p>　　int main(){</p><p>　　system("cls");

69、</p><p>　　system("color 1f");</p><p>　　system("mode con: cols=78 lines=35");</p><p>　　cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n";</p>

70、<p>　　cout<<" ┃㊣ 必做題：無向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) ㊣┃\n";</p><p>　　cout<<" ┃ 姓名：xxxx ┃\n";</p><p>　　cout

71、<<" ┃ 學(xué)號：xxxxxxxxx ┃\n";</p><p>　　cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n";</p><p>　　cout<<">>&g

72、t;>>>\n";</p><p>　　Graph1 G(10);</p><p>　　int x,y,w;</p><p>　　int node; </p><p>　　cout<<"你好,請依次輸入圖的節(jié)點(diǎn)數(shù)n和邊數(shù)e:"<<endl;</p><

73、p><b>　　int n,e;</b></p><p>　　cin>>n>>e;;</p><p>　　G.CreatG(n,e);</p><p>　　cout<<"恭喜你!你的圖已經(jīng)建立成功!"<<endl;</p><p>　　system

74、("pause");</p><p>　　while(true){</p><p>　　cout<<endl;</p><p>　　cout<<"╔══════════════════════════════════╗\n";</p><p>　　cout<<&quo

75、t;║ 歡迎進(jìn)入圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)演示系統(tǒng) ║\n";</p><p>　　cout<<"║ ----------------------------------------------------------------- ║\n";</p><

76、;p>　　cout<<"║ 請選擇您要的操作： ║\n";</p><p>　　cout<<"║ 1.輸出圖 2.判斷圖是否連通 ║\n";</p>&

77、lt;p>　　cout<<"║ 3.深度優(yōu)先搜索 4.求各頂點(diǎn)的度 ║\n";</p><p>　　cout<<"║ 5.插入新節(jié)點(diǎn) 6.刪除邊 ║\n";</p>

78、<p>　　cout<<"║ 7.求邊的權(quán)值 8.插入新的邊 ║\n";</p><p>　　cout<<"║ 0.退出系統(tǒng) ║\n";<

79、;/p><p>　　cout<<"╚══════════════════════════════════╝\n";</p><p>　　int choice;</p><p>　　cout<<endl;</p><p>　　cout<<"請你做出選擇!"<<e

80、ndl;</p><p>　　cin>>choice;</p><p>　　switch(choice){</p><p>　　case 1: G.PrintOut(G);break;</p><p><b>　　case 2:</b></p><p>　　if(G.islianton

81、g())</p><p>　　cout<<"該圖是連通的!"<<endl;</p><p><b>　　else</b></p><p>　　cout<<"該圖不是連通的!"<<endl;</p><p><b>　　bre

82、ak;</b></p><p><b>　　case 3:</b></p><p><b>　　int node;</b></p><p>　　cout<<"請輸入你選擇的起始節(jié)點(diǎn)!"<<endl;</p><p>　　cin>>n

83、ode;</p><p>　　cout<<"深度優(yōu)先搜索結(jié)果為:"<<endl;</p><p>　　G.Depth(node-1);</p><p>　　cout<<endl;</p><p><b>　　break;</b></p><p&g

84、t;　　case 4: G.outDu(G);break;</p><p><b>　　case 5:</b></p><p>　　cout<<"請輸入你要插入的新節(jié)點(diǎn)!"<<endl;</p><p>　　cin>>node;</p><p>　　G.insert

85、Node(node);</p><p>　　cout<<endl;</p><p><b>　　break;</b></p><p><b>　　case 6:</b></p><p>　　cout<<"請輸入你要?jiǎng)h除的邊!"<<endl;&l

86、t;/p><p>　　cin>>x>>y;</p><p>　　G.deleteEdge(x,y);</p><p>　　cout<<endl;</p><p><b>　　break;</b></p><p><b>　　case 7:</b>

87、;</p><p>　　cout<<"請輸入你要查詢的邊的兩個(gè)頂點(diǎn)"<<endl;</p><p>　　cin>>x>>y;</p><p>　　cout<<G.getWeight(x,y)<<endl;</p><p><b>　　brea

88、k;</b></p><p><b>　　case 8:</b></p><p>　　cout<<"請輸入你要添加的"<<e<<"條邊以及邊上對應(yīng)的權(quán)值!"<<endl;</p><p>　　cin>>x>>y>&g

89、t;w;</p><p>　　G.isertEdge(x,y,w);</p><p><b>　　break;</b></p><p><b>　　case 0:</b></p><p>　　cout<<"感謝使用！"<<endl;</p>

90、<p><b>　　return 0;</b></p><p>　　}//system("pause");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4 調(diào)試分析</

91、b></p><p><b>　　4.1調(diào)試問題</b></p><p>　　具體功能方面，在遍歷函數(shù)中，由于訪問節(jié)點(diǎn)數(shù)組visit[]構(gòu)建問題，無法達(dá)到遍歷目的，后新增另一遍歷功能函數(shù)，用于構(gòu)建visit[]，問題才得以解決，而于使用了清屏system("cls")和暫停system("pause")功能，在測試時(shí)一度出

92、現(xiàn)暫停次數(shù)過多的問題，通過在判斷結(jié)構(gòu)中加入break后解決，在判斷是否連通功能上，由于判斷問題遲遲未能下手，后在遍歷函數(shù)中加入了一個(gè)記錄訪問節(jié)點(diǎn)數(shù)的N，從而解決問題。</p><p>　　4.2 算法時(shí)間復(fù)雜度</p><p>　　圖的創(chuàng)建：時(shí)間復(fù)雜度為O(n);</p><p>　　深度遍歷: 時(shí)間復(fù)雜度為O(n);</p><p>　　插

93、入頂點(diǎn)和邊: 當(dāng)插入的頂點(diǎn)和邊為x，y時(shí)，若x>=y時(shí)間復(fù)雜度為O(x)反之為O(y);</p><p>　　刪除頂點(diǎn)和邊: 當(dāng)刪除的頂點(diǎn)和邊為x，y時(shí)，若x>=y時(shí)間復(fù)雜度為O(x)反之為O(y);</p><p><b>　　5　用戶手冊</b></p><p>　　本系統(tǒng)是關(guān)于圖的矩陣存儲(chǔ)系統(tǒng)，管理員和游客，要求首先創(chuàng)建一個(gè)圖

94、之后才能進(jìn)行后續(xù)的操作，并且在輸入過程中務(wù)必規(guī)范輸入。 </p><p><b>　　5.1 主界面</b></p><p><b>　　5.2 創(chuàng)建圖</b></p><p><b>　　5.3插入節(jié)點(diǎn)</b></p><p>　　5.4 深度優(yōu)先遍歷</p>

95、<p>　　5.5 求各頂點(diǎn)的度</p><p><b>　　5.6 輸出圖</b></p><p>　　5.7 判斷是否連通</p><p><b>　　5.8 求邊的權(quán)值</b></p><p><b>　　5.9 插入邊</b></p><p

96、><b>　　5.10 刪除邊 </b></p><p><b>　　結(jié) 論 </b></p><p>　　本次課程設(shè)計(jì)“無向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)”按照任務(wù)書相應(yīng)的要求成功的完成了任務(wù)，由于本課程設(shè)計(jì)涉及任務(wù)明確，采用圖的儲(chǔ)存結(jié)構(gòu)和算法比較方便處理數(shù)據(jù)的儲(chǔ)存、查詢、刪除等操作。但圖的操作比較難， 容易出錯(cuò)并且不易改動(dòng)。</p>

97、;<p><b>　　參考文獻(xiàn) </b></p><p>　　[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社出版。 </p><p>　　[2] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版) .清華大學(xué)出版社.2003年5月。</p><p>　　[3] 楊秀金，數(shù)據(jù)結(jié)構(gòu)(C++版) .高等教育出版社.2009年4月。</