數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--關(guān)鍵路徑的實(shí)現(xiàn)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　題目： 關(guān)鍵路徑的實(shí)現(xiàn)</p><p>　　院（系）：計(jì)算機(jī)工程學(xué)院 </p><p>　　學(xué)生姓名: </p><p>　　班級(jí)： 學(xué)號(hào):</p><p><b>　　一、需求分析<

2、;/b></p><p><b>　　1.問(wèn)題描述</b></p><p>　　找出實(shí)際工程中的關(guān)鍵路徑，合理安排關(guān)鍵活動(dòng)的施工順序。要求：</p><p>　　(1)表示工程的圖可以用鄰接表或鄰接矩陣存儲(chǔ)；</p><p>　　(2)應(yīng)能以圖形的方式輸出圖；</p><p>　　(3)輸出

3、關(guān)鍵路徑和關(guān)鍵活動(dòng)。</p><p><b>　　2.基本功能</b></p><p>　　(1)用鄰接表存儲(chǔ)有向圖并建立AOE網(wǎng) CreateGraph（）；</p><p>　　(2)用圖形的形式輸出有向圖Display();</p><p>　　(3)輸出關(guān)鍵路徑和關(guān)鍵活動(dòng) SearchMapPath（）；&l

4、t;/p><p><b>　　3.輸入輸出</b></p><p>　　輸入: (1)有向圖的頂點(diǎn)數(shù)和弧數(shù)，都是int型，中間用空格隔開；</p><p>　　(2)圖中的各個(gè)頂點(diǎn)的值，char型;</p><p>　　(3)圖中弧的權(quán)值、起點(diǎn)、終點(diǎn),都是int型，中間用空格隔開；</p><p>　

5、　輸出： 起點(diǎn)（char）、終點(diǎn)(char) 、最早開始時(shí)間(int)、最遲開始時(shí)間(int)、差值(int)、是否為關(guān)鍵活動(dòng)、關(guān)鍵路徑。</p><p><b>　　二、 概要設(shè)計(jì)</b></p><p><b>　　1.設(shè)計(jì)思路：</b></p><p>　　(1) 輸入圖的頂點(diǎn)數(shù)和弧數(shù)。</p>

6、<p>　　(2) 輸入這個(gè)圖中每段弧的起始點(diǎn)及權(quán)值。</p><p>　　(3) 用輸入的數(shù)據(jù)建立AOE網(wǎng)。</p><p>　　(4) 用鄰接表來(lái)存儲(chǔ)圖的這些信息。 </p><p>　　(5) 用CreateGraph( )函數(shù)建立AOE圖。</p><p>　　(6)用Display()函數(shù)輸出AOE圖。</p>

7、<p>　　(7) 用SearchMapPath ( )函數(shù)求出最長(zhǎng)路徑，并輸出關(guān)鍵路徑。</p><p><b>　　(8) 編寫程序。</b></p><p><b>　　2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：</b></p><p>　?。?）邏輯結(jié)構(gòu)采用圖狀的結(jié)構(gòu)。圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)

8、元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（即其孩子結(jié)點(diǎn)）相關(guān)，但只能和上一層中一個(gè)元素（即其雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。而由于本程序的操作對(duì)象是有向圖，所以必須采用圖狀的結(jié)構(gòu)。</p><p>　?。?）存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)降慕Y(jié)構(gòu)。由于

9、圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，因此無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系，即圖沒(méi)有順序映象的存儲(chǔ)結(jié)構(gòu)，因此采用鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)。</p><p>　　（3）抽象數(shù)據(jù)類型圖的定義如下：</p><p>　　ADT Graph{ 數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。</p><p><b>　　數(shù)

10、據(jù)關(guān)系R：</b></p><p><b>　　R={VR}</b></p><p>　　VR={<v,w>|v,w∈V且P（v,w）,<v,w>表示從v到w的弧，</p><p>　　謂詞P（v,w）定義了弧<v,w>的意義或信息}</p><p><b>　　

11、基本操作P：</b></p><p>　　CreateGraph(&G,V,VR );</p><p>　　初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。</p><p>　　操作結(jié)果：按V和VR的定義構(gòu)造圖G。 </p><p>　　SearchMapPath (&G,V,VR )；</p>&l

12、t;p>　　初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。</p><p>　　操作結(jié)果：求出最長(zhǎng)路徑，并輸出關(guān)鍵路徑。</p><p>　　Display(&G,V,VR)；</p><p>　　初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。</p><p>　　操作結(jié)果：以圖形的形式輸出圖。</p><p

13、>　　}ADT Graph</p><p><b>　　軟件結(jié)構(gòu)設(shè)計(jì)：</b></p><p><b>　　三、 詳細(xì)設(shè)計(jì) </b></p><p>　　定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu):</p><p><b>　　鄰接表的存儲(chǔ)單元:</b></p>

