数据结构课程设计排队购票问题

《数据结构课程设计排队购票问题》由会员分享，可在线阅读，更多相关《数据结构课程设计排队购票问题（25页珍藏版）》请在装配图网上搜索。

1、2014-1-7东北大学信息科学与工程学院数据结构课程设计报告题目排队购票问题课题组长XXX课题组成员XX XXX专业名称计算机科学与技术班级计算机1206指导教师杨雷2014年1月题目:排队购票问题问题描述：欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的 销售，售票处决定釆用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购o（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购 票，指令为1时，最大编号者到窗口购票。设计要求:设计算法实现按上述规则的排

2、队售票程序。（1）釆用STL的双端队列等数据结构。（2）实现STL的双端队列类dequeo（3）尝试采用不同数据结构的多种解法。指导教师签字：年 月曰目录1课题概述1.1课题任务1. 2课题原理1.3相关知识32需求分析42. 1课题调研42.2用户需求分析53方案设计73.1总体功能设计73.2数据结构设计8103. 3函数原型设计3.4主算法设计123.5用户界面设计144方案实现154- 1开发环境与工具 154.2程序设计关键技术164.3个人设计实现（按组员分工）4. 3.1 XX设计实现174. 3.2 XXX设计实现 194. 3.3 XXX设计实现215测试与调试235. 1个

3、人测试（按组员分工） 235. 1.1 XX 测试235. 1.2 XXX 测试265,1. 3 XXX 测试305.2组装与系统测试335.3系统运行36396课题总结6. 1课题评价396.2团队协作406.3团队协作416.4个人设计小结（按组员分工） 426. 4. 1 XX设计小结426. 4. 2 XXX设计小结456. 4. 3 XXX设计小结487附录A课题任务分工50A-1课题程序设计分工 50A-2课题报告分工 51附录B课题设计文档（光盘） 52B-1课程设计报告（电子版） 52B-2源程序代码(*. H, *CPP)52-5-#52B-4屏幕演示录像文件（可选）52附录

4、C用户操作手册（可选）53C. 1运行环境说明53C.2操作说明54B-3工程与可执行文件）-#1课题概述1.1课题任务欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的 销售，售票处决定釆用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队 购票。（4）售票窗II空闲时随机发出0或1指令，指令为0时，最小编号者到窗II购票，指 令为1时，最人编号者到窗II购票。1.2课题原理以及相关知识设计算法实现按上述规则的排队售票程序。（1）釆用STL的双端队列等数据结构。（2）实现ST

5、L的双端队列类dequeo（3）尝试采用不同数据结构的多种解法。2系统需求分析只需对来购票的人进行合理公平的随机分配即可，然后进行取票。开发环境：PC机Windows XP 系统使用软件：编写实验报告：Microsoft Office Word画图：陈柯铮制 作 程 序：Microsoft Visual C+ 6. 0-#-3算法流程-74方案实现与关键技术双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其 限定插入和删除操作在表的两端进行。双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做 端点1和端点2 (如下图(a)所示)。也可像栈一样，可以用

6、一个铁道转轨网络來 比喻双端队列，如下图(b)所示。在实际使用中，还可以有输出受限的双端队列 (即一个端点允许插入和删除，另一个端点只允许插入的双端队列)和输入受限 的双端队列(即一个端点允许插入和删除，另一个端点只允许删除的双端队列)。 而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就 蜕变为两个栈底相邻的栈了。双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除 数据项。这些方法可以叫作insertLeft ()和insertRight (),以及removeLeft () 和 removeRight () 如果严格禁止调用 insertLeft (

7、)和 removeLeft ()方法(或 禁用右段的操作),双端队列功能就和栈一样。禁止调用insertLeft()和 removeRight ()(或相反的另一对方法)，它的功能就和队列一样了。双端队列与 栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列來提 供栈和队列两种功能。5程序实现5.1个人程序实现5. 1. 1杨兵程序实现void OPl(deque &Dataiiit* Result,iiit PeopleCount,iiit TicketCount)ResultPTR=Data.fiont();PTR+;Data.pop_fiont();PeopleCount

