【和春笋一起学C++】（五十七）链表数据结构及其应用

本文介绍了链表的基本概念及其在队列实现中的应用。主要内容包括：1.链表的基本概念和结构；2.以ATM排队系统为例，详细设计了基于链表的队列类实现方案；3.重点阐述了队列的核心方法实现，包括入队(enqueue)和出队(dequeue)操作；4.讨论了析构函数、复制构造函数等特殊成员函数的实现要点；5.提供了完整的队列类实现代码。文章通过链表结构实现了队列的先进先出特性，避免了数组实现时的元素移动问

三月微暖寻春笋

726人浏览 · 2026-01-29 19:27:02

三月微暖寻春笋 · 2026-01-29 19:27:02 发布

2.2.4 复制构造函数和重载赋值操作符函数

2.2.5 附完整代码

1. 链表概念

链表是一种线性数据结构，由节点组成，每个节点都包含数据和指向下一个节点的指针。常见的链表有单向链表、双向链表、循环链表。

单向链接：每个节点都只包含一个指向其他节点的指针。下图是一个包含四个节点的单向链表，每个节点都只包含一个指向其他节点的指针。知道第一个节点的地址后，就可以沿指针找到后面的每一个节点。通常，单向链表的最后一个节点的指针被设置为NULL(或0)，用来指出后面没有节点了。要跟踪链表必须知道第一个节点的地址。

2. 应用实例——队列

一个典型的应用场景：通过模拟排队使用ATM机，估算出新来排队的人员需要等待的时间。

人员排队，很容易想到通过队列来解决。队列是一种抽象的数据类型，可以存储有序的对象序列，新对象被添加到队尾，并且可以删除队首的对象。队列是一种先进先出的结构，不同于堆栈的后进先出。

要解决该问题，首先需要定义队列类和客户类，然后再通过一个程序实现队列和客户之间的交互。

2.1 队列的类设计

队列类需要包含的功能：

能够存储有序的对象序列；
能容纳的对象数量有一定的限制；
应对能够创建空队列；
能够检查队列是否为空；
能够检查队列是否已满；
能够在队尾添加新对象；
能够在对首删除对象；
能够实时获取队列中的对象数目；

另外，还需要考虑如何来表示队列数据，由于队列是先进先出的，使用数组表示队列会很不方便，因为在删除一个元素后需要将所有的元素向前移动一位。而链表能很好的满足队列的要求。链表是由节点序列构成，每一个节点都包含要保存到链表中的信息以及一个指向下一节点的指针。这里将客户类定义为CConsumer，对于队列来说，数据部分就是一个CConsumer对象，因此可以使用下面的结构来表示节点：

    struct Node
	{
		CConsumer consumer;
		struct Node* next;
	};

对于单向链表来说，知道第一个节点的地址后，就可以沿指针找到后面的每一个节点。所以要跟踪链表，必须知道第一个节点的地址，可以让Queue类的一个数据成员指向链表的起始位置。另外，由于队列总是将新对象添加到队尾，所以包含一个指向最后一个节点的数据成员将会很方便。所以Queue类的声明（queue.h）可设计为如下：

class CConsumer
{
private:
	long arrive;///客户到达ATM机的时间
	int processtime;///客户使用ATM机的时间
public:
	CConsumer() { arrive = processtime = 0; }
	void set(long when);
	long when()const { return arrive; }
	int ptime()const { return processtime; }

};

class Queue
{
private:
	struct Node
	{
		CConsumer consumer;
		struct Node* next;
	};
	Node* front;///指向队列队首的指针
	Node* rear;///指向队列队尾的指针
	int Items;///当前队列的对象数目
	const int qsize;///队列可存储的最大对象数目
	Queue(const Queue& q) :qsize(0) {}///伪私有方法，确保Queue类对象在本程序中不被复制
	Queue& operator=(const Queue& q) { return *this; }///伪私有方法，确保Queue类对象在本程序中不被其他Queue类对象赋值

public:
	Queue(int qs);///队列可以存储的最大对象数目为10
	~Queue();
	bool isEmpty();///判断队列是否为空
	bool isFull();///判断队列是否已满
	int getQueueCount() const;///获取队列中对象的数目
	bool enqueue(const CConsumer& item);///在对尾增加对象
	bool dequeue(CConsumer& item);///在队首删除对象
};

2.2 队列的类方法实现

Queue类的声明中，isEmpty方法，isFull方法以及getQueueCount方法的实现较为简单。如果items为0，则队列是空的；如果items等于qsize，则队列已满；获取队列中的人数，只需要返回items的值即可。这里详细介绍入队方法enqueue和出队方法dequeue的实现，入队表示在队尾增加一个节点，出队表示在队首删除一个节点。

2.2.1 入队方法

入队函数定义如下：

bool Queue::enqueue(const CConsumer& item)
{
	if (isFull())///队列已满，则入队失败，返回
	{
		return false;
	}
	Node* add = new Node;///创建新入队的客户
	if (add == NULL)///内存空间不足，则入队失败，返回
	{
		return false;
	}
	add->consumer = item;///入队的客户数据复制
	add->next = NULL;///入队后的客户就是排在最后的客户
	Items++;////总的客户数目加1
	if (front == NULL)////如果前面没人的情况下，则新入队的客户就是最前面的客户
	{
		front = add;
	}
	else////前面有人的情况下，原来的rear节点的next指针指向的是NULL，现在需要将它改成add
	{
		rear->next = add;
	}
	rear = add;//客户（新节点）入队后，原本队尾的节点就不再是最后一个节点，最后一个节点变成了新增加的节点add
	return true;
}

