學生搭配問題

1、2008/2009學年度第二學期數(shù)據(jù)結(jié)構(gòu)課程設計說明書題 目:學生搭配問題班 級：姓 名：學 號：指導教師：日 期：2009/ 06/ 22-2009/06/26計算機與信息工程系1問題描述一班有m個女生，有n個男生（m不等于n）,現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的 椅子上每曲開始時，依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程，要求如下：1）輸出每曲配對情況2）計算出任何一個男生（編號為X）和任意女生（編號為Y）,在第K曲配對跳舞的情況至少求出 K的兩個值。2、需求分析核心問題：循環(huán)隊列的應用數(shù)據(jù)模型（邏輯結(jié)構(gòu)）：循

2、環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對 輸出。存儲結(jié)構(gòu)：循環(huán)鏈表核心算法：循環(huán)隊列的入隊，出隊，判隊滿，判隊空。輸入數(shù)據(jù)：男生人數(shù)、女生人數(shù)，歌曲數(shù)量輸出數(shù)據(jù)：每一首歌曲播放時，男生和女生搭配情況（只輸出編號即可）當要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行性。3、開發(fā)環(huán)境硬件開發(fā)環(huán)境：PC機。軟件開發(fā)環(huán)境：（1）操作系統(tǒng)環(huán)境：Window2000。（2）軟件開發(fā)工具：Visual C+ 6.0。4、算法設計思想隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表。循環(huán)隊列是在隊列的順序存儲結(jié)構(gòu)中，除了用乙組地

3、址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設兩個指針front和rear分別指示隊列頭元素和隊列尾元素的位置。循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊， 出隊，判隊滿，判隊空。（1）要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2。（2）將男生、女生兩組人分別存入這兩個隊列。以實現(xiàn)他們的循環(huán)配對輸出，這是循環(huán)隊列 固有的特性。（3）利用循環(huán)隊列的特性，將男女生分別進行入隊列和出隊列操作，且實現(xiàn)搭配輸出。（4）循環(huán)隊列的長度分別設為男女生的個數(shù)即可。（5）在計算機終端輸出的結(jié)果是：根據(jù)要求輸出男

4、生女生搭配情況。5、流程圖圖一程序流程圖6、課程設計過程中的關(guān)鍵算法建立兩個鏈式循環(huán)隊列來分別存儲男生和女生,然后調(diào)用入隊出隊函數(shù)實現(xiàn)循環(huán)隊列的配對輸出。為充分利用向量空間，克服上述假上溢現(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，存儲在其中成為循環(huán)隊列。在循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1朝前移動。只不過當頭尾指針指向向量上界時、其加1操作是指向向量的下界。 這樣就可以通過出隊再入隊來實現(xiàn)男生女生的循環(huán)搭配。課程設計過程中的關(guān)鍵算法如下：(1)關(guān)鍵算法之一：初始化隊列void lnitQ(LinkQueue &Q)QueuePtr p;p=(QueuePtr)mal

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

6、Q.rear)printf("隊列為空");p=Q.front->next;num=p->num;Q.front->next=p->next;q=p->next;if(Q.rear=q)Q.rear=Q.front;free(p);(4)關(guān)鍵算法之四：輸出第 i首曲子時女隊的情況void printF(LinkQueue &F,int i) /輸出第i首曲子時女隊的情況QueuePtr p;int n=1;while(nvi)printf("_ ");n+;p=F.front->next; while(F.re

7、ar!=p) printf("%d ",p->num); p=p->next; printf("%d n",p->num);7、測試及結(jié)果測試輸入數(shù)據(jù)：男女生的個數(shù)曲子數(shù)和要查找的男女生編號輸出結(jié)果為：每首曲子男女生搭配的情況程序運行界面如下:8、總結(jié)與收獲通過一周的學習和實踐，解決實際問題（學生搭配問題），讓我對循環(huán)隊列有了更深的了解，對數(shù)據(jù)結(jié)構(gòu)產(chǎn)生了濃厚的興趣，同時也讓我提高了解決實際問題的能力。我們要不斷的通過上機來提高自己的學習水平，在上機的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關(guān)鍵算法，有了算法設計

8、思想和流程圖， 并用c語言描繪出關(guān)鍵算法。以前我對數(shù)據(jù)結(jié)構(gòu)（c語言描述）的一些標準庫函數(shù)不太了解，還有對函數(shù)調(diào)用的正確使用不 夠熟悉，還有對C語言中經(jīng)常出現(xiàn)的錯誤也不了解，通過實踐，使我在這幾個方面的認識有所提高。讓自己有一定的能力去改正一些常見的錯誤語法，很高興這一周的學習讓我對數(shù)據(jù)結(jié)構(gòu)（C語言描述）有了新的認識，所以后在學習過程中，我會更加注視實踐操作，使自己便好地學好計算機。在這次課程設計的實驗中，我收獲了許多知識，通過查找大量資料，請教老師，以及不懈的努 力，也培養(yǎng)了獨立思考、動手操作的能力。我也學會了許多學習和解決實際問題的方法，讓我受益 匪淺。時間的緊缺成為一個很大的問題。也希望老