8、-;TicketCount;coutM通知:队首请购票Hendl;void OP2(deque&Dagint* Result,mt PeopleCount.int TicketCount) ResultPTR=Data.back();PTR+;Data.pop_back();PeopleCount-;TicketCount;cout通知:队尾请购票Hendl;void OP3(deque&Dagint* Result,mt* Stack.iiit PeopleCount.iiit TicketCount,mt* x) if(PeopleCount 今)*x;return;int p=MakeS

9、iand(l .Data.size()-1);int i;fbr(i=O;ip;i+)InStack(Stack,Data.frontO)；Data.pop_fiont();ResultPTR=Data.fiont();Data.pop_fiont();PTR+;fbr(i=O;ip;i+) Data.push_fiont(OutStack(Stack);PeopleCount-;TicketCount;coutvv”通知:当前队列中第”p+l”名顾客请购票endl;void DisplayResult(mt* Result)mt i;coutendlH获得门票人员的编号为endl;fbr(i

10、=O;iPTR;i+)if(0=i%10) coutendl;coutResultiH ”;coutendl;5. 1. 2王正海程序实现# iiiclude# iiiclude# mclude# mclude#include #include / 索#include using namespace std;mt MakeSiaiid(iiit x,mt y);/产生xy随机数的函数，不包括yvoid OPl(deque&Datcuint* Resultint,int PeopleCountjnt TicketCount);void OP2(deque&Datcuint* Resultint,

11、int PeopleCount,int TicketCount); void OP3(deque&Dagint* Result,mt* Stack.iiit PeopleCount.iiit TicketCount,mt* x);void DisplayResult(iiit* Result);/展示购票结果void InStack(int* Stack,hit Element);/辅助栈的进栈函数mt OutStack(mt* Stack)辅助栈的出栈函数mt PTR=0;结果数组Result的游标mt POP=-1;辅助栈的顶指针void InStack(int* Stack.iiit E

12、lement)POP+;StackPOP=Element;mt OutStack(iiit* Stack)POP-sreturn StackPOP+l；5. 1. 3陈柯铮程序实现void main()srand(unsigned)tune(NULL); 随机种子,这行语句必须放在主函数中，切记int PeopleCount;/初始化排队人数和总票数int TicketCount;pnntf(Mtt=aiH);请输入排队购票的人数和总票数，以空格隔开FT);E)；ciiiPeopleCouiitTicketCount;const int MAX=(PeopleCountTicketCount?

13、PeopleComit:TicketCoimt);/根据具体人数和票数判断情形并构造辅助数据结构int NIIN=(PeopleCountTicketCount? 1:2);/情形 1:人多票少;情形 2漂多人少.int* Result=new uitMAX;/构建结呆数组，存放购票结果mt* Stack=new mtPeopleCount;/构建辅助栈，辅助OP3函数的操作deque Data;/构建队列并给队列中的每一个人编号int i;coutendlH 正在构建队列,fendl;for(i= 1 ;i=PeopleCount;i-H-) Data.push_back(i);couten

14、dlH队列构建完成，正在购票Hendlendl;/int Decide/根据随机函数结呆判定摇号方式 for(i=O;iNnN ;i+)Decide=MakeSraiid(0,3)；switch(Decide)case 0:OP 1 (Data,Result,PeopleCount,TicketCount);break;/队首购票case l:OP2(Data,Result.PeopleCount,TicketCount);break;/队尾购票case 2:OP3(Data,Result,Stack,PeopleCount,TicketCount.&i);break;/ 队中随机编 号的人购

15、票switch( S ituation)/本次购票模拟结束，展示结果case 1 :coutendllf 所有门票已出 tt?,endl;break;case 2:coutendlM队列中所有人已获得门票endl;break;DisplavResult(Result);coutendl;mt MakeSiaiid(iiit x.mt v) nit n;n=rand()%(y-x);return n+x;6.1个人测试6.1. 1陈柯铮测试13*C:UsersansenDesktopsb 陈柯铮的代码DebugDeque.exe=琉青输入排队购票的人数和总票数，以空格隔开洪=搜狗拼音箱6. 1.

