《C++多线程编程实战》——1.9　链表、队列和栈示例

2023-10-12 13:53:34

本节书摘来自异步社区出版社《C++多线程编程实战》一书中的第1章，第1.9节，作者：【黑山*】Milos Ljumovic（米洛斯留莫维奇），更多章节内容可以访问云栖社区“异步社区”公众号查看。

1.9　链表、队列和栈示例

下面的示例将演示线性链表（可包含任何泛型类型T）的OOP用法。该示例背后的思想是把继承作为表示“B是一种A”这种关系的模型。

线性链表是一种线性排列元素的结构，第1个元素链接第2个元素，第2个元素链接第3个元素，以此类推。线性链表的基本操作是，在线性链表中插入元素（PUT）和获取元素（GET）。队列是一种线性链表，其中的元素按先进先出的次序排列，即FIFO（First In First Out）。因此，从队列的顶部获取元素，从队列的底部插入新元素。栈也是一种线性链表，从栈中获取元素的顺序与放入元素的顺序相反，也就是说，栈中的元素按先进后出的次序排列，即LIFO（Last In First Out）。

线性链表是按顺序排列的元素集合。每个链表都有用于设置元素值、从链表获取元素或简单查看元素的方法。链表可储存任何类型的对象。但是，为了满足链表类、队列和栈的特殊化，线性链表定义了插入元素和获取元素的精确位置。因此，作为泛化对象的链表是一个基类。

读者应该意识到，以这种方式设计的链表可实现为静态结构或动态结构。也就是说，这种链表可以实现为某种数组或结构，其中的各元素通过指针与相邻的元素链接。用指针来实现，可操作性强。

下面的示例中，将把线性链表实现为指针集合，这些指针指向用链表中的方法放置在链表中的原始对象。这样设计是为了实现链表元素的多态性，而不是把原始对象拷贝给链表。从语义上来看，这需要把更多的精力放在设计上。

准备就绪
确定安装并运行了Visual Studio。

操作步骤
执行以下步骤。

1．创建一个新的空C++控制台应用程序，名为LinkedList。

2．添加一个新的头文件CList.h，并输入下面的代码：

#ifndef _LIST_
#define _LIST_

#include <Windows.h>

template <class T>
class CNode
{
public:
　　CNode(T* tElement) : tElement(tElement), next(0) { }
　　T* Element() const { return tElement; }
　　CNode*& Next(){ return next; }
private:
　　T* tElement;
　　CNode* next;
};

template <class T>
class CList
{
public:
　　CList() : dwCount(0), head(0){ }
　　CList(T* tElement) : dwCount(1), head(new CNode<T>(tElement)){ }
　　virtual ~CList(){ }
　　void Append(CNode<T>*& node, T* tElement);
　　void Insert(T* tElement);
　　bool Remove(T* tElement);
　　DWORD Count() const { return dwCount; }
　　CNode<T>*& Head() { return head; }
　　T* GetFirst(){ return head != NULL ? head->Element() : NULL; }
　　T* GetLast();
　　T* GetNext(T* tElement);
　　T* Find(DWORD(*Function)(T* tParameter), DWORD dwValue);
protected:
　　CList(const CList& list);
　　CList& operator = (const CList& list);
private:
　　CNode<T>* head;
　　DWORD dwCount;
};

template <class T>
void CList<T>::Append(CNode<T>*& node, T* tElement)
{
　　if (node == NULL)
　　{
　　　　dwCount++;
　　　　node = new CNode<T>(tElement);
　　　　return;
　　}
　　Append(node->Next(), tElement);
}

template <class T>
void CList<T>::Insert(T* tElement)
{
　　dwCount++;
　　if (head == NULL)
　　{
　　　　head = new CNode<T>(tElement);
　　　　return;
　　}
　　CNode<T>* tmp = head;
　　head = new CNode<T>(tElement);
　　head->Next() = tmp;
}

template <class T>
bool CList<T>::Remove(T* tElement)
{
　　if (head == NULL)
　　{
　　　　return NULL;
　　}
　　if (head->Element() == tElement)
　　{
　　　　CNode<T>* tmp = head;
　　　　head = head->Next();

　　　　delete tmp;
　　　　dwCount--;

　　　　return true;
　　}

　　CNode<T>* tmp = head;
　　CNode<T>* lst = head->Next();

　　while (lst != NULL)
　　{
　　　　if (lst->Element() == tElement)
　　　　{
　　　　　　tmp->Next() = lst->Next();

　　　　　　delete lst;
　　　　　　dwCount--;

　　　　　　return true;
　　　　}

　　　　lst = lst->Next();
　　　　tmp = tmp->Next();
　　}
　　return false;
}