入队函数实现说明：

如果队列已满，则返回（队列的最大长度由用户通过构造函数指定）。
创建一个新节点，如果无法创建新节点（如请求内存失败）则返回。
在节点中放入正确的值。将item值复制到节点的数据部分，并将节点的next指针设置为NULL。
对象计数（items）加1。
将新节点添加到队尾。包含两个部分：（1）将新节点与链表中的另一个节点连接起来，即将当前队尾节点的next指针指向新的队尾节点；（2）将Queue类的成员指针rear设置为指向新的节点，使队列可以直接访问最后一个节点。另外，如果当前队列为空，则必须将front指针设置成指向新增的节点（如果只有一个节点，则它即是队首节点，也是队尾节点）。

2.2.2 出队方法

出队函数定义如下：

bool Queue::dequeue(CConsumer& item)
{
	if (front == NULL)///队列为空时，出队失败，返回
	{
		return false;
	}
	item = front->consumer;//将即将删除的节点数据复制到传递给方法的引用变量
	Items--;///对象计数减1
	Node* temp = front;///保存front节点的位置，供后面删除
	front = front->next;///让节点出队，将front指针设置成指向下一个节点。
	delete temp;///删除出队的节点，以节省内存空间
	if (Items == 0)///当第一个节点出队后，如果队列数量为0，则将指向队尾的节点指针设置为NULL
	{
		rear = NULL;
	}
	return true;
}

出队函数的说明在代码注释中已详细说明，此处不再重复说明。

2.2.3 析构函数

由于在入队方法的定义中使用了new创建新的节点，因此队列的析构函数不能使用默认的，虽然在出队方法中使用了delete删除出队的节点（对象），但不能保证队列在到期时为空。因此，Queue类需要一个显式析构函数，该函数用来删除剩余的所有节点。显式析构函数定义如下：

Queue::~Queue()
{
	Node* temp;
	while (front != NULL)
	{
		temp = front;
		front = front->next;
		delete temp;
	}
}

说明：函数用来删除剩余的所有节点，从链表头（front指针指向排在第一个的节点）开始，依次删除其中的每个节点。

2.2.4 复制构造函数和重载赋值操作符函数

Queue类的对象是否可以使用默认的复制构造函数呢？假设使用默认复制构造函数复制了一个Queue类的对象，那么新对象中指向队首和指向队尾的指针将指向原来链表中的头和尾，因此，使用默认复制构造函数复制Queue类的对象将修改共享的链表，对原先的链表造成破坏。所以默认的复制构造函数无法满足要求，所以需要显式定义复制构造函数。

因此，在Queue类声明中定义了两个伪私有方法：

Clas Queue
{
    private:
    Queue(const Queue& q):qsize(0){}
    Queue& operator= (const Queue& q){return *this}
}

正常的类中，显式定义复制构造函数和重载赋值操作符函数都是在公有部分中声明的，这里在私有部分中声明，有两个作用：

（1）避免自动生成默认的复制构造函数和重载赋值操作符函数定义；（2）由于这些方法是私有的，所以不能被广泛使用，即当语句中要用到Queue类的复制构造函数或重载赋值操作符时，编译将无法通过。假设q1和q2是Queue对象，则以下语句编译将无法通过：

Queue q3(q2);
q1 = q2;

在定义对象不允许被复制的类时，伪私有方法很有用。

2.3 队列的类方法完整代码

Queue类方法定义的完整代码如下。因CConsumer类方法很少，因此将CConsumer类的方法定义一起写在queue.cpp文件中。

#include "Queue.h"

Queue::Queue(int qs):qsize(qs)
{
	Items = 0;
	front = NULL;
	rear = NULL;
}

bool Queue::isEmpty()
{
	return Items == 0;
}
bool Queue::isFull()
{
	return Items = qsize;
}

int Queue::getQueueCount() const
{
	return Items;
}

bool Queue::enqueue(const CConsumer& item)
{
	if (isFull())///队列已满，则入队失败，返回
	{
		return false;
	}
	Node* add = new Node;///创建新入队的客户
	if (add == NULL)///内存空间不足，则入队失败，返回
	{
		return false;
	}
	add->consumer = item;///入队的客户数据复制
	add->next = NULL;///入队后的客户就是排在最后的客户
	Items++;////总的客户数目加1
	if (front == NULL)////如果前面没人的情况下，则新入队的客户就是最前面的客户
	{
		front = add;
	}
	else////前面有人的情况下，原来的rear节点的next指针指向的是NULL，现在需要将它改成add
	{
		rear->next = add;
	}
	rear = add;//客户（新节点）入队后，原本队尾的节点就不再是最后一个节点，最后一个节点变成了新增加的节点add
	return true;
}

bool Queue::dequeue(CConsumer& item)
{
	if (front == NULL)///队列为空时，出队失败，返回
	{
		return false;
	}
	item = front->consumer;//将即将删除的节点数据复制到传递给方法的引用变量
	Items--;///对象计数减1
	Node* temp = front;///保存front节点的位置，供后面删除
	front = front->next;///让节点出队，将front指针设置成指向下一个节点。
	delete temp;///删除出队的节点，以节省内存空间
	if (Items == 0)///当第一个节点出队后，如果队列数量为0，则将指向队尾的节点指针设置为NULL
	{
		rear = NULL;
	}
	return true;
}

Queue::~Queue()
{
	Node* temp;
	while (front != NULL)
	{
		temp = front;
		front = front->next;
		delete temp;
	}
}

void CConsumer::set(long when)
{
	processtime = std::rand() % 3 + 1;
	arrive = when;
}