题目4.赵斌是一个信管专业的学生，大学四年顺利毕业了。在毕业季，他也像其他学子一样，投身于求职大军，投出一份又一份求职简历，在苦苦地等待之后，他接到了中国移动通信公司广东分公司的面试通知书，通知他于本月1号10点到公司面试。当天，晴空万里，艳阳高照，他身着西装，高兴地早早来到公司楼下等待。10点钟整，他和其他新人一起，坐到公司的面试现场。他领取的一份程序设计题： 假如你是我公司一名客服技术人员，现请你选择自己熟悉的语言，来设计一个程序，管理客户向公司打进来的咨询电话。请事行分析使用方法和工具，说明自己的思路方法，写一份完整的程序，并实例测试。
二.问题分析
在现实生活中，排队叫号是经常发生的事情。从实习的题目看来，就是要求采用队列的逻辑结构及其物理结构，模拟日常生活中客服的接入情况。本次的课程设计其依据的主要相关知识是线性表、队列和函数模版等以及一些基础的C++编程语言知识。这里，我主要采用链队列相关的知识来完成本系统。
三．逻辑结构和存储结构设计
（一）、队列的定义
队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许插入（入队、进队）的一端称为队尾，允许删除（出队）的另一端称为队头。
队列中的元素之间不仅具有线性关系，而且具有先进先出的特性。
例如：按顺序入队：a1,a2,a3;；如果要删除元素，其出队的顺序是：a1,a3；
队列中的元素具有相同类型及先进先出特性，相邻元素具有前驱和后继的关系。
当客户打电话来咨询时，遇到多人同时需要办理业务，但是，考虑到客服人员不多，所以这里就要有一个先来后到的思想，即先进先出，刚好符合队列的逻辑思想，故而本系统采用队列的逻辑结构及其物理结构。
（二）、队列的顺序存储结构——循环队列
队列是特殊的线性表。 允许队列直接从数组中下标最大的位置延续到下标最小的位置，这个通过取模操比较容易实现，这种头尾相接的顺序存储结构称为循环队列。
队空和队满的判定方法：可以用一个数组的元素空间来实现队尾指针和队头指针相差1（类似于队满的临界状态）。
循环队列的实现：因为队列元素的数据类型不是很确定，这个时候我们还是要采用C++模版机制。其时间复杂度为O（1）。
（三）、循环队列的链接存储——链队列
为了使空队列和非空队列的操作一致，链队列也加上头结点。设置头指针指向链队列的头结点，队尾指针指向终端结点。
链队列的实现;同样的因为队列元素的数据类型不是很确定，这个时候我们还是要采用C++模版机制。其时间复杂度为O（1）。
四． 总体设计
1.系统流程图
2.系统概要分析图
五．算法设计
代码分析：
1.头文件（tel.h）
这里采用函数模版template<class DataType>。
Struct Node
node< DataType >*next;在头文件tel.h中定义结构体Node，其包含数据域DataType data;和指针域node< DataType >*next;指针。
2.无参构造函数
LinkQueue<DataType>::LinkQueue()
{
Node<DataType>*s = NULL;
s = new Node<DataType>;
s->next = NULL;
front = rear = s;
}
定义一个头结点，让头结点为空，front=rear=s这样队列就为空。
3．析构函数
template<classDataType>
LinkQueue<DataType>::~LinkQueue()
{
Node<DataType>*p = NULL;
while (front != NULL)
{
p = front->next;
delete front;
front = p;
}
}
析构函数可以释放存储空间，定义一个结点为空，其指针p所指向的头结点不为空时，就要进行删除操作，让不为空的头结点，指向新定义为空的指针P所指向的next域，即下一个空结点，删除不为空的头结点后，这个头结点被赋值为空指针P。
4.插入队列函数EnQueue()
voidLinkQueue<DataType>::EnQueue(DataType x)
{
Node<DataType>*s = NULL;
s = new Node<DataType>;
s->data = x;
s->next = NULL;
rear->next = s; rear = s;
}
template<classDataType>
定义一个新结点s为空，然后申请一个数据域为X的结点s，其nxet域为空，尾指针的next域被赋值为s，最后将结点s插入到队尾。
5.删除队列函数DeQueue()
DataTypeLinkQueue<DataType>::DeQueue()
{
Node<DataType>*p = NULL;
int x;
if (rear == front)throw"已经没有客户等候了";
p = front->next;
x = p->data;
front->next = p->next;
if (p->next == NULL)rear = front;
delete p;
return x;
}
6.取队头函数GetQueue()
template<classDataType>
DataTypeLinkQueue<DataType>::GetQueue()
{
if (front != rear)
return front->next->data;
}
template<classDataType>
7.判断是否为空值Empty()
intLinkQueue<DataType>::Empty()
{
if (front == rear)
return 1;
else
return 0;
}
六． 时间复杂度与空间复杂度分析
为了使空队列和非空队列的操作一致，链队列也加上头结点。设置头指针指向链队列的头结点，队尾指针指向终端结点。
链队列的实现;同样的因为队列元素的数据类型不是很确定，这个时候我们还是要采用C++模版机制。其时间复杂度为O（1）。空间复杂度为O（n）。
七． 程序运行结果
八．感想与收获
这个程序是基于课本队列那一章节的内容完成的，里面的客户排队其实就是运用了队列的原理。这让我体会到在生活之中处处都有它独特的逻辑与算法，即使是一个小小的客服，也会有很多的内容在里面。我记得有人说过一句话：“真正的科技就是让你感觉不到科技的存在。”是啊，一个真正好的，拥有良好用户体验的程序往往蕴含着紧密的逻辑结构。在这个程序里，我还加入了上个学期的struct结构用来储存客户资料，也算是温故知新吧。
九．附录（源程序）
头文件
#ifndef LinkQueue_H
#define LinkQueue_H
template<class DataType>
struct Node
{
DataType data;
Node<DataType>*next;
};
template<class DataType>
class LinkQueue
{
public:
LinkQueue();
~LinkQueue();
void EnQueue(DataType x);
DataType DeQueue();
DataType GetQueue();
int Empty();
private:
Node<DataType>*front,*rear;
};
#endif
算法
<pre class="cpp" name="code">#include"LinkQueue.h"
template<class DataType>
LinkQueue<DataType>::LinkQueue()
{
Node<DataType>*s = NULL;
s = new Node<DataType>;
s->next = NULL;
front = rear = s;
}
template<class DataType>
LinkQueue<DataType>::~LinkQueue()
{
Node<DataType>*p = NULL;
while (front != NULL)
{
p = front->next;
delete front;
front = p;
}
}
template<class DataType>
void LinkQueue<DataType>::EnQueue(DataType x)
{
Node<DataType>*s = NULL;
s = new Node<DataType>;
s->data = x;
s->next = NULL;
rear->next = s; rear = s;
}
template<class DataType>
DataType LinkQueue<DataType>::DeQueue()
{
Node<DataType>*p = NULL;
int x;
if (rear == front)throw"已经没有客户等候了";
p = front->next;
x = p->data;
front->next = p->next;
if (p->next == NULL)rear = front;
delete p;
return x;
}
template<class DataType>
DataType LinkQueue<DataType>::GetQueue()
{
if (front != rear)
return front->next->data;
}
template<class DataType>
int LinkQueue<DataType>::Empty()
{
if (front == rear)
return 1;
else
return 0;
}
主函数：
#include<iostream> #include<string> #include<iomanip> using namespace std; #include"LinkQueue.cpp"
struct info
{
char name[10];
int tel;
};
struct info data[50]; int n = 0; int g = 1; void show();
void main()
{
LinkQueue<int> Q;
int select;
do
{
system("cls");
cout << "|--- 欢迎致电123电话客服 ---|" << endl;
cout << "| 1、接入热线 |" << endl;
cout << "| 2、查询客服状态 |" << endl;
cout << "| 3、完成客户业务 |" << endl;
cout << "| 4、正在办理业务 |" << endl;
cout << "| 5、显示客户资料 |" << endl;
cout << "| 6、退出 |" << endl;
cout << "| 0、办理业务 |" << endl;
cin >> select;
switch (select)
{
case 0:
if (Q.Empty())
{
cout << "您好，客服mm为您服务" << endl;
try
{
n++;
cout << "\t姓名:";
cin >> data[n].name;
cout << "\t联系电话:";
cin >> data[n].tel;
cout << "操作完成！" << endl;
}
catch (char*wrong)
{
cout << wrong << endl;
}
}
else
cout << "客服正忙，请稍后..." << endl;
system("pause");
break;
case 1:
try
{
n++;
cout << "成功接入客服: " << endl;
cout << "您是今天的第" << n << "个客户""前面还有" << g - 1 << "个客户" << endl;
if (Q.Empty())
cout << "请按数字0办理业务" << endl;
else
cout << "请耐心等候..." << endl;
Q.EnQueue(g);
g++;
system("pause");
}
catch (char*wrong)
{
cout << wrong << endl;
}
break;
case 2:
cout << "查看对头元素:" << endl;
if (Q.Empty())
{
cout << "客户等待个数" << setw(24) << "正在办理业务客户号码" << setw(14) << "办理情况" << endl;
cout << setw(5) << 0 << setw(26) << "无客户办理业务" << setw(24) << "空闲等待中..." << endl;
}
else
{
cout << "客户等待个数" << setw(24) << "正在办理业务客户号码" << setw(14) << "办理情况" << endl;
cout << setw(5) << g - 1 << setw(22) << Q.GetQueue() << setw(24) << "办理中..." << endl;
cout << endl;
}
system("pause");
break;
case 3:
char s3;
int x;
cout << "是否完成该客户业务（是:y/Y,否：n/N）:";
cin >> s3;
if (s3 == 'y' || s3 == 'Y')
{
try
{
Q.DeQueue();
g--;
}
catch (char*wrong)
{
cout << wrong << endl;
}
}
else {
cout << "还有客户正在办理业务" << endl;
}
cout << "当前正在受理的是:" << endl; cout << Q.GetQueue() << "号客户" << endl;
system("pause");
break;
case 4: cout << "当前正在受理的是:" << endl; cout << Q.GetQueue() << "号客户" << endl;
system("pause");
break;
case 5:
show();
system("pause");
break;
}
} while (select != 6);
cout << left;
}
void show()
{
cout << "姓名" << setw(10) << "联系电话" << endl;
for (int i = 1; i <= n; i++)
{
cout << data[i].name << setw(10) << data[i].tel << endl;
}
cout << endl;
}
