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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　題 目: 學(xué)生搭配問(wèn)題 </p><p>　　學(xué) 院： </p><p>　　班 級(jí)： </p><p>　　學(xué)

2、生 姓 名： </p><p>　　學(xué) 生 學(xué) 號(hào)： </p><p>　　指 導(dǎo) 教 師： </p><p>　　2012 年 12 月 3 日</p><p><b>　　課程設(shè)計(jì)任務(wù)書</b>&l

3、t;/p><p><b>　　摘 要</b></p><p>　　針對(duì)學(xué)生搭配問(wèn)題，循環(huán)隊(duì)列是一種重要的鏈?zhǔn)浇Y(jié)構(gòu)，其特殊性在于需附設(shè)兩個(gè)指針front和rear分別指示對(duì)頭元素及隊(duì)尾元素的位置且對(duì)頭和隊(duì)尾相鄰接。在程序的設(shè)計(jì)過(guò)程中，運(yùn)用了各種基本的算法，有判斷隊(duì)空及隊(duì)滿，出隊(duì)，入隊(duì)等.循環(huán)隊(duì)列是在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的

4、元素外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。學(xué)生搭配問(wèn)題是典型的只有采用循環(huán)隊(duì)列才能解決的問(wèn)題，實(shí)驗(yàn)表明該算法的空間復(fù)雜度優(yōu)于其他算法。</p><p>　　本文用循環(huán)隊(duì)列會(huì)很好的把這個(gè)程序設(shè)計(jì)出來(lái)，會(huì)有很好的效果。得出的程序運(yùn)行結(jié)果能夠很形象的把結(jié)果表示出來(lái)。</p><p>　　關(guān)鍵詞：學(xué)生配對(duì)，數(shù)據(jù)結(jié)構(gòu)，循環(huán)隊(duì)列。 </p>&l

5、t;p><b>　　目錄</b></p><p><b>　　摘要I</b></p><p><b>　　1 設(shè)計(jì)題目1</b></p><p><b>　　2 運(yùn)行環(huán)境1</b></p><p>　　3 算法設(shè)計(jì)的思想1</p>

6、<p>　　4 算法的流程圖2</p><p>　　5 算法設(shè)計(jì)分析2</p><p><b>　　6 源代碼3</b></p><p>　　7 運(yùn)行結(jié)果分析8</p><p><b>　　8 收獲及體會(huì)8</b></p><p><b>　

7、　參考文獻(xiàn)9</b></p><p><b>　　致謝9</b></p><p><b>　　學(xué)生搭配問(wèn)題</b></p><p><b>　　1.設(shè)計(jì)題目</b></p><p>　　一班有m個(gè)女生,有n個(gè)男生(m不等于n),現(xiàn)要開一個(gè)舞會(huì). 男女生分別編號(hào)坐

8、在舞池的兩邊的椅子上.每曲開始時(shí),依次從男生和女生中各出一人配對(duì)跳舞, 本曲沒(méi)成功配對(duì)者坐著等待下一曲找舞伴。請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程,要求如下:</p><p>　?。?）輸出每曲配對(duì)情況</p><p>　?。?）計(jì)算出任何一個(gè)男生(編號(hào)為X)和任意女生(編號(hào)為Y),在第K曲配對(duì)跳舞的情況.至少求出K的兩個(gè)值。</p><p><b>　　

9、2.運(yùn)行環(huán)境</b></p><p>　　本課題的程序設(shè)計(jì)和測(cè)試等環(huán)節(jié)都是在Windows7操作系統(tǒng)下完成，軟件的編譯測(cè)試環(huán)境為vc6.0 以c語(yǔ)言編寫的。軟件的硬件運(yùn)行需求非常低，任何計(jì)算機(jī)都可運(yùn)行。</p><p><b>　　3.算法設(shè)計(jì)的思想</b></p><p>　　基本思路：隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而

10、在另一端進(jìn)行刪除的運(yùn)算受限的線性表。</p><p>　　循環(huán)隊(duì)列是在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。</p><p>　　循環(huán)隊(duì)列（兩個(gè)），將男生、女生兩組人分別存放，以實(shí)現(xiàn)循環(huán)配對(duì)輸出。循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。</p><p&g

