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

1、- -WORD 格式-可編輯-專業(yè)資料- - 數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計報告書班級學(xué)號專業(yè)姓名-完整版學(xué)習(xí)資料分享需求分析：, 本曲沒成功配對者坐著,要求如下 : (編號為 X)和任意女生 (編號為 Y)需求分析：, 本曲沒成功配對者坐著,要求如下 : (編號為 X)和任意女生 (編號為 Y),在第 K 曲配對跳舞的,可視情況適當(dāng)加分總體結(jié)構(gòu)設(shè)計：- 情況.至少課題描述：一、1.設(shè)計內(nèi)容一班有 m個女生 ,有n個男生 (m 不等于 n),現(xiàn)要開一個舞會 . 男女生分別編號坐在舞池的兩邊的椅子上 .每曲開始時 ,依次從男生和女生中各出一人配對跳舞等待下一曲找舞伴 . 請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述

2、過程1) 輸出每曲配對情況2) 計算出任何一個男生求出 K 的兩個值 . 3) 盡量設(shè)計出多種算法及程序2.需求本課題要對數(shù)目不等的男生女生跳舞進(jìn)行搭配，設(shè)計需要解決每一首曲子男生女生的搭配情況，要采用循環(huán)隊列的模式來解決，男生和女生各在兩個循環(huán)的隊列中，每首曲子開始，便在兩個隊首各取一人成功配對跳舞，并進(jìn)入隊尾，等待下一次配對。例如：（3男 5女情況）第一首：男 1和女 1 第二首：男 2和女 2 . 第四首：男 1和女 4 二、為實現(xiàn)上述功能和目的，要用到循環(huán)隊列的相關(guān)知識，同時，要定義一定的抽的數(shù)據(jù)類型，主函數(shù)調(diào)用各個函數(shù)模塊1.各模塊函數(shù)介紹：-完整版學(xué)習(xí)資料分享- -WORD 格式-

3、可編輯-專業(yè)資料- - 1)class cirularQueue 作用：定義一個一個循環(huán)隊列2)cirularQueue() 作用：定義析構(gòu)函數(shù)，使對象在撤銷時釋放3)bool IsFull() 作用：判斷隊列是否已滿4）bool IsEmpty() 作用：判斷隊列是否為空，用于出隊列前使用5）void push(T info) 作用：入隊。每對舞伴跳完舞之后，做入隊處理，到達(dá)隊尾，等待下次跳舞。6）void Pop(T &info) 作用：出隊。每取曲子響起時男生隊列和女生隊列作出隊處理，兩人跳舞。7）void GetHead(T &info) 作用：取隊首元素，對出隊的男女進(jìn)行識別。8）v

