《C++多線程程式設計實戰》——1.9 連結清單、隊列和棧示例ifndef _QUEUE _define _QUEUE _include "CList.h"endif` include include "CQueue.h"include "CStack.h"include include "CList.h"

本節書摘來自異步社群出版社《c++多線程程式設計實戰》一書中的第1章，第1.9節，作者： 【黑山共和國】milos ljumovic（米洛斯 留莫維奇），更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

下面的示例将示範線性連結清單（可包含任何泛型類型t）的oop用法。該示例背後的思想是把繼承作為表示“b是一種a”這種關系的模型。

線性連結清單是一種線性排列元素的結構，第1個元素連結第2個元素，第2個元素連結第3個元素，以此類推。線性連結清單的基本操作是，線上性連結清單中插入元素（put）和擷取元素（get）。隊列是一種線性連結清單，其中的元素按先進先出的次序排列，即fifo（first in first out）。是以，從隊列的頂部擷取元素，從隊列的底部插入新元素。棧也是一種線性連結清單，從棧中擷取元素的順序與放入元素的順序相反，也就是說，棧中的元素按先進後出的次序排列，即lifo（last in first out）。

線性連結清單是按順序排列的元素集合。每個連結清單都有用于設定元素值、從連結清單擷取元素或簡單檢視元素的方法。連結清單可儲存任何類型的對象。但是，為了滿足連結清單類、隊列和棧的特殊化，線性連結清單定義了插入元素和擷取元素的精确位置。是以，作為泛化對象的連結清單是一個基類。

讀者應該意識到，以這種方式設計的連結清單可實作為靜态結構或動态結構。也就是說，這種連結清單可以實作為某種數組或結構，其中的各元素通過指針與相鄰的元素連結。用指針來實作，可操作性強。

下面的示例中，将把線性連結清單實作為指針集合，這些指針指向用連結清單中的方法放置在連結清單中的原始對象。這樣設計是為了實作連結清單元素的多态性，而不是把原始對象拷貝給連結清單。從語義上來看，這需要把更多的精力放在設計上。

準備就緒

确定安裝并運作了visual studio。

操作步驟

執行以下步驟。

1．建立一個新的空c++控制台應用程式，名為<code>linkedlist</code>。

2． 添加一個新的頭檔案<code>clist.h</code>，并輸入下面的代碼：

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&amp; cqueue);

　　cqueue&amp; operator = (const cqueue&amp; cqueue);

};

4．類似地，再建立<code>cstack</code>。右鍵單擊【頭檔案】，建立一個新的頭檔案<code>cstack.h</code>，并輸入下面的以下代碼：

using namespace std;

int main()

　　cqueue* cqueue = new cqueue();

　　cstack* cstack = new cstack();

　　for (int i = 0; i &lt; 10; i++)

　　　　cqueue-&gt;enqueue(new int(i));

　　　　cstack-&gt;push(new double(i / 10.0));

　　cout &lt;&lt; "queue - integer collection:" &lt;&lt; endl;

　　for (; cqueue-&gt;count();)

　　　　cout &lt;&lt; *cqueue-&gt;dequeue() &lt;&lt; " ";

　　cout &lt;&lt; endl &lt;&lt; endl &lt;&lt; "stack - double collection:" &lt;&lt; endl;

　　for (; cstack-&gt;count();)

　　　　cout &lt;&lt; *cstack-&gt;pop() &lt;&lt; " ";

　　delete cqueue;

　　delete cstack;

　　cout &lt;&lt; endl &lt;&lt; endl;

　　return system("pause");

}<code>`</code>

示例分析

首先，解釋一下<code>clist</code>類。為了更友善地處理，該連結清單由<code>cnode</code>類型的元素組成。<code>cnode</code>類有兩個特征：<code>telement</code>指針（指向使用者自定義的元素）和<code>next</code>指針（指向連結清單下一個項）；實作了兩個方法：<code>element</code>和<code>next</code>。<code>element</code>方法傳回目前元素位址的指針，<code>next</code>方法傳回下一個項位址的引用。

