數(shù)據(jù)結(jié)構(gòu)實訓(xùn)學(xué)生分配問題

1、淮陰工學(xué)院算法設(shè)計技能訓(xùn)練實習(xí)報告題目： 學(xué)生搭配問題 系 （院）: 計算機工程學(xué)院 專 業(yè)： 微軟 班 級： 計1137 學(xué) 號： 1131317726 姓 名： 陸炎煒 指導(dǎo)教師： 周海巖 學(xué)年學(xué)期: 2014 2015 學(xué)年 第 1 學(xué)期2015年 1月 1 日算法設(shè)計技能訓(xùn)練任務(wù)書課題名稱 學(xué)生搭配問題設(shè)計目的1、 通過算法設(shè)計技能訓(xùn)練，深入理解算法設(shè)計的意義和重要性，更好地掌握 算法設(shè)計的知識。2、 能夠針對某一具體問題，設(shè)計算法進(jìn)行解決。3、 鍛煉實踐動手能力，提高解決問題的能力。實驗環(huán)境硬件：1、PC機，奔騰以上CPU， 512MB以上內(nèi)存，80G以上硬盤； 軟件：Visual

2、C+編程工具任務(wù)要求1、 應(yīng)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識進(jìn)行實際問題求解與分析2、 作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強的容錯能力3、 上機能正常運行代碼4、 分析算法的運行效率5、 按要求撰寫課程設(shè)計報告和設(shè)計總結(jié)工作進(jìn)度計劃序號起止日期工 作 內(nèi) 容12014.12.29任務(wù)下達(dá)，查閱文獻(xiàn)資料22014.12.292014.12.31總體設(shè)計、素材搜集、課題詳細(xì)設(shè)計、調(diào)試32014.12.312015.1.3完善設(shè)計、撰寫報告420答辯指導(dǎo)教師（簽章）： 年 月 日 摘要 針對學(xué)生搭配問題，循環(huán)隊列是一種重要的鏈?zhǔn)浇Y(jié)構(gòu)，其特殊性在于需附設(shè) 兩個指針front和rear分別指示對頭元素及隊尾元素

3、的位置且對頭和隊尾相鄰接。在程序的設(shè)計過程中，運用了各種基本的算法，有判斷隊空及隊滿，出隊，入隊等.循環(huán)隊列是在隊列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素和隊列尾元素的位置。學(xué)生搭配問題是典型的只有采用循環(huán)隊列才能解決的問題，實驗表明該算法的空間復(fù)雜度優(yōu)于其他算法。 本文用循環(huán)隊列會很好的把這個程序設(shè)計出來，會有很好的效果。得出的程序運行結(jié)果能夠很形象的把結(jié)果表示出來。關(guān)鍵詞： 學(xué)生搭配 數(shù)據(jù)結(jié)構(gòu) 循環(huán)隊列 目錄一、設(shè)計目的.二、課程設(shè)計. 1、設(shè)計內(nèi)容. 2、設(shè)計思想. 3、關(guān)鍵算法. 4、測試結(jié)

4、果.三、實驗程序.四、結(jié)論.5、 致謝.六、參考文獻(xiàn).一、設(shè)計目的1、通過算法設(shè)計技能訓(xùn)練，深入理解算法設(shè)計的意義和重要性，更好地掌握 算法設(shè)計的知識。2、能夠針對某一具體問題，設(shè)計算法進(jìn)行解決。3、鍛煉實踐動手能力，提高解決問題的能力。2、 課程設(shè)計1.設(shè)計內(nèi)容一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會. 男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:1) 輸出每曲配對情況2) 計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的

5、情況.至少求出K的兩個值.3) 盡量設(shè)計出多種算法及程序,可視情況適當(dāng)加分2、設(shè)計思想隊列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運算受限的線性表。循環(huán)隊列是在隊列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素和隊列尾元素的位置。 循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊，出隊，判隊滿，判隊空。 （1） 要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2。 （2） 將男生、女生兩組人分別存入這兩個隊列。以

