數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(完整版).doc

第二題：電梯模擬1、需求分析：模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個自動電梯，能在每層停留。九個樓層由下至上依次稱為地下層、第一層、第二層、第八層，其中第一層是大樓的進出層，即是電梯的“本壘層”，電梯“空閑”時，將來到該層候命。乘客可隨機地進出于任何層。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。模擬時鐘從0開始，時間單位為0.1秒。人和電梯的各種動作均要消耗一定的時間單位（簡記為t），比如：有人進出時，電梯每隔40t測試一次，若無人進出，則關(guān)門；關(guān)門和開門各需要20t；每個人進出電梯均需要25t；如果電梯在某層靜止時間超過300t，則駛回1層侯命。而題目的最終要求輸出時：按時序顯示系統(tǒng)狀態(tài)的變化過程，即發(fā)生的全部人和電梯的動作序列。2、設(shè)計21設(shè)計思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計本題中的電梯的變化，是一個動態(tài)變化的過程，要在動態(tài)過程中實現(xiàn)正常跳轉(zhuǎn)，首先要確定各種跳轉(zhuǎn)的狀態(tài)，因而這里我使用枚舉類型來表示電梯的各種狀態(tài)的：enum up,down,stop,homeState(home);同時初始化最初狀態(tài)為電梯在本壘層。而在電梯的運行過程中對于乘客來說，顯然有一個進入電梯與出電梯的隊列，因而在這里我是用的鏈表來實現(xiàn)這個過程的，同時用結(jié)構(gòu)體來保存該乘客的信息：typedef struct passageint now;/乘客當前所在的位置int dis;/乘客的目地地int wait;/最長的等待的時間int waitnow;/已經(jīng)等待的時間struct passage *next;Passage;雖然電梯中的狀態(tài)是由枚舉類型來實現(xiàn)的，但是在整個程序的運行過程中，我還是為電梯設(shè)置了一個結(jié)構(gòu)體類型，以便保存更多的信息：typedef struct liftint count_C;/計數(shù)電梯已到達的層數(shù)int count_A;/系統(tǒng)的總時間計數(shù)器 記得必須初始化為0int flag_inHigh;/九個樓層有無請求的標志 哪個樓層如果有請求 該標志置1int num;/等待隊列中的人數(shù) 記得要進行初始化為0int people;/電梯中人數(shù)int flag_outHigh;Lift;（2）算法設(shè)計顧名思義本程序在運行的過程中用到的算法便是“電梯算法”，電梯算法借鑒了磁盤尋道C-LOOK算法，即電梯向一個方向運行，直到這個方向上沒有服務(wù)為止。2.2設(shè)計表示（1）、函數(shù)調(diào)用關(guān)系圖及其說明如下:(2)函數(shù)接口說明：函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進行傳遞的過程中比較簡單，下面就將主要函數(shù)及他們之間的參數(shù)的關(guān)系列出如下：int OutOrIn(Lift &L,Passage *Queue,Passage *LiftQ);/進和出電梯的總函數(shù)int Update(Lift &L,Passage *Queue,Passage *LiftQ);/刷新的函數(shù)int Run(Lift &L,Passage *Queue,Passage *LiftQ);/整個電梯各種狀態(tài)轉(zhuǎn)換的函數(shù)int OpenTheDoor(Lift &L);/開門主要是用于解決其中的時間問題int CloseTheDoor(Lift &L);/關(guān)門int In(Lift &L);/進入 主要是解決每個人進入電梯的時間問題int Out(Lift &L);/出去int Test(Lift &L,Passage *Queue,Passage *LiftQ);/電梯測試關(guān)門還是開門的函數(shù)int Request(Lift &L,Passage *Queue);2.3詳細設(shè)計3、調(diào)試分析該程序的調(diào)試過程較為輕松，基本在算法實現(xiàn)的基礎(chǔ)上沒有出現(xiàn)什么錯誤，因而在調(diào)試的過程中并無什么深刻印象。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：1、 提示信息為：“請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志：”按要求輸入即可，本題即輸入9 11 v a2、 提示信息為“請完成該鄰接表的輸入”：由于鄰接表的輸入信息一般較多，而且均是采用的鏈表來存儲，因而該部分的輸入要特別的小心3、 在完成上面兩步的輸入后按enter鍵便能得到程序的運行結(jié)果，即輸出完成整項工程至少需要多少時間和影響工程進度的關(guān)鍵活動 5 測試數(shù)據(jù)及測試結(jié)果測試數(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程序運行結(jié)果如下：6、原程序清單如下：/*關(guān)鍵路徑問題2010年07月31日晚上08：36開始動工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存儲頂點的數(shù)目const int STACK_INIT_SIZE=20;/棧的存儲空間分配量/數(shù)據(jù)存儲部分/*一下是圖的鄰接表的存儲表示，由于第一次用 用的比較的生疏*/typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點的信息ArcNode *firstarc;/指向第一條依附該頂點的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當前頂點數(shù)和弧數(shù)char kind,kind1;/圖中的各類標志頂點和弧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ù)的具體實現(xiàn)部分*/構(gòu)造一個空棧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;/可以用于當棧的存儲空間不夠的情況下 進行擴充return 1;/元素進棧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;/找出每個頂點的入度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ā)生時間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入度頂點棧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;/計算各頂點的最遲發(fā)生時間及進行輸出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完成整項工程至少需要的時間是：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影響工程進度的關(guān)鍵活動是: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請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout請完成該鄰接表的輸入：endl;for(i=0;iG.vnum;i+)cout請輸入該頂點的信息G.verticesi.data;cout請輸入與G.kindG.verticesi.data號頂點相鄰的弧的數(shù)目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout請依次次輸入弧的信息（包括頂點的位置及權(quán)值和該邊的名稱）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout請依次次輸入弧的信息（包括頂點的位置及權(quán)值和該邊的名稱）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該頂點是G.kindG.verticesi.dataendl;cout與該頂點相鄰的頂點依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第五題：關(guān)鍵路徑問題1、需求分析：當一項工程被劃分為若干個子任務(wù)或活動后，人們不僅需要確定這些活動的先后次序，而且需要進一步計算完成整個工程的時間，確定哪些活動是影響工程進度的關(guān)鍵活動，以便合理組織人力、物力、財力，加快這些活動的進度，為按時或提前完成整個工程提供保證。要求：給定一個帶權(quán)的有向圖代表一個工程的AOE網(wǎng)絡(luò)，研究如下問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進度的關(guān)鍵活動？示例圖：2、設(shè)計21設(shè)計思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計本題中的數(shù)據(jù)結(jié)構(gòu)主要影響在于整個程序設(shè)計過程中數(shù)據(jù)的存儲和拓撲排序、關(guān)鍵路徑算法的實現(xiàn)，而在算法的實現(xiàn)過程中又要依賴數(shù)據(jù)的存儲結(jié)構(gòu)，而在圖的存儲結(jié)構(gòu)中，比較適合實現(xiàn)拓撲排序算法的顯然是鄰接表的存儲結(jié)構(gòu)，所以本程序設(shè)計過程中均采用的是鄰接表的存儲方法。其主要數(shù)據(jù)的主要存儲結(jié)構(gòu)體聲明如下：typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點的信息ArcNode *firstarc;/指向第一條依附該頂點的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當前頂點數(shù)和弧數(shù)char kind,kind1;/圖中的各類標志頂點和弧ALGraph;同時由于拓撲排序?qū)崿F(xiàn)過程中要用到進棧和出棧的操作，因此還有棧的聲明如下：typedef struct int *base;int *top;int stacksize;Stack;（2）算法設(shè)計本程序的算法設(shè)計主要體現(xiàn)在拓撲排序和求事件的最早發(fā)生時間和最遲發(fā)生時間的的過程中，因此算法設(shè)計主要也是針對拓撲排序和求事件發(fā)生的最早發(fā)生和最遲發(fā)生時間的算法設(shè)計。拓撲排序的思想是將入度為零的結(jié)點進行S1中的出棧操作，同時將其對T進行進棧，這主要是方便在進行完求最早發(fā)生時間后，通過出棧的操作直接求最遲發(fā)生時間。2.2設(shè)計表示（1）、函數(shù)調(diào)用關(guān)系圖及其說明如下:(2)函數(shù)接口說明：函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進行傳遞的過程中比較簡單，下面就將主要函數(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詳細設(shè)計該程序的算法主要在以下四個方面：拓撲排序、求出事件的最早發(fā)生時間、求出事件的最遲發(fā)生時間、求出關(guān)鍵活動，其中關(guān)鍵活動的算法設(shè)計較為簡單，即是在求出各活動的最早發(fā)生時間和最遲發(fā)生時間的前提下根據(jù)判斷兩時間是否相等，來判斷是否是關(guān)鍵活動，因而主要的算法設(shè)計便在前三個方面。拓撲排序與求事件的最早發(fā)生時間相結(jié)合，拓撲排序即將入度為零的棧S中的元素依次出棧，同時將該元素進棧到棧T中，在進棧的同時求出其最早發(fā)生時間算法如下：從ve（0）=0開始向前遞推Ve（j）=然后便是求事件的最遲發(fā)生時間，該過程就是對上面的過程中得到的棧T進行依次出棧，同時求其最遲發(fā)生時間，其算法簡要描述如下:從vl（n-1）=ve（n-1）起向后遞推Vl（i）=具體實現(xiàn)見代碼中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函數(shù)；3、調(diào)試分析該程序的調(diào)試過程較為輕松，基本在算法實現(xiàn)的基礎(chǔ)上沒有出現(xiàn)什么錯誤，因而在調(diào)試的過程中并無什么深刻印象。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：4、 提示信息為：“請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志：”按要求輸入即可，本題即輸入9 11 v a5、 提示信息為“請完成該鄰接表的輸入”：由于鄰接表的輸入信息一般較多，而且均是采用的鏈表來存儲，因而該部分的輸入要特別的小心6、 在完成上面兩步的輸入后按enter鍵便能得到程序的運行結(jié)果，即輸出完成整項工程至少需要多少時間和影響工程進度的關(guān)鍵活動 5 測試數(shù)據(jù)及測試結(jié)果測試數(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程序運行結(jié)果如下：6、原程序清單如下：/*關(guān)鍵路徑問題2010年07月31日晚上08：36開始動工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存儲頂點的數(shù)目const int STACK_INIT_SIZE=20;/棧的存儲空間分配量/數(shù)據(jù)存儲部分/*一下是圖的鄰接表的存儲表示，由于第一次用 用的比較的生疏*/typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc;/指下一條弧的指針int info;/該弧相關(guān)信息 即權(quán)值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點的信息ArcNode *firstarc;/指向第一條依附該頂點的弧的指針AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/圖中當前頂點數(shù)和弧數(shù)char kind,kind1;/圖中的各類標志頂點和弧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ù)的具體實現(xiàn)部分*/構(gòu)造一個空棧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;/可以用于當棧的存儲空間不夠的情況下 進行擴充return 1;/元素進棧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;/找出每個頂點的入度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ā)生時間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入度頂點棧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;/計算各頂點的最遲發(fā)生時間及進行輸出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完成整項工程至少需要的時間是：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影響工程進度的關(guān)鍵活動是: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請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout請完成該鄰接表的輸入：endl;for(i=0;iG.vnum;i+)cout請輸入該頂點的信息G.verticesi.data;cout請輸入與G.kindG.verticesi.data號頂點相鄰的弧的數(shù)目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout請依次次輸入弧的信息（包括頂點的位置及權(quán)值和該邊的名稱）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout請依次次輸入弧的信息（包括頂點的位置及權(quán)值和該邊的名稱）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該頂點是G.kindG.verticesi.dataendl;cout與該頂點相鄰的頂點依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第八題：研究生入學(xué)考試成績處理1、需求分析：假設(shè)某大學(xué)計算機應(yīng)用技術(shù)專業(yè)招收研究生n名，現(xiàn)在要根據(jù)報考者的考試成績擇優(yōu)錄取?？荚囌n程有政治、英語、數(shù)學(xué)、專業(yè)綜合四門?？荚嚦煽兎譃閮深悾旱谝活悶槊块T課程都達到最低錄取線；第二類為有一門或多門課程未達到最低錄取線。錄取方法是在每門課程達到最低錄取線的考生中按總分從高到低錄取。試設(shè)計一個成績處理程序?qū)崿F(xiàn)以上功能。根據(jù)錄取方法，打印輸出n份錄取通知書，列出錄取者四門課程的成績及總分（要求采用堆排序）。并能實現(xiàn)對任一考生或任一門課程成績的查找（要求兩種查找方式，根據(jù)考號或姓名進行查找，采用高效的查找算法）。錄取通知書的格式如下：2、設(shè)計21設(shè)計思想：（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計由于本題明確要求在進行排序時必須采用推排序的算法，而堆排序最常采用的數(shù)據(jù)存儲結(jié)構(gòu)便是順序表存儲結(jié)構(gòu)，因此在我的設(shè)計中是采用的結(jié)構(gòu)體數(shù)組將各個學(xué)生的信息進行存儲，同時這也方便排序算法的實現(xiàn)。typedef structstring name;int Politics;int English;int Mathematics;int Major;int Total;string Num;Student;（2）算法設(shè)計由于題目要求本程序的查找是針對考號和姓名兩種方式進行查找的，而不是針對相應(yīng)的可比較的數(shù)據(jù)進行查找，所以像二叉查找和二叉排序樹這些查找方法基本都用不上，因此本程序采用的是“蠻力”查找的方法，及對整個結(jié)構(gòu)體數(shù)組進行遍歷，而與要查找的信息一一進行對比，只不過在進行比較的過程中用的是string類中的重載“=”，這樣更加的方便快捷。而堆排序的算法，由于學(xué)生成績的錄取是一個從高分到低分排序的過程，因此推排序的算法就是一個建立“大頂堆”的過程。2.2設(shè)計表示（1）、函數(shù)調(diào)用關(guān)系圖及其說明如下:(2)函數(shù)接口說明：由于個人的喜愛不同，而本人在參數(shù)傳遞的過程中喜歡用引用和指針進行傳遞，因此本程序用的是指針進行傳遞，因而每個參數(shù)都相當于全局變量，這樣在接口方面方便而且不用重新開辟其他的空間。主要函數(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);/判斷該研究生是否有錄取資格 才能進行堆排序 int Find(Student (&S_ALL)MAX_SIZE);/查找成績 int Display();/輸出成績單 int PutIn(Student &S);/成績錄入2.3詳細設(shè)計由于查找的算法是用的“蠻力”的算法，而對成績的錄入也非常的簡單，因此詳細設(shè)計這一塊主要說說堆排序的詳細設(shè)計算法。堆排序的詳細設(shè)計分析：首先題目要求是按四門課程的總分進行排序，由此我們知道我們要建立的堆是一個“大頂堆”，而建堆過程中主要解決的兩個問題是：（1）如何由一個無序序列建成一個堆？（2）如何在輸出堆元素之后，調(diào)整剩余的元素成為一個新的堆？在無序序列建立堆的過程中在我的程序中是用HeapAdjust()這個函數(shù)實現(xiàn)的，將建堆的過程看做事一個反復(fù)篩選的過程，則只需從從最后一個非終端斷點n/2的下界開始向前一次進行篩選，若所比較的元素比其后繼的元素要小則不需要進行交換，否則需要該元素與其父節(jié)點進行交換。即該過程中每一步都是將二叉樹的子樹建立成一個小頂堆的過程，這主要是方便在后面調(diào)整的過程中將堆頂元素和最后一個元素進行交換，即將其從大到小排序的過程。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)試分析印象最深刻的是在二叉樹的第一個元素是下標從1開始，而順序表的數(shù)組的下標是從0開始，這個細節(jié)總會導(dǎo)致內(nèi)存出錯，最后通過在堆排序過程中，先將數(shù)組后移，排序完后將數(shù)組在前移解決了這個問題，因此印象較為深刻，其他的調(diào)試錯誤，一般都是在程序測試的過程中一一改正，問題不大。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：7、 首先提示輸入的是學(xué)生的個數(shù)：此時輸入你所需要輸入的學(xué)生的個數(shù)即可。8、 提示信息為“請按照學(xué)生的姓名、政治、英語、數(shù)學(xué)和專業(yè)綜合的分數(shù)以及考號依次進行輸入”：按照學(xué)生的信息一一進行輸入即可9、 提示信息為“請輸入要錄取學(xué)生的個數(shù)：”此時用戶輸入要錄取學(xué)生的個數(shù)，窗口中便會顯示出錄取學(xué)生的信息10、 然后便是查找的過程，用戶按提示進行輸入，便可按考號和姓名兩種方式對所需要的信息進行查找。5 測試數(shù)據(jù)及測試結(jié)果在測試的過程中我一共用到了如下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然后要求程序通過排序后錄取前五位，程序運行結(jié)果如下：通過與原數(shù)據(jù)的比較，結(jié)果準確無誤：一下便是查找的測試結(jié)果：通過分析知道，結(jié)果準確無誤。6.、原程序清單如下：/*研究生入學(xué)考試成績處理2010年8月1日開始動工*/#include#includeusing namespace std;const int MAX_SIZE=100;const int L_P=60;/分別表示各門的最低錄取分數(shù)線const int L_E=60;const int L_MATH=60;con