4、oid Initqueue(cirularQueue&,int); 作用：初始化隊列9）void display(int,int); 作用：根據(jù)男生和女生的人數(shù)和曲目的數(shù)目，來判斷每曲歌的男女配對情況10）void charge(int,int); 作用：判斷指定組合能否配對成功2.本程序包含三個模塊：1)主程序模塊：void main() 初始化；do 接受命令；處理命令；while( 命“ ”=退出” ”）-完整版學(xué)習(xí)資料分享定義集合的結(jié)點結(jié)構(gòu)各子模塊設(shè)計：每曲配對編號void void push(T info) bool IsFull() began - k 曲配對GetHead(T 輸

5、出-WORD 格式-可編輯定義集合的結(jié)點結(jié)構(gòu)各子模塊設(shè)計：每曲配對編號void void push(T info) bool IsFull() began - k 曲配對GetHead(T 輸出 2)、集合單元模塊 實現(xiàn)集合的各個函數(shù)模塊3)、結(jié)點結(jié)構(gòu)單元模塊三、1主函數(shù)調(diào)用關(guān)系圖主函數(shù)數(shù)據(jù)輸入cirularQueue() class cirularQueue void Pop(T &info) IsEmpty() 圖main() 2初始化示意-完整版學(xué)習(xí)資料分享iMaxsizevoid display(int,int) man.pop(x) void charge(int,int) - -W

6、ORD 格式-可編輯-專業(yè)資料- void display(int,int) man.pop(x) void charge(int,int) - 否圖 void Initqueue(cirularQueue &Q,int m) 3每曲配對函數(shù)調(diào)用關(guān)系圖初始化男 女循環(huán)隊列k=songnum否woman.pop(y) 是輸出 k 首男 x 女 yman.push(x) woman.push(y) k+ 圖 void display(int,int) end 4第k 曲配對函數(shù)調(diào)用圖初始化 男女-完整版學(xué)習(xí)資料分享循環(huán)隊列隊列為滿bool IsEmpty() 隊列為空不能入隊- 尾指針移-WORD

7、 格式-可編輯-專業(yè)資料- 隊列為滿bool IsEmpty() 隊列為空不能入隊- 尾指針移圖 void charge(int,int) 4隊滿判斷 bool IsFull() 首尾順序相鄰5對空判斷原則首尾指針相等6入隊流程 void push(T info) 隊滿-完整版學(xué)習(xí)資料分享隊尾進(jìn)入不能出隊頭指針移void GetHead(T &info) 編程實現(xiàn)：- -WORD 格式-可編輯-專業(yè)資料- 不能出隊頭指針移void GetHead(T &info) 編程實現(xiàn)：- 7出隊流程 void Pop(T &info) 隊空隊頭出列8.取隊首元素代碼四、#include template

8、 class cirularQueue /定義一個一個循環(huán)隊列 private: int MaxSize; int front; /頭指針int rear; /尾指針T *data; public: cirularQueue(int MaxLength) MaxSize=MaxLength; front=rear=0; data=new TMaxLength; cirularQueue() /定義析構(gòu)函數(shù)，使對象在撤銷時釋放 front=rear=0; delete data; void Initqueue() /隊列的申明 for(int i=0;imaxSize-1;i+) push(i)

9、; bool IsFull() /判斷隊列是否已滿 if(rear+1)%MaxSize=front) return true; else return false; bool IsEmpty() /判斷隊列是否為空-完整版學(xué)習(xí)資料分享0 - -WORD 格式-可編輯-專業(yè)資料- 0 - if(front=rear) return true; else return false; void push(T info) /入隊 if(IsFull() cout錯誤！隊列已滿！ endl; exit(-1); else datarear=info; rear=(rear+1)%MaxSize; vo

10、id Pop(T &info) /出隊 if(IsEmpty() cout錯誤！隊列為空！ endl; exit(-1); else info=datafront; front=(front+1)%MaxSize; void GetHead(T &info) /取隊首元素 if(IsEmpty() cout錯誤！隊列為空！ endl; exit (-1); else info=datafront; ; void Initqueue(cirularQueue&,int); void display(int,int); void charge(int,int); using namespace s

11、td; static int songnum=0; /定義歌曲的數(shù)量并初始化為static int m=0,n=0; /男生和女生的人數(shù)int main() /主函數(shù) coutmn; display(m,n); -完整版學(xué)習(xí)資料分享- -WORD 格式-可編輯-專業(yè)資料- - int a=0,b=0; /男生和女生的編號，以判斷他們在第幾首歌時能在一起跳舞char quit=y; /判斷是否繼續(xù)輸入 ,如果繼續(xù)輸入，則輸入 y；否則輸入 n while(quit!=n) coutab; while(am)|(bn) /如果輸入錯誤 coutab; charge(a,b); coutquit;

12、return 0; void Initqueue(cirularQueue &Q,int m) /初始化隊列 for(int i=1;i=m;i+) Q.push(i); void display(int m,int n) cirularQueue man(m+1); cirularQueue woman(n+1); Initqueue(man,m); Initqueue(woman,n); coutsongnum; cout每曲的配對情況為 :endl; for(int k=1;k=songnum;k+) int x=0,y=0; /男生和女生的編號man.Pop(x); /男生按順序出對跳

13、舞woman.Pop(y); /女生按順序出對跳舞cout第k 曲:tx 號男生 y 號女生 endl; /他們在一起跳舞man.push(x); /跳完舞后男生再次進(jìn)入隊列等在下一次跳舞woman.push(y); /跳完舞后男生再次進(jìn)入隊列等在下一次跳舞 void charge(int a,int b) int count=0; /定義舞曲計數(shù)以記錄他們能在第幾曲時在一起跳舞cirularQueue man1(m+1); cirularQueue woman1(n+1); Initqueue(man1,m); Initqueue(woman1,n); while(count=songnum

14、) int x, y; count+; -完整版學(xué)習(xí)資料分享測試結(jié)果：- -WORD 格式-可編輯-專業(yè)資料- 測試結(jié)果：- man1.Pop(x); woman1.Pop(y); man1.push(x); woman1.push(y); if(x=a)&(y=b) cout第count 首曲:ta 號男生 b 號女生endl; break; /如果他們在這個舞會上不能在一起跳舞，則輸出if(count=songnum+1) cout他們在這個舞會上不可能在一起跳舞 endl; 五、-完整版學(xué)習(xí)資料分享總結(jié)：主要利用用循環(huán)隊列的環(huán)C+，程序開始定義了類display()函數(shù)和 charge(

15、)函數(shù)，其中 display()用于對各位同學(xué)編號和每循環(huán)隊列是一種環(huán)狀的隊列并- cirular，其中有頭指針，尾指針及數(shù)據(jù)總結(jié)：主要利用用循環(huán)隊列的環(huán)C+，程序開始定義了類display()函數(shù)和 charge()函數(shù)，其中 display()用于對各位同學(xué)編號和每循環(huán)隊列是一種環(huán)狀的隊列并- cirular，其中有頭指針，尾指針及數(shù)據(jù)六、本設(shè)計采用的是循環(huán)隊列的基本操作順利的解決學(xué)生舞曲搭配問題，狀結(jié)構(gòu)，循環(huán)地執(zhí)行出列入列操作并在出隊列時進(jìn)行配對并輸出配對情況，而整個過程不需要不需要移動元素使程序在空間復(fù)雜度上降到最小，采用指針的移動大大加快了程序的執(zhí)行效率。并且對輸入進(jìn)行了改進(jìn)，以防止用戶隨意輸入時出現(xiàn)的各種意想不到的錯誤。本次程序設(shè)計中所用語言為域等。隨之定義了析構(gòu)函數(shù)，釋放對象，然后進(jìn)行了隊列的基本操作，有隊列的申明，判斷隊空及隊滿，出隊，入隊，其核心是隊的輸出情況， charge()用于計算已編號的同學(xué)在第幾曲中進(jìn)行配對。且對頭元素指向隊尾元素，學(xué)生搭配問題是典型的只有采用循環(huán)隊列才能解決的問題，實驗表明該算法的空間復(fù)雜度優(yōu)于其他算法。通過這次實驗，我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)這方面真是知之甚少，以前學(xué)習(xí)的知識也多有遺忘。與其說這是一次學(xué)習(xí)，倒不如說這是一次檢測。所以，這次實驗讓我很好的認(rèn)清自己對數(shù)據(jù)結(jié)