9、師可以為我們知道一下以后的發(fā)展方向。如果可 以讓每個人都有動手焊接以及參與其他的各個流程，有專門的知道就更好了。課程設計對我來說， 趣味性強，不僅鍛煉能力，而且可以學到很多東西，在與老師和同學的交流過程中，互動學習，將 知識融會貫通，也增強了我和同學之間的團隊合作的能力。讓我們知道只要努力，集中精力解決問 題，一定會有收獲的，過程也是很重要的。在這次課程設計中我們要學會利用時間，在規(guī)定的時間內(nèi)完成我們的任務，要逐漸養(yǎng)成用C語言編寫程序的良好習慣。這些對我來說都是一種鍛煉，一個知識積累的過程，一種能力的提高。 要打好基礎(chǔ)，才能用更好的辦法，更簡潔明了的程序解決實際問題，只有這樣才能進一步的取得更

10、 好的成績。我們會更加努力，努力的去彌補自己的缺點，發(fā)展自己的優(yōu)點，去充實自己，只有在了 解了自己的長短之后，我們會更加珍惜擁有的，更加努力的去完善它，增進它。雖然我現(xiàn)在的水平還很差，但我還會繼續(xù)努力的，在解決實際問題時如果遇到了難題，我們要 學會去查找大量的有關(guān)這方面的資料，還要借助于網(wǎng)絡不斷擴大自己的知識面和閱讀量。這樣也可以鍛煉我們的自主學習能力和解決問題的能力，學到了許多以前沒學到的東西。在課程設計中的程序都比較復雜，所以需要我們要更加地細心，認真的完成每一步的操作，修 改語法，按照老師的指導思想來完成。與此同時也讓我們增加了對程序和算法進一步理解?？傊?我學到了很多東西，很感謝學校

11、給我們這樣一次鍛煉自我的機會，也很感謝老師的指導。9、參考文獻1 徐孝凱編著。數(shù)據(jù)結(jié)構(gòu)實用教程（C/C+描述）。北京：清華大學出版社，19992 嚴蔚敏主編。數(shù)據(jù)結(jié)構(gòu)題集（C語言版）。北京：清華大學出版社，20063 孫巧萍主編。數(shù)據(jù)結(jié)構(gòu)實訓教程。北京：科學出版社，200010、指導教師評語附件一：程序清單#include <string.h>#include<stdio.h>#include <time.h>#include <malloc.h>#define MAXSIZE 60#define TRUE 1#define FALSE 0#de

12、fine OK 1#define ERROR 0#define OVERFLOW -1 typedef int system;typedef struct QNodeint num;struct QNode *next;QNode,* QueuePtr; typedef struct QueuePtr front;QueuePtr rear;LinkQueue;void sleep( clock_t wait ) / 延遲函數(shù) clock_t goal; goal = wait + clock(); while( goal > clock();void InitQ(LinkQueue &

13、amp;Q) / 建立空隊列QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); Q.front=p;Q.rear=p;Q.front->next=NULL;void EnQueue(LinkQueue &Q,int num)QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;void DeQueue(LinkQueue &Q, int &num)QueuePtr p,q;

14、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=Q.front;free(p);void printF(LinkQueue &F,int i) / 打印第 i 首曲子時女隊的情況 QueuePtr p;int n=1;while(n<i)printf("_ ");n+;p=F.front->next;while(F.rear

15、!=p)printf("%d ",p->num); p=p->next; printf("%d n",p->num);void printM(LinkQueue &M,int i) / 打印第 i 首曲子時男隊的情況 QueuePtr p;int n=1;while(n<i)printf("_ "); n+;p=M.front->next;while(M.rear!=p)printf("%d ",p->num);p=p->next;printf("%d n

16、",p->num);void main()int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F; / 女生隊LinkQueue M; / 男生隊printf(" 請輸入女生數(shù)量： ");scanf("%d",&m);printf(" 請輸入男生數(shù)量： ");scanf("%d",&n);printf(" 請輸曲子號： ");scanf("%d",&k);printf("

17、; 請輸入要查找的男生編號： ");scanf("%d",&a);printf(" 請輸入要查找的女生編號： ");scanf("%d",&b);InitQ(F);InitQ(M);for(i=1;i<=m;i+)EnQueue(F,i);for(i=1;i<=n;i+)EnQueue(M,i); for(i=1;i<=k;i+)system("CLS");printf(" 第 %d 首曲子 n",i);printF(F,i);printM(M,i);p=F.front->next;q=M.front-