數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)生搭配問題

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目: 學(xué)生搭配問題 學(xué) 院： 班 級： 學(xué) 生 姓 名： 學(xué) 生 學(xué) 號： 指 導(dǎo) 教 師： 2012 年 12 月 3 日課程設(shè)計(jì)任務(wù)書姓名班級學(xué)號設(shè)計(jì)題目學(xué)生搭配問題理論要點(diǎn) 隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。循環(huán)隊(duì)列是在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。設(shè)計(jì)目標(biāo)（1）輸出每曲配對情況。（2）計(jì)算出任何一個(gè)男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情

2、況.至少求出K的兩個(gè)值。研究方法步驟（1）先建立兩個(gè)循環(huán)隊(duì)列SqQueue和SqQueue2。（2）將男生、女生兩組人分別存入這兩個(gè)隊(duì)列。 （3）將男女生分別進(jìn)行入隊(duì)列和出隊(duì)列操作，且實(shí)現(xiàn)搭配輸出。（4）循環(huán)隊(duì)列的長度分別設(shè)為男女生的個(gè)數(shù)即可。（5）在計(jì)算機(jī)終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況。預(yù)期結(jié)果每一首歌曲播放時(shí)，男生和女生搭配情況（只輸出編號即可）當(dāng)要查找的男女搭配時(shí)輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行。計(jì)劃與進(jìn)步的安排1、2012年11月20日之前尋找到解決問題思搭配問題的路2、2012年11月25日之前必須編寫出程序3、2012年11月26日之前

3、檢查程序的運(yùn)行并找出錯(cuò)誤程序4、2012年11月29日之前找到解決錯(cuò)誤的方法5、2012年11月30日寫數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告摘 要 針對學(xué)生搭配問題，循環(huán)隊(duì)列是一種重要的鏈?zhǔn)浇Y(jié)構(gòu)，其特殊性在于需附設(shè)兩個(gè)指針front和rear分別指示對頭元素及隊(duì)尾元素的位置且對頭和隊(duì)尾相鄰接。在程序的設(shè)計(jì)過程中，運(yùn)用了各種基本的算法，有判斷隊(duì)空及隊(duì)滿，出隊(duì)，入隊(duì)等.循環(huán)隊(duì)列是在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。學(xué)生搭配問題是典型的只有采用循環(huán)隊(duì)列才能解決的問題，實(shí)驗(yàn)表明該算法的空間復(fù)雜度

4、優(yōu)于其他算法。本文用循環(huán)隊(duì)列會很好的把這個(gè)程序設(shè)計(jì)出來，會有很好的效果。得出的程序運(yùn)行結(jié)果能夠很形象的把結(jié)果表示出來。關(guān)鍵詞：學(xué)生配對，數(shù)據(jù)結(jié)構(gòu)，循環(huán)隊(duì)列。 目錄摘要I1 設(shè)計(jì)題目12 運(yùn)行環(huán)境13 算法設(shè)計(jì)的思想14 算法的流程圖25 算法設(shè)計(jì)分析26 源代碼37 運(yùn)行結(jié)果分析88 收獲及體會8參考文獻(xiàn)9致謝9學(xué)生搭配問題1.設(shè)計(jì)題目一班有m個(gè)女生,有n個(gè)男生(m不等于n),現(xiàn)要開一個(gè)舞會. 男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時(shí),依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴。請?jiān)O(shè)計(jì)一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:（1）輸出每曲配對情況（2）

5、計(jì)算出任何一個(gè)男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個(gè)值。2.運(yùn)行環(huán)境本課題的程序設(shè)計(jì)和測試等環(huán)節(jié)都是在Windows7操作系統(tǒng)下完成，軟件的編譯測試環(huán)境為vc6.0 以c語言編寫的。軟件的硬件運(yùn)行需求非常低，任何計(jì)算機(jī)都可運(yùn)行。3.算法設(shè)計(jì)的思想 基本思路：隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。 循環(huán)隊(duì)列是在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。循環(huán)隊(duì)列（兩個(gè)），將男生、女生兩組人分別存放，以

6、實(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ī)終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況 關(guān)鍵問題: 循環(huán)隊(duì)列的應(yīng)用 解決方法：數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 循環(huán)隊(duì)列（兩個(gè)），將男生、女生兩組人分別存放，以實(shí)現(xiàn)循環(huán)配對輸出。存儲結(jié)構(gòu): 循環(huán)鏈表

