《数据结构课程设计《排队购票问题》》由会员分享，可在线阅读，更多相关《数据结构课程设计《排队购票问题》（23页珍藏版）》请在金锄头文库上搜索。
1、- 1 -2014-1-72014-1-7 东北大学信息科学与工程学院东北大学信息科学与工程学院数据结构课程设计报告数据结构课程设计报告题目 排队购票问题课题组长 XXX课题组成员 XX XXX专业名称 计算机科学与技术班级 计算机 1206指导教师 杨雷2014 年 1 月- 2 -题目：题目：排队购票问题 问题描述：问题描述：欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全 的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购 票。（4）售票窗口空闲时
2、随机发出 0 或 1 指令，指令为 0 时，最小编号者到窗口 购票，指令为 1 时，最大编号者到窗口购票。设计要求：设计要求：设计算法实现按上述规则的排队售票程序。（1）采用 STL 的双端队列等数据结构。（2）实现 STL 的双端队列类 deque。（3）尝试采用不同数据结构的多种解法。指导教师签字：指导教师签字：年年 月月 日日- 3 -目录目录1 1 课题概述课题概述11.11.1 课题任务课题任务11.21.2 课题原理课题原理11.31.3 相关知识相关知识32 2 需求分析需求分析42.12.1 课题调研课题调研42.22.2 用户需求分析用户需求分析53 3 方案设计方案设计73
3、.13.1 总体功能设计总体功能设计73.23.2 数据结构设计数据结构设计83.33.3 函数原型设计函数原型设计.103.43.4 主算法设计主算法设计.123.53.5 用户界面设计用户界面设计.144 4 方案实现方案实现.154.14.1 开发环境与工具开发环境与工具.154.24.2 程序设计关键技术程序设计关键技术.164.34.3 个人设计实现（按组员分工）个人设计实现（按组员分工）4.3.14.3.1 XXXX 设计实现设计实现 174.3.24.3.2 XXXXXX 设计实现设计实现 .194.3.34.3.3 XXXXXX 设计实现设计实现 .215 5 测试与调试测试与
4、调试.235.15.1 个人测试（按组员分工）个人测试（按组员分工）.235.1.15.1.1 XXXX 测试测试 235.1.25.1.2 XXXXXX 测试测试 .265.1.35.1.3 XXXXXX 测试测试 .30- 4 -5.25.2 组装与系统测试组装与系统测试.335.35.3 系统运行系统运行.366 6 课题总结课题总结.396.16.1 课题评价课题评价.396.26.2 团队协作团队协作.406.36.3 团队协作团队协作.416.46.4 个人设计小结（按组员分工）个人设计小结（按组员分工）.426.4.16.4.1 XXXX 设计小结设计小结 426.4.26.4.
5、2 XXXXXX 设计小结设计小结 .456.4.36.4.3 XXXXXX 设计小结设计小结 .487 7 附录附录 A A 课题任务分工课题任务分工 50A-1A-1 课题程序设计分工课题程序设计分工.50A-2A-2 课题报告分工课题报告分工.51附录附录 B B 课题设计文档（光盘）课题设计文档（光盘） 52B-1B-1 课程设计报告（电子版）课程设计报告（电子版） .52B-2B-2 源程序代码（源程序代码（*.H*.H，*.CPP*.CPP） .52B-3B-3 工程与可执行文件）工程与可执行文件） .52 B-4B-4 屏幕演示录像文件（可选）屏幕演示录像文件（可选） .52 附
6、录附录 C C 用户操作手册（可选）用户操作手册（可选） 53C.1C.1 运行环境说明运行环境说明.53C.2 操作说明54- 5 -1 1 课题概述课题概述1.11.1 课题任务课题任务欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。（4）售票窗口空闲时随机发出 0 或 1 指令，指令为 0 时，最小编号者到窗口购票，指令为 1 时，最大编号者到窗口购票。1.2 课题原理以及相关知识课题原理以及相
7、关知识设计算法实现按上述规则的排队售票程序。 （1）采用 STL 的双端队列等数据结构。 （2）实现 STL 的双端队列类 deque。（3）尝试采用不同数据结构的多种解法。 2 系系统统需需求求分分析析只需对来购票的人进行合理公平的随机分配即可，然后进行取票。开发环境：PC 机Windows XP 系统使用软件：编写实验报告： Microsoft Office Word画 图：陈柯铮制 作 程 序：Microsoft Visual C+ 6.0- 6 -3 算算法法流流程程开始初始化票数大于人 数利用随机函数进行分配公布售票结果结束- 7 -4 4 方案实现与关键技术方案实现与关键技术双端队
8、列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点 1 和端点 2（如下图(a)所示） 。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列，如下图(b)所示。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列） 。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。双端队列就是一个两端都是结
9、尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫作 insertLeft()和 insertRight()，以及removeLeft()和 removeRight()。如果严格禁止调用 insertLeft()和removeLeft()方法（或禁用右段的操作） ，双端队列功能就和栈一样。禁止调用insertLeft()和 removeRight()（或相反的另一对方法） ，它的功能就和队列一样了。双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。5 5 程序实现程序实现5.15.1 个人程序实现个人程序实现5.1.15.1.1
10、 杨兵杨兵程序实现程序实现void OP1(deque PTR+;Data.pop_front();PeopleCount-;TicketCount-;- 8 -coutPTR+;Data.pop_back();PeopleCount-;TicketCount-;coutint MakeSrand(int x,int y);/产生 xy 随机数的函数,不包括 yvoid OP1(dequevoid OP2(deque- 10 -void OP3(dequevoid DisplayResult(int* Result);/展示购票结果void InStack(int* Stack,int Ele
11、ment);/辅助栈的进栈函数int OutStack(int* Stack);/辅助栈的出栈函数int PTR=0;/结果数组 Result 的游标int POP=-1;/辅助栈的顶指针void InStack(int* Stack,int Element)POP+;StackPOP=Element;int OutStack(int* Stack)POP-;return StackPOP+1;5.1.35.1.3 陈柯铮程序实现陈柯铮程序实现void main()srand(unsigned)time(NULL); /随机种子,这行语句必须放在主函数中，切记/-int PeopleCount
12、;/初始化排队人数和总票数int TicketCount;printf(“tt=n“); printf(“tt* *n“);printf(“tt* *n“);- 11 -printf(“tt*请输入排队购票的人数和总票数,以空格隔开*n“);printf(“tt* *n“);printf(“tt* *n“);printf(“tt=n“);cinPeopleCountTicketCount;/-const int MAX=(PeopleCountTicketCount?PeopleCount:TicketCount);/根据具体人数和票数判断情形并构造辅助数据结构int MIN=(PeopleC
13、ountTicketCount?1:2);/情形 1:人多票少;情形 2:票多人少.int* Result=new intMAX;/构建结果数组,存放购票结果int* Stack=new intPeopleCount;/构建辅助栈,辅助 OP3 函数的操作/-deque Data;/构建队列并给队列中的每一个人编号int i;cout- 17 -#include#include#include#include #include /搜索#include using namespace std;int MakeSrand(int x,int y);/产生 xy 随机数的函数,不包括 yvoid O
14、P1(dequevoid OP2(dequevoid OP3(dequevoid DisplayResult(int* Result);/展示购票结果void InStack(int* Stack,int Element);/辅助栈的进栈函数int OutStack(int* Stack);/辅助栈的出栈函数int PTR=0;/结果数组 Result 的游标int POP=-1;/辅助栈的顶指针void main()srand(unsigned)time(NULL); /随机种子,这行语句必须放在主函数中，切记/-int PeopleCount;/初始化排队人数和总票数int TicketCount;printf(“tt=n“); printf(“t
