蘭州大學數(shù)據(jù)結(jié)構(gòu)實驗 關(guān)鍵路徑實驗報告

1、蘭州大學信息科學與工程學院數(shù)據(jù)結(jié)構(gòu)實驗報告 課程名稱 數(shù)據(jù)結(jié)構(gòu) 實驗名稱 數(shù)據(jù)結(jié)構(gòu)實驗 專業(yè)班級 姓 名 學 號 實驗日期 第 日 周 星期 三,四 節(jié) 實驗地點 賀蘭堂 20122013學年度第 一 學期一、實驗?zāi)康?、熟悉圖的相關(guān)知識，加深對圖關(guān)鍵路徑查找方法的理解二、實驗內(nèi)容1、 對于給定的一個工程施工圖，該圖以邊為單位從鍵盤輸入，編寫能夠找出該圖的關(guān)鍵路徑的程序。三、實驗環(huán)境1、硬件配置：Pentium（R） Dual-Core9 CUP E6500 2.93GHz，1.96的內(nèi)存2、軟件環(huán)境：Microsoft Windows XP Professional Service Pack

2、 3，Microsoft Visual C+ 6.0四、需求分析1、輸入的形式和輸入值的范圍：根據(jù)題目要求與提示輸入點和邊的數(shù)目，然后根據(jù)你的圖的信息，將邊輸進程序中。2、輸出的形式：輸出關(guān)鍵路徑的各個節(jié)點。3、程序所能達到的功能：輸出給定圖的關(guān)鍵路徑。4、測試數(shù)據(jù)：輸入點和邊的數(shù)目，以空格隔開，然后輸入每條邊，邊的起點和終點，權(quán)以空格隔開，回車，輸出關(guān)鍵路徑。如：輸入點和邊的數(shù)目 3 2 輸入第一個邊的起點，終點 及權(quán) 1 2 12輸入第二個邊的起點，終點 及權(quán) 1 3 16輸出關(guān)鍵路徑為.五、概要設(shè)計為了實現(xiàn)上述操作，應(yīng)以數(shù)組和鏈表為存儲結(jié)構(gòu),。1、基本操作：（1）void creatad

3、jlist(adjlist *G,int n,int e)初始條件：adjlist *G指針形式的指針存在，以及存在節(jié)點的數(shù)目n, 節(jié)點的數(shù)目e；操作結(jié)果：建立以adjlist *G為指針的鄰接表。（2）int topsort(adjlist *G,int n)初始條件：adjlist *G為一已知圖的鄰接表，n為節(jié)點的數(shù)目；操作結(jié)果：返回節(jié)點的關(guān)鍵路徑最后節(jié)點的編號。（3）void creat_path(adjlist *G,int top2,int n)初始條件：adjlist *G，圖最后節(jié)點的編號top2,節(jié)點的數(shù)目n；操作結(jié)果：輸出圖adjlist *G的關(guān)鍵路徑。2、本程序包含三個

4、模塊：（1）主程序模塊；（2）構(gòu)造鄰接表函數(shù)，尋找關(guān)鍵路徑末節(jié)點和求各節(jié)點事件發(fā)生最早時間函數(shù)，輸出圖的關(guān)鍵路徑函數(shù)模塊（3）模塊調(diào)用圖：主程序模塊輸出圖關(guān)鍵路徑模塊尋找關(guān)鍵路徑末節(jié)點和求各節(jié)點事件發(fā)生最早模塊構(gòu)造鄰接表函數(shù)模塊3、流程圖主函數(shù)屏幕輸出“請輸入點和邊的數(shù)目”n =點的數(shù)目,e =邊的數(shù)目 設(shè)定圖類型的指針變量G，并開辟出相應(yīng)的空間調(diào)用創(chuàng)建鄰接表的函數(shù)調(diào)用求關(guān)鍵路徑最后節(jié)點和計算事件發(fā)生最早時間的函數(shù)調(diào)用輸出關(guān)鍵路徑的函數(shù)構(gòu)建鄰接表函數(shù)初始條件有圖類型的指針G，節(jié)點數(shù)n，邊數(shù)e當i 從0變到節(jié)點數(shù)圖的結(jié)構(gòu)體數(shù)組中每個指向下一個的元素為NULL設(shè)定每個點編號設(shè)定每個節(jié)點的入度為0設(shè)

