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

本节书摘来自异步社区出版社《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)

 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 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，甚至其他类都非常简单。

【数组与链表算法】矩阵算法在程序中常见的简单应用 | C++ 数组与链表都是相当重要的结构化数据类型，也都是典型线性表的应用。线性表用于计算机中的数据存储结构，按照内存存储的方式基本上可以分为以下两种：静态数据结构和动态数据结构。数组类型就是一种典型的静态数据结构，动态数据结构又称为链表。在我前面的算法系列文章都细致的对二者的使用方法做过讲解。
【奇妙的数据结构世界】用图像和代码对链表的使用进行透彻学习 | C++ 简单来说，数据结构是一种辅助程序设计并且进行优化的方法论，它不仅讨论数据的存储与处理的方法，同时也考虑到了数据彼此之间的关系与运算，从而极大程度的提高程序执行的效率，减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用，选择合适正确的数据结构，可以让算法发挥出更大的性能，给设计的程序带来更高效率的算法。
【C/C++】用格雷戈里公式求π 输入精度e，使用格雷戈里公式（π/4​=1-1/3+1/5+...）求π的近似值，精确到最后一项的绝对值小于e。要求定义和调用函数funpi(e)求π的近似值。
洛谷P1996 约瑟夫问题 c++链表做法 n 个人围成一圈，从第一个人开始报数,数到 mm 的人出列，再由下一个人重新从 11 开始报数，数到 mm 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。 输入两个整数 n,mn,m。 输出一行 nn 个整数，按顺序输出每个出圈人的编号。 输入输出样例 输入 #1 输出 #1 3 6 9 2 7 1 8 5 10 4
LeetCode1290 二进制链表转整数C++解法(vector实现) 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。
异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区，也是国内领先的IT专业图书社区，致力于优质学习内容的出版和分享，实现了纸书电子书的同步上架，于2015年8月上线运营。公众号【异步图书】，每日赠送异步新书。