template <class T>
T* CList<T>::GetLast()
{
　　if (head)
　　{
　　　　CNode<T>* tmp = head;
　　　　while (tmp->Next())
　　　　{
　　　　　　tmp = tmp->Next();
　　　　}
　　　　return tmp->Element();
　　}
　　return NULL;
}

template <class T>
T* CList<T>::GetNext(T* tElement)
{
　　if (head == NULL)
　　{
　　　　return NULL;
　　}
　　if (tElement == NULL)
　　{
　　　　return GetFirst();
　　}
　　if (head->Element() == tElement)
　　{
　　　　return head->Next() != NULL ? head->Next()->Element() : NULL;
　　}

　　CNode<T>* lst = head->Next();
　　while (lst != NULL)
　　{
　　　　if (lst->Element() == tElement)
　　　　{
　　　　　　return lst->Next() != NULL ? lst->Next()->Element() : NULL;
　　　　}
　　　　lst = lst->Next();
　　}
　　return NULL;
}

template <class T>
T* CList<T>::Find(DWORD(*Function)(T* tParameter), DWORD dwValue)
{
　　try
　　{
　　　　T* tElement = NULL;
　　　　while (tElement = GetNext(tElement))
　　　　{
　　　　　　if (Function(tElement) == dwValue)
　　　　　　{
　　　　　　　　return tElement;
　　　　　　}
　　　　}
　　}
　　catch (...) {}
　　return NULL;
}
#endif```
3．有了`CList`类的实现和定义，创建`CQueue`和`CStack`就很容易了。先创建`CQueue`，右键单击【头文件】，创建一个新的头文件`CQueue.h`，并输入下面的代码：

ifndef _QUEUE _

define _QUEUE _

include "CList.h"

template
class CQueue : CList
{
public:
　　CQueue() : CList(){ }
　　CQueue(T* tElement) : CList(tElement){ }
　　virtual ~CQueue(){ }
　　virtual void Enqueue(T* tElement)
　　{
　　　　Append(Head(), tElement);
　　}
　　virtual T* Dequeue()
　　{
　　　　T* tElement = GetFirst();
　　　　Remove(tElement);
　　　　return tElement;
　　}
　　virtual T* Peek()
　　{
　　　　return GetFirst();
　　}
　　CList::Count;
protected:
　　CQueue(const CQueue& cQueue);
　　CQueue& operator = (const CQueue& cQueue);
};

endif`

4．类似地，再创建CStack。右键单击【头文件】，创建一个新的头文件CStack.h，并输入下面的以下代码：

#ifndef _ _STACK_ _
#define _ _STACK_ _

#include "CList.h"

template<class T>
class CStack : CList<T>
{
public:
　　CStack() : CList<T>(){ }
　　CStack(T* tElement) : CList<T>(tElement){ }
　　virtual ~CStack(){ }
　　virtual void Push(T* tElement)
　　{
　　　　Insert(tElement);
　　}
　　virtual T* Pop()
　　{
　　　　T* tElement = GetFirst();
　　　　Remove(tElement);
　　　　return tElement;
　　}
　　virtual T* Peek()
　　{
　　　　return GetFirst();
　　}
　　CList<T>::Count;
protected:
　　CStack(const CStack<T>& cStack);
　　CStack<T>& operator = (const CStack<T>& cStack);
};
#endif```
5． 最后，实现`LinkedList.cpp`中的代码，我们用来充当`main`例程：

include

using namespace std;

include "CQueue.h"

include "CStack.h"

