【數(shù)據(jù)結(jié)構(gòu)】排隊購票問題

1、.東北大學信息科學與工程學院數(shù)據(jù)結(jié)構(gòu)課程設計報告題目 排隊購票問題課題組長 侯永躍 課題組成員 林浩成 李博然 韓碩專業(yè)名稱 計算機科學與技術(shù)班級 計1307指導教師 楊雷2015 年 1月課程設計任務書題目：排隊購票問題問題描述：歐洲杯足球賽正在激烈進行。決賽門票處于熱賣。為使門票公平、安全的銷售，售票處決定采用如下售票規(guī)則：（1）購票者到購票處領取一個隨機編號。（2）購票者按隨機編號從小到大排序。（3）隨機編號處于最小編號與最大編號之間的購票者，可直接到窗口排隊購票。（4）售票窗口空閑時隨機發(fā)出0或1指令，指令為0時，最小編號者到窗口購票，指令為1時，最大編號者到窗口購票。設計要求：設計算

2、法實現(xiàn)按上述規(guī)則的排隊售票程序。（1）采用STL的雙端隊列等數(shù)據(jù)結(jié)構(gòu)。（2）實現(xiàn)STL的雙端隊列類deque。（3）嘗試采用不同數(shù)據(jù)結(jié)構(gòu)的多種解法。指導教師簽字：2015年1月4日目錄1 課題概述51.1 課題任務51.2 課題原理51.3 相關(guān)知識52 需求分析62.1 課題調(diào)研62.2 用戶需求分析63 方案設計73.1 總體功能設計73.2 數(shù)據(jù)結(jié)構(gòu)設計73.3 函數(shù)原型設計73.4 主算法設計73.5 用戶界面設計74 方案實現(xiàn)94.1 開發(fā)環(huán)境與工具94.2 程序設計關(guān)鍵技術(shù)94.3 個人設計實現(xiàn)94.3.1 侯永躍設計實現(xiàn)94.3.2 李博然設計實現(xiàn)124.3.3 林浩成設計實現(xiàn)1

3、34.3.4 韓碩設計實現(xiàn)135 測試與調(diào)試155.1 個人測試155.1.1 侯永躍測試155.1.2 李博然測試155.1.3 林浩成測試165.2 組裝與系統(tǒng)測試175.3 系統(tǒng)運行186 課題總結(jié)216.1 課題評價216.2 個人設計小結(jié)216.2.1 侯永躍設計小結(jié)216.2.2 李博然設計小結(jié)216.2.3 林浩成設計小結(jié)21 6.2.4 韓碩設計小結(jié)217 附錄A 課題任務分工A-1 課題程序設計分工22A-2 課題報告分工23 附錄B 課題設計文檔（光盤）附B-1課程設計報告（電子版）B-2源程序代碼（*.H，*.CPP）24B-3工程與可執(zhí)行文件附 1 課題概述1.1 課題

4、任務歐洲杯足球賽正在激烈進行。決賽門票處于熱賣。為使門票公平、安全的銷售，售票處決定采用如下售票規(guī)則：（1）購票者到購票處領取一個隨機編號。（2）購票者按隨機編號從小到大排序。（3）隨機編號處于最小編號與最大編號之間的購票者，可直接到窗口排隊購票。（4）售票窗口空閑時隨機發(fā)出0或1指令，指令為0時，最小編號者到窗口購票，指令為1時，最大編號者到窗口購票。 要求：設計算法實現(xiàn)按上述規(guī)則的排隊售票程序。（1）采用STL的雙端隊列等數(shù)據(jù)結(jié)構(gòu)。（2）實現(xiàn)STL的雙端隊列類deque。（3）嘗試采用不同數(shù)據(jù)結(jié)構(gòu)的多種解法。1.2 課題原理讀取文件中的字符串，統(tǒng)計串中各字符出現(xiàn)的次數(shù)，成為權(quán)值，之后構(gòu)建最

5、優(yōu)二叉樹進行編碼。再將串中字符與編碼匹配，輸出編碼字符串，之后每八位用底層字符進行壓縮。每次有觀眾領取編號，利用隨機數(shù)輸出一個1100之間隨機的一個數(shù)。按從小到大的順序插入雙端隊列，售票窗口隨機發(fā)出0或1指令，指令為0時，最小編號出隊列，指令為1時，最大編號出隊列。1.3 相關(guān)知識 1.STL的雙端隊列。利用STL的雙端隊列deque類，實現(xiàn)隨機編號的入隊列、出隊列。2.隨機數(shù)的生成。通過隨機數(shù)的生成，實現(xiàn)給購票者分配一個隨機編號、售票窗口發(fā)出隨機指令等操作。2 需求分析2.1 課題調(diào)研： 1.為購票者分配隨機編號（范圍定為1-100）。 2.將分配到的編號插入隊列，使隊列中的元素順序為從小到

