圖的遍歷課設(shè)

1、沈陽航空航天大學(xué)課課 程程 設(shè)設(shè) 計計 報報 告告課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計題目：圖的建立及輸出圖的建立及輸出院（系）：計算機學(xué)院專 業(yè)： 計算機科學(xué)與技術(shù)班 級： 學(xué) 號： 姓 名： 指導(dǎo)教師： 沈陽航空航天大學(xué)課程設(shè)計報告 I 此頁為任務(wù)書沈陽航空航天大學(xué)課程設(shè)計報告 II 目目 錄錄1 題目和概要設(shè)計題目和概要設(shè)計.11.1 題目的內(nèi)容與要求 .11.2 概要設(shè)計.12 詳細(xì)設(shè)計詳細(xì)設(shè)計.22.1 算法設(shè)計思想原理 .22.1.1 鄰接矩陣表示法.22.2 算法的流程圖.33 結(jié)構(gòu)分析結(jié)構(gòu)分析.53.1 存儲結(jié)構(gòu) .53.2 算法描述 .54 調(diào)試與分析調(diào)試與

2、分析.74.1 調(diào)試過程 .74.2 程序執(zhí)行過程 .7參考文獻參考文獻.10附附 錄（程序清單）錄（程序清單）.11沈陽航空航天大學(xué)課程設(shè)計報告 1 1.題目和概要設(shè)計1.1 題目的內(nèi)容與要求題目的內(nèi)容與要求問題重述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。要求：1、獨立完成系統(tǒng)的設(shè)計、編碼的調(diào)試。2、系統(tǒng)利用 C 語言實現(xiàn)。3、按照課程設(shè)計規(guī)范書寫課程實際報告。1.2 概要設(shè)計概要設(shè)計CreateGraph(MGraph &G) 初始條件：圖 G 未創(chuàng)建。 操作

3、結(jié)果：創(chuàng)建一個圖 G。 CreateUDG(MGraph &G); 初始條件：無向圖 G 未創(chuàng)建。 操作結(jié)果：創(chuàng)建一個無向圖并求出其鄰接矩陣。CreateUDN(MGraph &G); 初始條件：有無向網(wǎng) G 未創(chuàng)建。 操作結(jié)果：創(chuàng)建一個無向網(wǎng)并求出其鄰接矩陣。 D Display(MGraph G)。 初始條件：圖 G 已創(chuàng)建。 操作結(jié)果：輸出圖 G 的鄰接矩陣。沈陽航空航天大學(xué)課程設(shè)計報告 2 2詳細(xì)設(shè)計2.1 算法設(shè)計思想原理算法設(shè)計思想原理2.1.1 鄰接矩陣表示法鄰接矩陣表示法鄰接矩陣表示法:設(shè) G=(V,E)是一個圖，其中 V=V1,V2,V3,Vn。G 的鄰接矩陣

4、是一個具有下述性質(zhì)的 n 階方陣：若(Vi,Vj)E 或者E，則 Ai,j=1 反之為 0；圖 5-2 中有向圖 G1 和無向圖 G2 的鄰接矩陣分別為 M1 和 M2:M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 M2= 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 注意無向圖的鄰接是一個對稱矩陣，例如 M2。用鄰接矩陣表示法來表示一個具有 n 個頂點的圖時，除了用鄰接矩陣中的n*n 個元素存儲頂點間相鄰關(guān)系外，往往還需要另設(shè)一個向量存儲 n 個頂點的信息。因此其類型定義如下： VertexType vertexMAX_VERTEX_NUM; /

5、頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志 若圖中每個頂點只含一個編號 i(1ivnum)，則只需一個二維數(shù)組表示圖的鄰接矩陣。此時存儲結(jié)構(gòu)可簡單說明如下：沈陽航空航天大學(xué)課程設(shè)計報告 3 type adjmatrix=array1.vnum,1.vnumof adj;利用鄰接矩陣很容易判定任意兩個頂點之間是否有邊（或?。┫嗦?lián)，并容易求得各個頂點的度。對于無向圖，頂點 Vi 的度是鄰接矩陣中第 i 行元素之和，即nD(Vi)Ai,j j=1 對于有向圖，頂點 V