5、定每個節(jié)點的最早開始時間為0當i從0 變到邊數(shù)e屏幕輸出“請輸入地%d邊的起點，終點及權(quán)”a= 起點b=終點w=權(quán)值設(shè)定鄰接表節(jié)點類型的變量pP的弧頭等于b,權(quán)值w標號b-1的鄰接表的頭節(jié)點的入度加一建立鄰接表a-1的相應(yīng)的指向關(guān)系尋找關(guān)鍵路徑的最后節(jié)點以及計算各個時間的最早發(fā)生時間的函數(shù)初始化有鄰接表類型的指針G，還有節(jié)點數(shù)ntop1 = 0,top2 = 0，當i從1變到小于n是如果節(jié)點的入度為0否top1賦值給該節(jié)點的入度i賦值給top1當top1不等于0j=top1top1值賦為編號j-1節(jié)點的入度j-1節(jié)點的入度賦值給top2top2=jm+p指向編號為j-1頭節(jié)點鄰接表所指向的節(jié)點

6、當p不為空k = p所在鄰接表節(jié)點的弧頭編號編號為k-1鄰接表頭節(jié)點的入度減一是如果編號為k-1頭節(jié)點的入度為0否編號為k-1頭節(jié)點的入度賦值為賦值為是編號時間小于時間加權(quán)值否的時間進行修改指向下一個鄰接表節(jié)點結(jié)構(gòu)體是小于的值否屏幕輸出“有回路！”然會的數(shù)值輸出關(guān)鍵路徑函數(shù)初始條件有圖類型的指針，關(guān)鍵路徑最后一個節(jié)點，節(jié)點總數(shù)設(shè)定整形變量來記錄關(guān)鍵路徑最后一個節(jié)點的位置當從變到每個鄰接表的頭節(jié)點數(shù)的時間最晚發(fā)生時間賦值為對應(yīng)事件的最早發(fā)生時間當?shù)闹挡粸闀rv=top2 top2等于編號頭節(jié)點的入度指向下一個鄰接表節(jié)點結(jié)構(gòu)體當不為空時j=p的弧尾編號是按公式算的最晚時間小于原來設(shè)定的最晚時間否修改

7、該點最晚時間指向下一個鄰接表節(jié)點結(jié)構(gòu)體屏幕輸出“關(guān)鍵路徑為”從變到指向編號的鄰接表表頭節(jié)點所指向的節(jié)點結(jié)構(gòu)體當不為時賦值為所在鄰接表節(jié)點結(jié)構(gòu)體的弧頭編號記錄事件發(fā)生的最早時間通過計算獲得事件發(fā)生的最晚時間是是否相等于否輸出該節(jié)點的鄰接表頭指針內(nèi)的編號指向鄰接表內(nèi)下一個節(jié)點輸出原先記錄的關(guān)鍵路徑最后一個節(jié)點六、詳細設(shè)計1、存儲類型，元素類型，結(jié)點類型：typedef struct node/鄰接表節(jié)點結(jié)構(gòu)體 int adjvex;/弧頭所在所在位置 int weight;/權(quán)值 struct node *next;node;typedef struct vexnode/鄰接表表頭結(jié)構(gòu)體 int

