第二題：電梯模擬1、需求分析：模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停留。九個(gè)樓層由下至上依次稱(chēng)為地下層、第一層、第二層、第八層，其中第一層是大樓的進(jìn)出層，即是電梯的“本壘層”，電梯“空閑”時(shí)，將來(lái)到該層候命。乘客可隨機(jī)地進(jìn)出于任何層。對(duì)每個(gè)人來(lái)說(shuō)，他有一個(gè)能容忍的最長(zhǎng)等待時(shí)間，一旦等候電梯時(shí)間過(guò)長(zhǎng)，他將放棄。模擬時(shí)鐘從0開(kāi)始，時(shí)間單位為0.1秒。人和電梯的各種動(dòng)作均要消耗一定的時(shí)間單位（簡(jiǎn)記為t），比如：有人進(jìn)出時(shí)，電梯每隔40t測(cè)試一次，若無(wú)人進(jìn)出，則關(guān)門(mén)；關(guān)門(mén)和開(kāi)門(mén)各需要20t；每個(gè)人進(jìn)出電梯均需要25t；如果電梯在某層靜止時(shí)間超過(guò)300t，則駛回1層侯命。而題目的最終要求輸出時(shí)：按時(shí)序顯示系統(tǒng)狀態(tài)的變化過(guò)程，即發(fā)生的全部人和電梯的動(dòng)作序列。2、設(shè)計(jì)21設(shè)計(jì)思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本題中的電梯的變化，是一個(gè)動(dòng)態(tài)變化的過(guò)程，要在動(dòng)態(tài)過(guò)程中實(shí)現(xiàn)正常跳轉(zhuǎn)，首先要確定各種跳轉(zhuǎn)的狀態(tài)，因而這里我使用枚舉類(lèi)型來(lái)表示電梯的各種狀態(tài)的：enum up,down,stop,homeState(home);同時(shí)初始化最初狀態(tài)為電梯在本壘層。而在電梯的運(yùn)行過(guò)程中對(duì)于乘客來(lái)說(shuō)，顯然有一個(gè)進(jìn)入電梯與出電梯的隊(duì)列，因而在這里我是用的鏈表來(lái)實(shí)現(xiàn)這個(gè)過(guò)程的，同時(shí)用結(jié)構(gòu)體來(lái)保存該乘客的信息：typedef struct passageint now;/乘客當(dāng)前所在的位置int dis;/乘客的目地地int wait;/最長(zhǎng)的等待的時(shí)間int waitnow;/已經(jīng)等待的時(shí)間struct passage *next;Passage;雖然電梯中的狀態(tài)是由枚舉類(lèi)型來(lái)實(shí)現(xiàn)的，但是在整個(gè)程序的運(yùn)行過(guò)程中，我還是為電梯設(shè)置了一個(gè)結(jié)構(gòu)體類(lèi)型，以便保存更多的信息：typedef struct liftint count_C;/計(jì)數(shù)電梯已到達(dá)的層數(shù)int count_A;/系統(tǒng)的總時(shí)間計(jì)數(shù)器 記得必須初始化為0int flag_inHigh;/九個(gè)樓層有無(wú)請(qǐng)求的標(biāo)志 哪個(gè)樓層如果有請(qǐng)求 該標(biāo)志置1int num;/等待隊(duì)列中的人數(shù) 記得要進(jìn)行初始化為0int people;/電梯中人數(shù)int flag_outHigh;Lift;（2）算法設(shè)計(jì)顧名思義本程序在運(yùn)行的過(guò)程中用到的算法便是“電梯算法”，電梯算法借鑒了磁盤(pán)尋道C-LOOK算法，即電梯向一個(gè)方向運(yùn)行，直到這個(gè)方向上沒(méi)有服務(wù)為止。2.2設(shè)計(jì)表示（1）、函數(shù)調(diào)用關(guān)系圖及其說(shuō)明如下:(2)函數(shù)接口說(shuō)明：函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進(jìn)行傳遞的過(guò)程中比較簡(jiǎn)單，下面就將主要函數(shù)及他們之間的參數(shù)的關(guān)系列出如下：int OutOrIn(Lift &L,Passage *Queue,Passage *LiftQ);/進(jìn)和出電梯的總函數(shù)int Update(Lift &L,Passage *Queue,Passage *LiftQ);/刷新的函數(shù)int Run(Lift &L,Passage *Queue,Passage *LiftQ);/整個(gè)電梯各種狀態(tài)轉(zhuǎn)換的函數(shù)int OpenTheDoor(Lift &L);/開(kāi)門(mén)主要是用于解決其中的時(shí)間問(wèn)題int CloseTheDoor(Lift &L);/關(guān)門(mén)int In(Lift &L);/進(jìn)入 主要是解決每個(gè)人進(jìn)入電梯的時(shí)間問(wèn)題int Out(Lift &L);/出去int Test(Lift &L,Passage *Queue,Passage *LiftQ);/電梯測(cè)試關(guān)門(mén)還是開(kāi)門(mén)的函數(shù)int Request(Lift &L,Passage *Queue);2.3詳細(xì)設(shè)計(jì)3、調(diào)試分析該程序的調(diào)試過(guò)程較為輕松，基本在算法實(shí)現(xiàn)的基礎(chǔ)上沒(méi)有出現(xiàn)什么錯(cuò)誤，因而在調(diào)試的過(guò)程中并無(wú)什么深刻印象。4、用戶(hù)手冊(cè)點(diǎn)擊運(yùn)行程序，在彈出的窗口中，會(huì)提示要輸入的信息：1、 提示信息為：“請(qǐng)輸入圖中的頂點(diǎn)數(shù)和弧數(shù)以及圖的標(biāo)志和弧的標(biāo)志：”按要求輸入即可，本題即輸入9 11 v a2、 提示信息為“請(qǐng)完成該鄰接表的輸入”：由于鄰接表的輸入信息一般較多，而且均是采用的鏈表來(lái)存儲(chǔ)，因而該部分的輸入要特別的小心3、 在完成上面兩步的輸入后按enter鍵便能得到程序的運(yùn)行結(jié)果，即輸出完成整項(xiàng)工程至少需要多少時(shí)間和影響工程進(jìn)度的關(guān)鍵活動(dòng) 5 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果測(cè)試數(shù)據(jù)如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6526 9 77 7 8617 4 9718 2 10818 4 1190程序運(yùn)行結(jié)果如下：6、原程序清單如下：/*關(guān)鍵路徑問(wèn)題2010年07月31日晚上08：36開(kāi)始動(dòng)工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存儲(chǔ)頂點(diǎn)的數(shù)目const int STACK_INIT_SIZE=20;/棧的存儲(chǔ)空間分配量/數(shù)據(jù)存儲(chǔ)部分/*一下是圖的鄰接表的存儲(chǔ)表示，由于第一次用 用的比較的生疏*/typedef struct ArcNodeint adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點(diǎn)的信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當(dāng)前頂點(diǎn)數(shù)和弧數(shù)char kind,kind1;/圖中的各類(lèi)標(biāo)志頂點(diǎn)和弧ALGraph;typedef struct int *base;int *top;int stacksize;Stack;int veMAX_V_NUM;Stack T;/函數(shù)體描述部分int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);/*下面是函數(shù)的具體實(shí)現(xiàn)部分*/構(gòu)造一個(gè)空棧int InitStack(Stack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;/可以用于當(dāng)棧的存儲(chǔ)空間不夠的情況下 進(jìn)行擴(kuò)充return 1;/元素進(jìn)棧int Push (Stack &S, int &e)*S.top+=e;return 1;/元素出棧int Pop(Stack &S, int &e)if(S.top=S.base)return 0;e=*-S.top;return 1;/判斷棧是否為空int StackEmpty(Stack &S)if(S.top=S.base)return 1;else return 0;/找出每個(gè)頂點(diǎn)的入度int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM)ArcNode *p;int i;for(i=0;iMAX_V_NUM;i+)indegreei=0;for(i=0;inextarc)indegreep-adjvex+;return 0;/拓?fù)渑判蛲瑫r(shí)求出各活動(dòng)的最早發(fā)生時(shí)間int ToPoOrder(ALGraph &G,Stack &T)int count=0;int i,j,k;Stack S1;ArcNode *p;int indegreeMAX_V_NUM;InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i+)if(indegreei=0)Push(S1,i);/建立0入度頂點(diǎn)棧Sfor(i=0;inextarc)k=p-adjvex;if(-indegreek=0)Push(S1,k);if(vej+(p-info)vek)vek=vej+(p-info);/for(i=0;iG.vnum;i+)/coutveiendl;if(countG.vnum)return 0;else return 1;/計(jì)算各頂點(diǎn)的最遲發(fā)生時(shí)間及進(jìn)行輸出int CriticalPath(ALGraph &G)int vlMAX_V_NUM;int dut;int i,j,k,ee,el;ArcNode *p;/char tag;if(!ToPoOrder(G,T)return 0;cout完成整項(xiàng)工程至少需要的時(shí)間是：veG.vnum-1endl;for(i=0;inextarc)k=p-adjvex;dut=(p-info);if(vlk-dutvlj)vlj=vlk-dut;/for(i=0;iG.vnum;i+)/coutvliendl;cout影響工程進(jìn)度的關(guān)鍵活動(dòng)是:endl;for(j=0;jnextarc)k=p-adjvex;dut=(p-info);ee=vej;el=vlk-dut;/coutj=jK=kdut=dutee=eeel=elendl;if(ee=el)/tag=(ee=el)?*:;coutG.kind1nameendl;return 1;int main()ALGraph G;int i,j,Hnum;ArcNode *p,*q;/int indegreeMAX_V_NUM;/ALGraph G;cout請(qǐng)輸入圖中的頂點(diǎn)數(shù)和弧數(shù)以及圖的標(biāo)志和弧的標(biāo)志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout請(qǐng)完成該鄰接表的輸入：endl;for(i=0;iG.vnum;i+)cout請(qǐng)輸入該頂點(diǎn)的信息G.verticesi.data;cout請(qǐng)輸入與G.kindG.verticesi.data號(hào)頂點(diǎn)相鄰的弧的數(shù)目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout請(qǐng)依次次輸入弧的信息（包括頂點(diǎn)的位置及權(quán)值和該邊的名稱(chēng)）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout請(qǐng)依次次輸入弧的信息（包括頂點(diǎn)的位置及權(quán)值和該邊的名稱(chēng)）q-adjvex;cinq-info;cinq-name;q-nextarc=p-nextarc;p-nextarc=q;/ToPoOrder(G,T);/CriticalPath(G);/test/*for(i=0;iG.vnum;i+)cout該頂點(diǎn)是G.kindG.verticesi.dataendl;cout與該頂點(diǎn)相鄰的頂點(diǎn)依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第五題：關(guān)鍵路徑問(wèn)題1、需求分析：當(dāng)一項(xiàng)工程被劃分為若干個(gè)子任務(wù)或活動(dòng)后，人們不僅需要確定這些活動(dòng)的先后次序，而且需要進(jìn)一步計(jì)算完成整個(gè)工程的時(shí)間，確定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)，以便合理組織人力、物力、財(cái)力，加快這些活動(dòng)的進(jìn)度，為按時(shí)或提前完成整個(gè)工程提供保證。要求：給定一個(gè)帶權(quán)的有向圖代表一個(gè)工程的AOE網(wǎng)絡(luò)，研究如下問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？示例圖：2、設(shè)計(jì)21設(shè)計(jì)思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本題中的數(shù)據(jù)結(jié)構(gòu)主要影響在于整個(gè)程序設(shè)計(jì)過(guò)程中數(shù)據(jù)的存儲(chǔ)和拓?fù)渑判颉㈥P(guān)鍵路徑算法的實(shí)現(xiàn)，而在算法的實(shí)現(xiàn)過(guò)程中又要依賴(lài)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，而在圖的存儲(chǔ)結(jié)構(gòu)中，比較適合實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ娘@然是鄰接表的存儲(chǔ)結(jié)構(gòu)，所以本程序設(shè)計(jì)過(guò)程中均采用的是鄰接表的存儲(chǔ)方法。其主要數(shù)據(jù)的主要存儲(chǔ)結(jié)構(gòu)體聲明如下：typedef struct ArcNodeint adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點(diǎn)的信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當(dāng)前頂點(diǎn)數(shù)和弧數(shù)char kind,kind1;/圖中的各類(lèi)標(biāo)志頂點(diǎn)和弧ALGraph;同時(shí)由于拓?fù)渑判驅(qū)崿F(xiàn)過(guò)程中要用到進(jìn)棧和出棧的操作，因此還有棧的聲明如下：typedef struct int *base;int *top;int stacksize;Stack;（2）算法設(shè)計(jì)本程序的算法設(shè)計(jì)主要體現(xiàn)在拓?fù)渑判蚝颓笫录淖钤绨l(fā)生時(shí)間和最遲發(fā)生時(shí)間的的過(guò)程中，因此算法設(shè)計(jì)主要也是針對(duì)拓?fù)渑判蚝颓笫录l(fā)生的最早發(fā)生和最遲發(fā)生時(shí)間的算法設(shè)計(jì)。拓?fù)渑判虻乃枷胧菍⑷攵葹榱愕慕Y(jié)點(diǎn)進(jìn)行S1中的出棧操作，同時(shí)將其對(duì)T進(jìn)行進(jìn)棧，這主要是方便在進(jìn)行完求最早發(fā)生時(shí)間后，通過(guò)出棧的操作直接求最遲發(fā)生時(shí)間。2.2設(shè)計(jì)表示（1）、函數(shù)調(diào)用關(guān)系圖及其說(shuō)明如下:(2)函數(shù)接口說(shuō)明：函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進(jìn)行傳遞的過(guò)程中比較簡(jiǎn)單，下面就將主要函數(shù)及他們之間的參數(shù)的關(guān)系列出如下：int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);2.3詳細(xì)設(shè)計(jì)該程序的算法主要在以下四個(gè)方面：拓?fù)渑判颉⑶蟪鍪录淖钤绨l(fā)生時(shí)間、求出事件的最遲發(fā)生時(shí)間、求出關(guān)鍵活動(dòng)，其中關(guān)鍵活動(dòng)的算法設(shè)計(jì)較為簡(jiǎn)單，即是在求出各活動(dòng)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間的前提下根據(jù)判斷兩時(shí)間是否相等，來(lái)判斷是否是關(guān)鍵活動(dòng)，因而主要的算法設(shè)計(jì)便在前三個(gè)方面。拓?fù)渑判蚺c求事件的最早發(fā)生時(shí)間相結(jié)合，拓?fù)渑判蚣磳⑷攵葹榱愕臈中的元素依次出棧，同時(shí)將該元素進(jìn)棧到棧T中，在進(jìn)棧的同時(shí)求出其最早發(fā)生時(shí)間算法如下：從ve（0）=0開(kāi)始向前遞推Ve（j）=然后便是求事件的最遲發(fā)生時(shí)間，該過(guò)程就是對(duì)上面的過(guò)程中得到的棧T進(jìn)行依次出棧，同時(shí)求其最遲發(fā)生時(shí)間，其算法簡(jiǎn)要描述如下:從vl（n-1）=ve（n-1）起向后遞推Vl（i）=具體實(shí)現(xiàn)見(jiàn)代碼中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函數(shù)；3、調(diào)試分析該程序的調(diào)試過(guò)程較為輕松，基本在算法實(shí)現(xiàn)的基礎(chǔ)上沒(méi)有出現(xiàn)什么錯(cuò)誤，因而在調(diào)試的過(guò)程中并無(wú)什么深刻印象。4、用戶(hù)手冊(cè)點(diǎn)擊運(yùn)行程序，在彈出的窗口中，會(huì)提示要輸入的信息：4、 提示信息為：“請(qǐng)輸入圖中的頂點(diǎn)數(shù)和弧數(shù)以及圖的標(biāo)志和弧的標(biāo)志：”按要求輸入即可，本題即輸入9 11 v a5、 提示信息為“請(qǐng)完成該鄰接表的輸入”：由于鄰接表的輸入信息一般較多，而且均是采用的鏈表來(lái)存儲(chǔ)，因而該部分的輸入要特別的小心6、 在完成上面兩步的輸入后按enter鍵便能得到程序的運(yùn)行結(jié)果，即輸出完成整項(xiàng)工程至少需要多少時(shí)間和影響工程進(jìn)度的關(guān)鍵活動(dòng) 5 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果測(cè)試數(shù)據(jù)如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6526 9 77 7 8617 4 9718 2 10818 4 1190程序運(yùn)行結(jié)果如下：6、原程序清單如下：/*關(guān)鍵路徑問(wèn)題2010年07月31日晚上08：36開(kāi)始動(dòng)工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存儲(chǔ)頂點(diǎn)的數(shù)目const int STACK_INIT_SIZE=20;/棧的存儲(chǔ)空間分配量/數(shù)據(jù)存儲(chǔ)部分/*一下是圖的鄰接表的存儲(chǔ)表示，由于第一次用 用的比較的生疏*/typedef struct ArcNodeint adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點(diǎn)的信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當(dāng)前頂點(diǎn)數(shù)和弧數(shù)char kind,kind1;/圖中的各類(lèi)標(biāo)志頂點(diǎn)和弧ALGraph;typedef struct int *base;int *top;int stacksize;Stack;int veMAX_V_NUM;Stack T;/函數(shù)體描述部分int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);/*下面是函數(shù)的具體實(shí)現(xiàn)部分*/構(gòu)造一個(gè)空棧int InitStack(Stack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;/可以用于當(dāng)棧的存儲(chǔ)空間不夠的情況下 進(jìn)行擴(kuò)充return 1;/元素進(jìn)棧int Push (Stack &S, int &e)*S.top+=e;return 1;/元素出棧int Pop(Stack &S, int &e)if(S.top=S.base)return 0;e=*-S.top;return 1;/判斷棧是否為空int StackEmpty(Stack &S)if(S.top=S.base)return 1;else return 0;/找出每個(gè)頂點(diǎn)的入度int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM)ArcNode *p;int i;for(i=0;iMAX_V_NUM;i+)indegreei=0;for(i=0;inextarc)indegreep-adjvex+;return 0;/拓?fù)渑判蛲瑫r(shí)求出各活動(dòng)的最早發(fā)生時(shí)間int ToPoOrder(ALGraph &G,Stack &T)int count=0;int i,j,k;Stack S1;ArcNode *p;int indegreeMAX_V_NUM;InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i+)if(indegreei=0)Push(S1,i);/建立0入度頂點(diǎn)棧Sfor(i=0;inextarc)k=p-adjvex;if(-indegreek=0)Push(S1,k);if(vej+(p-info)vek)vek=vej+(p-info);/for(i=0;iG.vnum;i+)/coutveiendl;if(countG.vnum)return 0;else return 1;/計(jì)算各頂點(diǎn)的最遲發(fā)生時(shí)間及進(jìn)行輸出int CriticalPath(ALGraph &G)int vlMAX_V_NUM;int dut;int i,j,k,ee,el;ArcNode *p;/char tag;if(!ToPoOrder(G,T)return 0;cout完成整項(xiàng)工程至少需要的時(shí)間是：veG.vnum-1endl;for(i=0;inextarc)k=p-adjvex;dut=(p-info);if(vlk-dutvlj)vlj=vlk-dut;/for(i=0;iG.vnum;i+)/coutvliendl;cout影響工程進(jìn)度的關(guān)鍵活動(dòng)是:endl;for(j=0;jnextarc)k=p-adjvex;dut=(p-info);ee=vej;el=vlk-dut;/coutj=jK=kdut=dutee=eeel=elendl;if(ee=el)/tag=(ee=el)?*:;coutG.kind1nameendl;return 1;int main()ALGraph G;int i,j,Hnum;ArcNode *p,*q;/int indegreeMAX_V_NUM;/ALGraph G;cout請(qǐng)輸入圖中的頂點(diǎn)數(shù)和弧數(shù)以及圖的標(biāo)志和弧的標(biāo)志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout請(qǐng)完成該鄰接表的輸入：endl;for(i=0;iG.vnum;i+)cout請(qǐng)輸入該頂點(diǎn)的信息G.verticesi.data;cout請(qǐng)輸入與G.kindG.verticesi.data號(hào)頂點(diǎn)相鄰的弧的數(shù)目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout請(qǐng)依次次輸入弧的信息（包括頂點(diǎn)的位置及權(quán)值和該邊的名稱(chēng)）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout請(qǐng)依次次輸入弧的信息（包括頂點(diǎn)的位置及權(quán)值和該邊的名稱(chēng)）q-adjvex;cinq-info;cinq-name;q-nextarc=p-nextarc;p-nextarc=q;/ToPoOrder(G,T);/CriticalPath(G);/test/*for(i=0;iG.vnum;i+)cout該頂點(diǎn)是G.kindG.verticesi.dataendl;cout與該頂點(diǎn)相鄰的頂點(diǎn)依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第八題：研究生入學(xué)考試成績(jī)處理1、需求分析：假設(shè)某大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)招收研究生n名，現(xiàn)在要根據(jù)報(bào)考者的考試成績(jī)擇優(yōu)錄取。考試課程有政治、英語(yǔ)、數(shù)學(xué)、專(zhuān)業(yè)綜合四門(mén)。考試成績(jī)分為兩類(lèi)：第一類(lèi)為每門(mén)課程都達(dá)到最低錄取線；第二類(lèi)為有一門(mén)或多門(mén)課程未達(dá)到最低錄取線。錄取方法是在每門(mén)課程達(dá)到最低錄取線的考生中按總分從高到低錄取。試設(shè)計(jì)一個(gè)成績(jī)處理程序?qū)崿F(xiàn)以上功能。根據(jù)錄取方法，打印輸出n份錄取通知書(shū)，列出錄取者四門(mén)課程的成績(jī)及總分（要求采用堆排序）。并能實(shí)現(xiàn)對(duì)任一考生或任一門(mén)課程成績(jī)的查找（要求兩種查找方式，根據(jù)考號(hào)或姓名進(jìn)行查找，采用高效的查找算法）。錄取通知書(shū)的格式如下：2、設(shè)計(jì)21設(shè)計(jì)思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)由于本題明確要求在進(jìn)行排序時(shí)必須采用推排序的算法，而堆排序最常采用的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)便是順序表存儲(chǔ)結(jié)構(gòu)，因此在我的設(shè)計(jì)中是采用的結(jié)構(gòu)體數(shù)組將各個(gè)學(xué)生的信息進(jìn)行存儲(chǔ)，同時(shí)這也方便排序算法的實(shí)現(xiàn)。typedef structstring name;int Politics;int English;int Mathematics;int Major;int Total;string Num;Student;（2）算法設(shè)計(jì)由于題目要求本程序的查找是針對(duì)考號(hào)和姓名兩種方式進(jìn)行查找的，而不是針對(duì)相應(yīng)的可比較的數(shù)據(jù)進(jìn)行查找，所以像二叉查找和二叉排序樹(shù)這些查找方法基本都用不上，因此本程序采用的是“蠻力”查找的方法，及對(duì)整個(gè)結(jié)構(gòu)體數(shù)組進(jìn)行遍歷，而與要查找的信息一一進(jìn)行對(duì)比，只不過(guò)在進(jìn)行比較的過(guò)程中用的是string類(lèi)中的重載“=”，這樣更加的方便快捷。而堆排序的算法，由于學(xué)生成績(jī)的錄取是一個(gè)從高分到低分排序的過(guò)程，因此推排序的算法就是一個(gè)建立“大頂堆”的過(guò)程。2.2設(shè)計(jì)表示（1）、函數(shù)調(diào)用關(guān)系圖及其說(shuō)明如下:(2)函數(shù)接口說(shuō)明：由于個(gè)人的喜愛(ài)不同，而本人在參數(shù)傳遞的過(guò)程中喜歡用引用和指針進(jìn)行傳遞，因此本程序用的是指針進(jìn)行傳遞，因而每個(gè)參數(shù)都相當(dāng)于全局變量，這樣在接口方面方便而且不用重新開(kāi)辟其他的空間。主要函數(shù)如下:Int HeapAdjust(Student (&S_USE)MAX_SIZE,int s,int m);/堆排序 int HeapSort(Student (&S_USE)MAX_SIZE);/調(diào)整 int PanDuan(Student (&S_ALL)MAX_SIZE,Student (&S_USE)MAX_SIZE,Student (&S_UNUSE)MAX_SIZE);/判斷該研究生是否有錄取資格 才能進(jìn)行堆排序 int Find(Student (&S_ALL)MAX_SIZE);/查找成績(jī) int Display();/輸出成績(jī)單 int PutIn(Student &S);/成績(jī)錄入2.3詳細(xì)設(shè)計(jì)由于查找的算法是用的“蠻力”的算法，而對(duì)成績(jī)的錄入也非常的簡(jiǎn)單，因此詳細(xì)設(shè)計(jì)這一塊主要說(shuō)說(shuō)堆排序的詳細(xì)設(shè)計(jì)算法。堆排序的詳細(xì)設(shè)計(jì)分析：首先題目要求是按四門(mén)課程的總分進(jìn)行排序，由此我們知道我們要建立的堆是一個(gè)“大頂堆”，而建堆過(guò)程中主要解決的兩個(gè)問(wèn)題是：（1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？（2）如何在輸出堆元素之后，調(diào)整剩余的元素成為一個(gè)新的堆？在無(wú)序序列建立堆的過(guò)程中在我的程序中是用HeapAdjust()這個(gè)函數(shù)實(shí)現(xiàn)的，將建堆的過(guò)程看做事一個(gè)反復(fù)篩選的過(guò)程，則只需從從最后一個(gè)非終端斷點(diǎn)n/2的下界開(kāi)始向前一次進(jìn)行篩選，若所比較的元素比其后繼的元素要小則不需要進(jìn)行交換，否則需要該元素與其父節(jié)點(diǎn)進(jìn)行交換。即該過(guò)程中每一步都是將二叉樹(shù)的子樹(shù)建立成一個(gè)小頂堆的過(guò)程，這主要是方便在后面調(diào)整的過(guò)程中將堆頂元素和最后一個(gè)元素進(jìn)行交換，即將其從大到小排序的過(guò)程。int HeapAdjust(Student (&S_USE)MAX_SIZE,int s,int m)Student rc;int j;rc=S_USEs;for(j=2*s;j=m;j*=2)if(jS_USEj+1.Total)j+;if(rc.Total=0;i-)S_USEi=S_USEi-1;/coutI am here!0;i-)/要不要減一 先記在這里HeapAdjust(S_USE,i,count_U);for(i=count_U;i1;i-)tmp=S_USE1;S_USE1=S_USEi;S_USEi=tmp;HeapAdjust(S_USE,1,i-1);for(i=0;icount_U;i+)S_USEi=S_USEi+1;return 0;3、調(diào)試分析印象最深刻的是在二叉樹(shù)的第一個(gè)元素是下標(biāo)從1開(kāi)始，而順序表的數(shù)組的下標(biāo)是從0開(kāi)始，這個(gè)細(xì)節(jié)總會(huì)導(dǎo)致內(nèi)存出錯(cuò)，最后通過(guò)在堆排序過(guò)程中，先將數(shù)組后移，排序完后將數(shù)組在前移解決了這個(gè)問(wèn)題，因此印象較為深刻，其他的調(diào)試錯(cuò)誤，一般都是在程序測(cè)試的過(guò)程中一一改正，問(wèn)題不大。4、用戶(hù)手冊(cè)點(diǎn)擊運(yùn)行程序，在彈出的窗口中，會(huì)提示要輸入的信息：7、 首先提示輸入的是學(xué)生的個(gè)數(shù)：此時(shí)輸入你所需要輸入的學(xué)生的個(gè)數(shù)即可。8、 提示信息為“請(qǐng)按照學(xué)生的姓名、政治、英語(yǔ)、數(shù)學(xué)和專(zhuān)業(yè)綜合的分?jǐn)?shù)以及考號(hào)依次進(jìn)行輸入”：按照學(xué)生的信息一一進(jìn)行輸入即可9、 提示信息為“請(qǐng)輸入要錄取學(xué)生的個(gè)數(shù)：”此時(shí)用戶(hù)輸入要錄取學(xué)生的個(gè)數(shù)，窗口中便會(huì)顯示出錄取學(xué)生的信息10、 然后便是查找的過(guò)程，用戶(hù)按提示進(jìn)行輸入，便可按考號(hào)和姓名兩種方式對(duì)所需要的信息進(jìn)行查找。5 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果在測(cè)試的過(guò)程中我一共用到了如下26組數(shù)據(jù)：aaa 97 98 85 91 1001bbb 56 89 45 97 1002ccc 62 68 64 92 1003 ddd 66 68 69 92 1004eee 70 72 48 95 1005fff 50 68 78 91 1006ggg 70 76 86 95 1007hhh 75 78 79 96 1008iii 45 65 68 78 1009jjj 65 68 69 98 1010kkk 62 32 68 97 1011lll 65 75 89 100 1012mmm 65 78 89 123 1013nnn 23 56 89 45 1014ooo 47 78 89 65 1015ppp 65 89 41 45 1016qqq 68 89 78 89 1017rrr 58 89 45 97 1018sss 45 78 56 89 1019ttt 61 61 61 91 1020uuu 73 74 75 94 1021vvv 56 58 59 124 1022www 65 68 69 95 1023xxx 68 69 78 94 1024yyy 56 23 45 56 1025zzz 12 45 56 98 1026然后要求程序通過(guò)排序后錄取前五位，程序運(yùn)行結(jié)果如下：通過(guò)與原數(shù)據(jù)的比較，結(jié)果準(zhǔn)確無(wú)誤：一下便是查找的測(cè)試結(jié)果：通過(guò)分析知道，結(jié)果準(zhǔn)確無(wú)誤。6.、原程序清單如下：/*研究生入學(xué)考試成績(jī)處理2010年8月1日開(kāi)始動(dòng)工*/#include#includeusing namespace std;const int MAX_SIZE=100;const int L_P=60;/分別表示各門(mén)的最低錄取分?jǐn)?shù)線const int L_E=60;const int L_MATH=60;con