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

1、 數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 說 明 書   學(xué)生姓名:  學(xué) 號(hào)：1021010309 學(xué) 院:軟件學(xué)院專 業(yè):軟件工程 題 目:學(xué)生搭配問題指導(dǎo)教師     2011年12月20日1. 設(shè)計(jì)任務(wù)概述一班有m個(gè)女生,有n個(gè)男生(m不等于n),現(xiàn)要開一個(gè)舞會(huì). 男女生分別編號(hào)坐在舞池的兩邊的椅子上.每曲開始時(shí),依次從男生和女生中各出一人配對(duì)跳舞,本曲沒成功配對(duì)者坐著等待下一曲找舞伴。實(shí)現(xiàn)功能：1)輸出每曲配對(duì)情況；。主函數(shù)第K曲配對(duì)每曲配對(duì)數(shù)據(jù)輸入輸出編號(hào)圖1.1 系統(tǒng)總體框圖2. 本設(shè)計(jì)所采

2、用的數(shù)據(jù)結(jié)構(gòu) 采用隊(duì)列（Queue）這一數(shù)據(jù)結(jié)構(gòu)，隊(duì)列是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。循環(huán)隊(duì)列是在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素外，尚需附設(shè)兩個(gè)指針 front 和 rear 分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。 3. 功能模塊詳細(xì)設(shè)計(jì)用循環(huán)隊(duì)列（兩個(gè)），將男生、女生兩組人分別存放，以實(shí)現(xiàn)循環(huán)配對(duì)輸出。循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。運(yùn)用循環(huán)隊(duì)列的基本操作順利的解決學(xué)生舞曲搭配問題，主要利用用循環(huán)隊(duì)列的環(huán)狀結(jié)構(gòu)，循環(huán)地執(zhí)行出列入列操作并在出隊(duì)列時(shí)進(jìn)行配對(duì)并輸出配對(duì)情況，而整個(gè)過程不需要移動(dòng)元素使程序在空間復(fù)

3、雜度上降到最小，采用指針的移動(dòng)大大加快了程序的執(zhí)行效率。并且對(duì)輸入進(jìn)行了改進(jìn)，以防止用戶隨意輸入時(shí)出現(xiàn)的各種意想不到的錯(cuò)誤。3.1 詳細(xì)設(shè)計(jì)思想（1）要模擬動(dòng)態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個(gè)循環(huán) 隊(duì)列 SqQueue1 和 SqQueue2。（2）將男生、女生兩組人分別存入這兩個(gè)隊(duì)列。以實(shí)現(xiàn)他們的循環(huán)配對(duì)輸出，這是循環(huán)隊(duì)列固有的特性。 （3）利用循環(huán)隊(duì)列的特性，將男女生分別進(jìn)行入隊(duì)列和出隊(duì)列操作，且實(shí)現(xiàn)搭配輸出。（4）循環(huán)隊(duì)列的長度分別設(shè)為男女生的個(gè)數(shù)即可。 （5）存儲(chǔ)結(jié)構(gòu): 循環(huán)鏈表； 核心算法: 循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判隊(duì)滿，判隊(duì)空。 輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)

4、量 輸出數(shù)據(jù): 每一首歌曲播放時(shí)，男生和女生搭配情況（只輸出編號(hào) 即可） 當(dāng)要查找的男女搭配時(shí)輸出歌曲編號(hào)， 和他們搭配的總次數(shù)。3.2 核心代碼 Status EnQueue (SqQueue *Q,QElemType e,int num) /* 入隊(duì)列，插入元素e為Q的新的隊(duì)尾元素 */ if(Q->rear+1)%(num+1) = Q->front) return ERROR; /* 隊(duì)列滿 */ Q->dataQ->rear = e; Q->rear = (Q->rear+1)%(num+1); return OK; /* EnQueue */ S

5、tatus DeQueue(SqQueue *Q,QElemType *e,int num)/* 若隊(duì)列不空，則刪除Q的對(duì)頭元素，用e返回其值，并返回OK/,否則返回ERROR */ if(Q->front=Q->rear) return ERROR; *e=Q->dataQ->front; Q->front=(Q->front+1)%(num+1); return OK; /* DeQueue */ Status bianhao(SqQueue *boys,SqQueue *girls) /* 隊(duì)列初始化及對(duì)男女生進(jìn)行編號(hào) */ int i; InitQu

6、eue(boys,boynum); for(i=1; i<=boynum; i+) if(EnQueue(boys,i,boynum)=ERROR) return ERROR; InitQueue(girls,girlnum); for(i=1; i<=girlnum; i+) if(EnQueue(girls,i,girlnum)=ERROR) return ERROR; return OK; /* peidui */ Status judge() /* 判斷輸入每位是否滿足（'0'-'9'）并且轉(zhuǎn)換為數(shù)字 */ int i,j=0,k=0,s=0

