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

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

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

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

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

5、tatus DeQueue(SqQueue *Q,QElemType *e,int num)/* 若隊列不空，則刪除Q的對頭元素，用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) /* 隊列初始化及對男女生進行編號 */ 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+) /* 記錄最后一個非空格字符的位置 */ 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; /* 第一個非空格字符是否為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、輸出每曲配對情況 */ 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支舞曲配對情況為-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) /* 對第K曲進行配對,并輸出配對情況 */ int min,max,t,i,p1,p2,k,a; bianhao(boys,girls); do printf("t請輸入您想知道的配對情況的曲目編號:"); 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曲配對情況如下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 程序運行結(jié)果 圖3.31 程序最初的運行結(jié)果 圖3.32 用戶輸入數(shù)據(jù)界面 圖3.33 各曲配對情況 圖3.33 第K曲配對情況4. 課程設(shè)計心得、存在問題及解決方法 調(diào)試過程中出現(xiàn)的問題1：在構(gòu)造隊列時，設(shè)隊列分配的最大空間為男女生的個數(shù)，此時便無法根據(jù) Q.front=Q.rear 來判別隊列空間是“空”還是“滿”,因此，在入 隊操作即插入一個新元素作為新的隊尾元素時出現(xiàn)了問題，即最后一位同學無法入隊。 解決方法：將隊列分配的最大空間至少再增加一個。 調(diào)試過程中出現(xiàn)的問題2：此次

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