14、<p>　　typedef struct node { </p><p>　　int adjvex; </p><p>　　int w; </p><p>　　struct node *nextedge; </p><p>　　}edgenode; </p><p><b>　

15、　表頭結(jié)點(diǎn):</b></p><p>　　typedef struct { </p><p>　　char data;</p><p>　　int id;</p><p>　　int x,y; //頂點(diǎn)的橫坐標(biāo)、縱坐標(biāo)</p><p>　　edgenode *firsted

16、ge; </p><p>　　}vexnode; </p><p>　　主函數(shù)和其他函數(shù)的偽碼算法:</p><p><b>　　主函數(shù)：</b></p><p>　　void main() </p><p>　　{ int vexnumber,arcnumber; </p&

17、gt;<p>　　printf("請(qǐng)輸入這個(gè)圖中的節(jié)點(diǎn)數(shù)和弧數(shù):"); </p><p>　　scanf("%d %d",&vexnumber,&arcnumber); </p><p>　　vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode)); <

18、;/p><p>　　CreateGraph(Graph,vexnumber,arcnumber); </p><p>　　SearchMapPath(Graph,vexnumber,arcnumber);</p><p><b>　　} </b></p><p><b>　　建立AOE網(wǎng)函數(shù)：</b>

19、;</p><p>　　void CreateGraph(vexnode* Graph,int vexnumber,int arcnumber) </p><p>　　{ int begin,end,duttem; </p><p><b>　　char ch;</b></p><p>　　edgenode *p;

20、 </p><p>　　//輸入頂點(diǎn)信息存儲(chǔ)在頂點(diǎn)表中，并初始化該頂點(diǎn)的便表。</p><p>　　for(int i=0;i<vexnumber;i++) </p><p><b>　　{ </b></p><p>　　Graph[i].id =0; </p><p>　　Gra

21、ph[i].firstedge =NULL; </p><p><b>　　} </b></p><p>　　//輸入邊所依附的兩個(gè)頂點(diǎn)的序號(hào)i和j然后生成新的鄰接點(diǎn)序號(hào)為j的//邊表結(jié)點(diǎn),將該結(jié)點(diǎn)插入到第i個(gè)表頭部。</p><p>　　printf("請(qǐng)輸入這個(gè)圖中的各個(gè)頂點(diǎn)的值:\n");</p>&l

22、t;p>　　for(i=0;i<vexnumber;i++)</p><p><b>　　{</b></p><p>　　scanf("%s",&ch);</p><p>　　Graph[i].data=ch;</p><p><b>　　} </b><

23、;/p><p>　　printf("請(qǐng)輸入圖中弧的權(quán)值、起點(diǎn)、終點(diǎn):（中間用空格隔開）\n"); </p><p>　　for(int k=0;k<arcnumber;k++) </p><p><b>　　{ </b></p><p>　　scanf("%d %d %d",

24、&duttem,&begin,&end); </p><p>　　p=(edgenode*)malloc(sizeof(edgenode)); </p><p>　　p->adjvex =end-1; </p><p>　　p->w =duttem; </p><p>　　Graph[end-1].

25、id ++;</p><p>　　p->nextedge =Graph[begin-1].firstedge ; </p><p>　　Graph[begin-1].firstedge =p; </p><p><b>　　} </b></p><p><b>　　}</b></

