毕业设计-数据结构排队购票问题.doc

东北大学信息科学与工程学院
数据结构课程设计报告

题目 排队购票问题

课题组长 侯永跃
课题组成员 林浩成 李博然 韩硕
专业名称 计算机科学与技术

班级 计1307

指导教师 杨雷

2015 年 1月
课程设计任务书
题目：
排队购票问题
问题描述：
欧洲杯足球赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销售，售票处决定采用如下售票规则：
（1）购票者到购票处领取一个随机编号。
（2）购票者按随机编号从小到大排序。
（3）随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。
（4）售票窗口空闲时随机发出0或1指令，指令为0时，最小编号者到窗口购票，指令为1时，最大编号者到窗口购票。

设计要求：
设计算法实现按上述规则的排队售票程序。
（1）采用STL的双端队列等数据结构。
（2）实现STL的双端队列类deque。
（3）尝试采用不同数据结构的多种解法。

指导教师签字：
2015年1月4日
目录
1 课题概述 5
1.1 课题任务 5
1.2 课题原理 5
1.3 相关知识 5
2 需求分析 6
2.1 课题调研 6
2.2 用户需求分析 6
3 方案设计 7
3.1 总体功能设计 7
3.2 数据结构设计 7
3.3 函数原型设计 7
3.4 主算法设计 7
3.5 用户界面设计 7
4 方案实现 9
4.1 开发环境与工具 9
4.2 程序设计关键技术 9
4.3 个人设计实现 9
4.3.1 侯永跃设计实现 9
4.3.2 李博然设计实现 12
4.3.3 林浩成设计实现 13
4.3.4 韩硕设计实现 13
5 测试与调试 15
5.1 个人测试 15
5.1.1 侯永跃测试 15
5.1.2 李博然测试 15
5.1.3 林浩成测试 16
5.2 组装与系统测试 17
5.3 系统运行 18
6 课题总结 21
6.1 课题评价 21
6.2 个人设计小结 21
6.2.1 侯永跃设计小结 21
6.2.2 李博然设计小结 21
6.2.3 林浩成设计小结 21
6.2.4 韩硕设计小结 21
7 附录A 课题任务分工
A-1 课题程序设计分工 22
A-2 课题报告分工 23
附录B 课题设计文档（光盘） 附
B-1课程设计报告（电子版）
B-2源程序代码（*.H，*.CPP） 24
B-3工程与可执行文件 附 1 课题概述
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.随机数的生成。通过随机数的生成，实现给购票者分配一个随机编号、售票窗口发出随机指令等操作。
2 需求分析

2.1 课题调研：
1.为购票者分配随机编号（范围定为1-100）。
2.将分配到的编号插入队列，使队列中的元素顺序为从小到大。
3.查看队列。
4.随机发出指令0或1。0时，移出最小编号；1时，移出最大编号。

2.2 用户需求分析：
1.随机分配给购票者编号。
2.能够从分配出的编号中选出最小编号和最大编号。
3.随机给出0或1指令。
3 方案设计
3.1 总体功能设计：
本程序主要实现三个功能：为购票者分配随机编号，售票窗口发出随机指令，查看正在队列中的编号。
为购票者分配编号需要用到随机函数，分配完毕之后插入队列。
将随机数依次与队列元素比较，找到合适的“位置”后插入到指针后面
3.2 数据结构设计：
本程序使用STL的双端队列类deque。主要涉及操作有push_front()、push_back()、insert()、begin()、end()、pop_front()、pop_back()。
3.3 函数原型设计：
delete_dequenum(intdeq &ideq, int ran1)实现指令的刷新，提醒当次排号购票
deque_num(intdeq &ideq, int num)实现插入元素位置查找和队列元素的增添
show_deque(intdeq &ideq)：用于输出正在队列中的编号，若队列为空，则输出无人排队。
show_num()：用于为购票者分配编号，编号为1-100之间的随机数。
show_command(intdeq &ideq)：用于显示售票窗口指令。
menu_back(intdeq &ideq, int &num, char cmd)，menu()：主菜单。

