算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

1、算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 報告課程設(shè)計題目：圖的基本操作及應(yīng)用 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實踐教學(xué)環(huán)節(jié)。本實踐教學(xué)是培養(yǎng)學(xué)生數(shù)據(jù)抽象能力，進行復(fù)雜程序設(shè)計的訓(xùn)練過程。要求學(xué)生能對所涉及問題選擇合適的數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)及算法，并編寫出結(jié)構(gòu)清楚且正確易讀的程序，提高程序設(shè)計基本技能和技巧。 一設(shè)計目的 1提高數(shù)據(jù)抽象能力。根據(jù)實際問題，能利用數(shù)據(jù)結(jié)構(gòu)理論課中所學(xué)到的知識選擇合適的邏輯結(jié)構(gòu)以及存儲結(jié)構(gòu)，并設(shè)計出有效解決問題的算法。 2提高程序設(shè)計和調(diào)試能力。學(xué)生通過上機實習(xí)，驗證自己設(shè)計的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。 3初步了解開發(fā)過程中問

2、題分析、整體設(shè)計、程序編碼、測試等基本方法和技能。 二設(shè)計任務(wù) 設(shè)計一個基于DOS菜單的應(yīng)用程序。要利用多級菜單實現(xiàn)各種功能。內(nèi)容如下： 1 無向圖的基本操作及應(yīng)用 創(chuàng)建無向圖的鄰接矩陣 創(chuàng)建無向圖的鄰接表 無向圖的深度優(yōu)先遍歷 無向圖的廣度優(yōu)先遍歷 2有向圖的基本操作及應(yīng)用 創(chuàng)建有向圖的鄰接矩陣 創(chuàng)建有向圖的鄰接表 拓撲排序 3無向網(wǎng)的基本操作及應(yīng)用 創(chuàng)建無向網(wǎng)的鄰接矩陣 創(chuàng)建無向網(wǎng)的鄰接表 求最小生成樹 4有向網(wǎng)的基本操作及應(yīng)用 創(chuàng)建有向網(wǎng)的鄰接矩陣 創(chuàng)建有向網(wǎng)的鄰接表 關(guān)鍵路徑 單源最短路徑 三設(shè)計指導(dǎo) 第一步：根據(jù)設(shè)計任務(wù)，設(shè)計DOS菜單。 第二步：設(shè)計菜單（c語言） #include

3、 void ShowMainMenu() printf(n); printf(*圖的基本操作及應(yīng)用*n); printf(* 1 無向圖的基本操作及應(yīng)用*n); printf(* 2 有向圖的基本操作及應(yīng)用 *n); printf(* 3 無向網(wǎng)的基本操作及應(yīng)用 *n); printf(* 4 有向網(wǎng)的基本操作及應(yīng)用 *n); printf(* 5 退出n); printf(*n); void UDG() int n; do printf(n); printf(*無向圖的基本操作及應(yīng)用*n); printf(* 1 創(chuàng)建無向圖的鄰接矩陣 *n); printf(* 2 創(chuàng)建無向圖的鄰接表 *n

4、); 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

