《数据结构》课程设计

发布时间：2020-12-15 06:02:40 所属栏目：安全来源：网络整理

导读：一.问题描述题目 4. 赵斌是一个信管专业的学生，大学四年顺利毕业了。在毕业季，他也像其他学子一样，投身于求职大军，投出一份又一份求职简历，在苦苦地等待之后，他接到了中国移动通信公司广东分公司的面试通知书，通知他于本月 1 号 10 点到公司面试。当

一.问题描述

题目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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

《数据结构》 课程设计

《数据结构》课程设计