11、t;　?。?） 要模擬動(dòng)態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個(gè)循環(huán)隊(duì)列SqQueue和SqQueue2。</p><p>　?。?） 將男生、女生兩組人分別存入這兩個(gè)隊(duì)列。以實(shí)現(xiàn)他們的循環(huán)配對(duì)輸出，這是循環(huán)隊(duì)列固有的特性。</p><p>　　（3） 利用循環(huán)隊(duì)列的特性，將男女生分別進(jìn)行入隊(duì)列和出隊(duì)列操作，且實(shí)現(xiàn)搭配輸出。</p><p>　　（4） 循環(huán)

12、隊(duì)列的長(zhǎng)度分別設(shè)為男女生的個(gè)數(shù)即可。</p><p>　?。?） 在計(jì)算機(jī)終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況 </p><p>　　關(guān)鍵問(wèn)題: 循環(huán)隊(duì)列的應(yīng)用</p><p>　　解決方法：數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 循環(huán)隊(duì)列（兩個(gè)），將男生、女生兩組人分別存放，以實(shí)現(xiàn)循環(huán)配對(duì)輸出。</p><p>　　存儲(chǔ)結(jié)構(gòu): 循環(huán)鏈表<

13、/p><p>　　核心算法: 循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。</p><p>　　輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)量</p><p>　　輸出數(shù)據(jù): 每一首歌曲播放時(shí)，男生和女生搭配情況（只輸出編號(hào)即可）當(dāng)要查找的男女搭配時(shí)輸出歌曲編號(hào)，和他們搭配的總次數(shù)。通過(guò)以上分析，該程序具有可行性。 </p><p><b>

14、;　　4.算法的流程圖</b></p><p><b>　　5.算法設(shè)計(jì)分析</b></p><p>　　調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法：</p><p>　　問(wèn)題：在構(gòu)造隊(duì)列時(shí)，設(shè)隊(duì)列分配的最大空間為男女生的個(gè)數(shù)，此時(shí)便無(wú)法根據(jù)Q.front=Q.rear來(lái)判別隊(duì)列空間是“空”還是“滿”,因此，在入隊(duì)操作即插入一個(gè)新元素作為新的隊(duì)

15、尾元素時(shí)出現(xiàn)了問(wèn)題，即最后一位同學(xué)無(wú)法入隊(duì)。</p><p>　　解決方法：將隊(duì)列分配的最大空間至少再增加一個(gè)</p><p><b>　　6.源代碼</b></p><p>　　#include <string.h></p><p>　　#include<stdio.h></p>

16、<p>　　#include <time.h></p><p>　　#include <malloc.h></p><p>　　#define MAXSIZE 60</p><p>　　#define TRUE 1 </p><p>　　#define FALSE 0</p><p>

17、　　#define OK 1</p><p>　　#define ERROR 0</p><p>　　#define OVERFLOW -1</p><p>　　//typedef int system;</p><p>　　typedef struct QNode{ </p><p><b>　　int n