7、,h=0; char a60; gets(a); for(i=0;ai!='0'i+) /* 記錄最后一個(gè)非空格字符的位置 */ if(ai!=' ') h=i; for(i=0;i<=h;i+) /* 去除前面的空格及判斷中間是否有空格 */ j+; if(ai=' ') k+; if(j!=k) return ERROR; continue; if(ak='0') return ERROR; /* 第一個(gè)非空格字符是否為0 */ if(ai<'0'|ai>'9') return

8、 ERROR; /* 字符是否在0-9之間 */ else s=s*10+ai-48; /* 將字符串轉(zhuǎn)換成相應(yīng)的數(shù)值 */ if(s<1|s>32768) return ERROR; /* 數(shù)字在1-32768之間 */ return s; Status check() /* 正確輸入數(shù)據(jù) */ int p=0; while(!p) p=judge(); if(!p) printf("tWrong number:"); return p; /* check */ Status All_peidui(SqQueue *boys,SqQueue *girl）/*

9、輸出每曲配對(duì)情況 */ int min,k,i,j; bianhao(boys,girls); min = boynum>girlnum ? girlnum:boynum; printf("nn"); for (i=1;i <= song_num; i+) printf("t-第%d支舞曲配對(duì)情況為-n",i); if (min<5) k = min; else k = 5; for (j=0;j<k;j+) printf(" 男<->女 "); printf("n"); for

10、( j=1;j <= min;j+) output(boys,girls); if (j%5=0) printf("n"); printf("nn"); return OK; /* All_peidui */ Status K_peidui(SqQueue *boys,SqQueue *girls) /* 對(duì)第K曲進(jìn)行配對(duì),并輸出配對(duì)情況 */ int min,max,t,i,p1,p2,k,a; bianhao(boys,girls); do printf("t請(qǐng)輸入您想知道的配對(duì)情況的曲目編號(hào):"); k = check()

11、; if(k>song_num) printf("t所選曲目超出曲目總數(shù)!n"); while (k>song_num); min = boynum>girlnum ? girlnum:boynum; max = boynum>girlnum ? boynum:girlnum; printf("nnnttt第%d曲配對(duì)情況如下n",k); t=min*(k-1)%max; if(boynum>girlnum) for (i=1;i<=t;i+) DeQueue(boys,&p1,boynum); EnQueue

12、(boys,p1,boynum); else for (i=1;i<=t;i+) DeQueue(girls,&p2,girlnum); EnQueue(girls,p2,girlnum); if (min<5) a = min; else a = 5; for (i=0;i<a;i+) printf(" 男<->女 "); printf("n"); for(i=1;i<=min;i+) output(boys,girls); if (i%5=0) printf("n"); /* for *

13、/ printf("nn"); return OK; /* K_peidui */ 3.3 程序運(yùn)行結(jié)果 圖3.31 程序最初的運(yùn)行結(jié)果 圖3.32 用戶輸入數(shù)據(jù)界面 圖3.33 各曲配對(duì)情況 圖3.33 第K曲配對(duì)情況4. 課程設(shè)計(jì)心得、存在問題及解決方法 調(diào)試過程中出現(xiàn)的問題1：在構(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è)。 調(diào)試過程中出現(xiàn)的問題2：此次

14、課程設(shè)計(jì)只有一個(gè)核心算法，即進(jìn)行學(xué)生搭配，在最初的設(shè)計(jì)過程中犯了一個(gè)的錯(cuò)誤，即沒有很好的進(jìn)行整體布局，也沒有定義統(tǒng)一的函數(shù)接口，以致程序的結(jié)構(gòu)與函數(shù)的混亂。當(dāng)各模塊組合在一起的時(shí)候更是無沒進(jìn)行調(diào)試。 解決辦法：一切從頭開始，重新分配任務(wù)，以及統(tǒng)一定義各函數(shù)的接口。課程設(shè)計(jì)心得：通過一周的學(xué)習(xí)和實(shí)踐，解決實(shí)際問題（學(xué)生搭配問題），讓我對(duì)循環(huán)隊(duì)列有了更深的了解，對(duì)數(shù)據(jù)結(jié)構(gòu)產(chǎn)生了濃厚的興趣，同時(shí)也讓我提高了解決實(shí)際問題的能力。我知道了當(dāng)一段相同的代碼在程序中多次使用并且功能相對(duì)單一時(shí)，有必要將其寫成一個(gè)函數(shù)，以減少工作量，并且使程序具有更好的可讀性。在編寫程序的過程中，及時(shí)對(duì)重要和難懂的程序段寫注釋是一個(gè)很好的習(xí)慣，無論是以后的測試還是以后的維護(hù)都能夠節(jié)省相當(dāng)多的時(shí)間。調(diào)試時(shí)最先進(jìn)行各函