數(shù)據(jù)結構電梯運行

1、第二題：電梯模擬1、需求分析：電梯運行模擬某校九層教學樓的電梯系統(tǒng)。該樓有一個自動電梯， 能在每層停留。九個樓層由下至上依次稱為地下層、第一層、第二層、第八層，其中第一層是大樓的進出層，即是電梯的“本壘層”，電梯“空閑”時，將來到該層候命。乘客可隨機地進出于任何層。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。模擬時鐘從0開始，時間單位為0.1秒。人和電梯的各種動作均要消耗一定的時間單位 (簡記為t),比如：有人進出時，電梯每隔40t測試一次，若無人進出，則關門；關門和開門各需要20t ;每個人進出電梯均需要25t;如果電梯在某層靜止時間超過300t，則駛回1層侯

2、命。而題目的最終要求輸出時：按時序顯示系統(tǒng)狀態(tài)的變化過程，即發(fā)生的全部人和電梯的動作序列。int wait now;/已經(jīng)等待的時間struct passage *n ext;Passage;雖然電梯中的狀態(tài)是由枚舉類型來實現(xiàn)的，但是在整個程序的運行過程中，我還是為電梯設置了一個結構體類型，以便保存更多的信息： typedef struct liftint cou nt_C;計數(shù)電梯已到達的層數(shù)int count_A;系統(tǒng)的總時間計數(shù)器記得必須初始化為0int flag_inHigh;九個樓層有無請求的標志哪個樓層如果有請求該標志置1int num;/等待隊列中的人數(shù)記得要進行初始化為0int

3、 people;/電梯中人數(shù)int flag_outHigh;Lift;(2)算法設計顧名思義本程序在運行的過程中用到的算法便是一“電梯算法”，電梯算法借鑒了磁盤尋道 C-LOOK算法，即電梯向一個方向運行，直到這個方向上沒有 服務為止。2.2設計表示(1)、函數(shù)調(diào)用關系圖及其說明如下：Out ()"In ()*OpenTheDClaseTheDoar () 2or () d“II II函數(shù)接口說明：函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進行傳遞的過程中比較簡單，下面就將主要函數(shù)及他們之間的參數(shù)的關系列出如下：int OutOrl n( Lift & L,Pass

4、age *Queue,Passage *LiftQ);進和出電梯的總函數(shù)int Update(Lift & L,Passage *Queue,Passage *LiftQ);刷新的函數(shù)int Run (Lift & L,Passage *Queue,Passage *LiftQ);整個電梯各種狀態(tài)轉換的函數(shù)int Ope nTheDoor(Lift &L);開門主要是用于解決其中的時間問題int CloseTheDoor(Lift &L);關門intln(Lift &L);進入 主要是解決每個人進入電梯的時間問題int Out(Lift &L);

5、出去int Test(Lift & L,Passage *Queue,Passage *LiftQ);電梯測試關門還是開門的函數(shù)int Request(Lift &L,Passage *Queue);2.3詳細設計3、調(diào)試分析該程序的調(diào)試過程較為輕松，基本在算法實現(xiàn)的基礎上沒有出現(xiàn)什么錯誤，因而在調(diào)試的過程中并無什么深刻印象。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：1、提示信息為：“請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志：”按要求輸入即可，本題即輸入9 11 v a2、提示信息為“請完成該鄰接表的輸入”：由于鄰接表的輸入信 息一般較多，而且均是采用

6、的鏈表來存儲，因而該部分的輸入要特別的小心3、在完成上面兩步的輸入后按enter鍵便能得到程序的運行結果，即輸出完成整項工程至少需要多少時間和影響工程進度 的關鍵活動5測試數(shù)據(jù)及測試結果測試數(shù)據(jù)如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6525 9 76 7 8617 4 978 2 10818 4 1190程序運行結果如下:6、原程序清單如下：/*關鍵路徑問題2010年07月31日晚上08: 36開始動工*/#in clude<iostream>using n amespace std;con st int MAX_V_NUM