6、大。3.查看隊列。4.隨機發(fā)出指令0或1。0時，移出最小編號；1時，移出最大編號。2.2 用戶需求分析：1.隨機分配給購票者編號。2.能夠從分配出的編號中選出最小編號和最大編號。3.隨機給出0或1指令。3 方案設計3.1 總體功能設計：本程序主要實現(xiàn)三個功能：為購票者分配隨機編號，售票窗口發(fā)出隨機指令，查看正在隊列中的編號。為購票者分配編號需要用到隨機函數(shù)，分配完畢之后插入隊列。將隨機數(shù)依次與隊列元素比較，找到合適的“位置”后插入到指針后面3.2 數(shù)據(jù)結(jié)構(gòu)設計：本程序使用STL的雙端隊列類deque。主要涉及操作有push_front()、push_back()、insert()、begin(

7、)、end()、pop_front()、pop_back()。3.3 函數(shù)原型設計：delete_dequenum(intdeq &ideq, int ran1)實現(xiàn)指令的刷新，提醒當次排號購票deque_num(intdeq &ideq, int num)實現(xiàn)插入元素位置查找和隊列元素的增添show_deque(intdeq &ideq)：用于輸出正在隊列中的編號，若隊列為空，則輸出無人排隊。show_num()：用于為購票者分配編號，編號為1-100之間的隨機數(shù)。show_command(intdeq &ideq)：用于顯示售票窗口指令。menu_back(

8、intdeq &ideq, int &num, char cmd)，menu()：主菜單。3.4 主算法設計 ：隨機數(shù)的生成：使用srand()提供種子數(shù)，再使用rand()函數(shù)生成隨機數(shù)。隊列的操作部分：查找、增添、刪除界面部分：隨機數(shù)和隊列的顯示3.5 用戶界面設計：主菜單：分配編號：查看隊列：輸出指令：4 方案實現(xiàn)4.1 開發(fā)環(huán)境與工具： 開發(fā)環(huán)境：Windows操作系統(tǒng) 開發(fā)工具：VC+6.04.2 程序設計的關(guān)鍵技術(shù)： STL的雙端隊列結(jié)構(gòu)。4.3 個人設計實現(xiàn)：4.3.1 侯永躍設計實現(xiàn)：主要負責主界面的設計，隨機編號的生成。void show_deque(intd

9、eq &ideq) /顯示正在排隊的購票者的編號system("cls");cout << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"if (ideq.empty()cout << "t現(xiàn)在沒有人排隊。" << endl;elsecout << "t當前正在排隊中的編號有:"copy(ideq.begin(),

10、ideq.end(), screen);/輸出隊列ideq中的元素，從 /begin到endcout << endl << "t"system("pause");int show_num()system("cls");srand(unsigned)time(NULL);int rnum=rand() % 100 + 1; /生成隨機數(shù)，范圍1-100numii=rnum;for(int j=0;j<ii;j+) if(rnum=numii) rnum=rand() % 100 + 1; ii+; cout

11、 << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"cout << "t您的編號為:" << rnum << endl;cout << endl << "t"/cout << "t按Esc鍵退出." << endl;system("pause");ret

12、urn rnum;void show_command(intdeq &ideq)/輸出售票窗口的指令。ran = rand() % 2;system("cls");cout << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"cout << "-"cout << "| " << ran << "

13、; |"cout << "-"if (!ideq.empty()if (ran = 0)cout << "t請編號" << ideq.front() << "的乘客到窗口購票." << endl;else if (ran = 1)cout << "t請編號" << ideq.back() << "的乘客到窗口購票." << endl;delete_dequenum(ideq, r