6、i 的出度 OD(Vi)為鄰接矩陣第 i 行元素之和，頂點 Vi 的入度 ID(Vi)為第 i 列元素之和。即 nnOD(Vi)Ai,j， ID(Vi)Aj,i） j=1j=1用鄰接矩陣也可以表示帶權(quán)圖，只要令 Ai,j Wij, 若(Vi,Vj)或者E 其中 Wij 為或(Vi,Vj)上的權(quán)值。2.2算法的流程圖算法的流程圖 1.算法先進行圖的建立，如圖 2.2-1 的構(gòu)造流程圖，描述了圖的建立及輸入過程，以鄰接矩陣的方法進行輸入存儲。 2.大體數(shù)據(jù)算法如圖 2.2-2 主程序流程圖所示，先選擇圖的類型，按順序的構(gòu)造并輸出圖的鄰接矩陣。沈陽航空航天大學(xué)課程設(shè)計報告 4 YNYNYN圖 2.2

7、-2 主程序流程圖YN圖 2.2-1 的構(gòu)造流程圖開始輸入vexnum，arcnumIncInfoivexnum輸入頂點jvexnum初始化鄰接矩陣karcnum設(shè)置鄰接矩陣結(jié)束ii+1ivexnumjj+1ii+1kk+1開始選擇圖的類型構(gòu)造圖輸出該圖的鄰接矩陣結(jié)束沈陽航空航天大學(xué)課程設(shè)計報告 5 3結(jié)構(gòu)分析3.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu)定義一個指針區(qū)域，包括頂點向量、鄰接矩陣、當(dāng)前頂點數(shù)和弧數(shù)、圖的種類標(biāo)志的信息。利用該指針進行圖的操作及存儲。typedef struct VertexType vertexMAX_VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣

8、 int vexnum, arcnum; / 圖的當(dāng)前頂點數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志3.2 算法描述算法描述1、無向圖鄰接矩陣的建立算法如下：procedure build-graph; 建立無向圖的鄰接矩陣beginfor i:=1 to n do read(G.vertexi)； 讀入 n 個頂點的信息for i:=1 to n dofor j:=1 to e doG.arcsij =0；將鄰接矩陣的每個元素初始化成 0 for k:=1 to e do e 為邊的數(shù)目 read(i,j,w) 讀入邊和權(quán)G.arcsij:=wG.arcsijG.arc

9、sii置對稱弧沈陽航空航天大學(xué)課程設(shè)計報告 6 end；該算法的執(zhí)行時間是 O(n+n2+e),其中消耗在鄰接矩陣初始化操作上的時間是O(n2),而 en2，所以上述算法的時間復(fù)雜度是 O(n2)。2、無向網(wǎng)鄰接矩陣的建立算法如下： procedure build-graph; 建立無向網(wǎng)的鄰接矩陣begin for i:=1 to n do read(G.vertexi)； 讀入 n 個頂點的信息 for i:=1 to n do for j:=1 to e do G.arcsij =maxint；將鄰接矩陣的每個元素初始化成 maxint,計算機內(nèi)用最大事數(shù) maxint 表示for k:

10、=1 to e do e 為邊的數(shù)目 read(i,j,w) 讀入邊和權(quán)G.arcsij:=w; G.arcsij:=w end；該算法的執(zhí)行時間是 O(n+n2+e),其中消耗在鄰接矩陣初始化操作上的時間是O(n2),而 en2，所以上述算法的時間復(fù)雜度是 O(n2)沈陽航空航天大學(xué)課程設(shè)計報告 7 4調(diào)試與分析4.1 調(diào)試過程調(diào)試過程 綜合這次課設(shè)過程，調(diào)試分析如下： 1：初步未掌握圖的創(chuàng)建方法，后通過學(xué)習(xí)圖，掌握了圖的輸入及輸出的鄰接矩陣。2：在創(chuàng)建圖時，產(chǎn)生了一些錯誤，原因未完全了解圖的規(guī)律，在深入學(xué)習(xí)后了解到了很多之前沒學(xué)到的關(guān)于圖的知識。 3：輸入圖的方法有很多考慮，后決定利用矩陣

11、的方法進行。:4.2 程序執(zhí)行過程程序執(zhí)行過程程序開始運行時輸出：請輸入要構(gòu)造的圖的類型(1.無向圖,2.無向網(wǎng)): 為了測試輸入為：1顯示：請輸入無向圖 G 的頂點數(shù):輸入：5顯示：請輸入無向圖 G 的邊數(shù):輸入：6顯示：_請輸入 5 個頂點的值:輸入：1 2 3 4 5顯示：(o)請輸入第 1 條邊的 2 個端點(以空格作為間隔):輸入：1 2顯示：(o)請輸入第 2 條邊的 2 個端點(以空格作為間隔):輸入：1 4顯示：(o)請輸入第 3 條邊的 2 個端點(以空格作為間隔):輸入：2 6顯示：(+) 對不起!您輸入的邊信息錯誤,請重新輸入第 3 條邊的 2 個端 點(以空格作為間隔)

