雙向鏈表實現
今天晚上用模板方法把雙向鏈表實現了下，由於有點小粗心，在 insert中手抖了下，把tail->prev 打成了 tail->next，由於錯誤是發生在drop函數執行時，讓我一直去調drop函數，調了半天還是一樣錯誤，最後我系統在vs中監視了下值的變化，終於看到是insert出錯了。 看來程序員離不開調試呀。
另外，昨天說的模板輸出重載，我說要在友元的實現時加上 <>， 但是今天我在gcc中測試了下，居然說找不到匹配的函數，導致編譯不通過，真心蛋疼，vs和g++的區別還真心大，看來改天要好好專研下模板輸出重載，知道的朋友希望能夠告知下。
對數據結構的實現，其實都很簡單，思想就是：
1、定義結點結構類，包含數據域和指針域
2、定義 鏈表(樹，圖)結構，其中封裝包含幾個結點，作為數據接口，因為節點定義指向自身類型的指針，因此而後所有的操作都圍繞這個數據接口進行。
對於雙向鏈表來說，結點定義很簡單，一個數據域，一個next指針，表示以後他將指向下一個結點； 一個prev指針，表示它將指向前一個結點。
template<typename T>
struct Node{
T datum;
Node* next;
Node* prev;
};
由於鏈式結構添加的結點都要new出來，且結點類包含了數據域，因此需要對結點類進行構造函數的編寫，一般兩個，帶數據域的（以後new來做鏈表中結點），默認無參的(用於new給head和tail的)；析構函數就不用了，因為其指針域所指向的東西是由表結構new出來的，操作應該留給表。
結點類定義好了後，我們定義下鏈表類，主要部分就是要包含下 head 指針， tail 指針。
另外，所有的表（樹，圖結構）最好包含個 “表示長度的數據”，如size, 這樣求length()操作只要O(1)的復雜度，要不然就要遍歷整個鏈表，復雜度就是O(n)了。
對於head指針，規定 head->next 指向第一個結點，head->prev 指向自身或NULL;
對於tail指針，規定 tail->prev 指向最後一個結點，tail->next指向自身或NULL; 這樣規定了head，tail後，後面的操作就會很順暢，我們就可以next/prev到底了，哈哈。
空的條件為： size == 0 或者 head->next == NULL 或者 tail->prev == NULL ，看個人喜好。
剩下一些增刪改查操作，別手抖寫錯了指向關系就行，另外可以加上一個位置判斷，看看是從頭或從尾開始，哪邊移動的少。
函數寫法可以給的建議是:
若只是訪問不修改，成員函數為const;
若需要操作類類型，則用 & 或 const&;
好的，直接上代碼：
先是頭文件，注意最後一行；
1 #ifndef MY_CHAIN_H 2 #define MY_CHAIN_H 3 #include <ostream> 4 using namespace std; 5 template <class T> 6 struct Node{ 7 T datum; 8 Node* prev; 9 Node* next; 10 11 Node(const T& x); 12 Node(); 13 }; 14 15 16 template<class T> 17 class dList{ 18 public: 19 dList(); 20 ~dList(); 21 bool find(int pos,T& hold) const; 22 int search(const T& x) const; 23 int length() const; 24 bool isEmpty() const; 25 dList<T>& drop(int pos, T& hold); 26 dList<T>& insert(int pos, const T& x); 27 dList<T>& push_back(const T& x); 28 dList<T>& push_front(const T& x); 29 T& operator[](int pos); 30 void show(std::ostream& os) const; 31 friend ostream& operator<< <>(ostream& os, const dList& d); 32 protected: 33 Node<T>* head; 34 Node<T>* tail; 35 int size; 36 }; 37 #endif 38 39 #include "chain.cpp" View Code接著是實現文件：
#ifndef MY_CHAIN_CPP #define MY_CHAIN_CPP #include "chain.h" #include <ostream> #include <cassert> using std::ostream; // 節點類的構造 template<class T> Node<T>::Node(const T& x) : datum(x){ next = prev = NULL; } template<class T> Node<T>::Node(){ next = prev = NULL; datum = 0; } // 雙向鏈表類的構造 template<class T> dList<T>::dList() { head = new Node<T>(); // tail = new Node<T>(); head->next = NULL; head->prev = head; tail = head; tail->next = tail; tail->prev = NULL; size = 0; } // 析構 template<typename T> dList<T>::~dList() { if(head){ // 一個建議，若類中數據成員是指針類型，且指向是通過new出來的，那麼最好這裡加上一個判斷。 當然我這裡是多余的，因為構造時必然new了。 Node<T>* p = head->next; Node<T>* t; while(p != NULL){ t = p; p = p->next; delete t; } delete head; head = NULL; // 最好刪除後指向空 tail = NULL; } } template<class T> bool dList<T>::isEmpty() const { return size == 0; } template<class T> bool dList<T>::find(int pos,T& hold) const // 訪問不修改，成員函數const { if(pos < 1 || pos > size) return false; Node<T>* p; if(pos <= (size>>1)){ // 從頭開始比較快 p = head; int count = pos; while(count--){p = p->next;} // next 給 head }else{ p = tail; // 從尾開始比較快 int count = size - pos; while(count--){p = p->prev;} // 哈哈，中就是為什麼把prev給tail, 代碼是不是很順暢？ } hold = p->datum; return true; } template<class T> int dList<T>::search (const T& x) const { Node<T>* p = head->next; int count = 1; while((p!= NULL) && (p->datum != x)){ p = p->next; count++; } if (p == NULL) { return 0; } return count; } template<class T> int dList<T>::length ()const { return size; } template<class T> dList<T>& dList<T>::push_front (const T& x) // 前插 { Node<T>* p = new Node<T>(x); if (size == 0) { head->next = p; p->prev = NULL; tail->prev = p; p->next = NULL; }else{ p->next = head->next; head->next->prev = p; p->prev = NULL; head->next = p; } ++size; return *this; } template<class T> dList<T>& dList<T>::push_back (const T& x) // 尾插 { Node<T>* p = new Node<T>(x); if (tail->prev == NULL) { head->next = p; p->prev = NULL; tail->prev = p; p->next = NULL; }else{ tail->prev->next = p; p->prev = tail->prev; p->next = NULL; tail->prev = p; } ++size; return *this; } template<class T> dList<T>& dList<T>::insert(int pos, const T& x) // 指定位置插入，范圍[1,size+1] 注意，我的代碼中，1為下標開始；除了後邊重載的[]操作符。 { if (pos == 1) { return push_front (x); } if (pos == (size+1)) { return push_back (x); } Node<T>* in = new Node<T>(x); Node<T>* p; if (pos <= (size/2)) { p = head; int t = pos; while(t--){p = p->next;} }else{ p = tail; int t = size - pos; while(t--){p = p->prev;} } in->next = p; in->prev = p->prev; // 哎，這裡就是我萬惡粗心的地方，Mark下，下次要心細點。 p->prev->next = in; p->prev = in; ++size; return *this; } template<class T> dList<T>& dList<T>::drop(int pos, T& hold) { if (pos < 1 || pos > size) { exit(1); } Node<T>* d = NULL; if(pos == 1){ d = head->next; hold = d->datum; if(size == 1){ tail->prev = NULL; head->next = NULL; }else{ head->next = d->next; d->next->prev = NULL; } --size; delete d; d = NULL; return *this; } if(pos == size){ d = tail->prev; hold = d->datum; tail->prev = d->prev; d->prev->next = NULL; size--; delete d; d = NULL; return *this; }else{ if(pos <= (size/2)){ int c=pos; d = head; while(c--){d = d->next;} }else{ int c = size - pos; d = tail; while(c--){d = d->prev;} } hold = d->datum; d->prev->next = d->next; d->next->prev = d->prev; --size; delete d; d = NULL; return *this; } } template<class T> T& dList<T>::operator[](int pos) { pos = pos + 1; if(pos<1 || pos> size) { exit(1); } Node<T>* p = NULL; if (pos <= (size>>1)) { int t = pos; p = head; while(t--){p = p->next;} }else{ int t = size - pos; p = tail; while (t--) { p = p->prev;} } return p->datum; } template<class T> void dList<T>::show (ostream& os) const { Node<T>* p = head->next; int t = 0; while(p != NULL){ os << p->datum << " "; p = p->next; t++; } assert(t==size); } template<class T> ostream& operator<< <>(ostream& out, const dList<T>& x) { x.show(out); return out; } #endif View Code最後是測試文件：
1 #include "chain.h" 2 #include <iostream> 3 using namespace std; 4 5 int main() 6 { 7 dList<int> dl; 8 int x=0; 9 dl.insert (1,5); 10 cout << "insert pos1 5: " << dl << endl; 11 cout << "length: " << dl.length() << endl; 12 dl.push_front (3); 13 cout << "push front 3: " << dl << endl; 14 cout << "length: " << dl.length() << endl; 15 dl.push_back (6); 16 cout << "push back 6: " << dl << endl; 17 cout << "length: " << dl.length() << endl; 18 dl.insert(4,8); 19 cout << "insert pos4 8: " << dl << endl; 20 cout << "length=" << dl.length () << endl; 21 dl.find (3,x); 22 dl.drop(2,x); 23 cout << "drop pos 2: " << dl << endl; 24 cout << "length=" << dl.length () << endl; 25 cout << "dl[0]=" << dl[0] << endl; 26 dl[0] = 10; 27 cout << "dl[0]=" << dl[0] << endl; 28 cout << dl << endl; 29 } View Code結果如下圖所示：
補充： 其實還可以重載更多的操作符，有心情的朋友可以自己添加下，比如++(int), ++操作等。甚至，可以加入個迭代器類，這樣更方便使用，有時間可以實現下哦。
另外，心細，心細，手別抖。 自勉下！
