算法與數據結構課程設計報告系 （院）： 計算機科學學院 專業班級： 教育技術學1001班 姓 名： 宋佳 學 號： 201003901 指導教師： 詹澤梅 設計時間： 2012.6.16 - 2012.6.24 設計地點： 4號樓2號機房 算法與數據結構課程設計任務書班級：教育技術11001課程設計題目：圖的基本操作及應用數據結構課程設計是在學完數據結構課程之后的實踐教學環節。本實踐教學是培養學生數據抽象能力，進行復雜程序設計的訓練過程。要求學生能對所涉及問題選擇合適的數據結構、存儲結構及算法，并編寫出結構清楚且正確易讀的程序，提高程序設計基本技能和技巧。一設計目的1提高數據抽象能力。根據實際問題，能利用數據結構理論課中所學到的知識選擇合適的邏輯結構以及存儲結構，并設計出有效解決問題的算法。2提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。3初步了解開發過程中問題分析、整體設計、程序編碼、測試等基本方法和技能。二設計任務設計一個基于DOS菜單的應用程序。要利用多級菜單實現各種功能。內容如下：1 無向圖的基本操作及應用 創建無向圖的鄰接矩陣 創建無向圖的鄰接表 無向圖的深度優先遍歷 無向圖的廣度優先遍歷2 有向圖的基本操作及應用 創建有向圖的鄰接矩陣 創建有向圖的鄰接表 拓撲排序3 無向網的基本操作及應用 創建無向網的鄰接矩陣 創建無向網的鄰接表 求最小生成樹 4 有向網的基本操作及應用 創建有向網的鄰接矩陣 創建有向網的鄰接表 關鍵路徑 單源最短路徑 三設計指導第一步：根據設計任務，設計DOS菜單。第二步：設計菜單（c語言）#includevoid ShowMainMenu()printf(n);printf(*圖的基本操作及應用*n);printf(* 1 無向圖的基本操作及應用 *n);printf(* 2 有向圖的基本操作及應用 *n);printf(* 3 無向網的基本操作及應用 *n);printf(* 4 有向網的基本操作及應用 *n);printf(* 5 退出n);printf(*n);void UDG()int n;doprintf(n);printf(*無向圖的基本操作及應用*n);printf(* 1 創建無向圖的鄰接矩陣 *n);printf(* 2 創建無向圖的鄰接表 *n);printf(* 3 無向圖的深度優先遍歷 *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 DG() int n;doprintf(n);printf(*有向圖的基本操作及應用*n);printf(* 1 創建有向圖的鄰接矩陣 *n);printf(* 2 創建有向圖的鄰接表 *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(*無向網的基本操作及 *n);printf(* 1 創建無向網的鄰接矩陣 *n);printf(* 2 創建無向網的鄰接表 *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(*有向網的基本操作*n);printf(* 1 創建有向網的鄰接矩陣 *n);printf(* 2 創建有向網的鄰接表 *n);printf(* 3 關鍵路徑 *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);第三步：添加功能函數。在主程序的合適位置添加相應的函數實現各功能（提示：語句printf(“-wait-”)所在位置）。四成績評定l 實習報告（文字不得少于4000字）一、 設計方案；二、 實現過程；三、 實現代碼；四、 測試；五、 結論；六、 難點與收獲。l 程序實現1. 程序運行正確，無編譯錯誤，無邏輯錯誤；2. 在第一條的基礎上，任務完成的越多，成績等級越高。l 成績由三部分組成：平時考核(20%)、程序實現(50%)、實習報告(30%)一、 設計方案由課程設計任務書，按照要求，需要設計有向圖3、有向網、無向圖 、無向網四種圖，鄰接矩陣、鄰接表兩種數據存儲結構，共十六種基本操作及應用，三層以上的顯示菜單。圖的操作中又包含有有關線性表、棧和隊列的基本操作。由于顯示菜單已給出，剩下的只是把函數寫入其中，而線性表、棧和隊列的基本操作并不復雜，很容易實現，我們只有完成圖的相關操作即可。圖的操作都是以兩種存儲結構為基礎的，鄰接矩陣存儲結構和鄰接表存儲結構，如四種圖（有向圖，有向網，無向圖，無向網）的創建，其他的操作都是在四種圖創建后才開始進行的。所以，首先必須理解兩種存儲結構的定義。圖的鄰接矩陣存儲結構即圖的數組表示法。用兩個數組分別存儲數據元素（頂點）的信息和數據元素之間的關系（邊或弧）的信息。用鄰接矩陣存儲結構的圖具有以下幾點特征：（一）：頂點數：vexnum，邊（弧）數：arcnum，圖的種類：kind；（二）：鄰接矩陣：arcs(1頂點關系類型:adj 2相關信息:*info)；（三）：頂點向量（頂點名）：vexs；其優點是以二維數組表示有n個頂點的圖時，需存放n頂點的信息和n*n個弧的信息存儲量。借助于鄰接矩陣容易判定任意兩個頂點之間是否有邊或弧相連，并容易求各個頂點的度。缺點其時間復雜度是O（n*n）,例如，構造一個具有n個頂點和e條邊的無向網的時間復雜度為O（n*n+e*n）。圖的鄰接表存儲結構是圖的一種鏈式存儲結構。對圖中的每個頂點建立一個單鏈表，每個結點有三個域組成，鄰接點域adjvex（弧尾在鄰接表鏈表中的位序），鏈域nextarc（下一條?。?，數據域info(權值)。還要建立一個鄰接表鏈表，用以存放頂點名data和后繼指針firstarc,表頭結點以順序結構的形式存儲，便于隨機訪問任一頂點的單鏈表。鄰接表存儲結構的優點在于其時間復雜度小。除此之外，還有十字鏈表存儲結構和多重鏈表存儲結構。由于，沒有用到他們，故不再詳細描述。樹的深度優先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。從圖中的某個頂點出發，訪問此頂點，然后依次從該頂點出發深度優先搜索遍歷圖，直至圖中所有與該頂點有關的路徑都被訪問到；此時圖中若還有頂點未被訪問到，則另選圖中的一個未被訪問的頂點作為起始點，重述上述過程，直至所有頂點都被訪問到。廣度優先搜索遍歷類似于樹的按層次遍歷的過程。以某個頂點為起始頂點，由近至遠，依次訪問和該頂點有路徑相通的且路徑長度為1， 2， 3，的頂點。當圖中所有頂點都被訪問到后，就完成了圖的廣度優先搜索遍歷。求無向網的最小生成樹問題有兩種算法：Prima算法和Kruskal算法。Prima算法是從網中的某個頂點出發，選擇與該頂點有路徑的所有頂點中路徑最小的一條路徑，從該最小路徑的另一頂點出發，重復上述過程，直至圖中所有頂點都被訪問完成。Kruskal算法是從網中找出所有路徑最小的一條路徑，記下已訪問該路徑的兩個頂點，再次從圖中找出剩下路徑中的最小路徑，重復上述過程，直至所有頂點都被訪問完成，按訪問的順序依次輸出各頂點，即構造了一棵最小生成樹。由某個集合上的一個偏序得到該集合的一個全序的操作就叫做拓撲排序。拓撲排序主要有兩個方面的操作：（1）在有向圖中選擇一個沒有前驅的頂點并輸出；（2）在圖中刪除該頂點和所有以它為尾的弧。重復上述兩步，直至全部頂點均已輸出，就得到了一個拓撲有序序列。求關鍵路徑的算法如下：輸入e條弧，建立AOE網的存儲結構；從源點v0出發,令ve0=0，按拓撲有序求其余各頂點的最早發生時間。如果得到的拓撲有序序列中的頂點個數小于網中的頂點數，則說明網中存在環，不能求關鍵路徑，算法終止；否則執行第三步。從匯點vn出發，令vln-1=ven-1，按逆拓撲有序求其余各頂點的最遲發生時間vli；根據各頂點的和值，求每條弧的最早開始時間e(s)和最遲開始時間e(s)，若某條弧滿足條件e(s)=l(s)，則為關鍵活動。從某個源點到其余各頂點的最短路徑問題：若從v到vi有弧，則Di為弧上的權值，否則Di為無窮大。顯然，長度為Dj=MinDi|vi屬于V的路徑就是從v出發的長度最短的一條路徑。二、 實現及測試過程按照設計任務的要求，我先完成了存儲結點、邊、鄰接矩陣、鄰接表、隊列、棧等儲存結構體的設計。其次是棧和隊列的基本操作和實現，四種圖的創建和顯示，然后是基于兩種存儲結構的各種算法的現，最后是三層顯示輸出菜單。測試樣圖：三、實現代碼#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; /求最小生成樹中的輔助數組int option; int visitedMAX_VERTEX_NUM; /頂點訪問標記數組int indegreeMAX_VERTEX_NUM; /頂點入度記錄數組int veMAX_VERTEX_NUM; /頂點權值記錄數組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; /鄰接矩陣類型設置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; /鄰接表類型設置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; /隊列創建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; /棧創建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(對圖類型的設置失敗);return ERROR; printf(鄰接矩陣：請輸入定點的個數、弧的個數：); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum20) printf(您輸入的頂點個數超過最大值); 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（如果互相鄰接則也要輸入）：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(請輸入無向網的兩個相鄰的頂點（x,y）以及相應的權值w：n); for(k=1;k20) printf(您輸入的頂點個數超過最大值); 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(請輸入弧（如AB,其中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(請輸入依次輸入弧以及這條弧的權值（如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(請輸入依次輸入弧以及這條弧的權值（如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; /創建鄰接表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