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

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

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

3、 void ShowMainMenu() printf(n); printf(*圖的基本操作及應(yīng)用*n); printf(* 1 無(wú)向圖的基本操作及應(yīng)用*n); printf(* 2 有向圖的基本操作及應(yīng)用 *n); printf(* 3 無(wú)向網(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(*無(wú)向圖的基本操作及應(yīng)用*n); printf(* 1 創(chuàng)建無(wú)向圖的鄰接矩陣 *n); printf(* 2 創(chuàng)建無(wú)向圖的鄰接表 *n

4、); printf(* 3 無(wú)向圖的深度優(yōu)先遍歷 *n); printf(* 4 無(wú)向圖的廣度優(yōu)先遍歷 *n); printf(* 5 退出n); printf(*n); printf(請(qǐng)選擇：); 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 拓?fù)渑判?*n); printf(* 4 退出 *n); printf(*n); printf(請(qǐng)選擇：); 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ú)向網(wǎng)的基本操作及 *n); printf(* 1 創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣 *n); printf(* 2 創(chuàng)建無(wú)向網(wǎng)的鄰接表 *n); printf(* 3 Prim算法求最小生成樹(shù) *n); printf(* 4 kraskal算法求最小生成樹(shù) *n); printf(* 5 退出n); printf(*n); printf(請(qǐng)選擇：); 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 單源頂點(diǎn)最短路徑問(wèn)題 *n); pr

8、intf(* 5 退出n); printf(*n); printf(請(qǐng)選擇：); 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(請(qǐng)選擇：); 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ù)實(shí)現(xiàn)各功能（提示：語(yǔ)句printf(“-wait-”)所在位置）。 四成績(jī)?cè)u(píng)定 l 實(shí)習(xí)報(bào)告（文字不得少于4000字） 一、 設(shè)計(jì)方案； 二、 實(shí)現(xiàn)過(guò)程； 三、 實(shí)現(xiàn)代碼； 四、 測(cè)試； 五、 結(jié)論； 六、 難點(diǎn)與收獲。 l 一、 設(shè)計(jì)方案：由課程設(shè)計(jì)

10、任務(wù)書(shū)，按照要求，需要設(shè)計(jì)有向圖3、有向網(wǎng)、無(wú)向圖 、無(wú)向網(wǎng)四種圖，鄰接矩陣、鄰接表兩種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，共十六種基本操作及應(yīng)用，三層以上的顯示菜單。圖的操作中又包含有有關(guān)線性表、棧和隊(duì)列的基本操作。由于顯示菜單已給出，剩下的只是把函數(shù)寫(xiě)入其中，而線性表、棧和隊(duì)列的基本操作并不復(fù)雜，很容易實(shí)現(xiàn)，我們只有完成圖的相關(guān)操作即可。 圖的操作都是以?xún)煞N存儲(chǔ)結(jié)構(gòu)為基礎(chǔ)的，鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ) 結(jié)構(gòu)，如四種圖（有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)）的創(chuàng)建，其他的操作都是在四種圖創(chuàng)建后才開(kāi)始進(jìn)行的。所以，首先必須理解兩種存儲(chǔ)結(jié)構(gòu)的定義。 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)即圖的數(shù)組表示法。用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）

11、的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔ⅰＳ绵徑泳仃嚧鎯?chǔ)結(jié)構(gòu)的圖具有以下幾點(diǎn)特征： （一）：頂點(diǎn)數(shù)：vexnum，邊（?。?shù)：arcnum，圖的種類(lèi)：kind； （二）：鄰接矩陣：arcs(1頂點(diǎn)關(guān)系類(lèi)型:adj 2相關(guān)信息:*info)； （三）：頂點(diǎn)向量（頂點(diǎn)名）：vexs； 其優(yōu)點(diǎn)是以二維數(shù)組表示有n個(gè)頂點(diǎn)的圖時(shí)，需存放n頂點(diǎn)的信息和n*n個(gè)弧的信息存儲(chǔ)量。借助于鄰接矩陣容易判定任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，并容易求各個(gè)頂點(diǎn)的度。缺點(diǎn)其時(shí)間復(fù)雜度是O（n*n）,例如，構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向網(wǎng)的時(shí)間復(fù)雜度為O（n*n+e*n）。 圖的鄰接表存儲(chǔ)結(jié)構(gòu)是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

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

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

