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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　課 程 設(shè) 計</b></p><p>　　題 目 學(xué)生搭配問題 </p><p>　　二Ｏ一Ｏ 年 十二 月 十五 日</p><p><b>　　學(xué)生搭配問題</b>&l

2、t;/p><p><b>　　設(shè)計題目</b></p><p>　　一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會. 男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴。請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:</p><p>　?。?）輸出每曲配對情況&l

3、t;/p><p>　?。?）計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值.</p><p><b>　　運行環(huán)境</b></p><p>　　本課題的程序設(shè)計和測試等環(huán)節(jié)都是在Windows7操作系統(tǒng)下完成，軟件的編譯測試環(huán)境為vc6.0 以c語言編寫的。軟件的硬件運行需求非常低，任何計算機都可運

4、行。</p><p><b>　　三、算法設(shè)計的思想</b></p><p>　　基本思路：隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表。</p><p>　　循環(huán)隊列是在隊列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素和

5、隊列尾元素的位置。</p><p>　　循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊，出隊，判隊滿，判隊空。</p><p>　?。?） 要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2。</p><p>　　（2） 將男生、女生兩組人分別存入這兩個隊列。以實現(xiàn)他們的循環(huán)配對輸出，這

6、是循環(huán)隊列固有的特性。</p><p>　　（3） 利用循環(huán)隊列的特性，將男女生分別進行入隊列和出隊列操作，且實現(xiàn)搭配輸出。</p><p>　　（4） 循環(huán)隊列的長度分別設(shè)為男女生的個數(shù)即可。</p><p>　?。?） 在計算機終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況 </p><p>　　關(guān)鍵問題: 循環(huán)隊列的應(yīng)用</p&

7、gt;<p>　　解決方法：數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。</p><p>　　存儲結(jié)構(gòu): 循環(huán)鏈表</p><p>　　核心算法: 循環(huán)隊列的入隊，出隊，判隊滿，判隊空。</p><p>　　輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)量</p><p>　　輸出數(shù)據(jù): 每

8、一首歌曲播放時，男生和女生搭配情況（只輸出編號即可）當(dāng)要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行性。 </p><p><b>　　四、算法的流程圖</b></p><p><b>　　五、算法設(shè)計分析</b></p><p>　　調(diào)試過程中出現(xiàn)的問題及解決方法：</p&

9、gt;<p>　　問題：在構(gòu)造隊列時，設(shè)隊列分配的最大空間為男女生的個數(shù)，此時便無法根據(jù)Q.front=Q.rear來判別隊列空間是“空”還是“滿”,因此，在入隊操作即插入一個新元素作為新的隊尾元素時出現(xiàn)了問題，即最后一位同學(xué)無法入隊。</p><p>　　解決方法：將隊列分配的最大空間至少再增加一個</p><p><b>　　六、源代碼</b><

10、;/p><p>　　#include <string.h></p><p>　　#include<stdio.h></p><p>　　#include <time.h></p><p>　　#include <malloc.h></p><p>　　#define MAXS

11、IZE 60</p><p>　　#define TRUE 1 </p><p>　　#define FALSE 0</p><p>　　#define OK 1</p><p>　　#define ERROR 0</p><p>　　#define OVERFLOW -1</p><p>　　

12、typedef int system;</p><p>　　typedef struct QNode{ </p><p><b>　　int num;</b></p><p>　　struct QNode *next;</p><p>　　}QNode,* QueuePtr;</p><p>　　

13、typedef struct{</p><p>　　QueuePtr front;</p><p>　　QueuePtr rear;</p><p>　　}LinkQueue;</p><p>　　void sleep( clock_t wait ) </p><p><b>　　{ </b>&l

14、t;/p><p>　　clock_t goal; </p><p>　　goal = wait + clock(); </p><p>　　while( goal > clock() ) ; </p><p><b>　　}</b></p><p>　　void InitQ(LinkQueue

15、&Q) </p><p><b>　　{</b></p><p>　　QueuePtr p; </p><p>　　p=(QueuePtr)malloc(sizeof(QNode));</p><p>　　Q.front=p;</p><p><b>　　Q.rear=p;<

16、;/b></p><p>　　Q.front->next=NULL;</p><p><b>　　}</b></p><p>　　void EnQueue(LinkQueue &Q,int num)</p><p><b>　　{</b></p><p>

17、　　QueuePtr p; </p><p>　　p=(QueuePtr)malloc(sizeof(QNode));</p><p>　　p->num=num;</p><p>　　p->next=NULL;</p><p>　　Q.rear->next=p;</p><p><b>　　

18、Q.rear=p;</b></p><p><b>　　}</b></p><p>　　void DeQueue(LinkQueue &Q, int &num)</p><p><b>　　{</b></p><p>　　QueuePtr p,q; </p>

19、<p>　　if(Q.front==Q.rear)</p><p>　　printf("隊列為空");</p><p>　　p=Q.front->next;</p><p>　　num=p->num;</p><p>　　Q.front->next=p->next;</p>

20、<p>　　q=p->next;</p><p>　　if(Q.rear==q)</p><p>　　Q.rear=Q.front;</p><p><b>　　free(p);</b></p><p><b>　　}</b></p><p>　　void