5、DG() int n; do printf(n); printf(*有向圖的基本操作及應(yīng)用*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; def

6、ault: printf(ERROR!); while(n!=4); void UDN() int n; do printf(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;

7、 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; do printf(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); pr

8、intf(* 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; do ShowMainMenu(); printf(請選擇：); scanf(%d,&n)

9、; 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ù)。在主程序的合適位置添加相應(yīng)的函數(shù)實現(xiàn)各功能（提示：語句printf(“-wait-”)所在位置）。 四成績評定 l 實習(xí)報告（文字不得少于4000字） 一、 設(shè)計方案； 二、 實現(xiàn)過程； 三、 實現(xiàn)代碼； 四、 測試； 五、 結(jié)論； 六、 難點與收獲。 l 一、 設(shè)計方案：由課程設(shè)計

10、任務(wù)書，按照要求，需要設(shè)計有向圖3、有向網(wǎng)、無向圖 、無向網(wǎng)四種圖，鄰接矩陣、鄰接表兩種數(shù)據(jù)存儲結(jié)構(gòu)，共十六種基本操作及應(yīng)用，三層以上的顯示菜單。圖的操作中又包含有有關(guān)線性表、棧和隊列的基本操作。由于顯示菜單已給出，剩下的只是把函數(shù)寫入其中，而線性表、棧和隊列的基本操作并不復(fù)雜，很容易實現(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ù)元素（頂點）

11、的信息和數(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個弧的信息存儲量。借助于鄰接矩陣容易判定任意兩個頂點之間是否有邊或弧相連，并容易求各個頂點的度。缺點其時間復(fù)雜度是O（n*n）,例如，構(gòu)造一個具有n個頂點和e條邊的無向網(wǎng)的時間復(fù)雜度為O（n*n+e*n）。 圖的鄰接表存儲結(jié)構(gòu)是圖的一種鏈式存儲結(jié)構(gòu)。

12、對圖中的每個頂點建立一個單鏈表，每個結(jié)點有三個域組成，鄰接點域adjvex（弧尾在鄰接表鏈表中的位序），鏈域nextarc（下一條?。?，數(shù)據(jù)域info(權(quán)值)。還要建立一個鄰接表鏈表，用以存放頂點名data和后繼指針firstarc,表頭結(jié)點以順序結(jié)構(gòu)的形式存儲，便于隨機訪問任一頂點的單鏈表。鄰接表存儲結(jié)構(gòu)的優(yōu)點在于其時間復(fù)雜度小。 除此之外，還有十字鏈表存儲結(jié)構(gòu)和多重鏈表存儲結(jié)構(gòu)。由于，沒有用到他們，故不再詳細描述。 樹的深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。從圖中的某個頂點出發(fā)，訪問此頂點，然后依次從該頂點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有與該頂點有關(guān)的路徑都被訪問到

13、；此時圖中若還有頂點未被訪問到，則另選圖中的一個未被訪問的頂點作為起始點，重述上述過程，直至所有頂點都被訪問到。 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。以某個頂點為起始頂點，由近至遠，依次訪問和該頂點有路徑相通的且路徑長度為1， 2， 3，的頂點。當(dāng)圖中所有頂點都被訪問到后，就完成了圖的廣度優(yōu)先搜索遍歷。 求無向網(wǎng)的最小生成樹問題有兩種算法：Prima算法和Kruskal算法。Prima算法是從網(wǎng)中的某個頂點出發(fā)，選擇與該頂點有路徑的所有頂點中路徑最小的一條路徑，從該最小路徑的另一頂點出發(fā)，重復(fù)上述過程，直至圖中所有頂點都被訪問完成。Kruskal算法是從網(wǎng)中找出所有路徑最小的一條路徑，

14、記下已訪問該路徑的兩個頂點，再次從圖中找出剩下路徑中的最小路徑，重復(fù)上述過程，直至所有頂點都被訪問完成，按訪問的順序依次輸出各頂點，即構(gòu)造了一棵最小生成樹。 由某個集合上的一個偏序得到該集合的一個全序的操作就叫做拓撲排序。拓撲排序主要有兩個方面的操作： （1）在有向圖中選擇一個沒有前驅(qū)的頂點并輸出； （2）在圖中刪除該頂點和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點均已輸出，就得到了一個拓撲有序序列。求關(guān)鍵路徑的算法如下： 輸入e條弧，建立AOE網(wǎng)的存儲結(jié)構(gòu)； 從源點v0出發(fā),令ve0=0，按拓撲有序求其余各頂點的最早發(fā)生時間。如果得到的拓撲有序序列中的頂點個數(shù)小于網(wǎng)中的頂點數(shù)，則說明網(wǎng)中存

15、在環(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è)計任務(wù)的要求，我先完成了存儲結(jié)點、邊、鄰接矩陣、鄰接表、隊列、棧等儲存結(jié)構(gòu)體的設(shè)計。其次是棧和隊列的基本操作和實現(xiàn)，四種圖的創(chuàng)建和顯

16、示，然后是基于兩種存儲結(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 10 typedef enumDG,DN,UDG,UDNGraphKind; typedef struct ArcCell int adj; /infotype *info; ArcCell,

17、 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_VERT

18、EX_NUM; typedef struct AdjList vertices; int vexnum,arcnum; GraphKind kind; ALGraph; /鄰接表 typedef struct QNode char data; struct QNode *next; QNode,*QueuePre; typedef struct QueuePre front; QueuePre rear; LinkQueue; /隊列 typedef struct int *base; int *top; int stacksize; SqStack; /棧 typedef struct ch

19、ar 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

20、=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(MGra

21、ph 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;

22、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 InitS

23、tack(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 ERR

24、OR; 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; i

25、f(!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.vexn

26、um;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)的兩個相鄰的頂點以及相應(yīng)的權(quán)值w（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c %d,&x,&y,&w);