14、an); /將該編號移出隊列elsecout << "t當前窗口沒有人排隊." << endl;cout << "t"system("pause");void menu_back(intdeq &ideq, int &num, char cmd) /主菜單選項的處理if (cmd = 'n' | cmd = 'N')num = show_num();deque_num(ideq, num);else if (cmd = 'l' | cm

15、d = 'L')show_deque(ideq);else if (cmd = 'r' | cmd = 'R')show_command(ideq);int main()char cmd;int num;intdeq ideq;srand(time(0);while (1)cmd = menu();menu_back(ideq, num, cmd);if (cmd = 'e' | cmd ='E')break;return 0; 4.3.2 李博然設計實現(xiàn)： 隊列元素位置查找和元素增添void deque_num(

16、intdeq &ideq, int num)int i = 0;/cout << "test" << endl;if(num < ideq.front()ideq.push_front(num);else if (num > ideq.back()ideq.push_back(num);elsedeque<int>:iterator deqIt;deqIt = ideq.begin();while (num > ideqi)deqIt+;i+;ideq.insert(deqIt, num);number+;4.3

17、.3 林浩成設計實現(xiàn)： 刷新指令及雙端隊列的元素移除。 void delete_dequenum(intdeq &ideq, int ran1) bool jud = 0;if (ran1 = 0)for (int i=0; i<ii; i+)if (numi = ideq.front()/deq.front()返回第一個元素（不檢測容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_front();/deq.pop_front()刪除第一個元素else if (ran1 = 1)for

18、(int i=0; i<ii; i+)if (numi = ideq.back()/deq.back()返回最后一個元素（不檢測容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_back();/刪除最后一個元素ii-;4.3.4 韓碩設計實現(xiàn)：主要負責主菜單char menu()char cmd;system("cls");cout << endl << endl;cout << "*"cout << &qu

19、ot;* 購票系統(tǒng) *"cout << "*"cout << "t按n鍵領取編號." << endl;cout << "t按r鍵刷新指令." << endl; cout << "t按l鍵查看隊列." << endl; cout << "t按e鍵退出." << endl; cin >> cmd;return cmd;5 測試與調(diào)試5.1 個人測試5.1.1 侯永躍個人測

20、試主要測試生成的隨機數(shù)有無重復，界面間的轉(zhuǎn)換有沒有問題。幾組測試后，發(fā)現(xiàn)在數(shù)量小于100的情況下，隨機數(shù)無重復現(xiàn)象。界面銜接的也很好。5.1.2李博然個人測試通過隨機搖號刪除一個頭（尾）節(jié)點之后的隊列5.1.3林浩成個人測試5.2 組裝與系統(tǒng)測試為了測試組裝之后的程序是否可用，方便起見，在分配編號和指令兩個界面分別輸出操作前后雙端隊列的狀態(tài)。測試結(jié)果顯示雙端隊列能夠正常工作。5.3系統(tǒng)運行 領取編號： 查看隊列： 售票窗口發(fā)出指令： 發(fā)出指令后刪除對應的編號6 課題總結(jié)6.1 課題評價 做完這次的程序設計之后，我們組的成員都感覺STL使用起來非常方便，節(jié)省了大量的設計抽象數(shù)據(jù)結(jié)構(gòu)的時間。通過這

21、個實驗我們了解了STL模板的使用，當然更重要的是積累了小組合作編程的經(jīng)驗。6.2 個人設計總結(jié)6.3.1 侯永躍個人總結(jié)通過這次編程，我發(fā)現(xiàn)STL模板庫的確非常好用，數(shù)量眾多的庫函數(shù)給我們的編程帶來了很多便利。誠然我們可以手動設計數(shù)據(jù)結(jié)構(gòu)，但那樣的效率顯然不能和直接使用STL庫相比。因此學習STL的使用還是很有必要的。在學習編程語言的過程中也應當注意把幾種不同的方法相比較，在應用的時候選擇效率高的一種。6.3.2 李博然個人總結(jié) 這次編程使用的C+模板類是首次接觸，在查閱大量資料后發(fā)現(xiàn)STL確實在很多方面能簡化編程，節(jié)省代碼量，甚至比A類題目編程起來還要簡單，但是STL還有很多功能我們還沒有了

22、解到，希望能在以后的編程中深入學習提升自己的編程能力。本次我主要負責的是隊列的增添和查找，在以前自己寫是很復雜的但這次用很短的代碼就實現(xiàn)了，所以希望以后能夠?qū)W習自用，在編程中考慮更多的應該是算法的復雜度和效率而不應該是如何寫一段代碼，這樣才能真正提升編程能力。6.3.3 林浩成個人總結(jié) 在此次課程設計中，STL的運用讓整個編程效率提高了很多，這讓我們體會到了標準模板庫的價值所在，學習標準模板庫或是別的模板庫，甚至是形成自己的編程習慣都是相當重要的，是一個程序員必須要掌握的基本素質(zhì)。代碼的規(guī)范性，高效性和兼容性都是衡量代碼是否質(zhì)量上乘的重要參數(shù)之一，在學習的路上，我們也要格外注意這些小的習慣，培

23、養(yǎng)好的習慣是為建立程序大廈所打好的堅實基礎。6.3.4 韓碩個人總結(jié) 這次B類實驗，我們在時間極其短暫的情況下，完成了對STL的學習并實現(xiàn)了程序的設計，我覺得團隊的力量是尤為重要的，然而這其中也體現(xiàn)了我編程能力上的不足，希望今后可以加強對編程能力的鍛煉。7 附錄7.1 附錄A 課題任務分工A-1 課題程序設計分工學號姓名程序設計函數(shù)原型、類功能說明20133981侯永躍show_deque(intdeq &ideq)，show_num(intdeq &ideq)，show_command(intdeq &ideq)， menu_back(intdeq &ideq

24、, int &num, char cmd)，menu()，main()主界面及各個功能界面，隨機編號和隨機指令的生成20133983李博然deque_num(intdeq &ideq, int num)查找位置和入隊列20131364林浩成Void delete_dequenum(intdeq &ideq, int ran1)刷新指令及雙端隊列的元素移除A-2 課題報告分工章節(jié)內(nèi)容完成人1 課題概述1.1 課題任務1.2 課題原理 1.3 相關(guān)知識侯永躍2 需求分析2.1 課題調(diào)研 2.2 用戶需求分析侯永躍3 方案設計3.1 總體功能設計3.2 數(shù)據(jù)結(jié)構(gòu)設計3.3 函

25、數(shù)原型設計3.4 主算法設計3.5 用戶界面設計侯永躍林浩成李博然韓碩4 方案實現(xiàn)4.1 開發(fā)環(huán)境與工具4.2 程序設計關(guān)鍵技術(shù)4.3 個人設計實現(xiàn)（按組員分工）4.3.1 侯永躍設計實現(xiàn)4.3.2 李博然設計實現(xiàn)4.3.3 林浩成設計實現(xiàn)4.3.4 韓碩設計實現(xiàn)侯永躍林浩成李博然韓碩5 測試與調(diào)試5.1 個人測試（按組員分工）5.1.1 侯永躍個人測試5.1.2 李博然個人測試5.1.3 林浩成個人測試5.2 組裝與系統(tǒng)測試5.3 系統(tǒng)運行侯永躍林浩成李博然6 課題總結(jié)6.1 課題評價6.2 團隊協(xié)作6.3 下一步工作6.4 個人設計心得（按組員分工）6.4.1 侯永躍設計心得6.4.2 李

26、博然設計心得6.4.3 林浩成設計心得6.4.4 韓碩設計心得侯永躍林浩成李博然韓碩附錄B 源代碼#include <iostream>#include <deque>#include <windows.h>#include <cstdlib>#include <ctime>#include <algorithm>#include <iterator>#include <time.h>using namespace std;typedef deque<int> intdeq;ostrea

27、m_iterator<int> screen(cout, " ");/屏幕顯示unsigned int number = 0;int num100;int ran;int ii;void delete_dequenum(intdeq &ideq, int ran1);void deque_num(intdeq &ideq, int num);void show_deque(intdeq &ideq);int show_num();char menu(intdeq &ideq);void delete_dequenum(intdeq

28、 &ideq, int ran1)bool jud = 0;if (ran1 = 0)for (int i=0; i<ii; i+)if (numi = ideq.front()/deq.front()返回第一個元素（不檢測容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_front();/deq.pop_front()刪除第一個元素else if (ran1 = 1)for (int i=0; i<ii; i+)if (numi = ideq.back()/deq.back()返

29、回最后一個元素（不檢測容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_back();/刪除最后一個元素ii-;void deque_num(intdeq &ideq, int num)int i = 0;/cout << "test" << endl;if(num < ideq.front()ideq.push_front(num);else if (num > ideq.back()ideq.push_back(num);elsede

30、que<int>:iterator deqIt;deqIt = ideq.begin();while (num > ideqi)deqIt+;i+;ideq.insert(deqIt, num);void show_deque(intdeq &ideq)system("cls");cout << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"if (ideq.empty(

31、)cout << "t現(xiàn)在沒有人排隊。" << endl;elsecout << "t當前正在排隊中的編號有:"copy(ideq.begin(),ideq.end(), screen);cout << endl << "t"system("pause");int show_num(intdeq &ideq)system("cls");srand(unsigned)time(NULL);int rnum=rand() % 100

32、 + 1;numii=rnum;for(int j=0;j<ii;j+) if(rnum=numii) rnum=rand() % 100 + 1; ii+; cout << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"cout << "t您的編號為:" << rnum << endl;cout << endl << "

33、t"system("pause");return rnum;void show_command(intdeq &ideq)ran = rand() % 2;system("cls");cout << endl << endl;cout << "*"cout << "* 購票系統(tǒng) *"cout << "*"cout << "-"cout << "| " << ran << " |"cout << "-"if (!ideq.empty()if (ran = 0)cout << "t請編號" << ideq.front() << "的乘客到窗口購票." <&