实验二之队列.doc

1、 1 / 17数据结构实验报告学号：2015111898 姓名：许明华 专业：计算机科学与技术知识范畴：栈与队列 完成日期：2017 年 03 月 31 日实验题目：基于循环队列的排队买票模拟程序实验内容及要求：编程建立循环队列存储结构，对排队买票过程进行模拟。要求程序在控制台屏幕上显示字符菜单：1. 排队输入新到达的买票人姓名，加入买票队列中；2. 售票排队队列中最前面的人购票成功，显示信息并将其从队列中删除；3. 查看队列从队首到队尾依次列出所有正在排队买票人的姓名；4. 结束退出系统。“排队”时，若队满，应提示等待（排队不成功） ；“售票”时，若队空，应提示无人排队（售票失败） 。实验目

2、的：掌握循环队列的基本操作。数据结构设计简要描述：序言：这是本学期第二个实验，实验主要目的是让我们熟悉循环队列的创建，入队，出队等操作数据结构设计：整个实验可分为一个大的模块，其中包含八个函数模块：菜单显示函数（Menu）,初始化队列（InitQueue） ，添加购票人到队列（enQueue） ，删除购票成功的人（dlQueue） ，输出队列中所有人的信息（Putall_Queue） ，读取到文件函数（write_file）以及判断队空和队满（Empty、Full）共八个函数模块，队列用结构体创建，其中包含整型（int）的队列容量n，队头指针 top，队尾指针 tail 和队列计数变量 c，以

3、及 string 类型的数组 elem；最后通过 c+语言 ofstream 将购票人信息保存到文件中和 c 语言 exit(0)退出系统，便完成了整个模拟买票系统的创建。评分满分5 分2 / 17算法设计简要描述：1，首先用结构体创建一个保存购票人的信息队列，为 string 类型；2，进行队列初始化，为 string 类型数组 new 一个动态内存，将队头和队尾置 0，并将从键盘输入的 n 值赋值给队列容量；3，判断队列为空或者为满，成立返回真，否则返回假；4，添加购票人信息，将新增的购票人信息添加到队列中去，为避免“假溢”以及搬动元素的操作，在入队时采用 r=（r+1）%n，则数组在逻辑

4、上成为圆环形，也即是采用循环队列；5，将购票成功的人信息显示出来并将其从队列中移除去，也是采用 r=（r+1）%n 循环队列来实现；6，输出显示所有正在购票人信息，先判断若没有人排队，则显示无人购票，否则采用循环队列输出所有人信息；7，采用 ofstream 将所有正在购票人信息读取到文件中去保存；输入/输出设计简要描述：1，排队：输入购票人“姓名” ，若队满，则输出“排队不成功，请等待！” ，否则输出“成功加入到购票队列中去” ；2，售票:调用售票函数时，直接输出排队队列中最前面的人购票成功，并输出其“编号和姓名” ，并显示将其从队列中删除；3，查看所有队列：调用查看所有队列函数，输出所有正

5、在排队的人的信息；4，写入到文件：输入文件名，若队为空，显示“无人购票，写入失败！” ，否则输出成功将其写入到文件中去；5，退出系统：调用退出函数，成功推出系统；编程语言说明：1， 编程软件，Code Blocks 16.0；2， 代码均用 C+语言实现；3， 输入输出采用 C+语言的 cout 和 cin 函数；4， 文件读写采用 ofstream 类型；5， 程序注释采用 C/C+规范；3 / 17主要函数说明：int Menu(void);/菜单显示函数void InitQueue(Queue,int);/初始化队列int enQueue(Queue, ElemTp);/在队列中添加新的

6、乘客int dlQueue(Queue);/将购票成功的人从队列中删除void Putall_Queue(Queue);/输出显示所有队列中的购票人的信息bool Empty(Queue);/判断队列是否为空bool Full(Queue);/判断队列是否满void write_file(Queue);/读取到文件中程序测试简要报告：见截图：1，2，4 / 173，4，5，5 / 176，7，8，6 / 179，源程序代码：#include#include#include#include#includeusing namespace std;typedef string ElemTp;/Ele

7、mTPy 一个 string 类型typedef struct nodeElemTp *elem;int n;/队列容量int top;/队头指针int tail;/队尾指针int c;/队列计数变量7 / 17*Queue;/函数声明int Menu(void);/菜单显示函数void InitQueue(Queue,int);/初始化队列int enQueue(Queue, ElemTp);/在队列中添加新的乘客int dlQueue(Queue);/将购票成功的人从队列中删除void Putall_Queue(Queue);/输出显示所有队列中的购票人的信息bool Empty(Queu

8、e);/判断队列是否为空bool Full(Queue);/判断队列是否满int write_file(Queue);/读取到文件中/队列初始化void InitQueue(Queue q,int n)q-elem = new ElemTp q-n;/先分配一个 M 大的内存空间q-top = q-tail = 0;/将队头和队尾置空q-n = n + 1;/从键盘输入一个队列的长度，并将其赋值给队列长度，这样就可以人为的控制队列的长度/队列为满bool Full(Queue q)8 / 17return (q-tail+1)%q-n = (q-top+q-n)%q-n;/判断队是否满/队为空

9、bool Empty(Queue q)if(q-top = q-tail)/若果队头等于队尾的话，就返回真，说明队空return true;return false;/添加购票人信息int enQueue(Queue q, ElemTp name)if(Full(q)coutelemq-tail = name;/添加排队人编号到队列中去q-tail = (q-tail+1)%q-n;/队尾指针进行加 1 扫描couttop+1;10 / 17name = q-elemq-top;/队头元素出队并保存在 Num1 中，以便打印显示couttop = (q-top+1)%q-n;/队头指针指向下一个队头元素，以让下一个人开始购票coutc = q-top;/这里用一个计数变量来保存队列，而不直接用 q-top,否则打印一次就相当于让一位购票人出队，而不是打印所有购票人信息int i = q-top+1;coutc = q-tail)cout“无人购票！“endl;/队头等于队尾，表示队为空，也就是无人排队购票else