14、記下已訪問(wèn)該路徑的兩個(gè)頂點(diǎn)，再次從圖中找出剩下路徑中的最小路徑，重復(fù)上述過(guò)程，直至所有頂點(diǎn)都被訪問(wèn)完成，按訪問(wèn)的順序依次輸出各頂點(diǎn)，即構(gòu)造了一棵最小生成樹(shù)。 由某個(gè)集合上的一個(gè)偏序得到該集合的一個(gè)全序的操作就叫做拓?fù)渑判?。拓?fù)渑判蛑饕袃蓚€(gè)方面的操作： （1）在有向圖中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并輸出； （2）在圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，就得到了一個(gè)拓?fù)溆行蛐蛄?。求關(guān)鍵路徑的算法如下： 輸入e條弧，建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)； 從源點(diǎn)v0出發(fā),令ve0=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間。如果得到的拓?fù)溆行蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)中的頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)中存

15、在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行第三步。 從匯點(diǎn)vn出發(fā)，令vln-1=ven-1，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vli； 根據(jù)各頂點(diǎn)的和值，求每條弧的最早開(kāi)始時(shí)間e(s)和最遲開(kāi)始時(shí)間e(s)，若某條弧滿(mǎn)足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)。 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問(wèn)題：若從v到vi有弧，則Di為弧上的權(quán)值，否則Di為無(wú)窮大。顯然，長(zhǎng)度為Dj=MinDi|vi屬于V的路徑就是從v出發(fā)的長(zhǎng)度最短的一條路徑。 二、 實(shí)現(xiàn)及測(cè)試過(guò)程 按照設(shè)計(jì)任務(wù)的要求，我先完成了存儲(chǔ)結(jié)點(diǎn)、邊、鄰接矩陣、鄰接表、隊(duì)列、棧等儲(chǔ)存結(jié)構(gòu)體的設(shè)計(jì)。其次是棧和隊(duì)列的基本操作和實(shí)現(xiàn)，四種圖的創(chuàng)建和顯

16、示，然后是基于兩種存儲(chǔ)結(jié)構(gòu)的各種算法的現(xiàn)，最后是三層顯示輸出菜單。 測(cè)試樣圖： 實(shí)現(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; /隊(duì)列 typedef struct int *base; int *top; int stacksize; SqStack; /棧 typedef struct ch

19、ar adjvex; int lowcost; closedgesMAX_VERTEX_NUM; /求最小生成樹(shù)中的輔助數(shù)組 int option; int visitedMAX_VERTEX_NUM; /頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組 int indegreeMAX_VERTEX_NUM; /頂點(diǎn)入度記錄數(shù)組 int veMAX_VERTEX_NUM; /頂點(diǎn)權(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; /鄰接矩陣類(lèi)型設(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; /鄰接表類(lèi)型設(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; /鄰接矩陣頂點(diǎn)定位 int LocateVex(ALGraph G,char v) int m; for(m=1;mnext=NULL; return OK; /隊(duì)列創(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; /元素入隊(duì)列 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; /元素出隊(duì)列 int QueueEmpty(LinkQueue Q) if(Q.front=Q.rear) return OK; return ERROR; /判斷隊(duì)列是否為空 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(對(duì)圖類(lèi)型的設(shè)置失敗);return ERROR; printf(鄰接矩陣：請(qǐng)輸入定點(diǎn)的個(gè)數(shù)、弧的個(gè)數(shù)：); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum20) printf(您輸入的頂點(diǎn)個(gè)數(shù)超過(guò)最大值); return ERROR; printf(請(qǐng)輸入%d個(gè)頂點(diǎn)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(請(qǐng)輸入有向圖的兩個(gè)相鄰的頂點(diǎn)（如果互相鄰接則也要輸入）：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(請(qǐng)輸入無(wú)向圖的兩個(gè)相鄰的頂點(diǎn)（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(請(qǐng)輸入有向網(wǎng)的兩個(gè)相鄰的頂點(diǎn)以及相應(yīng)的權(quán)值w（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c %d,&x,&y,&w);