int main()
{
　　CQueue* cQueue = new CQueue();
　　CStack* cStack = new CStack();

　　for (int i = 0; i < 10; i++)
　　{
　　　　cQueue->Enqueue(new int(i));
　　　　cStack->Push(new double(i / 10.0));
　　}

　　cout << "Queue - integer collection:" << endl;
　　for (; cQueue->Count();)
　　{
　　　　cout << *cQueue->Dequeue() << " ";
　　}

　　cout << endl << endl << "Stack - double collection:" << endl;
　　for (; cStack->Count();)
　　{
　　　　cout << *cStack->Pop() << " ";
　　}

　　delete cQueue;
　　delete cStack;

　　cout << endl << endl;
　　return system("pause");
}`
示例分析
首先，解释一下CList类。为了更方便地处理，该链表由CNode类型的元素组成。CNode类有两个特征：tElement指针（指向用户自定义的元素）和next指针（指向链表下一个项）；实现了两个方法：Element和Next。Element方法返回当前元素地址的指针，Next方法返回下一个项地址的引用。

从文字方面看，构造函数称为ctor，析构函数称为dtor。CList的默认构造函数是公有函数，创建一个空的链表。第2个构造函数创建一个包含一个开始元素的链表。具有动态结构的链表必须有析构函数。Append方法在链表的末尾插入一个元素，也是链表的最后一个元素。Count方法返回链表当前的元素个数。Head方法返回链表开始节点的引用。

GetFirst方法返回链表的第1个元素，如果链表为空，则返回NULL。GetLast方法返回链表的最后一个元素，如果链表为空，则返回NULL。GetNext方法返回链表的下一个项，即相对于地址由T* tElement参数提供的项的下一个项。如果未找到该项，GetNex方法返回NULL。

Find方法显然是一个高级特性，针对未定义类型T和未定义的Function方法（带tParameter参数）设计。假设要使用一个包含学生对象的链表，例如迭代数据（如，使用GetNext方法）或查找某个学生。如果有可能为将来定义的类型实现一个返回unsigned long类型（DWORD）的方法，而且该方法要把未知类型数据与dwValue参数做比较，应该怎么做？例如，假设要根据学生的ID找出这名学生，可以使用下面的代码：

#include <windows.h>
#include "CList.h"

class CStudent
{
public:
　　CStudent(DWORD dwStudentId) : dwStudentId(dwStudentId){ }
　　static DWORD GetStudentId(CStudent* student)
　　{
　　　　DWORD dwValue = student->GetId();
　　　　return dwValue;
　　}
　　DWORD GetId() const
　　{
　　　　return dwStudentId;
　　}
private:
　　DWORD dwStudentId;
};

int main()
{
　　CList<CStudent>* list = new CList<CStudent>();
　　list->Insert(new CStudent(1));
　　list->Insert(new CStudent(2));
　　list->Insert(new CStudent(3));
　　CStudent* s = list->Find(&CStudent::GetStudentId, 2);
　　if (s != NULL)
　　{
　　　　// 找到s
　　}
　　return 0;
}```
如果链表用于处理基本类型（如，int），可使用下面的代码：

include

include "CList.h"

DWORD Predicate(int* iElement)
{
　　return (DWORD)(*iElement);
}

int main()
{
　　CList* list = new CList();
　　list->Insert(new int(1));
　　list->Insert(new int(2));
　　list->Insert(new int(3));

　　int* iElement = list->Find(Predicate, 2);
　　if (iElement != NULL)
　　{
　　　　// 找到iElement
　　}
　　return 0;
}`
回到我们的示例。为何要把拷贝构造函数和perator=都声明为protected？要知道，我们在这里实现的链表中储存着指针，而这些指针指向那些在链表外的对象。如果用户能随意（或无意）地通过拷贝构造函数或=运算符来拷贝链表，会非常危险。因此，要把把拷贝构造函数和=运算符设置为protected，不让用户使用。为此，必须先把两个函数声明为protected，然后在需要时再实现它们；否则，编译器在默认情况下会把这两个函数设置为public，然后逐个拷贝指针，这样做是错误的。把它们声明为private也不够。在这种情况下，CList基类的派生类依旧会遇到同样的问题。派生类仍需要要把拷贝构造函数和=运算符声明为protected，否则编译器还是会把这些方法默认生成public。如果基类包含拷贝构造函数和=运算符，派生类就会默认调用它们，除非派生类能显式调用自己的版本。但是，我们的初衷是让派生类用上CList基类中的拷贝构造函数和=运算符，所以将其声明为protected。

CList类的private部分包含了把链表实现为线性链表所需的对象。这意味着链表中的每个元素都指向下一个元素，头节点指向第1个元素。

CQueue和CStack类分别实现为队列和栈。不难看出，设计好CList基类以后（尤其是设计了Enqueue、Dequeue、Push、Pop和Peek方法），实现这两个类有多么简单。只要CList类设计得当，设计CQueue、CStack，甚至其他类都非常简单。

码农公寓

1.9 链表、队列和栈示例

ifndef _QUEUE _

define _QUEUE _

include "CList.h"

endif`

include

include "CQueue.h"

include "CStack.h"

include

include "CList.h"

相关文章

1.9　链表、队列和栈示例