8、vertex,indegree;/圖節(jié)點的編號，入度 int ve,vl;/時間最早發(fā)生時間和最晚發(fā)生時間按 node *link;vexnode;typedef struct adjlist/鄰接表結(jié)構(gòu)體 vexnode A50;adjlist;2、每個模塊的分析：（1）主程序模塊：void main() int n,e; int top2; adjlist *G; printf("請輸入點和邊的數(shù)目:"); scanf("%d %d",&n,&e);/n,e分別代表圖的節(jié)點數(shù)和邊數(shù) G=(adjlist *)malloc(sizeof

9、(adjlist);/堆分配G的鄰接表空間 creatadjlist(G,n,e);/調(diào)用構(gòu)建鄰接表函數(shù) top2=topsort(G,n);/調(diào)用求關(guān)鍵路徑最后節(jié)點和計算最短時間的函數(shù) creat_path(G,top2,n);/調(diào)用輸出圖的關(guān)鍵路徑函數(shù)（2）構(gòu)造鄰接表模塊void creatadjlist(adjlist *G,int n,int e) /adjlist *G指針形式的指針存在，以及存在節(jié)點的數(shù)目n, 節(jié)點的數(shù)目e int a,b,w,i; node *p; for(i=0;i<n;i+) /初始化鄰接表的表頭 G->Ai.link=NULL; G->Ai

10、.vertex=i+1; G->Ai.indegree=0;/入度為0 G->Ai.ve=0;/最早發(fā)生時間為0 for(i=0;i<e;i+) printf("請輸入第%d個邊的起點,終點及權(quán) n",i+1); scanf("%d %d %d",&a,&b,&w); printf("n"); p=(node *)malloc(LEN);/開辟鄰接表節(jié)點結(jié)構(gòu)體空間，實現(xiàn)圖中邊的關(guān)系 p->adjvex=b; p->weight=w; G->Ab-1.indegree+;/弧頭

11、的入度增加 p->next=G->Aa-1.link;/建立弧尾為確定圖節(jié)點的指向其余圖節(jié)點的關(guān)系 G->Aa-1.link=p; 返回關(guān)鍵路徑最后節(jié)點和計算各節(jié)點最早發(fā)生時間函數(shù)模塊int topsort(adjlist *G,int n)/adjlist *G為一已知圖的鄰接表，n為節(jié)點的數(shù)目 int top1=0,top2=0;/top1用來記錄上一次遍歷圖節(jié)點的位置，top2用來記錄記錄每次遍歷圖節(jié)點的起始位置 int m=0,i,k,j; node *p; for(i=1;i<=n;i+) /有向無環(huán)圖中必有一個入度為0的節(jié)點，這個節(jié)點為關(guān)鍵路徑的起始節(jié)點 i

12、f(G->Ai-1.indegree=0) G->Ai-1.indegree=top1; top1=i; while(top1!=0) j=top1; top1=G->Aj-1.indegree;/top1為該節(jié)點的入度 G->Aj-1.indegree=top2; top2=j;/top2每次遍歷弧尾的位置 m+; /用來記錄尋找關(guān)鍵路徑過程，遍歷過節(jié)點的數(shù)目，無重復 p=G->Aj-1.link; while(p!=NULL) k=p->adjvex;/k等于圖節(jié)點的編號 G->Ak-1.indegree=G->Ak-1.indegree-;

13、/根據(jù)拓撲排序的方法，將于同一弧尾相連的弧頭的入度減一 if(G->Ak-1.indegree=0) G->Ak-1.indegree=top1;/利用修改圖節(jié)點的入度，記錄上一次遍歷節(jié)點的位置 top1=k; if(G->Aj-1.ve+p->weight)>G->Ak-1.ve) G->Ak-1.ve=G->Aj-1.ve + p->weight;/在遍歷圖的同時，求出每個節(jié)點時間的最早發(fā)生時間 p=p->next;/依照鄰接表遍歷與同一弧尾相連的各個弧頭節(jié)點 if(m<n)/若遍歷過程經(jīng)歷的節(jié)點數(shù)小于圖中所有的節(jié)點數(shù)，說明

14、圖不為有向無環(huán)圖 printf("有回路！"); return top2;輸出關(guān)鍵路徑函數(shù)模塊void creat_path(adjlist *G,int top2,int n)/adjlist *G，圖最后節(jié)點的編號top2,節(jié)點的數(shù)目n int i,v,j; int ei,el; node *p; int endnode; endnode=top2; for(i=0;i<n;i+) G->Ai.vl=G->An-1.ve;/初始化每個節(jié)點的最早發(fā)生時間和最晚發(fā)生時間 while(top2!=0) v=top2; top2=G->Av-1.inde

15、gree;/根據(jù)返回關(guān)鍵路徑最后節(jié)點和計算各節(jié)點最早發(fā)生時間函數(shù)，每個節(jié)點的入度為遍歷該節(jié)點的前一個遍歷節(jié)點的位置，利用此條性質(zhì)重新遍歷圖上各個節(jié)點 p=G->Av-1.link; while(p!=NULL) j=p->adjvex; if(G->Aj-1.vl-p->weight<G->Av-1.vl) G->Av-1.vl=G->Aj-1.vl-p->weight;/修改每個事件最晚發(fā)生時間 p=p->next; printf("n關(guān)鍵路徑是：n");/求關(guān)鍵路徑 for(i=0;i<n;i+) p=G