16、 2杨兵测试ress any key to continue 捜狗拼昔输人袪半:MV12 7 8356获得门要人员的编号为所有门票已出售队列构建完成正在嗨票正在构建队列vXC:Usersa nsenDesltopsb 陈柯铮的代码DebugDeque.exe，票票 购 请 餐 顾票票票票屯票票中票 购购购购列购购列购 主垦冃主冃土冃队青主冃队青 队队队队当当队 DDDDDDDDnL0 97. 1个人总结7.1.1陈柯铮总结在编写的时候只使用了相对较为简单的基础语言，代替了相对较为复杂的语言， 降低了运行效率。测试输入的数据也有一定的局限性，但是基本可以满足订票系 统的需求。1总体过程编译和调试

17、工具：选择Visual C+6.0,该工具稳定，其中有一个强大的调试 工具，但我不是熟悉。还需要进一步的练习。2 在一周半的时间里，不断地对程序及各模块进行修改、编译、调试、运行, 其间遇到很多问题：(1) 因本人能力有限，在编写的时候只使用了相对较为简单的基础语言， 代替了相对较为复杂的语言，降低了运行效率。(2) 程序在起初设计的时候，经常出现溢出错误，而且不只一处。为了 修正这些溢出错误，耗费了大量的时间，修正解释之后再看源程序，才发现原 來只是因为开始的函数定义的数据类型出现了问题，对函数的定义不清楚，字 符的不正确定义造成了后期大量的纠错工作，(3) 由于忘记了一些c语言的规范使得在

18、调试过程中一些错误没有发现。 例如，调用函数时，数组只需要传递数组名即可；字符0和整形的0是不同 的文明不可以直接对其画等号。(4) 测试用例具有一定的广泛性。运行程序时输入了多种不同字符信息, 经过多次修改结果达到了预期效果。说明程序具有一定的可靠性和稳定性。3 通过调试我自己认为，在哈夫曼编码译码系统中用出栈入栈进行哈夫曼译 码编码译码要简单于使用数组，而使用结构体数组來存储待编译的字符，编码 译码时通过结构体数组來实现要优于使用链表。4调试体会经过这次实习，我对调试掌握的更加熟练了，改变了过去只调试不知道如何 对照程序语言修改程序的坏习惯，对调试也有了新的认识，意识到了程序语言 的规范性

19、以及我们在编程时要有严谨的态度，同时在写程序时如果加一定量的 注释，既增加了程序的可读性，也可以使自己在读程序时更容易。7.1.2杨兵总结通过对这一课题的设计和实现，我认识到编程时要养成良好的风格，注意相 同内容的缩进和对齐。这样做，可以使程序代码出错的情况下，可以快速并且便 捷的查找到错误的行，利于很好的修改。通过这次编程我们深深的感受到对代码的变量命名，代码内注释格式，其至 嵌套中行缩进的长度和函数间的空行数字都有明确规定，良好的编写习惯，不但 有助于代码的移植和纠错，也有助于不同人员之间的协作。这个程序设计主要涉及到了数据结构中的随机函数、顺序栈及双端队列 操作等内容，只有充分掌握了这些

20、内容，才有可能组织好这些代码，使之符合运 算逻辑，得到理想的结果。善于总结，也是学习能力的一种体现，每次完成一个编程任务，完成一段 代码，都应当有目的的跟踪该程序的应用状况，随时总结，找到自己的不足，这 样所编写的程序才能逐步提高，生活就是这样，汗水预示着结果也见证着收获。 劳动是人类生存生活永恒不变的话题。通过实际动手做，我们才真正领略到“艰 苦奋斗”这一词的真正含义，我们想说，编程确实有些辛苦，但苦中也有乐，在 这个团队的任务中，一起的工作可以让我们有说有笑，相互帮助，配合默契。对 我们而言，知识上的收获重要，精神上的丰收是可喜的。挫折是一份财富，经历 是一份拥有。这次实际操作必将成为我们