7、=20; 最大存儲頂點的數(shù)目con st int STACK_INIT_SIZE=20; 棧的存儲空間分配量Illi數(shù)據(jù)存儲部分/*一下是圖的鄰接表的存儲表示，由于第一次用 用的比較的生疏*1typedef struct ArcNodei nt adjvex;該弧所指向的頂點的位置struct ArcNode *nextarc;ll 指下一條弧的指針int info;ll該弧相關信息 即權值int n ame;ll弧的名字ArcNode;typedef struct VNodeint data;ll頂點的信息A rcNode *firstarc;ll指向第一條依附該頂點的弧的指針AdjList

8、MAX_V_NUM; typedef structint vnum,arcnum;圖中當前頂點數(shù)和弧數(shù)char kind,kind1;圖中的各類標志頂點和弧ALGraph;typedef structint *base;int *top;int stacksize;Stack;in t veMAX_V_NUM;Stack T;/函數(shù)體描述部分int InitStack(Stack &S);int Push(Stack & S,i nt & e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &

9、G);int ToPoOrder(ALGraph &G ,Stack &T);int FindlnDegree(ALGraph &G ,int (&indegree)MAX_V_NUM);/*下面是函數(shù)的具體實現(xiàn)部分*/構造一個空棧int Ini tStack(Stack &S)S.base=(i nt*)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;可以用于當棧的存儲空間不夠的情況下進行擴充return 1

10、;/元素進棧int Push (Stack &S, int &e)*S.top+=e;return 1;/元素出棧if(S.top=S.base)return 0;e=*-S.top;return 1;；/判斷棧是否為空int StackEmpty(Stack &S)if(S.top=S.base)return 1;elsereturn 0;/找出每個頂點的入度int FindlnDegree(ALGraph &G ,int (&indegree)MAX_V_NUM)A rcNode *p;int i;for(i=0;i<MAX_V_NUM;i+)