26、p><p><b>　　顯示有向圖函數(shù)：</b></p><p>　　void Display(vexnode* Graph,int vexnumber,int arcnumber)</p><p><b>　　{</b></p><p><b>　　int i;</b></

27、p><p>　　int arw[6];</p><p>　　edgenode *p;</p><p>　　initgraph(400, 600);</p><p>　　for(i=0;i<vexnumber;i++)</p><p><b>　　{</b></p><p>

28、;　　if(i%3==0||i==0) </p><p><b>　　{</b></p><p>　　outtextxy(100,50*(i+1), Graph[i].data);</p><p>　　Graph[i].x=100;</p><p>　　Graph[i].y=50*(i+1);</p>&

29、lt;p><b>　　}</b></p><p>　　if(i%3==1||i==1) </p><p><b>　　{</b></p><p>　　outtextxy(10,50*(i+1), Graph[i].data);</p><p>　　Graph[i].x=10;</p&g

30、t;<p>　　Graph[i].y=50*(i+1);</p><p><b>　　}</b></p><p>　　if(i%3==2||i==2)</p><p><b>　　{</b></p><p>　　outtextxy(200,50*i, Graph[i].data);&

31、lt;/p><p>　　Graph[i].x=200;</p><p>　　Graph[i].y=50*i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<vexnumber;i++)</p&g

32、t;<p><b>　　{</b></p><p>　　p=Graph[i].firstedge;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　line(Graph[i].x,Graph[i]

33、.y,Graph[p->adjvex].x,Graph[p->adjvex].y);</p><p>　　outtextxy((Graph[i].x+Graph[p->adjvex].x)/2,(Graph[i].y+Graph[p->adjvex].y)/2,p->w+48);</p><p>　　arw[0]=Graph[p->adjvex].x+5

34、;</p><p>　　arw[1]=Graph[p->adjvex].y-10;</p><p>　　arw[2]=Graph[p->adjvex].x;</p><p>　　arw[3]=Graph[p->adjvex].y;</p><p>　　arw[4]=Graph[p->adjvex].x+5;</p

35、><p>　　arw[5]=Graph[p->adjvex].y+10;</p><p>　　drawpoly(3,arw);</p><p>　　p=p->nextedge;</p><p><b>　　}</b></p><p><b>　　}</b></p

36、><p><b>　　getch();</b></p><p>　　closegraph(); </p><p><b>　　}</b></p><p><b>　　求解關(guān)鍵路徑函數(shù)：</b></p><p>　　int SearchMapPath(ve

37、xnode* Graph,int vexnumber,int arcnumber) </p><p><b>　　{ </b></p><p>　　int totaltime=0;</p><p><b>　　int m=0;</b></p><p>　　int i,j,k,t; </p&

38、gt;<p>　　char sv[100];</p><p>　　int front,rear; </p><p>　　int *topology_queue,*vl,*ve,*el,*ee;</p><p>　　front=rear=-1; t=0;</p><p>　　topology_queue=(int*)malloc(

39、vexnumber*sizeof(int)); </p><p>　　vl=(int*)malloc(vexnumber*sizeof(int)); </p><p>　　ve=(int*)malloc(vexnumber*sizeof(int)); </p><p>　　el=(int*)malloc(

40、arcnumber*sizeof(int)); </p><p>　　ee=(int*)malloc(arcnumber*sizeof(int)); </p><p>　　edgenode *p; </p><p>　　for(i=0;i<vexnumber;i++) ve[i]=0; </p><p>

41、　　for(i=0;i<vexnumber;i++) </p><p><b>　　{ </b></p><p>　　if(Graph[i].id==0) </p><p><b>　　{</b></p><p>　　topology_queue[++rear]=i; </p>

42、;<p><b>　　m++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　while(front!=rear) </p><p><b>　　{ </b></p>

43、;<p>　　front++; </p><p>　　j=topology_queue[front]; </p><p><b>　　m++;</b></p><p>　　p=Graph[j].firstedge ; </p><p><b>　　while(p) </b><

44、/p><p><b>　　{ </b></p><p>　　k=p->adjvex; </p><p>　　Graph[k].id --; </p><p>　　if(ve[j]+p->w >ve[k]) </p><p>　　ve[k]=ve[j]+p->w ; &

45、lt;/p><p>　　if(Graph[k].id ==0) topology_queue[++rear]=k; </p><p>　　p=p->nextedge ; </p><p><b>　　} </b></p><p><b>　　} </b></p><p&

46、gt;　　if(m<vexnumber)</p><p><b>　　{</b></p><p>　　printf("\n該圖中存在回路，不可計(jì)算出關(guān)鍵路徑！\n");</p><p><b>　　return 0;</b></p><p><b>　　}<

47、/b></p><p>　　totaltime=ve[vexnumber-1]; </p><p>　　for(i=0;i<vexnumber;i++) </p><p>　　vl[i]=totaltime;</p><p>　　for(i=vexnumber-2;i>=0;i--) </p><p

48、><b>　　{ </b></p><p>　　j=topology_queue[i];</p><p>　　p=Graph[j].firstedge; </p><p><b>　　while(p) </b></p><p><b>　　{ </b></p&

49、gt;<p>　　k=p->adjvex ; </p><p>　　if((vl[k]-p->w )<vl[j]) </p><p>　　vl[j]=vl[k]-p->w; </p><p>　　p=p->nextedge; </p><p><b>　　} </b>

50、</p><p><b>　　} </b></p><p>　　printf("| 起點(diǎn) | 終點(diǎn) | 最早開始時(shí)間 | 最遲開始時(shí)間 | 差值 | \n"); i=0; </p><p>　　for(j=0;j<vexnumber;j++) </p><p><b&g

51、t;　　{ </b></p><p>　　p=Graph[j].firstedge; </p><p>　　while(p) </p><p><b>　　{ </b></p><p>　　k=p->adjvex ; </p><p>　　ee[++i]=ve[j];

52、 </p><p>　　el[i]=vl[k]-p->w; </p><p>　　printf("| %4c | %4c | %12d | %12d | %4d |",Graph[j].data ,Graph[k].data ,ee[i],el[i],el[i]-ee[i]); </p><p>　　if(el[i]==ee[i]) &

53、lt;/p><p><b>　　{ </b></p><p>　　printf(" 是關(guān)鍵活動(dòng) "); </p><p>　　sv[t]=Graph[j].data;t++;</p><p><b>　　}</b></p><p>　　printf("

54、;\n"); </p><p>　　p=p->nextedge; </p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　printf("關(guān)鍵路徑為：");</p><p>　　sv[t]

55、=Graph[vexnumber-1].data;</p><p>　　for(i=0;i<=t;i++)</p><p>　　{ printf("%c",sv[i]);</p><p>　　if(sv[i]!=Graph[vexnumber-1].data)</p><p>　　printf("→&qu

56、ot;);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　return 1; </p><p><b>　　} </b></p><p>　　主要函數(shù)的程序流程圖：</p>&

57、lt;p>　　4. 畫出函數(shù)之間的調(diào)用關(guān)系圖:</p><p><b>　　調(diào)試分析 </b></p><p>　　1.實(shí)際完成的情況說(shuō)明: </p><p>　　本程序完成的功能是：顯示用戶從鍵盤輸入的有向圖，并計(jì)算出其關(guān)鍵路徑。支持用戶輸入char型的頂點(diǎn)值，int型的弧數(shù)和頂點(diǎn)數(shù)，int型的權(quán)值；</p><p&

58、gt;　　2.程序的性能分析：</p><p>　　本程序的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O（1）。</p><p>　　3.上機(jī)過(guò)程中出現(xiàn)的問(wèn)題及其解決方案：</p><p>　　（1）有向圖的存儲(chǔ)。存儲(chǔ)時(shí)，由于對(duì)鄰接表的具體代碼實(shí)現(xiàn)不了解，導(dǎo)致在寫這部分程序的過(guò)程中遇到不少麻煩，比如如何在結(jié)點(diǎn)里添加指向下一鄰接結(jié)點(diǎn)的指針等，后來(lái)查閱了教材，解決了這一部分的問(wèn)

59、題。</p><p>　　（2）有向圖的顯示。如何在屏幕上以圖形的形式輸出圖，困惑了我好久。通過(guò)在網(wǎng)上查找資料及尋找?guī)椭?，明白了需在頭文件里添加graphics.h文件，并使用該庫(kù)里的line()函數(shù)和outtextxy()函數(shù)。接著是如何顯示帶箭頭的直線，由于graphics.h庫(kù)里不含有畫帶箭頭的直線的函數(shù)，于是，我使用了畫多邊形的函數(shù)drawpoly()來(lái)實(shí)現(xiàn)箭頭，但是這個(gè)函數(shù)的第二個(gè)形參類型是數(shù)組型的，需

60、用數(shù)組來(lái)存儲(chǔ)三個(gè)點(diǎn)的坐標(biāo)信息。</p><p>　?。?）關(guān)鍵路徑的求解。由于對(duì)關(guān)鍵路徑的基本算法不了解，所以特地查閱了這一方面的書籍，了解了關(guān)鍵路徑的基本算法。</p><p>　　4.程序中可以改進(jìn)的地方說(shuō)明：</p><p>　　有向圖的顯示里，箭頭無(wú)法隨直線的斜率的變化而變化，頂點(diǎn)值與箭頭重合，看不清箭頭的方向。</p><p>　　

61、5.程序中可以擴(kuò)充的功能及設(shè)計(jì)實(shí)現(xiàn)假想：</p><p>　　應(yīng)能顯示多個(gè)有向圖，能求解多個(gè)有向圖的關(guān)鍵路徑，關(guān)鍵活動(dòng)。界面可以做成可視化，人性化的界面。</p><p><b>　　測(cè)試結(jié)果</b></p><p>　　（1）輸入一組可以構(gòu)成AOE網(wǎng)的頂點(diǎn)與弧的數(shù)據(jù)</p><p>　　輸入一組不可構(gòu)成AOE網(wǎng)的頂點(diǎn)與

62、弧的數(shù)據(jù)（即存在回路）</p><p><b>　　用戶手冊(cè)</b></p><p>　　輸入圖中的節(jié)點(diǎn)數(shù)與弧數(shù) （2）輸入圖中各個(gè)頂點(diǎn)的值</p><p>　?。?）輸入圖中弧的權(quán)值、起點(diǎn)、終點(diǎn)（4）按回車鍵</p><p>　　按回車鍵（6）按任意鍵</p><p

63、>　　七、體會(huì)與自我評(píng)價(jià) </p><p>　　通過(guò)本次課程設(shè)，掌握了鄰接表的存儲(chǔ)結(jié)構(gòu)，圖形顯示的一些函數(shù)的使用以及關(guān)鍵路徑的求法。在實(shí)驗(yàn)過(guò)程中出現(xiàn)了不少的問(wèn)題，通過(guò)查閱資料，向老師、同學(xué)尋求幫助，解決了出現(xiàn)的問(wèn)題。</p><p>　　從這次的課程設(shè)計(jì)任務(wù)中我深刻地體會(huì)到：任何事情并不像我們想的那樣艱難。剛開始拿到這個(gè)課設(shè)任務(wù)時(shí)，對(duì)于關(guān)鍵路徑很是發(fā)怵，因?yàn)橹皩?duì)這一部分的知識(shí)運(yùn)用的

64、少，再加上任務(wù)書上還要求以圖形的形式顯示有向圖，在這次課設(shè)之前，我從來(lái)沒(méi)有接觸過(guò)圖形處理的函數(shù)。然而，俗話說(shuō)“世上無(wú)難事，只怕有心人”，通過(guò)積極地查閱書籍，上網(wǎng)查找資料，這些困難都一個(gè)個(gè)的迎刃而解。并且在解決這些困難的同時(shí)，自己也復(fù)習(xí)并掌握了這些知識(shí)。本次課設(shè)遇到了很多理論課上所沒(méi)有遇到過(guò)的問(wèn)題，也讓理論課上所學(xué)的理論得到驗(yàn)證和使用，通過(guò)實(shí)際操作，扎實(shí)了理論知識(shí)，開拓了自己的算法思想。通過(guò)本次課設(shè)，更讓我意識(shí)到團(tuán)隊(duì)合作的力量，通過(guò)小組成

65、員的討論和互相解惑，學(xué)到很多自己沒(méi)有遇到過(guò)的問(wèn)題的解決辦法，學(xué)會(huì)了如何在團(tuán)隊(duì)合作中互幫互助，共同進(jìn)步。</p><p>　　但是自己的程序仍存在一些不足，比如在有向圖的顯示方面，箭頭與頂點(diǎn)值重合了，導(dǎo)致無(wú)法清晰辨認(rèn)弧的方向。這次課設(shè)讓我明白了只有扎扎時(shí)時(shí)的學(xué)習(xí)知識(shí)才能解決實(shí)際生活中的實(shí)際問(wèn)題，以后要多了解相關(guān)知識(shí),更多的做一些實(shí)踐動(dòng)手活動(dòng)，將知識(shí)運(yùn)用到實(shí)際問(wèn)題中。同時(shí)，增加自己的動(dòng)手能力，這樣才能便于我們更好的解

66、決問(wèn)題。為今后打下好的基礎(chǔ)。課外時(shí)間應(yīng)該多擴(kuò)展一些編程方面的知識(shí)，提高自己的編程能力。</p><p><b>　　參考文獻(xiàn) </b></p><p>　　[1]嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言），清華大學(xué)出版社，2007</p><p>　　[2]邱建華，C語(yǔ)言程序設(shè)計(jì)教程，東軟電子出版社，2009</p><p>　　[3]