【实验报告】 线性数据结构的实现与应用_双端队列_逆波兰式_呼叫中心_XAUAT_(原问题自杜克大学C++ Stacks and Queues and Lists)
附问题链接:
https://blog.****.net/weixin_43781565/article/details/106506822
求打赏求收藏求转发!
提供DOC资源
https://download.****.net/download/weixin_43781565/12490532
(审核后可供下载)
Peace and love
图片全部转存失败我真的很难受.....有需要评论吧
目录
1. 掌握双端队列的双链表实现。
2. 掌握基于双端队列的栈的应用:逆波兰表达式求值。
3. 掌握基于双端队列的普通队列的应用:呼叫中心的离散事件模拟。
1. 基于双链表实现双端队列的典型操作(判空、头插、头删、尾插、尾删、普通构造、拷贝构造、赋值运算符重载、析构),编写简单程序使用该双端队列,测试和调试程序。
2. 基于双端队列的头插、头删操作,完成栈的应用:逆波兰表达式求值,测试和调试程序。
3. 基于双端队列的头删、尾插操作,完成普通队列的应用:呼叫中心的离散事件模拟,测试和调试程序。
4. 按要求撰写实验报告、录制程序运行以及讲解程序的视频。
计算机、Windows 操作系统、C++语言集成开发环境。
链表(linked list)是一种物理存储单元上非连续、非顺序的存储结构,是通过链表中的指针链接实现的。链表由一系列结点组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。而如果我们给链表的每一个结点都增加一对指针,并给予他们与原有结点相反的功能,我们就可以得到一个双端链表(double link list),或称为双端队列。
图4.1.1 双端链表(double link list)
对于双端队列,我们拥有4 种数据的操作:左端出队,右端入队,左端入队和右端出队,而在实验一中,我们就是要基于链表实现双端队列的“增删改查”以及相关的构造与重载。
插入元素对于链表来说,是通过更换指针所指的地址来实现元素的插入,在双端队列里也不例外。
我们将节点"ai-1"的后继节点改为"x";"x"的前继节点改为"ai-1",后继节点改为"ai";"ai"的前继节点改为"x",即完成了对双端队列的插入操作。
需要注意的是,操作①必须在操作③之前完成,否则可能会丢失前驱结点。
对于删除结点来说,与插入类似,是通过更换指针所指的地址来实现元素的删除。
我们要删除节点"ai",则需要将节点"ai-1"的后继节点改为"ai+1",将"ai+1"的前继节点改为"ai-1",即完成了对双端队列的删除操作。
而对于构造函数,我们则需要给每一个创建头结点与尾结点,表示两个指针;对于赋值运算符重载与拷贝构造函数的意义是一样的,我们设立一个copyAll()函数,进行两个队列的复制工作;于此同时,我们还设置了removeAll()函数,用来移除队列,isEmpty()函数用来返回队列是否已经不包含存储容量,用来辅助其他函数的功能实现以及后期的相关应用。
逆波兰表达式(Reverse Polish Notation)又称为后缀表达式,是波兰逻辑学家卢卡西维兹提出的一种表达式的表示方法, 是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法.我们平常使用的计算表达式大都是中缀表达式,如A+B*(C-D)-E*F,如图所示:
图4.2. A+B*(C-D)-E*F的二叉树表示
中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。上面的二叉树中序遍历的结果就是A+B*(C-D)-E*F。而逆波兰式是由后序遍历的结果得到的,上图的后缀表达式为:A B C D - * + E F * -。
相对于计算机来说,后缀表达式的处理成本要比中缀表达式相比较低。所以我们本次的实验,需要应用1中的双端队列的部分功能,实现逆波兰式的算式读取分析与计算,并读出结果。
我们可以以3 4 + 5 × 6 -的计算为例:
- 从左至右扫描,将3和4压入堆栈;
- 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
- 将5入栈;
- 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
- 将6入栈;
- 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。
所以经过分析,我们可以采用一个栈来实现计算,扫描表达式从左往右进行,如果扫描到数值,则压进辅助栈中,如果扫描到运算符,则从辅助栈中弹出两个数值参与运算,并将结果压进到栈中,当扫描表达式结束后,栈顶的数值就是表达式结果。我们需要利用双端队列,实现基本的栈的操作,如压栈(push),弾栈(pop),再加以适当的判断操作即可。
除此之外,为了满足实验的要求,还应加入判断函数,以对逆波兰式输入的内容进行判断,防止出现错误的数值或字符输入,导致程序崩溃。
在实验的第三部分,我们需要在第1部分双端队列的基础上,模拟一个呼叫中心的客服电话系统,系统需要根据用户在不同的打进电话时间,不同的用户身份等级与不同的处理时长的情况下,合理的分配电话的接听与等待。基于要求的设定,我们需要将双链表的双端队列改造成为一个单链表的普通队列。
链表(list),是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。其中存储数据元素信息的域称作数据域(data),存储直接后继存储位置的域称为指针域(next)。指针域中存储的信息又称做指针或链。
与形成双端队列的双链表不同的是,单链表的每个结点仅有一个指针域,指向下一个结点,即为“单向”模式,较双链表来说随功能不如双链表完善,但节约空间资源,且符合我们本次实验“电话排队”的要求。
因为对于每个打进电话的用户来说,都需要记录他们的时间点(timestamp),姓名(Name),等级(status)和处理时间长度(duration),所以可以根据对应的需求建立客人类(Customer),并包含对应的字段进行对象创建,并应该包含插入队列和根据等级查找客人的操作。其次,实验要求从文件输入程序所需要的数据,我们需要创建文件对象并使用文件输入对应的数据。
根据实验要求,我们应该先读入总共模拟的电话数,为每一个级别创建一个队列,然后读入对应的字段,并进入第一个时间片,搜索最先且同时打进电话的用户,并根据等级选择最高的用户开始通话,并读取该用户电话接听所需时间片,开始处理,不断循环,与此同时在不同的时间片打进电话的用户,给予提示信息,直到最后一位用户电话接听所需时间片结束且没有电话接入,程序结束。
在程序中应使用if else结构判断各种的情况,并应该加入当前电话状态的判断,具体的程序细节在第五部分呈现。
包含文件数:3
文件名:DList.h, Dlist.cpp, 源.cpp
- class emptyList
- {
- // OVERVIEW: an exception class
- };
- template <class T>
- class Dlist
- {
- // OVERVIEW: contains a double-ended list of Objects
- public:
- // Operational methods
- bool isEmpty() const;
- // EFFECTS: returns true if list is empy, false otherwise
- void insertFront(T* o);
- // MODIFIES this
- // EFFECTS inserts o at the front of the list
- void insertBack(T* o);
- // MODIFIES this
- // EFFECTS inserts o at the back of the list
- T* removeFront();
- // MODIFIES this
- // EFFECTS removes and returns first object from non-empty list
- // throws an instance of emptyList if empty
- T* removeBack();
- // MODIFIES this
- // EFFECTS removes and returns last object from non-empty list
- // throws an instance of emptyList if empty
- // Maintenance methods
- Dlist(); // constructor
- Dlist(const Dlist& l); // copy constructor
- Dlist& operator=(const Dlist& l); // assignment operator
- ~Dlist(); // destructor
- private:
- // A private type
- struct node
- {
- node* next;
- node* prev;
- T* o;
- };
- node* first; // The pointer to the first node (NULL if none)
- node* last; // The pointer to the last node (NULL if none)
- // Utility methods
- void removeAll();
- // EFFECT: called by destructor/operator= to remove and destroy
- // all list elements
- void copyAll(const Dlist& l);
- // EFFECT: called by copy constructor/operator= to copy elements
- // from a source instance l to this instance
- };
- #include"Dlist.h"
- #include <cstdlib>
- #include<iostream>
- using namespace std;
- template<class T>
- bool Dlist<T> ::isEmpty() const {
- return (first == NULL) && (last == NULL);
- }//如果列表为空,则返回true,否则返回false(判空)
- template<class T>
- void Dlist<T> ::insertFront(T* o) {
- node* np = new node;
- np->o = o;
- np->next = first;
- np->prev = NULL;
- if (!isEmpty()) {
- first->prev = np;
- }
- else {
- last = np;
- }
- first = np;
- return;
- }//在列表的前面插入o(头插)
- template<class T>
- void Dlist<T> ::insertBack(T* o) {
- node* np = new node;
- np->o = o;
- np->prev = last;
- np->next = NULL;
- if (!isEmpty()) {
- last->next = np;
- }
- else {
- first = np;
- }
- last = np;
- return;
- }//在列表的后面插入o(尾插)
- template<class T>
- T* Dlist<T> ::removeFront() {
- if (isEmpty()) {
- emptyList error;
- throw error;
- }
- node* victim = first;
- first = victim->next;
- if (first == NULL) {
- last = NULL;
- }
- else {
- first->prev = NULL;
- }
- T* o = victim->o;
- delete victim;
- return o;
- } //从非空列表中删除并返回第一个对象(头删)
- //如果为空则抛出emptyList的实例
- template<class T>
- T* Dlist<T> ::removeBack() {
- if (isEmpty()) {
- emptyList error;
- throw error;
- }
- node* victim = last;
- last = victim->prev;
- if (last == NULL) {
- first = NULL;
- }
- else {
- last->next = NULL;
- }
- T* o = victim->o;
- delete victim;
- return o;
- }//从非空列表中删除并返回最后一个对象(尾删)
- //如果为空则抛出emptyList的实例
- template<class T>
- Dlist<T> ::Dlist() {
- first = NULL;
- last = NULL;
- }//构造函数
- template<class T>
- Dlist<T> ::Dlist(const Dlist& test_list) {
- first = NULL;
- last = NULL;
- copyAll(test_list);
- }//拷贝构造函数
- template<class T>
- Dlist<T>& Dlist<T> :: operator=(const Dlist& test_list) {
- copyAll(test_list);
- return *this;
- }//赋值运算符重载
- template<class T>
- Dlist<T> :: ~Dlist() {
- removeAll();
- }//析构函数
- template<class T>
- void Dlist<T> ::removeAll() {
- while (!isEmpty()) {
- T* o = removeFront();
- delete o;
- }
- return;
- }//由析构函数 / = 运算符重载 调用删除所有列表元素
- template<class T>
- void Dlist<T> ::copyAll(const Dlist& test_list) {
- removeAll();
- node* np = test_list.first;
- while (np != NULL) {
- T* o = new T(*np->o);
- insertBack(o);
- np = np->next;
- }
- return;
- }
- //由拷贝构造函数/ = 运算符重载 调用复制元素
- //从源实例test_list到此实例
- #include <cstdlib>
- #include<iostream>
- #include"Dlist.cpp"
- using namespace std;
- int main(int argc, char* argv[])
- {
- /* 示例程序:
- Dlist<int> ilist;
- int* ip = new int(3);
- ilist.insertFront(ip);
- ip = ilist.removeFront();
- cout << *ip << endl;
- delete ip;
- return 0;
- */
- //自编程序:
- cout << "前插13,15,17到test_list中并前删" << endl;
- Dlist<int> test_list;
- int* a = new int(13);
- int* b = new int(15);
- int* c = new int(17);
- test_list.insertFront(a);
- test_list.insertFront(b);
- test_list.insertFront(c);
- cout << endl << *test_list.removeFront() << endl;
- cout << *test_list.removeFront() << endl;
- cout << *test_list.removeFront() << endl;
- cout << endl << "使用前插13,15,17到test_list中并尾删" << endl;
- test_list.insertFront(a);
- test_list.insertFront(b);
- test_list.insertFront(c);
- cout << endl << *test_list.removeBack() << endl;
- cout << *test_list.removeBack() << endl;
- cout << *test_list.removeBack() << endl;
- cout << endl;
- test_list.insertFront(a);
- test_list.insertFront(b);
- test_list.insertFront(c);
- cout << "拷贝构造函数构造x" << endl;
- Dlist<int> x(test_list);
- cout << "x的尾删" << endl;
- cout << *x.removeBack() << endl;
- cout << "重载运算符y=test_list" << endl;
- Dlist<int> y = test_list;
- cout << "y尾删" << endl;
- cout << *y.removeBack() << endl;
- }
包含文件数:3;
文件名:DList.h, Dlist.cpp, DataStructure_1_2.cpp;
备注:DList.h, Dlist.cpp与1中代码相同,为引用形式
- // DataStructure_1_2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
- //
- //软件1801 孙嘉成 1806050127
- #include <iostream>
- #include <string>
- #include <string.h>
- #include <cstdlib>
- #include "C:\Users\Edward\source\repos\DataStructe_1\Dlist.h"
- #include "C:\Users\Edward\source\repos\DataStructe_1\Dlist.cpp"
- using namespace std;
- bool isInteger(string str);
- //判断数字:
- //如果str仅由int组成,则返回true
- //否则返回false
- //如果str是以“ +”开头的int,则返回false
- int main() {
- Dlist<int> RPNStack; // 开辟堆栈
- string inputString = "";
- int* tempIntPtr = NULL;
- cin >> inputString;
- while (1) {
- if (inputString == "+") {
- //加法运算
- int* tempOperandPtr1 = NULL;
- int* tempOperandPtr2 = NULL;
- if (!RPNStack.isEmpty()) {
- tempOperandPtr1 = RPNStack.removeFront();
- if (!RPNStack.isEmpty()) {
- tempOperandPtr2 = RPNStack.removeFront();
- // Ptr1保存总和值
- *tempOperandPtr1 = *tempOperandPtr1 + *tempOperandPtr2;
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- delete tempOperandPtr2;
- }
- else { //在第二次弹栈之前栈为空
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "-") {
- //减法运算
- int* tempOperandPtr1 = NULL;
- int* tempOperandPtr2 = NULL;
- if (!RPNStack.isEmpty()) {
- tempOperandPtr1 = RPNStack.removeFront();
- if (!RPNStack.isEmpty()) {
- tempOperandPtr2 = RPNStack.removeFront();
- // Ptr1保留差值
- *tempOperandPtr1 = *tempOperandPtr2 - *tempOperandPtr1;
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- delete tempOperandPtr2;
- }
- else { //在第二次弹栈之前栈为空
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "*") {
- //乘法运算
- int* tempOperandPtr1 = NULL;
- int* tempOperandPtr2 = NULL;
- if (!RPNStack.isEmpty()) {
- tempOperandPtr1 = RPNStack.removeFront();
- if (!RPNStack.isEmpty()) {
- tempOperandPtr2 = RPNStack.removeFront();
- // Ptr1保留乘积
- *tempOperandPtr1 = (*tempOperandPtr1) * (*tempOperandPtr2);
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- delete tempOperandPtr2;
- }
- else { //在第二次弹栈之前栈为空
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "/") {
- //除法运算
- int* tempOperandPtr1 = NULL;
- int* tempOperandPtr2 = NULL;
- if (!RPNStack.isEmpty()) {
- tempOperandPtr1 = RPNStack.removeFront();
- if (RPNStack.isEmpty()) {
- //在第二次移除之前堆叠为空
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- else if (*tempOperandPtr1 == 0) {
- //无法除以0,将优先级降低为不足操作数
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Divide by zero" << endl;
- //然后进入下一个输入
- }
- else {
- tempOperandPtr2 = RPNStack.removeFront();
- //Ptr1保留除法值
- *tempOperandPtr1 = (*tempOperandPtr2) / (*tempOperandPtr1);
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- delete tempOperandPtr2;
- }
- }
- else { //第一次删除之前堆栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "n") {
- //求相反数
- if (!RPNStack.isEmpty()) {
- tempIntPtr = RPNStack.removeFront();
- *tempIntPtr = (*tempIntPtr) * (-1);
- RPNStack.insertFront(tempIntPtr);
- tempIntPtr = NULL;
- }
- else { //在弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "d") {
- //复制操作
- if (!RPNStack.isEmpty()) {
- int* tempOriginalPtr;
- tempOriginalPtr = RPNStack.removeFront();
- int* tempDuplicatePtr = new int(*tempOriginalPtr);
- RPNStack.insertFront(tempOriginalPtr);
- RPNStack.insertFront(tempDuplicatePtr);
- tempOriginalPtr = NULL;
- tempDuplicatePtr = NULL;
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "r") {
- //反向操作,栈顶元素与次栈顶元素交换次序
- int* tempOperandPtr1 = NULL;
- int* tempOperandPtr2 = NULL;
- if (!RPNStack.isEmpty()) {
- tempOperandPtr1 = RPNStack.removeFront();
- if (!RPNStack.isEmpty()) {
- tempOperandPtr2 = RPNStack.removeFront();
- //首先提取Ptr1
- RPNStack.insertFront(tempOperandPtr1);
- RPNStack.insertFront(tempOperandPtr2);
- tempOperandPtr1 = NULL;
- tempOperandPtr2 = NULL;
- }
- else { //在第二次弹栈之前栈为空
- RPNStack.insertFront(tempOperandPtr1);
- tempOperandPtr1 = NULL;
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "p") {
- //打印操作
- if (!RPNStack.isEmpty()) {
- tempIntPtr = RPNStack.removeFront();
- cout << (*tempIntPtr) << endl;
- RPNStack.insertFront(tempIntPtr);
- tempIntPtr = NULL;
- }
- else { //在第一次弹栈之前栈为空
- cout << "Not enough operands" << endl;
- //然后进入下一个输入
- }
- }
- else if (inputString == "c") {
- //清除所有元素
- while (!RPNStack.isEmpty()) {
- int* tempClearPtr;
- tempClearPtr = RPNStack.removeFront();
- delete tempClearPtr;
- }
- }
- else if (inputString == "a") {
- //打印所有元素
- Dlist<int> printRPNStack(RPNStack);
- while (!printRPNStack.isEmpty()) {
- int* tempPrintPtr;
- tempPrintPtr = printRPNStack.removeFront();
- cout << (*tempPrintPtr) << " ";
- delete tempPrintPtr;
- }
- cout << endl;
- // printRPNStack的析构函数将解决内存泄漏风险(现在应该没有)
- }
- else if (inputString == "q") {
- //退出操作
- break;
- //内存泄漏风险将由析构函数处理
- }
- else if (isInteger(inputString)) {
- //将int数字推入堆栈
- tempIntPtr = new int(atoi(inputString.c_str()));
- //atoi(ascii to integer)把字符串转换成整型数
- RPNStack.insertFront(tempIntPtr);
- tempIntPtr = NULL;
- }
- else {
- //输入无效
- cout << "Bad input" << endl;
- }
- //继续下一个输入
- cin >> inputString;
- }
- return 0;
- }
- bool isInteger(string str) {
- const char* C_String = str.c_str();
- //将C++的string转化为C的字符串数组
- unsigned long length = strlen(C_String);
- if (length == 0) {
- return false;
- }
- else if (length == 1) {
- return isdigit(C_String[0]);
- //用来判断一个字符是否是数字
- //返回值为真表示是数字,假表示不是数字
- }
- else { //C_String至少有两个字符
- if ((isdigit(*C_String)) || (*C_String == '-')) {
- //第一个字符为十进制数字或'-'
- //从第二个字符开始
- for (unsigned long index = 1; index < length; index++) {
- if (!isdigit(C_String[index])) {
- return false;
- }
- //如果C_String [index]是数字,则继续检查
- }
- //所有数字通过检查
- return true;
- }
- else {
- //第一个字符既不是十进制数字也不是'-'
- return false;
- }
- }
- }
包含文件数:3;
文件名:DList.h, Dlist.cpp, DataStructure_1_3.cpp;
备注:DList.h, Dlist.cpp与1中代码相同,为引用形式
- #include <iostream>
- #include <string>
- #include <cstdlib>
- #include <fstream>
- #include "C:\Users\Edward\source\repos\DataStructe_1\Dlist.h"
- #include "C:\Users\Edward\source\repos\DataStructe_1\Dlist.cpp"
- //软件1801 孙嘉成 1806050127
- using namespace std;
- struct callEvent {
- int callTimeStamp; //该电话的拨入时间,非负整数
- string callerName; //用户姓名
- int callerStatus; //用户的等级,1-4
- int callDuration; //需要持续的时间片长度,正整数
- };
- enum status {
- LEVEL1, LEVEL2, LEVEL3, LEVEL4
- };
- status returnStatusEnum(int statusString);
- //返回对应的状态枚举
- int main() {
- int remainingBusyTime = 0;
- int remainingCallNum = 0;
- int nextCallTimeStamp = 0;
- int tickTok = 0;
- callEvent* tempCallPtr = NULL;
- Dlist<callEvent> Level1Quene;
- Dlist<callEvent> Level2Quene;
- Dlist<callEvent> Level3Quene;
- Dlist<callEvent> Level4Quene;
- // 所有队列前删后插
- ifstream infile;
- infile.open("sample.txt");
- infile >> remainingCallNum;
- if (remainingCallNum > 0) {
- infile >> nextCallTimeStamp;
- }
- else {
- cerr << "Unexpected total call number." << endl;
- }
- //每个时间片进行一次循环
- while (1) {
- cout << "Starting tick #" << tickTok << endl;
- if ((Level1Quene.isEmpty()) && (Level2Quene.isEmpty()) && (Level3Quene.isEmpty()) && (Level4Quene.isEmpty()) && (remainingBusyTime == 0) && (remainingCallNum == 0)) {
- break;
- }
- else { //仍在通话处理接听,完成处理并排队清除
- // 1.搜索呼入匹配时间片
- while (nextCallTimeStamp == tickTok) {
- // 1.1建立一个结构来保存通话信息
- tempCallPtr = new callEvent;
- tempCallPtr->callTimeStamp = nextCallTimeStamp;
- infile >> tempCallPtr->callerName
- >> tempCallPtr->callerStatus
- >> tempCallPtr->callDuration;
- remainingCallNum--;
- // 1.2更新nextCallTimeStamp
- if (remainingCallNum > 0) {
- infile >> nextCallTimeStamp;
- }
- else {
- nextCallTimeStamp = -1;
- //tickTok不会等于-1
- //不会进入while循环
- }
- // 1.3宣布呼入
- //例如“来自Andrew的level1 电话”
- cout << "Call from "
- << tempCallPtr->callerName
- << " a Level"
- << tempCallPtr->callerStatus
- << " member" << endl;
- // 1.4 将通话排队
- switch (returnStatusEnum(tempCallPtr->callerStatus)) {
- case LEVEL1:
- Level1Quene.insertBack(tempCallPtr);
- break;
- case LEVEL2:
- Level2Quene.insertBack(tempCallPtr);
- break;
- case LEVEL3:
- Level3Quene.insertBack(tempCallPtr);
- break;
- case LEVEL4:
- Level4Quene.insertBack(tempCallPtr);
- break;
- default:
- cerr << "Invalid status enum for caller "
- << tempCallPtr->callerName
- << " with status "
- << tempCallPtr->callerStatus
- << endl;
- tempCallPtr->callerName = "我是错误等级";
- //只是为了避免内存泄漏
- Level1Quene.insertBack(tempCallPtr);
- break;
- }
- tempCallPtr = NULL;
- }
- // 2.结束通话或使另一个通话出队
- if (remainingBusyTime != 0) {
- // 2.1当前通话未完成
- remainingBusyTime--;
- }
- else {
- //接线员空闲
- // 2.2 从级别1开始从队列接听下一个呼叫
- if (!Level1Quene.isEmpty()) {
- //接听level1用户的电话
- callEvent* tempAnswerPtr;
- tempAnswerPtr = Level1Quene.removeFront();
- cout << "Answering call from "
- << tempAnswerPtr->callerName
- << endl;
- remainingBusyTime = tempAnswerPtr->callDuration - 1;
- delete tempAnswerPtr;
- }
- else if (!Level2Quene.isEmpty()) {
- //接听Level2用户的电话
- callEvent* tempAnswerPtr;
- tempAnswerPtr = Level2Quene.removeFront();
- cout << "Answering call from "
- << tempAnswerPtr->callerName
- << endl;
- remainingBusyTime = tempAnswerPtr->callDuration - 1;
- delete tempAnswerPtr;
- }
- else if (!Level3Quene.isEmpty()) {
- //接听level3用户的电话
- callEvent* tempAnswerPtr;
- tempAnswerPtr = Level3Quene.removeFront();
- cout << "Answering call from "
- << tempAnswerPtr->callerName
- << endl;
- remainingBusyTime = tempAnswerPtr->callDuration - 1;
- delete tempAnswerPtr;
- }
- else if (!Level4Quene.isEmpty()) {
- //接听Level4用户的电话
- callEvent* tempAnswerPtr;
- tempAnswerPtr = Level4Quene.removeFront();
- cout << "Answering call from "
- << tempAnswerPtr->callerName
- << endl;
- remainingBusyTime = tempAnswerPtr->callDuration - 1;
- delete tempAnswerPtr;
- }
- //其他:如果所有队列都为空,则滚动到下一个时间点
- } // “ if(remainingBusyTime!= 0)”中else的结尾
- } // else from“if (time to exit while loop)”的结尾
- tickTok++;
- } //“ while(1)”的结尾
- return 0;
- }
- status returnStatusEnum(int statusString) {
- if (statusString == 1) {
- return LEVEL1;
- }
- else if (statusString == 2) {
- return LEVEL2;
- }
- else if (statusString == 3) {
- return LEVEL3;
- }
- else if (statusString == 4) {
- return LEVEL4;
- }
- else {
- return LEVEL1; // LEVEL1 == 0
- }
- }//返回对应的状态枚举
图6.1.1 示例程序运行结果
图6.1.2 自测程序运行结果
图6.2 示例程序运行结果
图6.3 示例程序运行结果
在双链表的实现测试中,主要是对class Dlist中的相关函数进行测试,因此在main()函数的测试过程中除运行示例测试程序之外,还重新设置了新队列,并运用了插入,删除,拷贝构造与运算符重载等相关函数对Dlist进行测试,经测试程序能够正确运行,并打印出了相关的数据,符合要求。
在逆波兰式表达式程序的测试中,运用示例程序进行测试,主要是测试程序在利用之前双端列表的情况下,改进后的进栈与弾栈操作是否符合相关的要求,能否计算出对应算式正确的值;并且检测程序是否实现了要求中的功能,如“输入错误”,“算式错误”,取相反数与按要求退出等,经测试程序能够正确运行,并计算出了示例程序中的相关算式结果,同时实现了相关的特定功能,符合要求。
在呼叫中心模拟程序的测试中,运用示例文本文件sample.txt进行测试,主要是测试程序能否按照相关的要求,处理好不同时间与不同等级的用户来电情况,涉及的主要内容是队列的操作,如头插尾插等。分别输入总电话个数与不同等级下,同一时间与不同时间接入的电话,以测试程序是否能够按照预期的操作呈现最终的接听结果。经测试程序能够正确运行,并得出了对所有用户的操作情况,与实验的预期结果相同,符合要求。