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

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

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

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

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

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

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

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

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

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

10、ideq.end(), screen);/輸出隊(duì)列ideq中的元素，從 /begin到endcout << endl << "t"system("pause");int show_num()system("cls");srand(unsigned)time(NULL);int rnum=rand() % 100 + 1; /生成隨機(jī)數(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 << "* 購(gòu)票系統(tǒng) *"cout << "*"cout << "t您的編號(hào)為:" << 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 << "* 購(gòu)票系統(tǒng) *"cout << "*"cout << "-"cout << "| " << ran << "

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

14、an); /將該編號(hào)移出隊(duì)列elsecout << "t當(dāng)前窗口沒(méi)有人排隊(duì)." << endl;cout << "t"system("pause");void menu_back(intdeq &ideq, int &num, char cmd) /主菜單選項(xiàng)的處理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 李博然設(shè)計(jì)實(shí)現(xiàn)： 隊(duì)列元素位置查找和元素增添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 林浩成設(shè)計(jì)實(shí)現(xiàn)： 刷新指令及雙端隊(duì)列的元素移除。 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()返回第一個(gè)元素（不檢測(cè)容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_front();/deq.pop_front()刪除第一個(gè)元素else if (ran1 = 1)for

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

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

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

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

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

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

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

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

26、博然設(shè)計(jì)心得6.4.3 林浩成設(shè)計(jì)心得6.4.4 韓碩設(shè)計(jì)心得侯永躍林浩成李博然韓碩附錄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()返回第一個(gè)元素（不檢測(cè)容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_front();/deq.pop_front()刪除第一個(gè)元素else if (ran1 = 1)for (int i=0; i<ii; i+)if (numi = ideq.back()/deq.back()返

29、回最后一個(gè)元素（不檢測(cè)容器是否為空）jud = 1;if (jud = 1)numi = numi+1;if (jud = 1)numii = 0;ideq.pop_back();/刪除最后一個(gè)元素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 << "* 購(gòu)票系統(tǒng) *"cout << "*"if (ideq.empty(

31、)cout << "t現(xiàn)在沒(méi)有人排隊(duì)。" << endl;elsecout << "t當(dāng)前正在排隊(duì)中的編號(hào)有:"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 << "* 購(gòu)票系統(tǒng) *"cout << "*"cout << "t您的編號(hào)為:" << 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 << "* 購(gòu)票系統(tǒng) *"cout << "*"cout << "-"cout << "| " << ran << " |"cout << "-"if (!ideq.empty()if (ran = 0)cout << "t請(qǐng)編號(hào)" << ideq.front() << "的乘客到窗口購(gòu)票." <&