數據結構學習講座(C++) 單鏈表（１）

單鏈表()
   
節點類

#ifndef Node_H
#define Node_H

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

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

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

　　單鏈表類定義與實現

#ifndef List_H
#define List_H
#ifndef TURE
　#define TURE
#endif
#ifndef FALSE
　#define FALSE
#endif

typedef int BOOL;

#include Nodeh

template <class Type> class List //單鏈表定義
{
　//基本上無參數的成員函數操作的都是當前節點即current指的節點
　//認為表中第個節點是第個節點請注意即表長為時最後一個節點是第個節點
　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 = ;
　　　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 <= ) return FALSE;
　　　　current = first>link;
　　　　for (int j = ; 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)
　　{
　　　lFirst();
　　　while (lcurrent>link != NULL) strm << *lNext() << ;
　　　　strm << endl;
　　　　lFirst();
　　　　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)
　{<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23010.html