16、->Ai.link; while(p!=NULL) j=p->adjvex; ei=G->Ai.ve; el=G->Aj-1.vl-p->weight; if(ei=el)/關(guān)鍵路徑上每個點的最晚發(fā)生時間與最早發(fā)生時間相同 printf("V%d,",G->Ai.vertex);/輸出關(guān)鍵路徑上的節(jié)點 p=p->next; printf("V%d n",G->Aendnode-1.vertex);3）函數(shù)調(diào)用關(guān)系圖main()void creat_path(adjlist *G,int top2,int n

17、)int topsort(adjlist *G,int n)void creatadjlist(adjlist *G,int n,int e)3、完整的程序：#include "stdio.h"#include "malloc.h"#define LEN sizeof (node)#define NULL 0typedef struct node int adjvex; int weight; struct node *next;node;/鄰接表的節(jié)點typedef struct vexnode int vertex,indegree; int ve,

18、vl; node *link;vexnode;/鄰接表表頭typedef struct adjlist vexnode A50;adjlist;/鄰接表void creatadjlist(adjlist *G,int n,int e)/創(chuàng)建鄰接表 int a,b,w,i; node *p; for(i=0;i<n;i+) G->Ai.link=NULL; G->Ai.vertex=i+1; G->Ai.indegree=0; G->Ai.ve=0; for(i=0;i<e;i+) printf("請輸入第%d個邊的起點,終點及權(quán) n",i

19、+1); scanf("%d %d %d",&a,&b,&w); printf("n"); p=(node *)malloc(LEN); p->adjvex=b; p->weight=w; G->Ab-1.indegree+; p->next=G->Aa-1.link; G->Aa-1.link=p; int topsort(adjlist *G,int n)/尋找關(guān)鍵路徑的最后節(jié)點 int top1=0,top2=0; int m=0,i,k,j; node *p; for(i=1;i<

20、=n;i+) if(G->Ai-1.indegree=0) G->Ai-1.indegree=top1; top1=i; while(top1!=0) j=top1; top1=G->Aj-1.indegree; G->Aj-1.indegree=top2; top2=j; m+; p=G->Aj-1.link; while(p!=NULL) k=p->adjvex; G->Ak-1.indegree=G->Ak-1.indegree-; if(G->Ak-1.indegree=0) G->Ak-1.indegree=top1; to

21、p1=k; if(G->Aj-1.ve+p->weight)>G->Ak-1.ve) G->Ak-1.ve=G->Aj-1.ve + p->weight;/修改各個節(jié)點的最早發(fā)生時間 p=p->next; if(m<n) printf("有回路！"); return top2;void creat_path(adjlist *G,int top2,int n)/輸出關(guān)鍵路徑 int i,v,j; int ei,el; node *p; int endnode; endnode=top2; for(i=0;i<n;i

22、+) G->Ai.vl=G->An-1.ve; while(top2!=0) v=top2; top2=G->Av-1.indegree; p=G->Av-1.link; while(p!=NULL) j=p->adjvex; if(G->Aj-1.vl-p->weight<G->Av-1.vl) G->Av-1.vl=G->Aj-1.vl-p->weight;/修改最晚發(fā)生時間 p=p->next; printf("n關(guān)鍵路徑是：n");/求關(guān)鍵路徑 for(i=0;i<n;i+) p=G

23、->Ai.link; while(p!=NULL) j=p->adjvex; ei=G->Ai.ve; el=G->Aj-1.vl-p->weight;/各個事件的最晚發(fā)生時間 if(ei=el)/最早發(fā)生時間與最晚發(fā)生時間相同的節(jié)點為關(guān)鍵路徑上的節(jié)點 printf("V%d,",G->Ai.vertex); p=p->next; printf("V%d n",G->Aendnode-1.vertex);void main() int n,e; int top2; adjlist *G; printf("請輸入點和邊的數(shù)目:"); scanf("%d %d",&n,&e); G=(adjlist *)malloc(sizeof(adjlist);/為存儲圖開辟相應(yīng)的空間 creatadjlist(G,n,e); top2=to