杨瑶组排队购票问题.doc

《杨瑶组排队购票问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计报告题目排队购票问题课题组长杨瑶课题组成员张祎王梅冲专业名称物联网工程班级物联网1201指导教师孟凡荣课程设计任务书题目：排队购票问题问题描述：欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：（1）购票者到购票处领取一个随机编号。（2）购票者按随机编号从小到大排序。（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。设计

2、要求：设计算法实现按上述规则的排队售票程序。（1）采用STL的双端队列等数据结构。（2）实现STL的双端队列类deque。（3）尝试采用不同数据结构的多种解法。　　　　　　　　　　　　指导教师签字：2014年月日目录1课题概述51.1课题任务51.2课题原理51.3相关知识52需求分析62.1课题调研62.2用户需求分析63方案设计73.1总体功能设计73.2数据结构设计73.3函数原型设计83.5用户界面设计114方案实现124.1开发环境与工具124.2程序设计关键技术124.3个人设计实现（按组员分工）125测试与调试135.1个

3、人测试（按组员分工）136课题总结196.1课题评价196.2团队协作196.3个人设计小结（按组员分工）197附录课题程序设计分工学号姓名程序设计函数原型、类功能说明20124078杨瑶voidinitque(que&q)voidkuaipai(que&q,intlow,inthigh)intpai(que&q,intlow,inthigh)//杨瑶1.创建双端队列2.将购票者根据随机号码进行从小到大的快速排序20124080张祎voidCMyDlg::Ongoupiao()读取购票人数n，设置时间种子，给每个人一个0~n-1的随机号

4、码，将号码显示在列表框中，并进行快速排序20124077王梅冲voidCMyDlg::Onjieguo()利用时间种子随机发出0或1的信号，将购票者的信息显示在列表框中课题报告分工章节内容完成人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个人设计实现（按组员分工）杨瑶、王梅冲、张祎5测试与调试5.1个

5、人测试（按组员分工）5.2系统运行杨瑶、王梅冲、张祎6课题总结6.1课题评价6.2团队协作6.3个人设计心得（按组员分工）杨瑶、王梅冲、张祎1课题概述1.1课题任务以公平公正的原理，写出一个运用随机数，利用双端队列，实现购票的购票程序。1.2课题原理因为要或以号码最小，或以号码最大输出结果，所以我们利用快速排序对购票者号码进行排序，然后用队列存储，实现头尾输出。其次在随机数中，为了尽量使随机数随机，我们选用时间作为随机种子。1.3相关知识1.双端队列：队列尾插入数据，头尾皆可删除数据2.快速排序是选择排序的一种算法，最好情况下复杂度可为

6、nlogn，最坏情况下时间复杂度为n的平方。2.随机数：用srand（）函数创建种子，rand（）函数得出随机数。2需求分析2.1课题调研因为现实生活中，该种购票模式较少，所以无法从现实生活中调研，我们通过组内讨论，确定该购票程序至少需要：1.实现随机号码分配：利用随机数，给每一个购票者一个随机号码2.实现随机信号0，1，获得购票结果：利用随机号码，0则最小号码购票，1则最大号码购票2.2用户需求分析购票系统的要求主要由以下几部分构成：1.分配号码：以公平公正为原则，利用随机数，给每一个购票者一个随机号码2.购票结果：实现随机信号0，1

7、，获得购票结果，将购票结果在列表框显示。3方案设计3.1总体功能设计1.分配号码：以时间做种子，给每个购票者一个随机号码，进行快速排序，以队列存储2.购票结果：以时间为种子设立0，1随机信号，0则队头输出，1则队尾输出，结果显示在列表框中3.2数据结构设计主要运用了双端队列的数据结构。具体类型如下：typedefstruct{intno,num;}term;typedefstruct{term*base;inthead,tail;}que;程序设计流程：开始读入购票者n产生随机号码产生随机信号并输出结果结束3.3函数原型设计分配号码函数

8、voidCMyDlg::Ongoupiao()//张祎{//TODO:Addyourcontrolnotificationhandlercodehereinti,n;CStrings1="第",strtem