7、核心算法: 循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。 輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)量 輸出數(shù)據(jù): 每一首歌曲播放時(shí)，男生和女生搭配情況（只輸出編號即可）當(dāng)要查找的男女搭配時(shí)輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行性。 4.算法的流程圖5.算法設(shè)計(jì)分析 調(diào)試過程中出現(xiàn)的問題及解決方法：問題：在構(gòu)造隊(duì)列時(shí)，設(shè)隊(duì)列分配的最大空間為男女生的個(gè)數(shù)，此時(shí)便無法根據(jù)Q.front=Q.rear來判別隊(duì)列空間是“空”還是“滿”,因此，在入隊(duì)操作即插入一個(gè)新元素作為新的隊(duì)尾元素時(shí)出現(xiàn)了問題，即最后一位同學(xué)無法入隊(duì)。解決方法：將隊(duì)列分配的最大空間至少再增加一個(gè)6.源代碼#includ

8、e <string.h>#include<stdio.h>#include <time.h>#include <malloc.h>#define MAXSIZE 60#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1/typedef int system;typedef struct QNode int num;struct QNode *next;QNode,* QueuePtr;typedef structQueuePtr front;Que

9、uePtr rear;LinkQueue;void sleep( clock_t wait ) clock_t goal; goal = wait + clock(); while( goal > clock() ) ; void InitQ(LinkQueue &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(si

10、zeof(QNode);p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;void DeQueue(LinkQueue &Q, int &num)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);void printF(LinkQueue

11、 &F,int i) QueuePtr p; int n=1;while(n<i)printf("_ ");n+; p=F.front->next;while(F.rear!=p) printf("%d ",p->num);p=p->next;printf("%d n",p->num);void printM(LinkQueue &M,int i) QueuePtr p;int n=1;while(n<i)printf("_ ");n+;p=M.front->

12、;next;while(M.rear!=p) printf("%d ",p->num);p=p->next;printf("%d n",p->num);int 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)

13、;printf("請輸曲子號：");scanf("%d",&k);printf("請輸入要查找的男生編號：");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&q

14、uot;); printf("第%d首曲子 n",i);printF(F,i);printM(M,i);p=F.front->next;q=M.front->next;printf("目前跳舞的是第%d號女生和第%d號男生n",p->num,q->num);if(p->num=a&&q->num=b)count+; printf("第%d曲是要查找的男女生跳舞n",i);sleep(3000);DeQueue(F,num); EnQueue(F,num);DeQueue(M,num)

15、;EnQueue(M,num); printf("該對男女生共跳舞%d次n",count);system("PAUSE");return 0;7.運(yùn)行結(jié)果分析 測試及運(yùn)行結(jié)果 測試輸入數(shù)據(jù)：男女生的個(gè)數(shù)曲子數(shù)和要查找的男女生編號 輸出結(jié)果為：每首曲子男女生搭配的情況 程序運(yùn)行界面：8.收獲及體會通過一周的學(xué)習(xí)和實(shí)踐，解決實(shí)際問題（學(xué)生搭配問題），讓我對循環(huán)隊(duì)列有了更深的了解，對數(shù)據(jù)結(jié)構(gòu)產(chǎn)生了濃厚的興趣，同時(shí)也讓我提高了解決實(shí)際問題的能力。我們要不斷的通過上機(jī)來提高自己的學(xué)習(xí)水平，在上機(jī)的同時(shí)改正了自己對某些算法的錯(cuò)誤使用，使自己在通過程序解決問題時(shí)抓住關(guān)鍵算法，有了算法設(shè)計(jì)思想和流程圖，并用C語言描繪出關(guān)鍵算法。參考文獻(xiàn)1 數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏 吳偉明 編著，清華大學(xué)出版社2 C語言程序設(shè)計(jì)（第三版）譚浩強(qiáng) 著，清華大學(xué)出版社 致謝首先，我要感謝學(xué)校給我們提供了此次課程設(shè)計(jì)的機(jī)會，能讓同學(xué)們在一起學(xué)習(xí)與研究，讓我們有機(jī)會對所學(xué)的理論知識進(jìn)行實(shí)踐