數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---關(guān)鍵路徑-wenkub
2023-02-02 21:52:15 本頁(yè)面
【正文】 數(shù)：endl。//圖中頂點(diǎn)數(shù)和邊數(shù) VNode adjlist[MAXV]。typedef struct//鄰接表頭結(jié)點(diǎn)的類(lèi)型{ Vertex data。 //該弧所代表的活動(dòng)的最早開(kāi)始時(shí)間 int l。 //該弧的起點(diǎn), 表示此弧所代表的活動(dòng)開(kāi)始事件 char end。 //頂點(diǎn)入度 int ve。 源點(diǎn)和匯點(diǎn)分別表示整個(gè)工程的開(kāi)始事件和結(jié)束事件ve：任一事件的最早可發(fā)生時(shí)間, 其值為源點(diǎn)到該點(diǎn)所有路徑長(zhǎng)度的最大值；vl：在不影響整個(gè)工程進(jìn)度的情況下各事件的最晚可發(fā)生時(shí)間，其值為該點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑之差；e：各項(xiàng)活動(dòng)的最早開(kāi)始時(shí)間，若以i, j表示該活動(dòng)，則e(i,j) = ve(i)；l：各項(xiàng)活動(dòng)的最晚開(kāi)始時(shí)間，若以i, j表示該活動(dòng)，則v(i,j) = vl(j)time；d：在不增加整個(gè)工程所需總時(shí)間的情況下，某項(xiàng)活動(dòng)可以拖延的時(shí)，其值為el；◆ 采用鄰接表的方式建立工程圖◆ 對(duì)AOE網(wǎng)進(jìn)行排序, 若發(fā)現(xiàn)回路，則提醒用戶(hù)數(shù)據(jù)錯(cuò)誤，讓其重新輸入◆ 對(duì)于源點(diǎn)，對(duì)于源點(diǎn)，置其ve = 0，依次計(jì)算出各事件的ve；對(duì)于匯點(diǎn)，置其vl = ve, 然后依次計(jì)算出各事件的vl；再計(jì)算出各活動(dòng)的e, l, d。 關(guān)鍵路徑可以很方便的讓我們估算出某個(gè)工程最短的時(shí)間開(kāi)銷(xiāo)，以及這個(gè)工程中哪些活動(dòng)，即哪些項(xiàng)目是主要的，是影響工程進(jìn)度的關(guān)鍵，從而讓我們對(duì)工程的實(shí)施做出更好的時(shí)間安排，并且可以分清主次，抓住核心工程，做到有的放矢。AOE網(wǎng)可以用來(lái)估算工程的完成時(shí)間。工程通常分為若干個(gè)稱(chēng)為“活動(dòng)”的子工程。數(shù)據(jù)：自行設(shè)計(jì)每個(gè)活動(dòng)的前導(dǎo)活動(dòng)和后續(xù)活動(dòng)以及活動(dòng)的進(jìn)行時(shí)間，然后依據(jù)這些活動(dòng)的前后次序，畫(huà)出其網(wǎng)絡(luò)圖，選擇存儲(chǔ)結(jié)構(gòu)。操作：（1）求工程最短工期；（2）輸出關(guān)鍵路徑；（3）輸出關(guān)鍵活動(dòng)。完成了這些“活動(dòng)”，這個(gè)工程就可以完成了。他可以使人們了解： (1). 研究某個(gè)工程至少需要多少時(shí)間? (2). 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？ 由于AOE網(wǎng)中的有些活動(dòng)可以并行進(jìn)行，從開(kāi)始點(diǎn)到各個(gè)頂點(diǎn)，以致從開(kāi)始點(diǎn)到完成點(diǎn)的有向路徑可能不止一條，這些路徑的長(zhǎng)度也可能不同?？偟膩?lái)說(shuō)，正因?yàn)殛P(guān)鍵路徑可以幫助我們對(duì)工程進(jìn)行非常有必要的估算，讓我們得以看清全局，作出更為優(yōu)化的安排，所以可見(jiàn)關(guān)鍵路徑的求出對(duì)一項(xiàng)工程而言是非常必要的?！?找出關(guān)鍵活動(dòng)和關(guān)鍵路徑 詳細(xì)設(shè)計(jì)： 數(shù)據(jù)結(jié)構(gòu)： typedef struct//頂點(diǎn)類(lèi)型{ char num。 //頂點(diǎn)所表示的事件的最早發(fā)生時(shí)間 int vl。 //該弧的終點(diǎn)，表示此弧所代表的活動(dòng)的結(jié)束事件 int vp。 //該弧所代表的活動(dòng)的最遲開(kāi)始時(shí)間 int d。 //該頂點(diǎn)的相關(guān)信息 ArcNode *firstarc。 //鄰接鏈表}ALGraph。 do { sign = 1。 } } while (!sign)。 i n。 gadjlist[i]. = gadjlist[i]. = 0。 k++) { cout第k項(xiàng)：。 pend = j+65。 gadjlist[j].++。 int i, k。 i ++) //計(jì)算各頂點(diǎn)所表示事件的最早發(fā)生時(shí)間ve { p = gadjlist[i].firstarc。 } p = pnextarc。 i ) //計(jì)算各頂點(diǎn)所表示事件的最遲發(fā)生時(shí)間vl { p = gadjlist[i].firstarc。 } p = pnextarc。 while (p != NULL) { k = pvp。 //某活動(dòng)可以推遲的時(shí)間是其最遲開(kāi)始時(shí)間與最早開(kāi)始時(shí)間之差 p = pnextarc。 i ++) coutgadjlist[i].\t gadjlist[i].\t gadjlist[i].endl。 i++) { ArcNode *p = gadjlist[i].firstarc。 p = pnextarc。 //棧st的指針為top ArcNode *p。 st[top] = i。 //輸出頂點(diǎn) sum ++。 if (gadjlist[j]. == 0) //入度為0的相鄰頂點(diǎn)入棧 { top ++。 return (sum == gn)。 i gn。 } } coutendl。 //記錄關(guān)鍵路徑的條數(shù) cout\n關(guān)鍵路徑有：endl。 while (p != NULL) { if (pd == 0) { t[j].start = pstart。 } p = pnextarc。 //用于一條關(guān)鍵路徑計(jì)算完以后從新計(jì)算下一條關(guān)鍵路徑的入口 char num。 sign = k。 } } k++。 } } }}所有操作的入口：void Interface() //所有操作的入口，主函數(shù)通過(guò)調(diào)用此函數(shù)來(lái)完成相關(guān)操作{ char choose1, choose2, ch。 cout| 開(kāi)始 S 退出 Q |endl。 cinchoose1。s39。 if (!TopSort(G)) { cout圖中有回路!請(qǐng)檢查后重新輸入!endl。 cout是否顯示事件及活動(dòng)相關(guān)信息？ Yes — Y No — any key endl。 || ch == 39。 KeyActs(G)。 if (choose2 == 39。) flag2 = 1。 } else if (choose1 == 39。) { cout\n 謝謝使用!歡迎再次使用! endl。}三、系統(tǒng)實(shí)現(xiàn)： 源代碼見(jiàn)報(bào)告尾部； 調(diào)試分析，測(cè)試數(shù)據(jù)及界面如下：四、設(shè)計(jì)總結(jié)：由于上學(xué)期時(shí)間緊張，關(guān)鍵路徑這塊基本上沒(méi)有理解，通過(guò)這次課程設(shè)計(jì)，我選了這個(gè)課題，一是為了讓自己能很好的掌握這個(gè)知識(shí)點(diǎn)，二是為了在得分的壓力下把輸出多條關(guān)鍵路徑的這個(gè)算法寫(xiě)出來(lái)。數(shù)據(jù)結(jié)構(gòu)這門(mén)課程對(duì)我們學(xué)習(xí)好這個(gè)專(zhuān)業(yè)很重要，在以后，我會(huì)盡量利用我的空閑時(shí)間把以前不熟的和掌握不牢固的知識(shí)點(diǎn)再學(xué)習(xí)一遍，讓它成為一門(mén)為我所用的課程。 //頂點(diǎn)入度 int ve。 //該弧的起點(diǎn), 表示此弧所代表的活動(dòng)開(kāi)始事件 char end。 //該弧所代表的活動(dòng)的最早開(kāi)始時(shí)間 int l。typedef struct//鄰接表頭結(jié)點(diǎn)的類(lèi)型{ Vertex data。//圖中頂點(diǎn)數(shù)和邊數(shù) VNode adjlist[MAXV]。}void CreateGraph(ALGraph *g) //創(chuàng)建有向圖的鄰接鏈表{ ArcNode *p。 cinne。 gn = n。 i++) //初始化頂點(diǎn)信息 { gadjlist[i]. = i+65。 } cout\n請(qǐng)輸入各項(xiàng)活動(dòng)的開(kāi)始事件和結(jié)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1