11、in degreei=0;for(i=0;i<G .vnum;i+)for(p=G .verticesi.firstarc;p;p=p->nextarc)in degreep_>adjvex+;return 0;/拓撲排序同時求出各活動的最早發(fā)生時間int ToPoOrder(ALGraph &G ,Stack &T)int coun t=0;int i,j,k;Stack S1;A rcNode *p;in t i ndegreeMAX_V_NUM;In itStack(SI);Findln Degree(G,i ndegree);for(i=0;i<

12、G .vnum;i+)if(i ndegreei=0)Push(S1,i);/建立0入度頂點棧Sfor(i=0;i<G .vnum;i+)vei=0;while(!StackEmpty(S1)Pop(S1,j);Push(T,j);coun t+;for(p=G .verticesj.firstarc;p;p=p->nextarc)k=p->adjvex;if(-i ndegreek=0)Push(S1,k);if(vej+(p->i nfo)>vek) vek=vej+(p->in fo);/ for(i=0;i<G .vnum;i+)/cout&l

13、t;<vei<<e ndl;if(count<G .vnum)return 0;elsereturn 1;/計算各頂點的最遲發(fā)生時間及進行輸出int CriticalPath(ALGraph &G)in t vlMAX_V_NUM;int dut;int i,j,k,ee,el;A rcNode *p;/ char tag;if(!ToPoOrder(G ,T)cout<<"完成整項工程至少需要的時間是："<<veG .vnum-1<<endl;for(i=0;i<G .vnum;i+)vli=veG

14、.v num-1;while(!StackEmpty(T)for(Pop(T,j),p=G.verticesj.firstarc;p;p=p->n extarc)k=p_>adjvex;dut=(p->i nfo);if(vlk-dut<vlj)vlj=vlk-dut;/ for(i=0;i<G .vnum;i+)/cout<<vli<<e ndl;cout<<"影響工程進度的關鍵活動是:"<<e ndl;for(j=0;j<G .vnum;j+)for(p=G .verticesj.fir

15、starc;p;p=p->nextarc)k=p->adjvex;dut=(p->i nfo);ee=vej;el=vlk-dut;cout<<"j="<<j<<"K="<<k<<"dut="<<dut<<"ee="<<ee<<"el="<<el<<en dl;if(ee=el)tag=(ee=el)?'*':”；cout<&

16、lt;G.k in d1<<p->n ame<<e ndl;return 1;int mai n()A LGraph G;in t i,j,H num;A rcNode *p,*q;/ int in degreeMAX_V_NUM;/ALGraph G;cout<<"請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志："<<e ndl;cin»G .vnum;cin»G .arc num;cin»G .ki nd;cin»G .ki ndl;cout<<"請完成該

17、鄰接表的輸入："<<e ndl;for(i=0;i<G .vnum;i+)cout<<"請輸入該頂點的信息 "<<e ndl;cin»G .verticesi.data;cout<<"請輸入與"<<G.kind<<G .verticesi.data<<"號頂點相鄰的 弧的數(shù)目:"<<endl;cin»Hnum;if(Hnu m=0)G.verticesi.firstarc=0;elsecout<&l

18、t;"請依次次輸入弧的信息(包括頂點的位置及權值和 該邊的名稱)"<<e ndl;p=(ArcNode *)malloc(sizeof(ArcNode);G.verticesi.firstarc=p;p->n extarc=0;cin> >p_>adjvex;cin> >p_>i nfo;cin> >p->n ame;for(j=0;j< Hnu m_1;j+)cout<<"請依次次輸入弧的信息(包括頂點的位置及權 值和該邊的名稱)"<<e ndl;q=

19、(ArcNode *)malloc(sizeof(ArcNode);cin>> q->adjvex;cin>> q_>i nfo;cin»q_>n ame;q->n extarc=p->n extarc;p_>n extarc=q;/ToPoOrder(G,T); /CriticalPath(G);/test/ /* for(i=0;i<G .vnum;i+)cout<<"該頂點是"<<G.kind<<G.verticesi.data<<endl; c

20、out<<"與該頂點相鄰的頂點依次是："<<e ndl;for(p=G .verticesi.firstarc;p;p=p->nextarc)cout<<G.kind<<G .verticesp->adjvex.data<<endl; */Findln Degree(G ,in degree);for(i=0;i<G .vnum;i+)/cout<<"i ndegree"<<i<<"="<<i ndegreei

21、<<e ndl;CriticalPath(G);/test en d/ return 0;/*第五題：關鍵路徑問題1、需求分析:當一項工程被劃分為若干個子任務或活動后，人們不僅需要確定這些活動的先后次序， 而且需要進一步計算完成整個工程的時間，確定哪些活動是影響工程進度的關鍵活動，以便合理組織人力、物力、財力，加快這些活動的進度，為按時或提前完成整個工程提供保證。要求：給定一個帶權的有向圖代表一個工程的AOE網(wǎng)絡，研究如下問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進度的關鍵活動？示例圖：2、設計2. 1設計思想：（1）數(shù)據(jù)結構設計本題中的數(shù)據(jù)結構主要影響在于

22、整個程序設計過程中數(shù)據(jù)的存儲和 拓撲排序、關鍵路徑算法的實現(xiàn)，而在算法的實現(xiàn)過程中又要依賴數(shù)據(jù)的存儲結構，而在圖的存儲結構中，比較適合實現(xiàn)拓撲排序算法的顯然是鄰接表的存儲結構，所以本程序設計過程中均采用的是鄰接表的存儲方法。其主要數(shù)據(jù)的主要存儲結構體聲明如下：typedef struct ArcNodeint adjvex;該弧所指向的頂點的位置struct ArcNode *nextarc;/ 指下一條弧的指針int info;/該弧相關信息即權值int name;/弧的名字ArcNode;typedef struct VNodeint data;/頂點的信息ArcNode *firstar

23、c;/指向第一條依附該頂點的弧的指針AdjListMAX_V_NUM; typedef structAdjList vertices;int vnum,arcnum;/圖中當前頂點數(shù)和弧數(shù) char kind,kind1;/圖中的各類標志頂點和弧ALGraph;同時由于拓撲排序實現(xiàn)過程中要用到進棧和出棧的操作，因此還有棧的聲明如下：typedef structint *base;int *top;int stacksize;Stack;（2）算法設計本程序的算法設計主要體現(xiàn)在拓撲排序和求事件的最早發(fā)生時 間和最遲發(fā)生時間的的過程中，因此算法設計主要也是針對拓撲排序 和求事件發(fā)生的最早發(fā)生和最遲

24、發(fā)生時間的算法設計。拓撲排序的思想是將入度為零的結點進行 S1中的出棧操作，同時將其對 T進行進 棧，這主要是方便在進行完求最早發(fā)生時間后，通過出棧的操作直接求最遲發(fā)生時間。2.2設計表示（1）、函數(shù)調(diào)用關系圖及其說明如下函數(shù)中的參數(shù)均是使用的全局變量的傳遞，因而在函數(shù)間進行傳遞的過程中比較簡單，下面就將主要函數(shù)及他們之間的參數(shù)的關系列出如下：in tin itStack(Stack & S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &

25、G);int ToPoOrder(ALGraph &G,Stack &T);int Findln Degree(ALGraph & G,i nt (&in degree)MAX_V_NUM);2.3詳細設計該程序的算法主要在以下四個方面：拓撲排序、求出事件的最早發(fā)生時間、求出事件的最遲發(fā)生時間、求出關鍵活動，其中關鍵活動的算法設計較為簡單，即是在求出各活動的最早發(fā)生時間和最遲發(fā)生時間的前提下 根據(jù)判斷兩時間是否相等，來判斷是否是關鍵活動，因而主要的算法設計 便在前三個方面。拓撲排序與求事件的最早發(fā)生時間相結合，拓撲排序即將入度為零的棧S中的元素依次出棧，同時將該

26、元素進棧到棧 T中，在進棧的同時求出 其最早發(fā)生時間算法如下：從ve( 0)=0開始向前遞推Ve(j)=Maxve(i) dut( ： i, j )然后便是求事件的最遲發(fā)生時間，該過程就是對上面的過程中得到的 棧T進行依次出棧，同時求其最遲發(fā)生時間，其算法簡要描述如下：從vl ( n-1)=ve( n-1 )起向后遞推Vl(i)=Minvl(j) -dut(： i, j )具體實現(xiàn)見代碼中int ToPoOrder(ALGraph &G,Stack &T)和 intCriticalPath(ALGraph &G) 函數(shù)；3、調(diào)試分析該程序的調(diào)試過程較為輕松，基本在算法實

27、現(xiàn)的基礎上沒有出現(xiàn)什么錯誤，因而在調(diào)試的過程中并無什么深刻印象。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：4、提示信息為：“請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧 的標志：”按要求輸入即可，本題即輸入 9 11 v a5、提示信息為“請完成該鄰接表的輸入”：由于鄰接表的輸入信 息一般較多，而且均是采用的鏈表來存儲，因而該部分的輸入要特別的小心6、在完成上面兩步的輸入后按enter鍵便能得到程序的運行結果，即輸出完成整項工程至少需要多少時間和影響工程進度 的關鍵活動5測試數(shù)據(jù)及測試結果測試數(shù)據(jù)如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1

28、5415 2 6525 9 76 7 8617 4 9718 2 10817 4 1190程序運行結果如下：81>:可的動 §S 少關 至的 程度 工進 項程 整工宀元診ala4a7a8al0all6、原程序清單如下:/*關鍵路徑問題2010年07月31日晚上08: 36開始動工*/#in clude<iostream>using n amespace std;con st int MAX_V_NUM=20; 最大存儲頂點的數(shù)目con st int STACK_INIT_SIZE=20; 棧的存儲空間分配量Illi數(shù)據(jù)存儲部分/*一下是圖的鄰接表的存儲表示，由于第一

29、次用用的比較的生疏*1typedef struct ArcNodei nt adjvex;該弧所指向的頂點的位置struct ArcNode *nextarc;ll 指下一條弧的指針int info;ll該弧相關信息 即權值int n ame;ll弧的名字ArcNode;typedef struct VNodeint data;ll頂點的信息A rcNode *firstarc;ll指向第一條依附該頂點的弧的指針AdjListMAX_V_NUM;typedef structAdjList vertices;int vnum,arcnum;圖中當前頂點數(shù)和弧數(shù)char kind,kind1;ll

30、圖中的各類標志頂點和弧ALGraph;typedef structint *base;int *top;int stacksize;Stack;in t veMAX_V_NUM;Stack T;/函數(shù)體描述部分in tin itStack(Stack & S);int Push(Stack & S,i nt & e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G ,Stack &T);int FindlnDegree(A

31、LGraph &G ,int (&indegree)MAX_V_NUM);/*下面是函數(shù)的具體實現(xiàn)部分*/構造一個空棧int Ini tStack(Stack &S)S.base=(i nt*)malloc(STACK_INIT_SIZE*sizeof(i nt); 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;/元素

32、出棧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;elsereturn 0;/找出每個頂點的入度int FindlnDegree(ALGraph &G ,int (&indegree)MAX_V_NUM) A rcNode *p;int i;for(i=0;i<MAX_V_NUM;i+)in degreei=0;for(i=0;i<G .v

33、num;i+)for(p=G .verticesi.firstarc;p;p=p->nextarc)in degreep_>adjvex+;return 0;/拓撲排序同時求出各活動的最早發(fā)生時間int ToPoOrder(ALGraph &G ,Stack &T)int coun t=0;int i,j,k;Stack S1;A rcNode *p;in t i ndegreeMAX_V_NUM;In itStack(T);In itStack(S1);Findln Degree(G,i ndegree);for(i=0;i<G .vnum;i+)if(i

34、ndegreei=0)Push(S1,i);/建立0入度頂點棧Sfor(i=0;i<G .vnum;i+) vei=0;while(!StackEmpty(S1) Pop(S1,j);Push(T,j); coun t+;k=p_>adjvex;if(-i ndegreek=O)Push(S1,k);if(vej+(p->i nfo)>vek) vek=vej+(p->in fo);/ for(i=0;i<G .vnum;i+)/cout<<vei<<e ndl;if(count<G .vnum)return 0;elseret

35、urn 1;/計算各頂點的最遲發(fā)生時間及進行輸出int CriticalPath(ALGraph &G)in t vlMAX_V_NUM;int dut;int i,j,k,ee,el;A rcNode *p;/ char tag;if(!ToPoOrder(G ,T)return 0;cout<<"完成整項工程至少需要的時間是："<<veG .vnum-1<<endl;for(i=0;i<G .vnum;i+)vli=veG.v num-1;while(!StackEmpty(T)for(Pop(T,j),p=G.vert

36、icesj.firstarc;p;p=p->n extarc)k=p->adjvex;dut=(p->i nfo);if(vlk-dut<vlj)vlj=vlk-dut;/ for(i=0;i<G .vnum;i+)/cout<<vli<<e ndl;for(j=0;j<G .vnum;j+)for(p=G .verticesj.firstarc;p;p=p->nextarc)k=p_>adjvex;dut=(p_>i nfo);ee=vej;el=vlk-dut;cout<<"j="

37、<<j<<"K="<<k<<"dut="<<dut<<"ee="<<ee<<"el="<<el<<en dl;if(ee=el)tag=(ee=el)?'*':”;cout<<G.k in d1<<p->n ame<<e ndl;return 1;int mai n()A LGraph G;in t i,j,H num;A rcNode *

38、p,*q;/int in degreeMAX_V_NUM;/ALGraph G;cout<<"請輸入圖中的頂點數(shù)和弧數(shù)以及圖的標志和弧的標志："<<e ndl;cin»G .vnum;cin»G .arc num;cin»G .ki nd;cin»G .ki nd1;cout<<"請完成該鄰接表的輸入："<<e ndl;for(i=0;i<G .vnum;i+)cout<<"請輸入該頂點的信息 "<<e ndl;cin

39、»G .verticesi.data;cout<<"請輸入與"<<G.kind<<G .verticesi.data<<"號頂點相鄰的 弧的數(shù)目:"<<endl;if(Hnu m=0)G.verticesi.firstarc=O;elsecout<<"請依次次輸入弧的信息(包括頂點的位置及權值和 該邊的名稱)"<<e ndl;p=(ArcNode *)malloc(sizeof(ArcNode);G.verticesi.firstarc=p;

40、p->n extarc=O;cin> >p_>adjvex;cin> >p_>i nfo;cin> >p->n ame;for(j=0;j< Hnu m_1;j+)cout<<"請依次次輸入弧的信息(包括頂點的位置及權 值和該邊的名稱)"<<e ndl;q=(ArcNode *)malloc(sizeof(ArcNode);cin>> q->adjvex;cin>> q_>i nfo;cin»q_>n ame;q->n exta

41、rc=p->n extarc;p_>n extarc=q;/ToPoOrder(G,T);/CriticalPath(G);/test/* for(i=0;i<G .vnum;i+)cout<<"該頂點是"<<G.kind<<G.verticesi.data<<endl;cout<<"與該頂點相鄰的頂點依次是："<<e ndl;for(p=G .verticesi.firstarc;p;p=p->nextarc)cout<<G.kind<&l

42、t;G .verticesp->adjvex.data<<endl;*/ Findln Degree(G ,in degree);for(i=0;i<G .vnum;i+)/cout<<"i ndegree"<<i<<"="<<i ndegreei<<e ndl;CriticalPath(G);/test en d/return 0;/*第八題：研究生入學考試成績處理1、需求分析：假設某大學計算機應用技術專業(yè)招收研究生n名，現(xiàn)在要根據(jù)報考者的考試成績擇優(yōu)錄取。考試課程有政

43、治、英語、數(shù)學、專業(yè)綜合四門?？荚嚦煽兎譃閮深悾旱谝活悶槊块T課 程都達到最低錄取線；第二類為有一門或多門課程未達到最低錄取線。錄取方法是在每門課程達到最低錄取線的考生中按總分從高到低錄取。試設計一個成績處理程序實現(xiàn)以上功能。根據(jù)錄取方法，打印輸出n份錄取通知書，列出錄取者四門課程的成績及總分（要求采用堆排序）。并能實現(xiàn)對任一考生或任一門課程成績的查找（要求兩種查找方式，根據(jù)考號 或姓名進行查找，采用高效的查找算法）。錄取通知書的格式如下：輕皿(姓名)匕屮You have been admitted+JYour scares: Politi 匚£EnglishMathematicsXX

44、，MajorTotal2、設計2. 1設計思想：（1）數(shù)據(jù)結構設計由于本題明確要求在進行排序時必須采用推排序的算法，而堆排序最常采用的數(shù)據(jù)存儲結構便是順序表存儲結構，因此在我的設計中是采用的結構體數(shù)組將各個學生的信息進行存儲，同時這也方便排序算法的實現(xiàn)。typedef structstri ng n ame;int Politics;int En glish;int Mathematics;int Major;int Total;stri ng Num;Stude nt;(2)算法設計由于題目要求本程序的查找是針對考號和姓名兩種方式進行查找的，而不是針對相應的可比較的數(shù)據(jù)進行查找，所以像二叉查

45、找和二叉排序樹這些查找方法基本都用不上，因此本程序采用的是“蠻力”查找的方法，及對整個結構體數(shù)組進行遍歷，而與要查找的信息一一進行對比，只不過在進行比較的過程中用的是string類中的重載“=”,這樣更加的方便快捷。而堆排序的算法，由于學生成績的錄取是一個從高分到低分排序 的過程，因此推排序的算法就是一個建立“大頂堆”的過程。2.2設計表示(1)、函數(shù)調(diào)用關系圖及其說明如下：函數(shù)接口說明：由于個人的喜愛不同，而本人在參數(shù)傳遞的過程中喜歡用引用和指針 進行傳遞，因此本程序用的是指針進行傳遞，因而每個參數(shù)都相當于全局變量，這樣在接口方面方便而且不用重新開辟其他的空間。主要函數(shù)如下：Int He a

46、pAdjust(Stude nt (&S_USE)MAX_SIZE,i nt s,i nt m);堆排序int HeapSort(Stude nt (&S_USE)MAX_SIZE);調(diào)整intPa nDua n(Stude nt(&S_ALL)MAX_SIZE,Stude nt(&S_USE)MAX_SIZE,Stude nt (&S_U NUSE)MAX_SIZE); 判斷該研究生 是否有錄取資格才能進行堆排序in t Display。;/輸出成績單int Put In (Stude nt &S);成績錄入2.3詳細設計由于查找的算法是用的“

47、蠻力”的算法，而對成績的錄入也非常的簡 單，因此詳細設計這一塊主要說說堆排序的詳細設計算法。堆排序的詳細設計分析：首先題目要求是按四門課程的總分進行排 序，由此我們知道我們要建立的堆是一個“大頂堆”，而建堆過程中主要解決的兩個問題是：(1)如何由一個無序序列建成一個堆？ (2)如何在輸出堆元素之后，調(diào)整剩余的元素成為一個新的堆？在無序序列建立堆的 過程中在我的程序中是用HeapAdjust()這個函數(shù)實現(xiàn)的，將建堆的過程看做事一個反復篩選的過程，則只需從從最后一個非終端斷點n/2的下界開始向前一次進行篩選，若所比較的元素比其后繼的元素要小則不需要進 行交換，否則需要該元素與其父節(jié)點進行交換。即

48、該過程中每一步都是將二叉樹的子樹建立成一個小頂堆的過程，這主要是方便在后面調(diào)整的過程中將堆頂元素和最后一個元素進行交換，即將其從大到小排序的過程。int HeapAdjust(Student (&S_USE)MAX_SIZE,int s,int m)Stude nt rc;int j;rc=S_USEs;f or(j=2*s;j<=m;j*=2)if(j< m&&( S_USEj.Total>S_USEj+1.Total)j+;if(rc.Total<S_USEj.Total)break;S_USEs=S_USEj;s=j;S_USEs=rc;r

49、etur n 0;而調(diào)整的過程比較簡單，即將隊堆頂?shù)脑嘏c順序表的最后一個元素 進行交換，然后將剩下的元素建堆的一個過程，主要函數(shù)實現(xiàn)如下：int HeapSort(Stude nt (&S_USE)MAX_SIZE)i nt i;Stude nt tmp;f or(i=co un t_U;i>=0;i_)S_USEi=S_USEi-1;/cout<<"I am here!"<<e ndl;f or(i=cou nt_U/2;i>0;i-)要不要減一先記在這里f or(i=co un t_U;i>1;i-)tmp=S_USE

50、1;S_USE1=S_USEi;S_USEi=tmp;Heap Adjust(S_USE,1,i-1);f or(i=0;i<co un t_U;i+)S_USEi=S_USEi+1;retur n 0;3、調(diào)試分析印象最深刻的是在二叉樹的第一個元素是下標從1開始，而順序表的數(shù)組的下標是從0開始，這個細節(jié)總會導致內(nèi)存出錯，最后通過在堆排序 過程中，先將數(shù)組后移，排序完后將數(shù)組在前移解決了這個問題，因此印象較為深刻，其他的調(diào)試錯誤，一般都是在程序測試的過程中一一改正， 問題不大。4、用戶手冊點擊運行程序，在彈出的窗口中，會提示要輸入的信息：7、首先提示輸入的是學生的個數(shù)：此時輸入你所需要輸

51、入的學 生的個數(shù)即可。8、提示信息為“請按照學生的姓名、政治、英語、數(shù)學和專業(yè)綜合的分數(shù)以及考號依次進行輸入”：按照學生的信息一一進 行輸入即可9、提示信息為“請輸入要錄取學生的個數(shù)：”此時用戶輸入要錄 取學生的個數(shù)，窗口中便會顯示出錄取學生的信息10、然后便是查找的過程，用戶按提示進行輸入，便可按考號和 姓名兩種方式對所需要的信息進行查找。5測試數(shù)據(jù)及測試結果在測試的過程中我一共用到了如下26組數(shù)據(jù)：aaa 97 98 85 91 1001bbb 56 89 45 97 1002ccc 62 68 64 92 1003ddd 66 68 69 92 1004eee 70 72 48 95 1

52、005fff 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 1011III 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

53、 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然后要求程序通過排序后錄取前五位，程序運行結果如下:ADMISSION NOTICE:¥ou liave beenadnittedVour scores =Po lit ics9798mat ics85Major91Total371CFina Universityof GeoscienceADMISSION NOTICEmntm:Vou

54、 Fave beenadnittedYour scores:Polit ics65ngflisli78nathematics89Major123Total355hina Universityof GeoscienceADMISSION NOTICE111：Vou have been admitted¥aur scores:Politics65English75Mathemat ics89Majoi-100Total329China Univepsitv of Geosc ienceADMISSION NOTICEhhh：Vou haue been admittedVouir scor

55、es :Politics75English78tlatlieinat ics79Major96Total32SChina University of GeoscienceADMISSION NOTICEYou Jiave been admittedYour scores：Polit ics70English76latlie mat ics86riajov95fTotal327通過與原數(shù)據(jù)的比較，結果準確無誤: 一下便是查找的測試結果：通過分析知道，結果準確無誤。6.、原程序清單如下：/*研究生入學考試成績處理2010年8月1日開始動工*/#in clude<iostream>#in

56、 clude<stri ng>using n amespace std;con st int MAX_SIZE=100;con st int L_P=60;分別表示各門的最低錄取分數(shù)線con st int L_E=60;const int L_MATH=60;const int L_MAJOR=90;in t cou nt_A=0;用于記錄全部錄入的學生的個數(shù)in t cou nt_U=O;用于記錄達到最低分數(shù)線的學生的個數(shù)in t cou nt_N=O;用與記錄為達到最低分數(shù)線的學生的個數(shù)in t cou nt_ACC=0;用于記錄錄取學生的個數(shù)typedef structstri ng n ame;int En glish;int Mathematics;int Major;int Total;stri ng Num;Stude nt;/int HeapAdjust(Stude nt(&S_USE)MAX_SIZE,i nts,i ntm);/堆排序int HeapSort(Stu