21、人生旅途上一个非常美好的回忆！回顾起此次课程设计，我至今仍感慨颇多，的确，自从拿到题目到完成整 个编程，从理论到实践，在这段日子里，可以学到很多很多的东西，同时不仅可 以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通 过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远 不够的，只有把所学的理论知识与实践相结合起來，从理论中得出结论，才能真 正为社会服务，从而提高自己的实际动手能力和独立思考的能力。同时，在助教 老师的身上我学得到很多实用的知识，在此表示感谢！同时，对给过我帮助的所 有同学和指导老师再次表示忠心的感谢！71. 3王正海总结在课程结束之际，

22、我们按老师要求进行了课程设计。在课程设计的过程中, 我收获颇丰，不仅深切感受到了团队合作的优势，而且也对课堂上所学的知识有 了进一步的了解。这次的课程设计让我更熟悉了从理论到实践的跨越。从当初的查阅图书，请 教老师及同学，到现在的程序成功运行，这中间有很多值得回味的地方。记得从 儿周前开始准备的时候，我们常常在一些简单的问题上花费大量的时间。按照安排，我主要负责栈的基本操作。课程设计可以检验学生对知识的掌握程度。同时更反映了一个学生对课程设 计的态度，对待任何事都要认真，可以不会，可以做的不是最好的，但是一定要 尽自己最大的努力去完成一件哪怕再小的事。在这次课程设计中学到了很多新的 知识，同时

23、也巩固了之前学过知识。对拓扑排序有了更深的理解。虽然，最后根 据要求完成了任务，但期间还是出现了种种的问题。同时，为了更好的完成任务 还查阅了好多资料，不懂的就到处搜索，去图书馆借相应的书籍來看，锻炼了自 己查阅资料的能力。除此之外，我觉得本此课程设计最大的收获就是学会按部就班的完成任务。 首先想好用什么数据结构，主要的思想要明确的认定。然后选一个简单的例子， 按照你选定的思想，一步一步的走程序，才能更早的发现程序还存在那些没有考 虑到的缺陷。特别忌讳的是到写程序的时候，对主要思想和数据结构还不是很确 定。最后在调试程序的阶段，这次我开始用设置断点的方法，一步一步看是否达 到你要的理想结果，从

24、而來找出程序中出错的地方。还有，一种方法也是用一个 输出语句，分别放在程序的不同位置，通过输出结果，也可以快速判断出程序不 能运行的是那一个语句了。从而方便你修改，快速得到正确的结果。还有，这次 调试的过程中，我表现的比以前要更有耐心，这也是一个很好的收获。还有一 个更重要的体会就是，遇到不会的地方,我开始习惯到图书馆或是网上去找资料。 这是一个很好的学习过程，它不仅仅是可以解决这个问题，关键是你会从找资料 学习的过程中，会学好很多很多意想不到的知识。可能会比你手头上要学习的知 识多得多。8源代码# include # mclude-17 -# mclude# mclude#include #

25、include /搜索#include using namespace std;mt MakeSiaiid(iiit x,mt y);/产生xy随机数的函数，不包括yvoid OPl(deque&Dagint* Resultint,int PeopleCountjnt TicketCount);void OP2(deque&Dagint* Resultint,int PeopleCountjnt TicketCount);void OP3(deque&Dagint* Result,mt* Stack.iiit PeopleCount.iiit TicketCount,mt* x);void D

26、isplayResult(iiit* Result);/展示购票结果void InStack(int* Stack,int Element);/辅助栈的进栈函数mt OutStack(mt* Stack)辅助栈的出栈函数mt PTR=0;/结果数组Result的游标mt POP辅助栈的顶指针 void main()srand(unsigned)tiine(NULL); 随机种子,这行语句必须放在主函数中，切记/int PeopleCount;/初始化排队人数和总票数int TicketCount;pnntf(Mtt=aiH);prmtf(tt*请输入排队购票的人数和总票数，以空格隔开T);E)