21、printF(LinkQueue &F,int i) </p><p><b>　　{</b></p><p>　　QueuePtr p; </p><p><b>　　int n=1;</b></p><p>　　while(n<i)</p><p><

22、b>　　{</b></p><p>　　printf("_ ");</p><p><b>　　n++; </b></p><p><b>　　}</b></p><p>　　p=F.front->next;</p><p>　　w

23、hile(F.rear!=p)</p><p><b>　　{ </b></p><p>　　printf("%d ",p->num);</p><p>　　p=p->next;}</p><p>　　printf("%d \n",p->num);</p&g

24、t;<p><b>　　}</b></p><p>　　void printM(LinkQueue &M,int i) </p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p><b>　　int n=1;</b>

25、;</p><p>　　while(n<i)</p><p><b>　　{</b></p><p>　　printf("_ ");</p><p><b>　　n++;</b></p><p><b>　　}</b></

26、p><p>　　p=M.front->next;</p><p>　　while(M.rear!=p)</p><p><b>　　{ </b></p><p>　　printf("%d ",p->num);</p><p>　　p=p->next;</p&

27、gt;<p><b>　　}</b></p><p>　　printf("%d \n",p->num);</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{ </b><

28、/p><p>　　int m,n,k,i,a,b;</p><p>　　int count=0,num;</p><p>　　QueuePtr p,q;</p><p>　　LinkQueue F;</p><p>　　LinkQueue M;</p><p>　　printf("請輸入

29、女生數(shù)量：");</p><p>　　scanf("%d",&m);</p><p>　　printf("請輸入男生數(shù)量：");</p><p>　　scanf("%d",&n);</p><p>　　printf("請輸曲子號：");&

30、lt;/p><p>　　scanf("%d",&k);</p><p>　　printf("請輸入要查找的男生編號：");</p><p>　　scanf("%d",&a);</p><p>　　printf("請輸入要查找的女生編號：");</

31、p><p>　　scanf("%d",&b);</p><p><b>　　InitQ(F);</b></p><p><b>　　InitQ(M);</b></p><p>　　for(i=1;i<=m;i++)</p><p><b&g

32、t;　　{</b></p><p>　　EnQueue(F,i);</p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　EnQueue(M,i);<

33、/p><p><b>　　}</b></p><p>　　for(i=1;i<=k;i++)</p><p><b>　　{</b></p><p>　　system("CLS"); </p><p>　　printf("第%d首曲子 \n&q

34、uot;,i);</p><p>　　printF(F,i);</p><p>　　printM(M,i);</p><p>　　p=F.front->next;</p><p>　　q=M.front->next;</p><p>　　printf("目前跳舞的是第%d號女生和第%d號男生\n&

35、quot;,p->num,q->num);</p><p>　　if(p->num==a&&q->num==b)</p><p><b>　　{</b></p><p><b>　　count++;</b></p><p>　　printf("第%d

36、曲是要查找的男女生跳舞\n",i);</p><p><b>　　}</b></p><p>　　sleep(3000);</p><p>　　DeQueue(F,num);</p><p>　　EnQueue(F,num);</p><p>　　DeQueue(M,num);</

37、p><p>　　EnQueue(M,num); </p><p><b>　　}</b></p><p>　　printf("該對男女生共跳舞%d次\n",count);</p><p><b>　　}</b></p><p><b>　　七、運行結(jié)

38、果分析</b></p><p><b>　　測試及運行結(jié)果：</b></p><p>　　測試輸入數(shù)據(jù)：男女生的個數(shù)曲子數(shù)和要查找的男女生編號</p><p>　　輸出結(jié)果為：每首曲子男女生搭配的情況</p><p><b>　　程序運行界面：</b></p><p&

39、gt;<b>　　八、收獲及體會</b></p><p>　　通過一周的學(xué)習(xí)和實踐，解決實際問題（學(xué)生搭配問題），讓我對循環(huán)隊列有了更深的了解，對數(shù)據(jù)結(jié)構(gòu)產(chǎn)生了濃厚的興趣，同時也讓我提高了解決實際問題的能力。</p><p>　　我們要不斷的通過上機來提高自己的學(xué)習(xí)水平，在上機的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關(guān)鍵算法，有了算法設(shè)計思