数据结构排队购票问题版

东北大学信息科学与工程学院数据结构课程设计报告题目 排队购票问题课题组长 侯永跃课题组成员林浩成李博然韩硕专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015年1月课程设计任务书题目：排队购票问题问题描述：欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。设计要求：设计算法实现按上述规则的排队售票程序。（1）采用5口的双端队列等数据结构。（2）实现5口的双端队列类deque。（3）尝试采用不同数据结构的多种解法。指导教师签字：2015年1月4日目录TOC\o"1-5"\h\z\o"CurrentDocument"课题任务 5\o"CurrentDocument"课题原理 5\o"CurrentDocument"相关知识 5\o"CurrentDocument"2需求分析 6\o"CurrentDocument"课题调研 6\o"CurrentDocument"用户需求分析 6\o"CurrentDocument"3方案设计 7\o"CurrentDocument"总体功能设计 7\o"CurrentDocument"数据结构设计 7\o"CurrentDocument"函数原型设计 7\o"CurrentDocument"主算法设计 7\o"CurrentDocument"用户界面设计 7\o"CurrentDocument"4方案实现 9\o"CurrentDocument"开发环境与工具 9\o"CurrentDocument"程序设计关键技术 9\o"CurrentDocument"个人设计实现 9\o"CurrentDocument"侯永跃设计实现 9\o"CurrentDocument"李博然设计实现 12\o"CurrentDocument"林浩成设计实现 13\o"CurrentDocument"韩硕设计实现 13\o"CurrentDocument"5测试与调试 15\o"CurrentDocument"个人测试 15\o"CurrentDocument"侯永跃测试 15\o"CurrentDocument"李博然测试 15\o"CurrentDocument"林浩成测试 16\o"CurrentDocument"组装与系统测试 17\o"CurrentDocument"系统运行 18\o"CurrentDocument"6课题总结 21\o"CurrentDocument"课题评价 21\o"CurrentDocument"个人设计小结 21侯永跃设计小结 21李博然设计小结 21林浩成设计小结 21韩硕设计小结 217附录A课题任务分工\o"CurrentDocument"A-1课题程序设计分工 22\o"CurrentDocument"A-2课题报告分工 23附录B课题设计文档（光盘） 附B-1课程设计报告（电子版） B-2源程序代码（粒H，*.CPP） 24B-3工程与可执行文件 附1课题概述1.1课题任务欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。要求：设计算法实现按上述规则的排队售票程序。（1）采用5底的双端队列等数据结构。（2）实现STL的双端队列类deque。（3）尝试采用不同数据结构的多种解法。课题原理读取文件中的字符串，统计串中各字符出现的次数，成为权值，之后构建最优二叉树进行编码。再将串中字符与编码匹配，输出编码字符串，之后每八位用底层字符进行压缩。每次有观众领取编号，利用随机数输出一个1〜100之间随机的一个数。按从小到大的顺序插入双端队列，售票窗口随机发出0或1指令，指令为0时，最小编号出队列，指令为1时，最大编号出队列。相关知识1.STL的双端队列。利用STL的双端队列deque类，实现随机编号的入队列、出队列。.随机数的生成。通过随机数的生成，实现给购票者分配一个随机编号、售票窗口发出随机指令等操作。2需求分析课题调研：.为购票者分配随机编号（范围定为1-100）。.将分配到的编号插入队列，使队列中的元素顺序为从小到大。.查看队列。.随机发出指令0或1。0时，移出最小编号；1时，移出最大编号用户需求分析：.随机分配给购票者编号。.能够从分配出的编号中选出最小编号和最大编号。.随机给出0或1指令。3方案设计总体功能设计：本程序主要实现三个功能：为购票者分配随机编号，售票窗口发出随机指令，查看正在队列中的编号。为购票者分配编号需要用到随机函数，分配完毕之后插入队列。将随机数依次与队列元素比较，找到合适的“位置”后插入到指针后面数据结构设计：本程序使用STL的双端队列类deque。主要涉及操作有push_front()、push_back()、insert()、begin()、end()、pop_front()、pop_back()。函数原型设计：delete_dequenum(intdeq&ideq,intran1)实现指令的刷新，提醒当次排号购票 一 一deque_num(intdeq&ideq,intnum)实现插入元素位置查找和队列元素的增添show_deque(intdeq&ideq)：用于输出正在队列中的编号，若队列为空，则输出无人排队。show_num()：用于为购票者分配编号，编号为1-100之间的随机数。show_command(intdeq&ideq)：用于显示售票窗口指令。menu_back(intdeq&ideq,int&num,charcmd),menu()：主菜单。主算法设计：随机数的生成：使用srand()提供种子数，再使用rand()函数生成随机数。队列的操作部分：查找、增添、删除界面部分：随机数和队列的显示用户界面设计：主菜单：分配编号:查看队列:输出指令:

