數據結構學習(C++)之單鏈表

節點類

【說明】因為數據結構裡用到這個結構的地方太多了，如果用《數據結構》那種聲明友元的做法，那聲明不知道要比這個類的本身長多少。不如開放成員，事實上，這種結構只是C中的struct，除了為了方便初始化一下，不需要任何的方法，原書那是畫蛇添足。下面可以看到，鏈表的public部分沒有返回Node或者Node*的函數，所以，別的類不可能用這個開放的接口對鏈表中的節點操作。

【重要修改】原書的缺省構造函數是這樣的Node() : data(NULL), link(NULL) {} 。我原來也是照著寫的，結果當我做擴充時發現這樣是不對的。當Type為結構而不是簡單類型（int、……），不能簡單賦NULL值。這樣做使得定義的模板只能用於很少的簡單類型。顯然，這裡應該調用Type的缺省構造函數。 這也要求，用在這裡的類一定要有缺省構造函數。在下面可以看到構造鏈表時，使用了這個缺省構造函數。當然，這裡是約定帶表頭節點的鏈表，不帶頭節點的情況請大家自己思考。

【閒話】請不要對int *p = new int(1);這種語法有什麼懷疑，實際上int也可以看成一種class。

單鏈表類定義與實現

#ifndef List_H
#define List_H
#ifndef TURE
　#define TURE 1
#endif
#ifndef FALSE
　#define FALSE 0
#endif
typedef int BOOL;
#include "Node.h"
template <class Type> class List //單鏈表定義
{
　//基本上無參數的成員函數操作的都是當前節點，即current指的節點
　//認為表中“第1個節點”是第0個節點，請注意，即表長為1時，最後一個節點是第0個節點
　public:
　　List() { first = current = last = new Node<Type>; prior = NULL; }
　　~List() { MakeEmpty(); delete first; }
　　 void MakeEmpty() //置空表
　　{
　　　Node<Type> *q;
　　　while (first->link != NULL)
　　　{
　　　　q = first->link;
　　　　first->link = q->link;
　　　　delete q;
　　　}
　　　Initialize();
　　}
　　BOOL IsEmpty()
　　{
　　　if (first->link == NULL)
　　　{
　　　　Initialize();
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　int Length() const //計算帶表頭節點的單鏈表長度
　　{
　　　Node<Type> *p = first->link;
　　　int count = 0;
　　　while (p != NULL)
　　　{
　　　　p = p->link;
　　　　count++;
　　　}
　　　return count;
　　}
　　Type *Get()//返回當前節點的數據域的地址
　　{
　　　if (current != NULL) return &current->data;
　　　else return NULL;
　　}
　　BOOL Put(Type const &value)//改變當前節點的data，使其為value
　　{
　　　if (current != NULL)
　　　{
　　　　current->data = value;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　Type *GetNext()//返回當前節點的下一個節點的數據域的地址，不改變current
　　{
　　　if (current->link != NULL) return &current->link->data;
　　　else return NULL;
　　}
　　Type *Next()//移動current到下一個節點，返回節點數據域的地址
　　{
　　　if (current != NULL && current->link != NULL)
　　　{
　　　　prior = current;
　　　　current = current->link;
　　　　return &current->data;
　　　}
　　　else
　　　{
　　　　return NULL;
　　　}
　　}
　　void Insert(const Type &value)//在當前節點的後面插入節點，不改變current
　　{
　　　Node<Type> *p = new Node<Type>(value, current->link);
　　　current->link = p;
　　}
　　BOOL InsertBefore(const Type &value)//在當前節點的前面插入一節點，不改變current，改變prior
　　{
　　　Node<Type> *p = new Node<Type>(value);
　　　if (prior != NULL)
　　　{
　　　　p->link = current;
　　　　prior->link = p;
　　　　prior = p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　BOOL Locate(int i)//移動current到第i個節點
　　{
　　　if (i <= -1) return FALSE;
　　　　current = first->link;
　　　　for (int j = 0; current != NULL && j < i; j++, current = current->link)
　　　　　prior = current;
　　　　　if (current != NULL) return TURE;
　　　　　else return FALSE;
　　}
　　void First()//移動current到表頭
　　{
　　　current = first;
　　　prior = NULL;
　　}
　　void End()//移動current到表尾
　　{
　　　if (last->link != NULL)
　　　{
　　　　for ( ;current->link != NULL; current = current->link)
　　　　　prior = current;
　　　　　last = current;
　　　}
　　　current = last;
　　}
　　BOOL Find(const Type &value)//移動current到數據等於value的節點
　　{
　　　if (IsEmpty()) return FALSE;
　　　for (current = first->link, prior = first; current != NULL && current->data != value;
　　　current = current->link)
　　　　prior = current;
　　　　if (current != NULL) return TURE;
　　　　else return FALSE;
　　}
　　BOOL Remove()//刪除當前節點，current指向下一個節點，如果current在表尾，執行後current = NULL
　　{
　　　if (current != NULL && prior != NULL)
　　　{
　　　　Node<Type> *p = current;
　　　　prior->link = p->link;
　　　　current = p->link;
　　　　delete p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　BOOL RemoveAfter()//刪除當前節點的下一個節點，不改變current
　　{
　　　if (current->link != NULL && current != NULL)
　　　{
　　　　Node<Type> *p = current->link;
　　　　current->link = p->link;
　　　　delete p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　friend ostream & operator << (ostream & strm, List<Type> &l)
　　{
　　　l.First();
　　　while (l.current->link != NULL) strm << *l.Next() << " " ;
　　　　strm << endl;
　　　　l.First();
　　　　return strm;
　　}
　　protected:
　　/*主要是為了高效的入隊算法所添加的。因為Insert()，Remove()，RemoveAfter()有可能改變last但沒有改變last所以這個算法如果在public裡除非不使用這些，否則不正確。但是last除了在隊列中非常有用外，其他的時候很少用到，沒有必要為了這個用途而降低Insert()，Remove()的效率所以把這部分放到protected，實際上主要是為了給隊列繼承*/ void LastInsert(const Type &value)
　{
　　Node<Type> *p = new Node<Type>(value, last->link);
　　last->link = p;
　　last = p;
　}
　void Initialize()//當表為空表時使指針復位
　{
　　current = last = first;
　　prior = NULL;
　}
　//這部分函數返回類型為Node<Type>指針,是擴展List功能的接口
　
　Node<Type> *pGet()
　{
　　return current;
　}
　Node<Type> *pNext()
　{
　　prior = current;
　　current = current->link;
　　return current;
　}
　Node<Type> *pGetNext()
　{
　　return current->link;
　}
　Node<Type> *pGetFirst()
　{
　　return first;
　}
　Node<Type> *pGetLast()
　{
　　return last;
　}
　Node<Type> *pGetPrior()
　{
　　return prior;
　}
　void PutLast(Node<Type> *p)
　{
　　last = p;
　}
//這部分插入刪除函數不建立或刪除節點，是原位操作的接口
　void Insert(Node<Type> *p)
　{
　　p->link = current->link;
　　current->link = p;
　}
　void InsertBefore(Node<Type> *p)
　{
　　p->link = current;
　　prior->link = p;
　　prior = p;
　}
　void LastInsert(Node<Type> *p)
　{
　　p->link = NULL;
　　last->link = p;
　　last = p;
　}
　Node<Type> *pRemove()
　{
　　if (current != NULL && prior != NULL)
　　{
　　　Node<Type> *p = current;
　　　prior->link = current->link;
　　　current = current->link;
　　　return p;
　　}
　　else return NULL;
　}
　Node<Type> *pRemoveAfter()
　{
　　if (current->link != NULL && current != NULL)
　　{
　　　Node<Type> *p = current->link;
　　　current->link = current->link->link;
　　　return p;
　　}
　　else return NULL;
　}
　private:
　　List(const List<Type> &l);
　　Node<Type> *first, *current, *prior, *last;
　　//盡量不要使用last，如果非要使用先用End()使指針last正確
};
#endif

【說明】我將原書的游標類Iterator的功能放在了鏈表類中，屏蔽掉了返回值為Node以及Node*類型的接口，這樣的鏈表簡單、實用，擴充性能也很好。

在完成書後作業的時候，我發現了原書做法的好處，也就是我的做法的不足。如果使用原書的定義，在完成一個功能時，只需要寫出對應的函數實現。而在我的定義中，必須先派生一個類，然後把這個功能作為成員或者友元。但是這種比較並不說明書上的定義比我的要合理。首先，使用到原位操作的情況並不多，書後作業只是一種特殊情況；換句話說，書上的定義只是對完成書後作業更實用些。其次，在使用到鏈表的時候，通常只會用到插入、刪除、取數據、搜索等很少的幾個功能，我的定義足夠用了。而在完成一個軟件時，對鏈表的擴充功能在設計階段就很清晰了，這時可以派生一個新類在整個軟件中使用，對整體的規劃更為有利。而對於單個鏈表的操作，把它作為成員函數更好理解一些。也就是說我的定義靈活性不差。

單鏈表應用

有人曾經建議最好把鏈表和鏈表位置這兩個分開，C++標准庫是這麼做的；但對於初學者來說，一個類總比兩個類好操作。我不清楚在書中這部分的程序究竟調沒調試，但這種語句我是絕對看不懂的：

pa, pb, p 究竟指向什麼？你說這很清楚，ListNode<Term>這樣的節點呗。但按照原書的定義，ListIterator::First()等等函數返回是指向data域的指針，他們怎麼能直接賦值？到了下面更亂了，pb指向的區域直接分解出了Term的數據成員，也就是說是指向Term結構的；然後讓ListNode<Term>類型的指針p指向這個Term結構，最後，居然把這個結構delete了，天啊，ListNode<Term>這樣的節點的data域被delete了！

在下面將會有些重載運算符的例子，我們的工作將是使多項式的運算看起來更符合書寫習慣。完成這些是我覺得我擅自將原書的“＋”改成了PolyAdd()，總要給個交待吧。

下面將完成單鏈表的賦值運算的重載，請把這部分加到List類的public部分。的確，這部分也可以放在多項式類裡實現；但是，復制一個多項式實際上就是復制一個單鏈表，與其單單做一個多項式賦值，還不如完成單鏈表的賦值，讓派生類都能共享。

還記得List類的private裡面的這個List(const List<Type> &l)嗎？當初怕它惹禍，直接將它禁用了，既然現在=都能用了，為了這種語法List<Type> b = a;順便也把它完成了吧。現在可以把它從private放到public了。

終於可以這樣寫了a = b + c * d

【後記】很顯然，在“＋”的處理上我偷懶了，但這是最方便的。乘法部分只要參照手工運算，還是很簡單的，我就不解釋了。對於“－”，可以先完成（－a）這樣的算法，然後就可以用加法完成了，而你要是象我一樣懶很可能就會做這種事－a＝－1×a，真的不提倡，超低的效率。對於除法，如果你會用匯編寫多字節除法（跟手工計算很像），依樣畫葫蘆也能弄出來，但首先要完成“－”。如果要寫又得好長，留給你完成吧。到這裡你明白原位加法的重要了吧，這些運算實際上都是靠它實現的。