從文字方面看，構造函數稱為<code>ctor</code>，析構函數稱為<code>dtor</code>。<code>clist</code>的預設構造函數是公有函數，建立一個空的連結清單。第2個構造函數建立一個包含一個開始元素的連結清單。具有動态結構的連結清單必須有析構函數。<code>append</code>方法在連結清單的末尾插入一個元素，也是連結清單的最後一個元素。<code>count</code>方法傳回連結清單目前的元素個數。head方法傳回連結清單開始節點的引用。

<code>getfirst</code>方法傳回連結清單的第1個元素，如果連結清單為空，則傳回<code>null</code>。<code>getlast</code>方法傳回連結清單的最後一個元素，如果連結清單為空，則傳回<code>null</code>。<code>getnext</code>方法傳回連結清單的下一個項，即相對于位址由t*<code>telement</code>參數提供的項的下一個項。如果未找到該項，<code>getnex</code>方法傳回<code>null</code>。

<code>find</code>方法顯然是一個進階特性，針對未定義類型t和未定義的<code>function</code>方法（帶<code>tparameter</code>參數）設計。假設要使用一個包含學生對象的連結清單，例如疊代資料（如，使用<code>getnext</code>方法）或查找某個學生。如果有可能為将來定義的類型實作一個傳回<code>unsigned long</code>類型（<code>dword</code>）的方法，而且該方法要把未知類型資料與<code>dwvalue</code>參數做比較，應該怎麼做？例如，假設要根據學生的id找出這名學生，可以使用下面的代碼：

dword predicate(int* ielement)

　　return (dword)(*ielement);

}

　　clist* list = new clist();

　　list-&gt;insert(new int(1));

　　list-&gt;insert(new int(2));

　　list-&gt;insert(new int(3));

　　int* ielement = list-&gt;find(predicate, 2);

　　if (ielement != null)

　　　　// 找到ielement

　　return 0;

回到我們的示例。為何要把拷貝構造函數和<code>perator=</code>都聲明為<code>protected？</code>要知道，我們在這裡實作的連結清單中儲存着指針，而這些指針指向那些在連結清單外的對象。如果使用者能随意（或無意）地通過拷貝構造函數或=運算符來拷貝連結清單，會非常危險。是以，要把把拷貝構造函數和=運算符設定為protected，不讓使用者使用。為此，必須先把兩個函數聲明為<code>protected</code>，然後在需要時再實作它們；否則，編譯器在預設情況下會把這兩個函數設定為<code>public</code>，然後逐個拷貝指針，這樣做是錯誤的。把它們聲明為<code>private</code>也不夠。在這種情況下，<code>clist</code>基類的派生類依舊會遇到同樣的問題。派生類仍需要要把拷貝構造函數和=運算符聲明為<code>protected</code>，否則編譯器還是會把這些方法預設生成<code>public</code>。如果基類包含拷貝構造函數和=運算符，派生類就會預設調用它們，除非派生類能顯式調用自己的版本。但是，我們的初衷是讓派生類用上<code>clist</code>基類中的拷貝構造函數和=運算符，是以将其聲明為<code>protected</code>。

<code>clist</code>類的<code>private</code>部分包含了把連結清單實作為線性連結清單所需的對象。這意味着連結清單中的每個元素都指向下一個元素，頭節點指向第1個元素。

<code>cqueue</code>和<code>cstack</code>類分别實作為隊列和棧。不難看出，設計好<code>clist</code>基類以後（尤其是設計了<code>enqueue</code>、<code>dequeue</code>、<code>push</code>、<code>pop</code>和peek方法），實作這兩個類有多麼簡單。隻要<code>clist</code>類設計得當，設計<code>cqueue</code>、<code>cstack</code>，甚至其他類都非常簡單。