4方案实现开发环境与工具：开发环境：Windows操作系统开发工具：VC++6.0程序设计的关键技术：STL的双端队列结构。个人设计实现：侯永跃设计实现：主要负责主界面的设计，随机编号的生成。voidshow_deque(intdeq&ideq)〃显示正在排队的购票者的编号{system("cls");cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1***”;if(ideq.empty())cout<<"\t现在没有人排队。"<<endl;else{cout<<〃\t当前正在排队中的编号有:〃；copy(ideq.begin(),ideq.end(),screen);//输出队列ideq中的元素，从} //begin至Uendcout<<endl<<"\t";system("pause");)intshow_num(){system("cls");srand((unsigned)time(NULL));intrnum=rand()%100+1; 〃生成随机数，范围1-100num[ii]=rnum;

for(intj=0;j<ii;j++){if(rnum==num[ii])rnum=rand()%100+1;)ii++;cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<"\t您的编号为:"<<rnum<<endl;cout<<endl<<"\t";//cout<<"\t按Esc键退出."<<endl;system("pause");returnrnum;)voidshow_command(intdeq&ideq)//输出售票窗口的指令。{ran=rand()%2;system("cls");cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1***”;cout <<〃<<ran<<<<cout<<"|cout<<ran<<<<〃;if(!ideq.empty()){if(ran==0)cout<<"\t请编号"<<ideq.front()<<”的乘客到窗口购票."<<endl;elseif(ran==1)cout<<〃\t请编号〃<<ideq.back()<<〃的乘客到窗口购票.〃<<endl;delete_dequenum(ideq,ran); //将该编号移出队列)elsecout<<〃\t当前窗口没有人排队.〃<<endl;cout<<"\t";system("pause");)voidmenu_back(intdeq&ideq,int&num,charcmd) //主菜单选项的处理{if(cmd==，n'||cmd==，N，){num=show_num();deque_num(ideq,num);)elseif(cmd=='l'||cmd=='L')show_deque(ideq);elseif(cmd=='r'||cmd=='R')show_command(ideq);)intmain(){charcmd;intnum;intdeqideq;srand(time(0));while(1){cmd=menu();menu_back(ideq,num,cmd);if(cmd=='e'||cmd=='E')break;)return0;李博然设计实现：队列元素位置查找和元素增添voiddeque_num(intdeq&ideq,intnum){inti=0;//cout<<“test"<<endl;if(num<ideq.front())ideq.push_front(num);elseif(num>ideq.back())ideq.push_back(num);else{deque<int>::iteratordeqIt;deqIt=ideq.begin();while(num>ideq[i]){deqIt++;i++;)ideq.insert(deqIt,num);)number++;)林浩成设计实现：刷新指令及双端队列的元素移除。voiddelete_dequenum(intdeq&ideq,intrani){booljud=0;if(rani==0){for(inti=0;i<ii;i++){if(num[i]==ideq.front())//deq.front()返回第一个元素(不检测容器是否为空)jud=1;if(jud==1){num[i]=num[i+1];))if(jud==1)num[ii]=0;ideq.pop_front();〃deq.pop_front()删除第一个元素)elseif(ran1==1){for(inti=0;i<ii;i++){if(num[i]==ideq.back())〃deq.back()返回最后一个元素(不检测容器是否为空)jud=1;if(jud==1)num[i]=num[i+1];)if(jud==1)num[ii]=0;ideq.pop_back();〃删除最后一个元素)ii--;)韩硕设计实现：主要负责主菜单charmenu(){charcmd;system("cls");cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃\t按n键领取编号.〃<<endl;cout<<"\t按r键刷新指令."<<endl;cout<<〃\t按l键查看队列.〃<<endl;cout<<"\t按e键退出."<<endl;cin>>cmd;returncmd)5测试与调试个人测试侯永跃个人测试主要测试生成的随机数有无重复，界面间的转换有没有问题。几组测试后，发现在数量小于100的情况下，随机数无重复现象。界面衔接的也很好。主要测试生成的随机数有无重复，界面间的转换有没有问题。几组测试后，发现在数量小于100的情况下，随机数无重复现象。界面衔接的也很好。李博然个人测试C:\U&ers\hp-1\Desktap\B\dequs\bin\IDebug\deque.exe购票系统1MlM1MlM"HC"S1MlM"M1MlM1MlM1MBMc1MBM"M*编号有：1D1012355377939595通过随机摇号删除一个头（尾）节点之后的队列C:\U&ers\hp-1\Desktap\B\dequs\bin\IDebug\deque.exe购票系统IMXXXXXXXXXXXXXXXXXXXXXXXXXXXXX编号有：1@101235537793955.1.3林浩成个人测试组装与系统测试为了测试组装之后的程序是否可用，方便起见，在分配编号和指令两个界面分别输出操作前后双端队列的状态。测试结果显示双端队列能够正常工作。5.3系统运行号令列第午队■改1-有一〕一^^退iw-mil-m--nx--处承觉处nr1eIB领取编号:查看队列:售票窗口发出指令:

发出指令后删除对应的编号6课题总结课题评价做完这次的程序设计之后，我们组的成员都感觉STL使用起来非常方便，节省了大量的设计抽象数据结构的时间。通过这个实验我们了解了$乩模板的使用，当然更重要的是积累了小组合作编程的经验。个人设计总结侯永跃个人总结通过这次编程，我发现STL模板库的确非常好用，数量众多的库函数给我们的编程带来了很多便利。诚然我们可以手动设计数据结构，但那样的效率显然不能和直接使用STL库相比。因此学习STL的使用还是很有必要的。在学习编程语言的过程中也应当注意把几种不同的方法相比较，在应用的时候选择效率高的一种。李博然个人总结这次编程使用的C++模板类是首次接触，在查阅大量资料后发现STL确实在很多方面能简化编程，节省代码量，甚至比A类题目编程起来还要简单，但是STL还有很多功能我们还没有了解到，希望能在以后的编程中深入学习提升自己的编程能力。本次我主要负责的是队列的增添和查找，在以前自己写是很复杂的但这次用很短的代码就实现了，所以希望以后能够学习自用，在编程中考虑更多的应该是算法的复杂度和效率而不应该是如何写一段代码，这样才能真正提升编程能力。林浩成个人总结在此次课程设计中，STL的运用让整个编程效率提高了很多，这让我们体会到了标准模板库的价值所在，学习标准模板库或是别的模板库，甚至是形成自己的编程习惯都是相当重要的，是一个程序员必须要掌握的基本素质。代码的规范性，高效性和兼容性都是衡量代码是否质量上乘的重要参数之一，在学习的路上，我们也要格外注意这些小的习惯，培养好的习惯是为建立程序大厦所打好的坚实基础。韩硕个人总结这次B类实验，我们在时间极其短暂的情况下，完成了对$乩的学习并实现了程序的设计，我觉得团队的力量是尤为重要的，然而这其中也体现了我编程能力上的不足，希望今后可以加强对编程能力的锻炼。

7附录7.1附录A课题任务分工A-1课题程序设计分工学号姓名程序设计函数原型、类功能说明20133981侯永跃show_deque(intdeq&ideq)，show_num(intdeq&ideq)，show_command(intdeq&ideq)，menu_back(intdeq&ideq,int&num,charcmd)，menu()，main()主界面及各个功能界面，随机编号和随机指令的生成20133983李博然deque_num(intdeq&ideq,intnum)查找位置和入队列20131364林浩成Voiddelete_dequenum(intdeq&ideq,intran1)刷新指令及双端队列的元素移除A-2课题报告分工

A-H-章节内容完成人1课题概述1.1课题任务1.2课题原理1.3相关知识侯永跃2需求分析2.1课题调研2.2用户需求分析侯永跃3方案设计总体功能设计数据结构设计函数原型设计主算法设计用户界面设计侯永跃林浩成李博然韩硕4方案实现开发环境与工具程序设计关键技术个人设计实现（按组员分工）侯永跃设计实现李博然设计实现林浩成设计实现韩硕设计实现侯永跃林浩成李博然韩硕5测试与调试个人测试（按组员分工）侯永跃个人测试李博然个人测试林浩成个人测试组装与系统测试系统运行侯永跃林浩成李博然6课题总结课题评价团队协作下一步工作个人设计心得（按组员分工）侯永跃设计心得李博然设计心得林浩成设计心得韩硕设计心得侯永跃林浩成李博然韩硕附录B源代码#include<iostream>#include<deque>#include<windows.h>#include<cstdlib>#include<ctime>#include<algorithm>#include<iterator>#include<time.h>usingnamespacestd;typedefdeque<int>intdeq;ostream_iterator<int>screen(cout,"");//屏幕显示unsignedintnumber=0;intnum[100];intran;intii;voiddelete_dequenum(intdeq&ideq,intrani);voiddeque_num(intdeq&ideq,intnum);voidshow_deque(intdeq&ideq);intshow_num();charmenu(intdeq&ideq);voiddelete_dequenum(intdeq&ideq,intrani){booljud=0;if(ran1==0){for(inti=0;i<ii;i++){if(num[i]==ideq.front())//deq.front()返回第一个元素(不检测容器是否为空)jud=1;if(jud==1){num[i]=num[i+1];))if(jud==1)num[ii]=0;ideq.pop_front();//deq.pop_front()删除第一个元素)elseif(rani==1){for(inti=0;i<ii;i++){if(num[i]==ideq.back())〃deq.back()返回最后一个元素(不检测容器是否为空)jud=1;if(jud==1)num[i]=num[i+1];)if(jud==1)num[ii]=0;ideq.pop_back();〃删除最后一个元素)ii--;)voiddeque_num(intdeq&ideq,intnum){inti=0;//cout<<“test"<<endl;if(num<ideq.front())ideq.push_front(num);elseif(num>ideq.back())ideq.push_back(num);else{deque<int>::iteratordeqIt;deqIt=ideq.begin();while(num>ideq[i]){deqIt++;i++;)ideq.insert(deqIt,num);))voidshow_deque(intdeq&ideq){system("cls");cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;if(ideq.empty())cout<<"\t现在没有人排队。"<<endl;else{cout<<〃\t当前正在排队中的编号有:〃；copy(ideq.begin(),ideq.end(),screen);)cout<<endl<<"\t";system("pause");)intshow_num(intdeq&ideq){system("cls");srand((unsigned)time(NULL));intrnum=rand()%100+1;num[ii]=rnum;for(intj=0;j<ii;j++){if(rnum==num[ii])rnum=rand()%100+1;)ii++;cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<"\t您的编号为:"<<rnum<<endl;cout<<endl<<"\t";system("pause");returnrnum;)voidshow_command(intdeq&ideq){ran=rand()%2;system("cls");cout<<endl<<endl;cout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*,,〃**;cout<<〃* 购票系统*”;TOC\o"1-5"\h\zcout <<”*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*