6、實現(xiàn)他們的循環(huán)配對輸出，這是循環(huán)隊列固有的特性。 （3） 利用循環(huán)隊列的特性，將男女生分別進(jìn)行入隊列和出隊列操作，且實現(xiàn)搭配輸出。 （4） 循環(huán)隊列的長度分別設(shè)為男女生的個數(shù)即可。（5） 在計算機終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況。3、關(guān)鍵算法建立兩個鏈?zhǔn)窖h(huán)隊列來分別存儲男生和女生，然后調(diào)用入隊出隊函數(shù)實現(xiàn)循環(huán)隊列的配對輸出。為充分利用向量空間，克服上述假上溢現(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，存儲在其中成為循環(huán)隊列。在循環(huán)隊列中進(jìn)行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界時、其加1操作是指向向量的下界。這樣就可以通過出隊再入隊來實現(xiàn)

7、男生女生的循環(huán)搭配。課程設(shè)計過程中的關(guān)鍵算法如下：1)關(guān)鍵算法之一：初始化隊列void InitQ(LinkQueue &Q)    QueuePtr p;   p=(QueuePtr)malloc(sizeof(QNode);  Q.front=p;  Q.rear=p;  Q.front->next=NULL; (2)關(guān)鍵算法之二：入隊函數(shù) void EnQueue(LinkQueue&#

8、160;&Q,int num)/入隊函數(shù)   QueuePtr p;   p=(QueuePtr)malloc(sizeof(QNode);  p->num=num;  p->next=NULL;  Q.rear->next=p;  Q.rear=p; (3)關(guān)鍵算法之三：出隊函數(shù) void DeQueue(LinkQueue &Q, int 

9、&num)/出隊函數(shù)   QueuePtr p,q;   if(Q.front=Q.rear)   printf("隊列為空");  p=Q.front->next;  num=p->num;  Q.front->next=p->next;  q=p->next;  if(Q.rear=q)   Q.rear=

10、Q.front;  free(p); (4)關(guān)鍵算法之四：輸出第i首曲子時女隊的情況 void printF(LinkQueue &F,int i) /輸出第i首曲子時女隊的情況   QueuePtr p;   int n=1;  while(n<i)     printf("_ ");   n

11、+;     p=F.front->next;  while(F.rear!=p)      printf("%d ",p->num);   p=p->next;  printf("%d n",p->num); 4、測試結(jié)果：三、實驗程序#include<iostream>template <class T

12、>class cirularQueue /定義一個一個循環(huán)隊列 private: int MaxSize; int front; /頭指針 int rear; /尾指針 T *data; public: cirularQueue(int MaxLength) MaxSize=MaxLength; front=rear=0; data=new TMaxLength; cirularQueue() /定義析構(gòu)函數(shù)，使對象在撤銷時釋放 front=rear=0; delete data; void Initqueue() /隊列的申明 for(int i=0;i<maxSize-1;i+

13、) push(i);bool IsFull() /判斷隊列是否已滿 if(rear+1)%MaxSize=front) return true; else return false; bool IsEmpty() /判斷隊列是否為空 if(front=rear) return true; else return false;void push(T info) /入隊 if(IsFull() cout<<"錯誤！隊列已滿！"<<endl; exit(-1); else datarear=info; rear=(rear+1)%MaxSize; void

14、 Pop(T &info) /出隊 if(IsEmpty() cout<<"錯誤！隊列為空！"<<endl; exit(-1); else info=datafront; front=(front+1)%MaxSize; void GetHead(T &info) /取隊首元素 if(IsEmpty() cout<<"錯誤！隊列為空！"<<endl; exit (-1); else info=datafront; ;void Initqueue(cirularQueue<int>

15、&,int);void display(int,int);void charge(int,int);using namespace std;static int songnum=0; /定義歌曲的數(shù)量并初始化為0static int m=0,n=0; /男生和女生的人數(shù) int main() /主函數(shù) cout<<"請分別輸入男生和女生的人數(shù):" cin>>m>>n; display(m,n); int a=0,b=0; /男生和女生的編號，以判斷他們在第幾首歌時能在一起跳舞 char quit='y' /判斷是否

16、繼續(xù)輸入,如果繼續(xù)輸入，則輸入'y'；否則輸入'n' while(quit!='n') cout<<"請輸入男生和女生的編號:" cin>>a>>b; while(a>m)|(b>n) /如果輸入錯誤 cout<<"輸入的編號過大，請重新輸入:" cin>>a>>b; charge(a,b); cout<<"是否繼續(xù)(是請輸入'y',否則請輸入'n'):" ci

17、n>>quit; return 0;void Initqueue(cirularQueue<int> &Q,int m) /初始化隊列 for(int i=1;i<=m;i+) Q.push(i);void display(int m,int n) cirularQueue<int> man(m+1); cirularQueue<int> woman(n+1); Initqueue(man,m); Initqueue(woman,n); cout<<"請輸入曲目數(shù):" cin>>songn

18、um; cout<<"每曲的配對情況為:"<<endl; for(int k=1;k<=songnum;k+) int x=0,y=0; /男生和女生的編號 man.Pop(x); /男生按順序出對跳舞 woman.Pop(y); /女生按順序出對跳舞 cout<<"第"<<k<<"曲:t"<<x<<"號男生<->"<<y<<"號女生"<<endl; /他們在

19、一起跳舞 man.push(x); /跳完舞后男生再次進(jìn)入隊列等在下一次跳舞 woman.push(y); /跳完舞后男生再次進(jìn)入隊列等在下一次跳舞 void charge(int a,int b) int count=0; /定義舞曲計數(shù)以記錄他們能在第幾曲時在一起跳舞 cirularQueue<int> man1(m+1); cirularQueue<int> woman1(n+1); Initqueue(man1,m); Initqueue(woman1,n); while(count<=songnum) int x, y; count+; man1.Pop

20、(x); woman1.Pop(y); man1.push(x); woman1.push(y); if(x=a)&&(y=b) cout<<"第"<<count<<"首曲:t"<<a<<"號男生<->"<<b<<"號女生"<<endl; break; /如果他們在這個舞會上不能在一起跳舞，則輸出 if(count=songnum+1) cout<<"他們在這個舞會上不可

21、能在一起跳舞"<<endl; 結(jié) 論設(shè)計采用的是循環(huán)隊列的基本操作順利的解決學(xué)生舞曲搭配問題，主要利用用循環(huán)隊列的環(huán)狀結(jié)構(gòu)，循環(huán)地執(zhí)行出列入列操作并在出隊列時進(jìn)行配對并輸出配對情況，而整個過程不需要不需要移動元素使程序在空間復(fù)雜度上降到最小，采用指針的移動大大加快了程序的執(zhí)行效率。并且對輸入進(jìn)行了改進(jìn)，以防止用戶隨意輸入時出現(xiàn)的各種意想不到的錯誤。本次程序設(shè)計中所用語言為C+，程序開始定義了類cirular，其中有頭指針，尾指針及數(shù)據(jù)域等。隨之定義了析構(gòu)函數(shù)，釋放對象，然后進(jìn)行了隊列的基本操作，有隊列的申明，判斷隊空及隊滿，出隊，入隊，其核心是display()函數(shù)和ch

22、arge()函數(shù)，其中display()用于對各位同學(xué)編號和每隊的輸出情況，charge()用于計算已編號的同學(xué)在第幾曲中進(jìn)行配對。循環(huán)隊列是一種環(huán)狀的隊列并且對頭元素指向隊尾元素，學(xué)生搭配問題是典型的只有采用循環(huán)隊列才能解決的問題，實驗表明該算法的空間復(fù)雜度優(yōu)于其他算法。 致 謝 踉踉蹌蹌地忙碌近三四天，我的實訓(xùn)報告也終將告一段落。點擊運行，也基本達(dá)到預(yù)期的效果，虛榮的成就感在沒人的時候也總會冒上心頭。但由于能力和時間的關(guān)系，總是覺得有很多不盡人意的地方?？墒牵矣謺悬c自戀式地安慰自己：做一件事情，不必過于在乎最終的結(jié)果，可貴的是過程中的收獲。以此語言來安撫我尚沒平復(fù)的心。感謝，衷心的感謝。在實訓(xùn)設(shè)計完成之際，衷心感謝我的老師周海巖老師對我的導(dǎo)和教誨。周老師開闊的思維、敏銳的洞察力以及詳細(xì)的修改意見給我大的啟發(fā)。金老師不僅專業(yè)學(xué)識淵博、治學(xué)嚴(yán)謹(jǐn)，待人平易近人；同時他對工作的積極熱情、對學(xué)生認(rèn)真負(fù)責(zé)、實事求是的態(tài)度，給我留下了深刻的印象，使我受益非淺。唯一的遺憾是我自己不夠主動，錯過了許多與您交流的機會。在此，我再次向周老師表示衷心的感謝和深深的敬意。 感謝我的母校給我們授課的各位尊敬的老師和計算機系培養(yǎng)我的領(lǐng)導(dǎo)與輔導(dǎo)老師