12、:輸入：2 3顯示：(o)請輸入第 4 條邊的 2 個端點(以空格作為間隔):沈陽航空航天大學(xué)課程設(shè)計報告 8 輸入：2 5顯示：(o)請輸入第 5 條邊的 2 個端點(以空格作為間隔):輸入：3 4顯示：(o)請輸入第 6 條邊的 2 個端點(以空格作為間隔):輸入：3 5顯示：該圖的鄰接矩陣為： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 圖 4.2-1 無向圖的構(gòu)建及輸出沈陽航空航天大學(xué)課程設(shè)計報告 9 圖 4.2-2 無向網(wǎng)的構(gòu)建及輸出沈陽航空航天大學(xué)課程設(shè)計報告 10 參考文獻1 恰汗合孜爾 C 語言程序設(shè)計第三版北京：中國鐵道

13、出版社，2010.1288 2 譚浩強c 程序設(shè)計（第四版）清華大學(xué)出版社20103 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C 語言版）清華大學(xué)出版社20134 李素若數(shù)據(jù)結(jié)構(gòu)（語言描述）化學(xué)工業(yè)出版社2006沈陽航空航天大學(xué)課程設(shè)計報告 11 附 錄（程序清單）#include #include #include #include #include#define ERROR 0#define OK 1#define MAX_VERTEX_NUM 20 /定義最大值#define INFINITY 32768 /定義極大值#define MAX_INFO 20typedef int VrType; /定義新

14、的類型typedef int InfoType;typedef char VertexType;typedef enum DG,DN,UDG,UDNGraphKind; /有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcCell VrType adj; / 頂點關(guān)系類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct 沈陽航空航天大學(xué)課程設(shè)計報告 12 VertexType vertexMAX_VERTEX_NUM; / 頂點向量 AdjMat

15、rix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;void CreateUDG(MGraph &G) / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向圖 int i,j,k; /i，j，k 為計數(shù)器 int v1,v2; /用于放置輸入的弧的兩個頂點 printf(請輸入無向圖 G 的頂點數(shù):n); scanf(%d,&G.vexnum); printf(請輸入無向圖 G 的邊數(shù):n); scanf(%d,&G.arcnum); printf(_請輸入%d 個

16、頂點的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您輸入的頂點值錯誤,請重新輸入第%d 個頂點的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij.adj=0;沈陽航空航天大學(xué)課程設(shè)計報告 13 G.=NULL; for(k=0;kG.vexnum)|(v2G.vexnum)printf(+) 對不起!您輸入的邊信息錯誤,請重新輸入第%d 條邊的始點

17、和終點:n,k+1); scanf(%d %d,&v1,&v2); i=v1-1; j=v2-1; G.arcsij.adj=G.arcsji.adj=1; / 置的對稱弧 /CreateUDG void CreateUDN(MGraph &G) / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng) int i,j,k,w; /i，j，k 為計數(shù)器，w 用于放置權(quán)值 int v1,v2; /用于放置輸入的弧的兩個頂點 printf(請輸入無向網(wǎng) G 的頂點數(shù):n); scanf(%d,&G.vexnum); printf(請輸入無向網(wǎng) G 的邊數(shù):n); scanf(%d

18、,&G.arcnum); printf(_請輸入%d 個頂點的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您輸入的頂點值錯誤,請重新輸入第%d 個頂點的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; /adj,info for(k=0;kG.vexnum)|(v2G.vexnum) printf(+) 對不

19、起!您輸入的邊信息錯誤,請重新輸入第%d 條邊的始點和終點:n,k+1); scanf(%d %d %d,&v1,&v2,&w); i=v1-1; j=v2-1;沈陽航空航天大學(xué)課程設(shè)計報告 15 G.arcsij.adj=G.arcsji.adj=w; / 置的對稱弧 /CreateUDNint CreateGraph(MGraph &G) /構(gòu)造圖printf(請輸入要構(gòu)造的圖的類型:n*1.無向圖*n*2.無向網(wǎng)*n);scanf (%d,&G.kind);switch(G.kind) case 1: CreateUDG(G);break;case 2: CreateUDN(G);break;default: return ERROR;void Display(MGraph G) /輸出圖的鄰接矩陣 int i,j; printf(該圖的鄰接矩陣為：n); for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum