数据结构排队购票问题

如有帮助欢迎下载支持东北大学信息科学与工程学院数据结构课程设计报告题目 排队购票问题课题组长 侯永跃课题组成员 林浩成李博然 韩硕专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015年1月1如有帮助欢迎下载支持课程设计任务书题目：排队购票问题问题描述：欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：1）购票者到购票处领取一个随机编号。2）购票者按随机编号从小到大排序。3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。设计要求：设计算法实现按上述规则的排队售票程序。1）采用STL的双端队列等数据结构。2）实现STL的双端队列类deque。3）尝试采用不同数据结构的多种解法。指导教师签字：2015年1月4日2如有帮助欢迎下载支持目录1课题概述 51.1课题任务1.2课题原理1.3相关知识

...................................................5...................................................5...................................................52需求分析......................................................62.1课题调研...................................................62.2用户需求分析..............................................63方案设计......................................................73.1总体功能设计3.2数据结构设计3.3函数原型设计

..............................................7..............................................7..............................................73.4主算法设计 73.5用户界面设计 74方案实现 94.1开发环境与工具 94.2程序设计关键技术 94.3个人设计实现 9 侯永跃设计实现 李博然设计实现

.....................................9....................................12 林浩成设计实现 13 韩硕设计实现 13测试与调试5.1个人测试

..................................................15..................................................15 侯永跃测试 李博然测试 林浩成测试

.........................................15.........................................15.........................................163如有帮助欢迎下载支持5.2组装与系统测试 175.3系统运行 186课题总结 216.1课题评价 216.2个人设计小结 21 侯永跃设计小结 李博然设计小结 林浩成设计小结

....................................21....................................21....................................21 韩硕设计小结 217附录A课题任务分工A-1课题程序设计分工 22A-2课题报告分工 23附录B课题设计文档（光盘）B-1课程设计报告（电子版）

............................ 附................................B-2源程序代码（*.H，*.CPP） 24B-3工程与可执行文件. 附4如有帮助欢迎下载支持课题概述1.1课题任务欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。要求：设计算法实现按上述规则的排队售票程序。（1）采用STL的双端队列等数据结构。（2）实现STL的双端队列类deque。（3）尝试采用不同数据结构的多种解法。1.2课题原理读取文件中的字符串，统计串中各字符出现的次数，成为权值，之后构建最优二叉树进行编码。再将串中字符与编码匹配，输出编码字符串，之后每八位用底层字符进行压缩。每次有观众领取编号，利用随机数输出一个1~100之间随机的一个数。按从小到大的顺序插入双端队列，售票窗口随机发出0或1指令，指令为0时，最小编号出队列，指令为1时，最大编号出队列。1.3相关知识1.STL的双端队列。利用STL的双端队列deque类，实现随机编号的入队列、出队列。2.随机数的生成。通过随机数的生成，实现给购票者分配一个随机编号、售票窗口发出随机指令等操作。5如有帮助欢迎下载支持需求分析2.1课题调研：为购票者分配随机编号（范围定为1-100）。将分配到的编号插入队列，使队列中的元素顺序为从小到大。查看队列。随机发出指令0或1。0时，移出最小编号；1时，移出最大编号。2.2用户需求分析：随机分配给购票者编号。能够从分配出的编号中选出最小编号和最大编号。随机给出0或1指令。6如有帮助欢迎下载支持方案设计3.1总体功能设计：本程序主要实现三个功能：为购票者分配随机编号，售票窗口发出随机指令，查看正在队列中的编号。为购票者分配编号需要用到随机函数，分配完毕之后插入队列。将随机数依次与队列元素比较，找到合适的“位置”后插入到指针后面3.2数据结构设计：本程序使用STL的双端队列类deque。主要涉及操作有push_front()、push_back()、insert()、begin()、end()、pop_front()、pop_back()。3.3函数原型设计：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()：主菜单。3.4主算法设计 ：随机数的生成：使用srand()提供种子数，再使用rand()函数生成随机数。队列的操作部分：查找、增添、删除界面部分：随机数和队列的显示3.5用户界面设计：主菜单：7如有帮助欢迎下载支持分配编号：查看队列：输出指令：8如有帮助欢迎下载支持9如有帮助欢迎下载支持方案实现4.1开发环境与工具：开发环境：Windows操作系统开发工具：VC++6.04.2程序设计的关键技术：STL 的双端队列结构。4.3个人设计实现： 侯永跃设计实现：主要负责主界面的设计，随机编号的生成。voidshow_deque(intdeq&ideq)// 显示正在排队的购票者的编号{system("cls");cout<<endl<<endl;cout<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";if(ideq.empty())cout<<"\t 现在没有人排队。 "<<endl;else{cout<<"\t 当前正在排队中的编号有 :";copy(ideq.begin(),ideq.end(),screen);// 输出队列 ideq中的元素，从} //begin 到endcout<<endl<<"\t";system("pause");}intshow_num(){system("cls");srand((unsigned)time(NULL));intrnum=rand()%100+1; // 生成随机数，范围 1-100num[ii]=rnum;10如有帮助欢迎下载支持for(intj=0;j<ii;j++){if(rnum==num[ii])rnum=rand()%100+1;}ii++;cout<<endl<<endl;cout<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";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 <<"********************************************************************************";cout << "* 购票系统*";cout <<"********************************************************************************";cout <<"--------------------------------------------------------------------------------";cout <<"| " <<ran <<"|";cout <<"------------------------------------------------------------------------------11如有帮助欢迎下载支持--";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;12如有帮助欢迎下载支持} 李博然设计实现：队列元素位置查找和元素增添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,intran1){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];}13如有帮助欢迎下载支持}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<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";cout<<"\t 按n键领取编号."<<endl;cout<<"\t 按r键刷新指令."<<endl;cout<<"\t 按l键查看队列."<<endl;cout<<"\t 按e键退出."<<endl;14如有帮助欢迎下载支持cin>>cmd;returncmd;}15如有帮助欢迎下载支持测试与调试5.1个人测试 侯永跃个人测试主要测试生成的随机数有无重复，界面间的转换有没有问题。几组测试后，发现在数量小于 100的情况下，随机数无重复现象。界面衔接的也很好。李博然个人测试16如有帮助欢迎下载支持通过随机摇号删除一个头（尾）节点之后的队列林浩成个人测试17如有帮助欢迎下载支持5.2组装与系统测试为了测试组装之后的程序是否可用，方便起见，在分配编号和指令两个界面分别输出操作前后双端队列的状态。18如有帮助欢迎下载支持测试结果显示双端队列能够正常工作。5.3系统运行19如有帮助欢迎下载支持领取编号：查看队列：售票窗口发出指令：20如有帮助欢迎下载支持发出指令后删除对应的编号21如有帮助欢迎下载支持课题总结6.1课题评价做完这次的程序设计之后，我们组的成员都感觉STL使用起来非常方便，节省了大量的设计抽象数据结构的时间。通过这个实验我们了解了STL模板的使用，当然更重要的是积累了小组合作编程的经验。6.2个人设计总结 侯永跃个人总结通过这次编程，我发现STL模板库的确非常好用，数量众多的库函数给我们的编程带来了很多便利。诚然我们可以手动设计数据结构，但那样的效率显然不能和直接使用STL库相比。因此学习STL的使用还是很有必要的。在学习编程语言的过程中也应当注意把几种不同的方法相比较，在应用的时候选择效率高的一种。 李博然个人总结这次编程使用的C++模板类是首次接触，在查阅大量资料后发现STL确实在很多方面能简化编程，节省代码量，甚至比A类题目编程起来还要简单，但是STL还有很多功能我们还没有了解到，希望能在以后的编程中深入学习提升自己的编程能力。本次我主要负责的是队列的增添和查找，在以前自己写是很复杂的但这次用很短的代码就实现了，所以希望以后能够学习自用，在编程中考虑更多的应该是算法的复杂度和效率而不应该是如何写一段代码，这样才能真正提升编程能力。 林浩成个人总结在此次课程设计中， STL的运用让整个编程效率提高了很多，这让我们体会到了标准模板库的价值所在， 学习标准模板库或是别的模板库， 甚至是形成自己的编程习惯都是相当重要的， 是一个程序员必须要掌握的基本素质。 代码的规范性，高效性和兼容性都是衡量代码是否质量上乘的重要参数之一， 在学习的路上，我们也要格外注意这些小的习惯，培养好的习惯是为建立程序大厦所打好的坚实基础。 韩硕个人总结这次B类实验，我们在时间极其短暂的情况下，完成了对 STL的学习并实现了程序的设计，我觉得团队的力量是尤为重要的，然而这其中也体现了我编程能力上的不足，希望今后可以加强对编程能力的锻炼。22如有帮助欢迎下载支持7附录7.1附录A课题任务分工A-1课题程序设计分工学号姓名程序设计函数原型、类功能说明show_deque(intdeq&ideq)，show_num(intdeq&ideq)，20133981show_command(intdeq&ideq)，主界面及各个功能界面，随侯永跃&ideq,intmenu_back(intdeq机编号和随机指令的生成&num,charcmd)，menu()，main()20133983deque_num(intdeq&ideq,int查找位置和入队列李博然num)Voiddelete_dequenum(intdeq刷新指令及双端队列的元&ideq,intran1)素移除20131364林浩成23如有帮助欢迎下载支持A-2课题报告分工章节内容完成人1课题概述1.1课题任务1.2课题原理侯永跃1.3相关知识2需求分析2.1课题调研侯永跃2.2用户需求分析3方案设计3.1总体功能设计侯永跃3.2数据结构设计林浩成3.3函数原型设计李博然3.4主算法设计韩硕3.5用户界面设计4方案实现4.1开发环境与工具4.2程序设计关键技术侯永跃4.3个人设计实现（按组员分工）林浩成4.3.1侯永跃设计实现李博然4.3.2李博然设计实现韩硕4.3.3林浩成设计实现4.3.4韩硕设计实现5测试与调试5.1个人测试（按组员分工）5.1.1侯永跃个人测试侯永跃5.1.2李博然个人测试林浩成5.1.3林浩成个人测试李博然5.2组装与系统测试5.3系统运行6课题总结6.1课题评价6.2团队协作6.3下一步工作侯永跃6.4个人设计心得（按组员分工）林浩成6.4.1侯永跃设计心得李博然6.4.2李博然设计心得韩硕6.4.3林浩成设计心得6.4.4韩硕设计心得24如有帮助欢迎下载支持附录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,intran1);voiddeque_num(intdeq&ideq,intnum);voidshow_deque(intdeq&ideq);intshow_num();charmenu(intdeq&ideq);voiddelete_dequenum(intdeq&ideq,intran1){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() 删除第一个元素25如有帮助欢迎下载支持}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--;}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");26如有帮助欢迎下载支持cout<<endl<<endl;cout<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";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<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";cout<<"\t 您的编号为:"<<rnum<<endl;27如有帮助欢迎下载支持cout<<endl<<"\t";system("pause");returnrnum;}voidshow_command(intdeq&ideq){ran=rand()%2;system("cls");cout<<endl<<endl;cout<<"********************************************************************************";cout << "* 购票系统*";cout<<"********************************************************************************";cout <<"---------------------------------