3.4 主算法设计 ：
随机数的生成：使用srand()提供种子数，再使用rand()函数生成随机数。
队列的操作部分：查找、增添、删除
界面部分：随机数和队列的显示
3.5 用户界面设计：
主菜单：

分配编号：

查看队列：

输出指令：

4 方案实现
4.1 开发环境与工具：
开发环境：Windows操作系统
开发工具：VC++6.0
4.2 程序设计的关键技术：
STL的双端队列结构。
4.3 个人设计实现：
4.3.1 侯永跃设计实现：
主要负责主界面的设计，随机编号的生成。
void show_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到end
cout << endl << "\t";
system("pause");
}

int show_num()
{
system("cls");
srand((unsigned)time(NULL));
int rnum=rand() % 100 + 1; //生成随机数，范围1-100
num[ii]=rnum;
for(int j=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");

return rnum;
}

void show_command(intdeq &ideq)//输出售票窗口的指令。
{
ran = rand() % 2;
system("cls");
cout << endl << endl;
cout << "********************************************************************************";
cout << "* 购票系统 *";
cout << "********************************************************************************";
cout << "--------------------------------------------------------------------------------";
cout << "| " << ran << " |";
cout << "--------------------------------------------------------------------------------";
if (!ideq.empty())
{
if (ran == 0)
cout << "\t请编号" << ideq.front() << "的乘客到窗口购票." << endl;
else if (ran == 1)
cout << "\t请编号" << ideq.back() << "的乘客到窗口购票." << endl;
delete_dequenum(ideq, ran); //将该编号移出队列
}
else
cout << "\t当前窗口没有人排队." << endl;
cout << "\t";
system("pause");
}

void menu_back(intdeq &ideq, int &num, char cmd) //主菜单选项的处理
{
if (cmd == 'n' || cmd == 'N')
{
num = show_num();
deque_num(ideq, num);
}
else if (cmd == 'l' || cmd == 'L')
show_deque(ideq);
else if (cmd == 'r' || cmd == 'R')
show_command(ideq);
}

int main()
{
char cmd;
int num;
intdeq ideq;

srand(time(0));

while (1)
{
cmd = menu();
menu_back(ideq, num, cmd);
if (cmd == 'e' || cmd =='E')
break;
}
return 0;
}

4.3.2 李博然设计实现：
队列元素位置查找和元素增添
void deque_num(intdeq &ideq, int num)
{
int i = 0;
//cout << "test" << endl;
if(num < ideq.front())
ideq.push_front(num);
else if (num > ideq.back())
ideq.push_back(num);
else
{
deque<int>::iterator deqIt;
deqIt = ideq.begin();
while (num > ideq[i])
{
deqIt++;
i++;
}
ideq.insert(deqIt, num);
}
number++;
}

4.3.3 林浩成设计实现：
刷新指令及双端队列的元素移除。
void delete_dequenum(intdeq &ideq, int ran1)
{
bool jud = 0;
if (ran1 == 0)
{
for (int i=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()删除第一个元素

}
else if (ran1 == 1)
{
for (int i=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--;
}
4.3.4 韩硕设计实现：
主要负责主菜单
char menu()
{
char cmd;

system("cls");
cout << endl << endl;
cout << "********************************************************************************";
cout << "* 购票系统 *";
cout << "********************************************************************************";
cout << "\t按n键领取编号." << endl;
cout << "\t按r键刷新指令." << endl;
cout << "\t按l键查看队列." << endl;
cout << "\t按e键退出." << endl;
cin >> cmd;

return cmd;
}

5 测试与调试
5.1 个人测试
5.1.1 侯永跃个人测试
主要测试生成的随机数有无重复，界面间的转换有没有问题。

几组测试后，发现在数量小于100的情况下，随机数无重复现象。界面衔接的也很好。
5.1.2李博然个人测试

通过随机摇号删除一个头（尾）节点之后的队列

5.1.3林浩成个人测试

5.2 组装与系统测试
为了测试组装之后的程序是否可用，方便起见，在分配编号和指令两个界面分别输出操作前后双端队列的状态。

测试结果显示双端队列能够正常工作。
5.3系统运行

领取编号：

查看队列：

售票窗口发出指令：

发出指令后删除对应的编号

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

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 韩硕设计心得
侯永跃
林浩成
李博然
韩硕

附录B 源代码
#include <iostream>
#include <deque>
#include <windows.h>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <time.h>
using namespace std;

typedef deque<int> intdeq;
ostream_iterator<int> screen(cout, " ");//屏幕显示

unsigned int number = 0;
int num[100];
int ran;
int ii;

void delete_dequenum(intdeq &ideq, int ran1);
void deque_num(intdeq &ideq, int num);
void show_deque(intdeq &ideq);
int show_num();
char menu(intdeq &ideq);

void delete_dequenum(intdeq &ideq, int ran1)
{
bool jud = 0;
if (ran1 == 0)
{
for (int i=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()删除第一个元素

}
else if (ran1 == 1)
{
for (int i=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--;
}

void deque_num(intdeq &ideq, int num)
{
int i = 0;
//cout << "test" << endl;
if(num < ideq.front())
ideq.push_front(num);
else if (num > ideq.back())
ideq.push_back(num);
else
{
deque<int>::iterator deqIt;
deqIt = ideq.begin();
while (num > ideq[i])
{
deqIt++;
i++;
}
ideq.insert(deqIt, num);
}
}

void show_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);
}
cout << endl << "\t";
system("pause");
}

int show_num(intdeq &ideq)
{
system("cls");
srand((unsigned)time(NULL));
int rnum=rand() % 100 + 1;
num[ii]=rnum;
for(int j=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";
system("pause");

return rnum;
}

void show_command(intdeq &ideq)
{
ran = rand() % 2;

system("cls");
cout << endl << endl;
cout << "********************************************************************************";
cout << "* 购票系统 *";
cout << "********************************************************************************";
cout << "--------------------------------------------------------------------------------";
cout << "| " << ran << " |";
cout << "--------------------------------------------------------------------------------";
if (!ideq.empty())
{
if (ran == 0)
cout << "\t请编号" << ideq.front() << "的乘客到窗口购票." << endl;
else if (ran == 1)
cout << "\t请编号" << ideq.back() << "的乘客到窗口购票." << endl;
delete_dequenum(ideq, ran);
}
else
cout << "\t当前窗口没有人排队." << endl;
cout << "\t";
system("pause");
}

void menu_back(intdeq &ideq, int &num, char cmd)
{
if (cmd == 'n' || cmd == 'N')
{
num = show_num(ideq);
deque_num(ideq, num);
}
else if (cmd == 'l' || cmd == 'L')
show_deque(ideq);
else if (cmd == 'r' || cmd == 'R')
show_command(ideq);
}

char menu()
{
char cmd;

system("cls");
cout << endl << endl;
cout << "********************************************************************************";
cout << "* 购票系统 *";
cout << "********************************************************************************";
cout << "\t按n键领取编号." << endl;
cout << "\t按r键刷新指令." << endl;
cout << "\t按l键查看队列." << endl;
cout << "\t按e键退出." << endl;
cin >> cmd;

return cmd;
}

int main()
{
char cmd;
int num;
intdeq ideq;

srand(time(0));

while (1)
{
cmd = menu();
menu_back(ideq, num, cmd);
if (cmd == 'e' || cmd =='E')
break;
}
return 0;
}

附录C 操作说明
操作环境：Windows 7/8/xp
操作说明：见主菜单

30