18、um;</b></p><p>　　struct QNode *next;</p><p>　　}QNode,* QueuePtr;</p><p>　　typedef struct{</p><p>　　QueuePtr front;</p><p>　　QueuePtr rear;</p>

19、<p>　　}LinkQueue;</p><p>　　void sleep( clock_t wait ) </p><p><b>　　{ </b></p><p>　　clock_t goal; </p><p>　　goal = wait + clock(); </p><p>

20、;　　while( goal > clock() ) ; </p><p><b>　　}</b></p><p>　　void InitQ(LinkQueue &Q) </p><p><b>　　{</b></p><p>　　QueuePtr p; </p><

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

22、><p>　　void EnQueue(LinkQueue &Q,int num)</p><p><b>　　{</b></p><p>　　QueuePtr p; </p><p>　　p=(QueuePtr)malloc(sizeof(QNode));</p><p>　　p->n

23、um=num;</p><p>　　p->next=NULL;</p><p>　　Q.rear->next=p;</p><p><b>　　Q.rear=p;</b></p><p><b>　　}</b></p><p>　　void DeQueue(Lin

24、kQueue &Q, int &num)</p><p><b>　　{</b></p><p>　　QueuePtr p,q; </p><p>　　if(Q.front==Q.rear)</p><p>　　printf("隊(duì)列為空");</p><p>　

25、　p=Q.front->next;</p><p>　　num=p->num;</p><p>　　Q.front->next=p->next;</p><p>　　q=p->next;</p><p>　　if(Q.rear==q)</p><p>　　Q.rear=Q.front;&l

26、t;/p><p><b>　　free(p);</b></p><p><b>　　}</b></p><p>　　void printF(LinkQueue &F,int i) </p><p><b>　　{</b></p><p>　　Queu

27、ePtr p; </p><p><b>　　int n=1;</b></p><p>　　while(n<i)</p><p><b>　　{</b></p><p>　　printf("_ ");</p><p><b>　　n++;

28、</b></p><p><b>　　}</b></p><p>　　p=F.front->next;</p><p>　　while(F.rear!=p)</p><p><b>　　{ </b></p><p>　　printf("%d &qu

29、ot;,p->num);</p><p>　　p=p->next;}</p><p>　　printf("%d \n",p->num);</p><p><b>　　}</b></p><p>　　void printM(LinkQueue &M,int i) </p&

30、gt;<p><b>　　{</b></p><p>　　QueuePtr p;</p><p><b>　　int n=1;</b></p><p>　　while(n<i)</p><p><b>　　{</b></p><p>

31、　　printf("_ ");</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　p=M.front->next;</p><p>　　while(M.rear!=p)</p><p><

32、b>　　{ </b></p><p>　　printf("%d ",p->num);</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　printf("%d \n",p->num);</p

33、><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{ </b></p><p>　　int m,n,k,i,a,b;</p><p>　　int count=0,num;</p><p>　　Queue

34、Ptr p,q;</p><p>　　LinkQueue F;</p><p>　　LinkQueue M;</p><p>　　printf("請(qǐng)輸入女生數(shù)量：");</p><p>　　scanf("%d",&m);</p><p>　　printf("請(qǐng)

35、輸入男生數(shù)量：");</p><p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸曲子號(hào)：");</p><p>　　scanf("%d",&k);</p><p>　　printf("請(qǐng)輸入要查找的男生編號(hào)：&qu

36、ot;);</p><p>　　scanf("%d",&a);</p><p>　　printf("請(qǐng)輸入要查找的女生編號(hào)：");</p><p>　　scanf("%d",&b);</p><p><b>　　InitQ(F);</b><

37、/p><p><b>　　InitQ(M);</b></p><p>　　for(i=1;i<=m;i++)</p><p><b>　　{</b></p><p>　　EnQueue(F,i);</p><p><b>　　}</b></p&g

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

39、;<b>　　{</b></p><p>　　system("CLS"); </p><p>　　printf("第%d首曲子 \n",i);</p><p>　　printF(F,i);</p><p>　　printM(M,i);</p><p>　　p

40、=F.front->next;</p><p>　　q=M.front->next;</p><p>　　printf("目前跳舞的是第%d號(hào)女生和第%d號(hào)男生\n",p->num,q->num);</p><p>　　if(p->num==a&&q->num==b)</p>&l

41、t;p><b>　　{</b></p><p><b>　　count++;</b></p><p>　　printf("第%d曲是要查找的男女生跳舞\n",i);</p><p><b>　　}</b></p><p>　　sleep(3000);&

42、lt;/p><p>　　DeQueue(F,num);</p><p>　　EnQueue(F,num);</p><p>　　DeQueue(M,num);</p><p>　　EnQueue(M,num); </p><p><b>　　}</b></p><p>　　pr

43、intf("該對(duì)男女生共跳舞%d次\n",count);</p><p>　　system("PAUSE");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　7.運(yùn)行結(jié)果分

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

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

46、程圖，并用C語(yǔ)言描繪出關(guān)鍵算法。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏 吳偉明 編著，清華大學(xué)出版社</p><p>　　[2] C語(yǔ)言程序設(shè)計(jì)（第三版）譚浩強(qiáng) 著，清華大學(xué)出版社</p><p><b>　　致謝</b></p&

47、gt;<p>　　首先，我要感謝學(xué)校給我們提供了此次課程設(shè)計(jì)的機(jī)會(huì)，能讓同學(xué)們?cè)谝黄饘W(xué)習(xí)與研究，讓我們有機(jī)會(huì)對(duì)所學(xué)的理論知識(shí)進(jìn)行實(shí)踐。</p><p>　　其次，我還要特別感謝我的輔導(dǎo)老師張?zhí)l(fā)老師，在他的精心輔導(dǎo)和幫助下，我的設(shè)計(jì)才得以順利完成，并使所學(xué)知識(shí)得以真正的應(yīng)用。對(duì)他為我的設(shè)計(jì)所提出的寶貴意見表示忠心的感謝！</p><p>　　最后，在設(shè)計(jì)過(guò)程中，也得到了許多同