27、；ciiiPeopleCouiitTicketCount;const int MAX=(PeopleCountTicketCoimt?PeopleCount:TicketCount);/根据具体人数和票数判断情形并构造辅助数据结构int NIIN=(PeopleCountTicketCount? 1:2);/情形 1:人多票少;情形 2漂多人少.int* Result=new uitMAX;/构建结呆数组，存放购票结果int* Stack=new mtPeopleCount;/构建辅助栈，辅助OP3函数的操作deque Data;/构建队列并给队列中的每一个人编号int i;coutendlH

28、 正在构建队列,fendl;for(i= 1 ;i=PeopleCount;i-H-) Data.push_back(i);coutendlH队列构建完成，正在购票Hendlendl;/int Decide/根据随机函数结呆判定摇号方式for(i=O;iNnN ;i+)Decide=MakeSraiid(03)；switch(Decide)case 0:OP 1 (Data,Result,PeopleCount,TicketCount);break;/队首购票case l:OP2(Data,Result.PeopleCount,TicketCount);break;/队尾购票case 2:OP

29、3(Data,Result,Stack,PeopleCount,TicketCount.&i);break;/ 队中随机编 号的人购票/switch(Situation)/本次购票模拟结束，展示结果case l:coutendlM所有门票己出 tt?,endl;break;case 2:coutendlM队列中所有人已获得门票Hendl;break;DisplavResult(Result);coutendl;mt MakeSiaiid(iiit x.mt v)int n;n=rand()%(y-x);return n+x;void OPl(deque &Datajnt* Result,iii

30、t PeopleCount,int TicketCount) ResultPTR=Data.fiont();PTR+;Data.pop_fiont();PeopleCount-;TicketCount-;cout*通知:队首请购票endl;void OP2(deque&Dagint* Result,iiit PeopleCount.int TicketCount)ResultPTR=Data.back();PTR+;Data.pop_back();PeopleCount-;TicketCount-;cout通知:队尾请购票”endl; void OP3(deque&Data,int* Resu

31、lt,mt* Stackiiit PeopleCount,int TicketCount,mt* x) if(PeopleCount 今)*X-；return;int p=MakeSiand(l .Data.size()-1);int i;fbr(i=O;ip;i+)InStack(Stack,Data.frontO)；Data.pop_fiont();ResultPTR=Data.fiont();Data.pop_fiont();PTR+;fbr(i=O;ip;i+) Data.push_fiont(OutStack(Stack);PeopleCount-;TicketCount-;cout

32、vv”通知:当前队列中第yp+l”名顾客请购票”endl; void DisplayResult(mt* Result)coutendlH获得门票人员的编号为,Vendl;fbr(i=O;iPTR;i+)if(0=i%10) coutendl; coutResultiH H;coutendl;void InStack(int* Stack,int Element) POP+;StackPOP=Element;mt OutStack(iiit* Stack)POP-sreturn StackPOP+l；-23 -附录AA-1课题程序设计分工学号姓名程序设计函数原型、类功能说明20123955陈柯

33、铮主函数main随机函数MakeSiand(int x,int y)主函数程序实现，需 求实现，随机模拟出售 票顺序20123971王正海栈的实现voidIiiStackint OutStack用到了栈的辅助应用20123975杨兵输出输入函数 void DisplavResult void OP1 void OP2 void OP3输入输出子函数-# -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. 14. 3.24. 3. 3杨兵王正海 陈柯铮5测试与调试5.1个人测试（按组员分工）5. 1. 15. 1.25. 1. 35.2组装与系统测试5.3系统运行陈柯铮杨兵 干正海6课题总结6. 1课题评价6.2团队协作6. 3下一步工作6.4个人设计心得（按组员分工）6. 4. 16. 4.26. 1.3王正海杨兵陈柯铮-25 -