數據結構課程設計-學生搭配問題

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

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

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

4、其他算法。 本文用循環(huán)隊列會很好的把這個程序設計出來， 會有很好的效果。 得出的程 序運行結果能夠很形象的把結果表示出來。關鍵詞：學生配對，數據結構，循環(huán)隊列。摘要 1 設計題目 目錄錯誤! 未定義書簽錯誤! 未定義書簽2 運行環(huán)境 13 算法設計的思想 14 算法的流程圖 25 算法設計分析 26 源代碼 37 運行結果分析 88 收獲及體會 8參考文獻 9致謝 9學生搭配問題1. 設計題目一班有m個女生,有n個男生（m不等于n）,現(xiàn)要開一個舞會.男女生分別編 號坐在舞池的兩邊的椅子上 . 每曲開始時 , 依次從男生和女生中各出一人配對跳 舞, 本曲沒成功配對者坐著等待下一曲找舞伴。 請設計

5、一系統(tǒng)模擬動態(tài)地顯示出 上述過程,要求如下:（1）輸出每曲配對情況（2）計算出任何一個男生（編號為X）和任意女生（編號為丫），在第K曲配對跳 舞的情況.至少求出K的兩個值。2. 運行環(huán)境本課題的程序設計和測試等環(huán)節(jié)都是在 Win dows7操作系統(tǒng)下完成，軟件的 編譯測試環(huán)境為 vc6.0 以 c 語言編寫的。軟件的硬件運行需求非常低，任何計 算機都可運行。3. 算法設計的思想基本思路：隊列（Queue是只允許在一端進行插入，而在另一端進行刪除 的運算受限的線性表。循環(huán)隊列是在隊列的順序存儲結構中， 除了用乙組地址連續(xù)的存儲單元依次 存放從隊列頭到隊列尾的元素外，尚需附設兩個指針 front

6、和 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)隊列的長度分別設為男女生的個數即可。（5）在計算機終端輸出的結果是：根據要求輸出男生女生搭配情況 關鍵問題 : 循環(huán)隊列的應用解決方法：數據模型

7、（邏輯結構） : 循環(huán)隊列（兩個），將男生、女生兩組 人分別存放，以實現(xiàn)循環(huán)配對輸出。存儲結構 : 循環(huán)鏈表核心算法：循環(huán)隊列的入隊，出隊，判隊滿，判隊空。輸入數據：男生人數、女生人數，歌曲數量輸出數據：每一首歌曲播放時，男生和女生搭配情況（只輸出編號即可）當 要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數。通過以上分析，該程序具有可行性。4. 算法的流程圖5. 算法設計分析調試過程中出現(xiàn)的問題及解決方法：問題：在構造隊列時，設隊列分配的最大空間為男女生的個數， 此時便無法 根據Q.front=Q.rear來判別隊列空間是“空”還是“滿”,因此，在入隊操作即 插入一個新元素作為新的隊尾元素

8、時出現(xiàn)了問題，即最后一位同學無法入隊。解決方法：將隊列分配的最大空間至少再增加一個6. 源代碼 #include <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; st

9、ruct QNode *next; QNode,* QueuePtr; typedef struct QueuePtr front; QueuePtr 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;

10、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;if(Q.front=Q.rear)printf(" 隊列為空 "); p=Q.front->next;num=p->num;Q.front->next=p->n

11、ext;q=p->next;if(Q.rear=q)Q.rear=Q.front;free(p);void printF(LinkQueue &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)Que

12、uePtr 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",p->num);int main()int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F;LinkQueue M;printf(" 請輸入女生數量： "); scanf("%d&qu

13、ot;,&m);printf(" 請輸入男生數量： ");scanf("%d",&n);printf(" 請輸曲子號： ");scanf("%d",&k);printf(" 請輸入要查找的男生編號： ");scanf("%d",&a);printf(" 請輸入要查找的女生編號： ");scanf("%d",&b);InitQ(F);InitQ(M);for(i=1;i<=m;i+)EnQue

14、ue(F,i);for(i=1;i<=n;i+)EnQueue(M,i); for(i=1;i<=k;i+)system("CLS");prin tf(" 第4 首曲子 n",i); printF(F,i);printM(M,i);p=F.front->next;q=M.front->next;printf("目前跳舞的是第d號女生和第c號男生n",p->num,q->num);if(p->num=a&&q->num=b)count+;printf("第4曲是要

15、查找的男女生跳舞n",i);sleep(3000);DeQueue(F,num);EnQueue(F,num);DeQueue(M,num);EnQueue(M,num);printf("該對男女生共跳舞d次n",count);system("PAUSE");return 0;7. 運行結果分析測試及運行結果測試輸入數據：男女生的個數曲子數和要查找的男女生編號 輸出結果為：每首曲子男女生搭配的情況程序運行界面：C; DocuBeBts and Sett ingsX&dBin 1 st ratoiXMQTC-i-rDebugCppI

16、71; exeofrorDECS生生男女 量量k的 菱：養(yǎng) 主主£& -m 了要冇竭男生2 3 4 5 62 3 4 5前ft舞拘是穿1呂女生和第丄號男生245612 自 4 5 13 4 5 6 1 2 4512g黔澎量備;號女生和售4號男生S 6 1 2 45 12 3 4尋摯界勺是寰號女生幣誦帝號男生S 1 2 3 4 5L 2 3 4 5屠曙醪是篥6專女生和第丄號男生1 2 3 4 5 A2 3 4 5 1SW舞旳是第i弓女比和第2號男生 該動男女掘共趾舞0次Press &nj keu to continuem 5目胃廻沸旳罡算琦女主和弟3號男生 躬首曲子4 5 6 12 38. 收獲及體會通過一周的學習和實踐，解決實際問題（學生搭配問題），讓我對循環(huán)隊列 有了更深的了解，對數據結構產生了濃厚的興趣，同時也讓我提高了解決實際問 題的能力。我們要不斷的通過上機來提高自己的學習水平， 在上機的同時改正了自己對 某些算法的錯誤使用，使自己在通過程序解決問題時抓住關鍵算法， 有了算法設 計思想和流程圖，并用C語言描繪出關鍵算法。參考文獻1 數據結構（ C 語言版）嚴蔚敏 吳偉明 編著，清華大學出版社2 C 語言程序設計（第三版）譚浩強 著，清華大學出版社致謝首先，我要感謝學校給我們提供了此次課程設計的機會， 能讓同學們在