學(xué)生搭配問題

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

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

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

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

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

6、 QueuePtr p,q;if(Q.front=Q.rear)printf("隊(duì)列為空");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首曲子時(shí)女隊(duì)的情況void printF(LinkQueue &F,int i) /輸出第i首曲子時(shí)女隊(duì)的情況 QueuePtr p;int n=1; while(n<i) printf("_ ");n

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

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

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

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

11、進(jìn)一步理解?？傊?， 我學(xué)到了很多東西，很感謝學(xué)校給我們這樣一次鍛煉自我的機(jī)會，也很感謝老師的指導(dǎo)。9、參考文獻(xiàn)1徐孝凱編著。數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C+描述）。北京：清華大學(xué)出版社，19992嚴(yán)蔚敏主編。數(shù)據(jù)結(jié)構(gòu)題集（C語言版）。北京：清華大學(xué)出版社，20063孫巧萍主編。數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)教程。北京：科學(xué)出版社，200010、指導(dǎo)教師評語附件一：程序清單#include <string.h>#include<stdio.h>#include <time.h>#include <malloc.h>#define MAXSIZE 60#define TRU

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

13、nitQ(LinkQueue &Q) / 建立空隊(duì)列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)Qu

14、euePtr p,q;if(Q.front=Q.rear) printf(" 隊(duì)列為空");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 首曲子時(shí)女隊(duì)的情況QueuePtr p;int n=1;while(n<i)printf("_ ");n+;p=F.front->next;while

15、(F.rear!=p) printf("%d ",p->num);p=p->next;printf("%d n",p->num);void printM(LinkQueue &M,int i) / 打印第 i 首曲子時(shí)男隊(duì)的情況 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

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

17、tf(" 請輸入要查找的男生編號：");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->next;pr