圖的基本操作及應用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告.doc

算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告系 （院）： 計算機科學學院 專業(yè)班級： 教育技術(shù)學1001班 姓 名： 宋佳 學 號： 201003901 指導教師： 詹澤梅 設(shè)計時間： 2012.6.16 - 2012.6.24 設(shè)計地點： 4號樓2號機房 算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務書班級：教育技術(shù)11001課程設(shè)計題目：圖的基本操作及應用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是在學完數(shù)據(jù)結(jié)構(gòu)課程之后的實踐教學環(huán)節(jié)。本實踐教學是培養(yǎng)學生數(shù)據(jù)抽象能力，進行復雜程序設(shè)計的訓練過程。要求學生能對所涉及問題選擇合適的數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)及算法，并編寫出結(jié)構(gòu)清楚且正確易讀的程序，提高程序設(shè)計基本技能和技巧。一設(shè)計目的1提高數(shù)據(jù)抽象能力。根據(jù)實際問題，能利用數(shù)據(jù)結(jié)構(gòu)理論課中所學到的知識選擇合適的邏輯結(jié)構(gòu)以及存儲結(jié)構(gòu)，并設(shè)計出有效解決問題的算法。2提高程序設(shè)計和調(diào)試能力。學生通過上機實習，驗證自己設(shè)計的算法的正確性。學會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。3初步了解開發(fā)過程中問題分析、整體設(shè)計、程序編碼、測試等基本方法和技能。二設(shè)計任務設(shè)計一個基于DOS菜單的應用程序。要利用多級菜單實現(xiàn)各種功能。內(nèi)容如下：1 無向圖的基本操作及應用 創(chuàng)建無向圖的鄰接矩陣 創(chuàng)建無向圖的鄰接表 無向圖的深度優(yōu)先遍歷 無向圖的廣度優(yōu)先遍歷2 有向圖的基本操作及應用 創(chuàng)建有向圖的鄰接矩陣 創(chuàng)建有向圖的鄰接表 拓撲排序3 無向網(wǎng)的基本操作及應用 創(chuàng)建無向網(wǎng)的鄰接矩陣 創(chuàng)建無向網(wǎng)的鄰接表 求最小生成樹 4 有向網(wǎng)的基本操作及應用 創(chuàng)建有向網(wǎng)的鄰接矩陣 創(chuàng)建有向網(wǎng)的鄰接表 關(guān)鍵路徑 單源最短路徑 三設(shè)計指導第一步：根據(jù)設(shè)計任務，設(shè)計DOS菜單。第二步：設(shè)計菜單（c語言）#includevoid ShowMainMenu()printf(n);printf(*圖的基本操作及應用*n);printf(* 1 無向圖的基本操作及應用 *n);printf(* 2 有向圖的基本操作及應用 *n);printf(* 3 無向網(wǎng)的基本操作及應用 *n);printf(* 4 有向網(wǎng)的基本操作及應用 *n);printf(* 5 退出n);printf(*n);void UDG()int n;doprintf(n);printf(*無向圖的基本操作及應用*n);printf(* 1 創(chuàng)建無向圖的鄰接矩陣 *n);printf(* 2 創(chuàng)建無向圖的鄰接表 *n);printf(* 3 無向圖的深度優(yōu)先遍歷 *n);printf(* 4 無向圖的廣度優(yōu)先遍歷 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DG() int n;doprintf(n);printf(*有向圖的基本操作及應用*n);printf(* 1 創(chuàng)建有向圖的鄰接矩陣 *n);printf(* 2 創(chuàng)建有向圖的鄰接表 *n);printf(* 3 拓撲排序 *n);printf(* 4 退出 *n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:break;default:printf(ERROR!);while(n!=4);void UDN() int n;doprintf(n);printf(*無向網(wǎng)的基本操作及 *n);printf(* 1 創(chuàng)建無向網(wǎng)的鄰接矩陣 *n);printf(* 2 創(chuàng)建無向網(wǎng)的鄰接表 *n);printf(* 3 Prim算法求最小生成樹 *n);printf(* 4 kraskal算法求最小生成樹 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(- -wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DN() int n;doprintf(n);printf(*有向網(wǎng)的基本操作*n);printf(* 1 創(chuàng)建有向網(wǎng)的鄰接矩陣 *n);printf(* 2 創(chuàng)建有向網(wǎng)的鄰接表 *n);printf(* 3 關(guān)鍵路徑 *n);printf(* 4 單源頂點最短路徑問題 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void main()int n;doShowMainMenu();printf(請選擇：);scanf(%d,&n);switch(n)case 1:UDG();break;case 2:DG();break;case 3:UDN();break;case 4:DN();break;case 5:break;default:printf(ERROR!);break;while(n!=5);第三步：添加功能函數(shù)。在主程序的合適位置添加相應的函數(shù)實現(xiàn)各功能（提示：語句printf(“-wait-”)所在位置）。四成績評定l 實習報告（文字不得少于4000字）一、 設(shè)計方案；二、 實現(xiàn)過程；三、 實現(xiàn)代碼；四、 測試；五、 結(jié)論；六、 難點與收獲。l 程序?qū)崿F(xiàn)1. 程序運行正確，無編譯錯誤，無邏輯錯誤；2. 在第一條的基礎(chǔ)上，任務完成的越多，成績等級越高。l 成績由三部分組成：平時考核(20%)、程序?qū)崿F(xiàn)(50%)、實習報告(30%)一、 設(shè)計方案由課程設(shè)計任務書，按照要求，需要設(shè)計有向圖3、有向網(wǎng)、無向圖 、無向網(wǎng)四種圖，鄰接矩陣、鄰接表兩種數(shù)據(jù)存儲結(jié)構(gòu)，共十六種基本操作及應用，三層以上的顯示菜單。圖的操作中又包含有有關(guān)線性表、棧和隊列的基本操作。由于顯示菜單已給出，剩下的只是把函數(shù)寫入其中，而線性表、棧和隊列的基本操作并不復雜，很容易實現(xiàn)，我們只有完成圖的相關(guān)操作即可。圖的操作都是以兩種存儲結(jié)構(gòu)為基礎(chǔ)的，鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)，如四種圖（有向圖，有向網(wǎng)，無向圖，無向網(wǎng)）的創(chuàng)建，其他的操作都是在四種圖創(chuàng)建后才開始進行的。所以，首先必須理解兩種存儲結(jié)構(gòu)的定義。圖的鄰接矩陣存儲結(jié)構(gòu)即圖的數(shù)組表示法。用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔?。用鄰接矩陣存儲結(jié)構(gòu)的圖具有以下幾點特征：（一）：頂點數(shù)：vexnum，邊（?。?shù)：arcnum，圖的種類：kind；（二）：鄰接矩陣：arcs(1頂點關(guān)系類型:adj 2相關(guān)信息:*info)；（三）：頂點向量（頂點名）：vexs；其優(yōu)點是以二維數(shù)組表示有n個頂點的圖時，需存放n頂點的信息和n*n個弧的信息存儲量。借助于鄰接矩陣容易判定任意兩個頂點之間是否有邊或弧相連，并容易求各個頂點的度。缺點其時間復雜度是O（n*n）,例如，構(gòu)造一個具有n個頂點和e條邊的無向網(wǎng)的時間復雜度為O（n*n+e*n）。圖的鄰接表存儲結(jié)構(gòu)是圖的一種鏈式存儲結(jié)構(gòu)。對圖中的每個頂點建立一個單鏈表，每個結(jié)點有三個域組成，鄰接點域adjvex（弧尾在鄰接表鏈表中的位序），鏈域nextarc（下一條弧），數(shù)據(jù)域info(權(quán)值)。還要建立一個鄰接表鏈表，用以存放頂點名data和后繼指針firstarc,表頭結(jié)點以順序結(jié)構(gòu)的形式存儲，便于隨機訪問任一頂點的單鏈表。鄰接表存儲結(jié)構(gòu)的優(yōu)點在于其時間復雜度小。除此之外，還有十字鏈表存儲結(jié)構(gòu)和多重鏈表存儲結(jié)構(gòu)。由于，沒有用到他們，故不再詳細描述。樹的深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。從圖中的某個頂點出發(fā)，訪問此頂點，然后依次從該頂點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有與該頂點有關(guān)的路徑都被訪問到；此時圖中若還有頂點未被訪問到，則另選圖中的一個未被訪問的頂點作為起始點，重述上述過程，直至所有頂點都被訪問到。廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。以某個頂點為起始頂點，由近至遠，依次訪問和該頂點有路徑相通的且路徑長度為1， 2， 3，的頂點。當圖中所有頂點都被訪問到后，就完成了圖的廣度優(yōu)先搜索遍歷。求無向網(wǎng)的最小生成樹問題有兩種算法：Prima算法和Kruskal算法。Prima算法是從網(wǎng)中的某個頂點出發(fā)，選擇與該頂點有路徑的所有頂點中路徑最小的一條路徑，從該最小路徑的另一頂點出發(fā)，重復上述過程，直至圖中所有頂點都被訪問完成。Kruskal算法是從網(wǎng)中找出所有路徑最小的一條路徑，記下已訪問該路徑的兩個頂點，再次從圖中找出剩下路徑中的最小路徑，重復上述過程，直至所有頂點都被訪問完成，按訪問的順序依次輸出各頂點，即構(gòu)造了一棵最小生成樹。由某個集合上的一個偏序得到該集合的一個全序的操作就叫做拓撲排序。拓撲排序主要有兩個方面的操作：（1）在有向圖中選擇一個沒有前驅(qū)的頂點并輸出；（2）在圖中刪除該頂點和所有以它為尾的弧。重復上述兩步，直至全部頂點均已輸出，就得到了一個拓撲有序序列。求關(guān)鍵路徑的算法如下：輸入e條弧，建立AOE網(wǎng)的存儲結(jié)構(gòu)；從源點v0出發(fā),令ve0=0，按拓撲有序求其余各頂點的最早發(fā)生時間。如果得到的拓撲有序序列中的頂點個數(shù)小于網(wǎng)中的頂點數(shù)，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行第三步。從匯點vn出發(fā)，令vln-1=ven-1，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vli；根據(jù)各頂點的和值，求每條弧的最早開始時間e(s)和最遲開始時間e(s)，若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。從某個源點到其余各頂點的最短路徑問題：若從v到vi有弧，則Di為弧上的權(quán)值，否則Di為無窮大。顯然，長度為Dj=MinDi|vi屬于V的路徑就是從v出發(fā)的長度最短的一條路徑。二、 實現(xiàn)及測試過程按照設(shè)計任務的要求，我先完成了存儲結(jié)點、邊、鄰接矩陣、鄰接表、隊列、棧等儲存結(jié)構(gòu)體的設(shè)計。其次是棧和隊列的基本操作和實現(xiàn)，四種圖的創(chuàng)建和顯示，然后是基于兩種存儲結(jié)構(gòu)的各種算法的現(xiàn)，最后是三層顯示輸出菜單。測試樣圖：三、實現(xiàn)代碼#include #include#include #define ERROR 0#define OK 1#define INFINITY INT_MAX#define MAX_VERTEX_NUM 21#define STACK_INIT_SIZE 100#define STACKINCREAMENT 10typedef enumDG,DN,UDG,UDNGraphKind;typedef struct ArcCell int adj; /infotype *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind;MGraph; /鄰接矩陣typedef struct ArcNode int adjvex; int quan; struct ArcNode *nextarc; ArcNode,*AList;typedef struct VNode char data; AList firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; GraphKind kind;ALGraph; /鄰接表typedef struct QNodechar data;struct QNode *next;QNode,*QueuePre;typedef structQueuePre front;QueuePre rear;LinkQueue; /隊列typedef struct int *base;int *top;int stacksize;SqStack; /棧typedef struct char adjvex;int lowcost;closedgesMAX_VERTEX_NUM; /求最小生成樹中的輔助數(shù)組int option; int visitedMAX_VERTEX_NUM; /頂點訪問標記數(shù)組int indegreeMAX_VERTEX_NUM; /頂點入度記錄數(shù)組int veMAX_VERTEX_NUM; /頂點權(quán)值記錄數(shù)組int SetGraphKind(MGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /鄰接矩陣類型設(shè)置int SetGraphKind(ALGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /鄰接表類型設(shè)置int LocateVex(MGraph G,char v) int m; for(m=1;m=G.vexnum;m+) if(G.vexsm=v) return m; return ERROR; /鄰接矩陣頂點定位int LocateVex(ALGraph G,char v) int m; for(m=1;mnext=NULL;return OK; /隊列創(chuàng)建int EnQueue(LinkQueue &Q,int e)QueuePre p;p=(QueuePre)malloc(sizeof(QNode);if(!p) return OK;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; /元素入隊列int DeQueue(LinkQueue &Q,int &e)QueuePre p;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK; /元素出隊列int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return OK;return ERROR; /判斷隊列是否為空int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /棧創(chuàng)建int Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;*S.top+=e;return OK; /元素入棧int Pop(SqStack &S,int &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK; /元素出棧int StackEmpty(SqStack S)if(S.top=S.base) return OK;return ERROR; /判斷棧是否為空int CreatGraph(MGraph &G) int i,j,k,w;char x,y; if(!SetGraphKind(G,option) printf(對圖類型的設(shè)置失敗);return ERROR; printf(鄰接矩陣：請輸入定點的個數(shù)、弧的個數(shù)：); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum20) printf(您輸入的頂點個數(shù)超過最大值); return ERROR; printf(請輸入%d個頂點n,G.vexnum); for(i=1;i=G.vexnum;+i) fflush(stdin); scanf(%c,&G.vexsi); if(G.kind=DG|G.kind=UDG) for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=0; if(G.kind=DG) printf(請輸入有向圖的兩個相鄰的頂點（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x);j=LocateVex(G,y); G.arcsij.adj=1; else printf(請輸入無向圖的兩個相鄰的頂點（x,y）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=1; G.arcsji.adj=G.arcsij.adj; else for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=INT_MAX; if(G.kind=DN) printf(請輸入有向網(wǎng)的兩個相鄰的頂點以及相應的權(quán)值w（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c %d,&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=w; else printf(請輸入無向網(wǎng)的兩個相鄰的頂點（x,y）以及相應的權(quán)值w：n); for(k=1;k20) printf(您輸入的頂點個數(shù)超過最大值); return ERROR; printf(請輸入個頂點：n);for(i=1;i=G.vexnum;i+)fflush(stdin);scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;keyi=0;if(G.kind=DG)printf(請輸入?。ㄈ鏏B,其中AB與BA是不同的?。簄);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=UDG)printf(請輸入?。ㄈ鏏B,其中AB與BA是不同的弧）：n);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=DN)printf(請輸入依次輸入弧以及這條弧的權(quán)值（如AB 8,其中AB與BA是不同的?。簄); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; if(G.kind=UDN)printf(請輸入依次輸入弧以及這條弧的權(quán)值（如AB 8,其中AB與BA是不同的?。簄); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; return OK; /創(chuàng)建鄰接表int FirstAdjVex(ALGraph G,int v)if(G.verticesv.firstarc)return G.verticesv.firstarc-adjvex;return 0;int NextAdjVex(ALGraph G,int v,int w)AList s;s=G.verticesv.firstarc;while(s-adjvex!=w)s=s-nextarc;if(s-nextarc)return s-nextarc-adjvex;return 0;void DFS(ALGraph G,int v)int w;visitedv=1; printf(%c ,G.verticesv);for(w=FirstAdjVex(G,v);w=1;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w); void DFSTraverse(ALGraph G)int v;visited0=1;for(v=1;v=G.vexnum;v+) visitedv=0;for(v=1;v=G.vexnum;v+)if(!visitedv) DFS(G,v); /圖的深度遍歷void BFSTraverse(ALGraph G)int v,w,u;LinkQueue Q;for(v=1;v=G.vexnum;v+) visitedv=0;visited0=1;InitQueue(Q);for(v=1;v=1;w=NextAdjVex(G,u,w) if(!visitedw)visitedw=1; printf(%c ,G.verticesw);EnQueue(Q,w); else break; /圖的廣度遍歷void FindInDegree(ALGraph G,int in)int i,j,k;AList p;for(k=1;k=G.vexnum;k+) ink=0;for(i=1;iadjvex;inj+;p=p-nextarc; /計算各頂點入度 int TopologicalSort(ALGraph G)int i,k,count;AList p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);if(count=G.vexnum) return ERROR;else return OK; /拓撲排序int Minimum(MGraph G,closedges m)int i,j,min=INFINITY;for(i=1;i=G.vexnum;i+)if(mi.lowcost)if(mi.lowcostmin)min=mi.lowcost;j=i; return j;void MinSpanTree_PRIM(MGraph G,char u)int i,j,k;closedges closedge;k=LocateVex(G,u);for(j=1;j=G.vexnum;j+)if(j!=k) closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=2;i=G.vexnum;i+)k=Minimum(G,closedge);printf(%c%c ,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=1;j=G.vexnum;j+)if(G.arcs