單鏈表是最基本最簡單的結構了，用處也蠻多的吧，尤其是後面在層序結構的各種樹與圖結構的時候大量使用鏈表而且還很多是單鏈表形式的。學習雙向鏈表還是由約瑟夫問題引入的呢，在單鏈表的刪除操作時需要用並排的兩個指針同步向後移動，為避免這個問題雙向鏈表就派上用場了。雙向鏈表顧名思義是每個結點有兩個方向了，那麼在結點裡面不僅僅要保存一個後向指針還要保存一個前向指針了。 [cpp] #pragma once #include<iostream> using namespace std; template<class T> class LinkNode //節點類 { public: //全為公共的方便操作 T data; //模板類型的一個數據 LinkNode<T> *next; //該結點的一個指針，用於指向後繼 LinkNode<T> *prior;//用於指向前驅 public: LinkNode(LinkNode<T> *ptr = NULL)//只初始化指針的構造函數,並使指針域為空 { next = ptr; prior = ptr; } LinkNode(const T& item,LinkNode<T> *ptr = NULL)//數據與指針一同初始化的構造函數，依舊指針域默認參數為空 { data = item; next = ptr; prior = ptr; } ~LinkNode(){} }; 雙向鏈表在插入的時候搭鏈是一個很有講究的過程，某些步驟是有嚴格順序的： [cpp] newNode->prior = current; //雙向鏈表插入的關鍵四步，最後一句必須最後執行 newNode->next = current->next; current->next->prior = newNode; current->next = newNode; 大致上就是先搞定新結點的prior和next指針，然後是待插位置的後一個結點的prior和前一個結點的next了。 雙向鏈表的刪除直接是先保存待刪除結點指針然後覆蓋就行了，其他的操作基本可以看作是單鏈表了。 [cpp] #pragma once //#include"LinearList.h" #include"LinkNode.h" #include<iostream> using namespace std; template<class T>//繼承的過程中，加上此句派生類依然為類模板 class List { protected: LinkNode<T>* first;//封裝 public: List(); //List(const T& x);//感覺沒用到過 List(List<T>& L); ~List(); void makeEmpty();//依次銷毀每個結點的空間 int Length() const;//搜索當前表節點數 LinkNode<T>* getHead() const;//返回頭指針 LinkNode<T>* Search(T x) const;//搜索並返回指針 LinkNode<T>* Locate(int i) const;//定位並返回指針 bool GetData(int i,T& x) const;//返回第i個結點的元素值以引用的形式 bool SetData(int i,T& x);//修改第i個結點的元素值 bool Insert(int i,T& x);//在第i個節點後面插入新節點元素值 LinkNode<T>* Remove(int i,T& x);//刪除第i個結點 bool isEmpty() const;//判表空 void Sort(); //排序 void input(T endTag);//建立表並輸入 void output();//輸出表 void operator = (List<T>& L);//復制重載 }; template<class T> List<T>::List() { first = new LinkNode<T>;//構造函數中開辟頭結點 } template<class T> List<T>::List(List<T>& L) { LinkNode<T> *srcptr = L.getHead() ->next; //獲取頭指針 用於遍歷 LinkNode<T> *destptr = first = new LinkNode<T>;//建立頭結點 初始化 LinkNode<T> *newNode; T value; while(srcptr != NULL)//直到最後一個結點的尾指針為空結束 { value = srcptr->data; newNode = new LinkNode<T>(value); newNode->prior = destptr;//往新鏈表的後面插入 destptr->next = newNode; srcptr = srcptr->next;//後移 destptr = destptr->next; } } template<class T> List<T>::~List() {} template<class T> void List<T>::makeEmpty() //全部銷毀指針資源 { LinkNode<T> *current = first->next; LinkNode<T> *del; while(current != NULL) { del = current; current = current->next; delete del; } } template<class T> int List<T>::Length() const { int count = 0; LinkNode<T> *current = first;//頭指針副本用於遍歷 while(current->next != NULL)//與單鏈表的遍歷控制條件相同，當前結點後後繼是否為空 { current = current->next; count++ ; } return count; } template<class T> LinkNode<T>* List<T>::getHead() const { return first; } template<class T> LinkNode<T>* List<T>::Search(T x) const { LinkNode<T> *current = first->next; while(current != NULL)//此時的控制條件為某個結點的next知否為空 { if(current->data == x) return current;//如果查詢到直接函數返回,不用無用操作(如果鏈表中有多個x元素值,則以第一個為准返回) current = current->next; } return NULL; } template<class T> LinkNode<T>* List<T>::Locate(int i) const { if(i < 0) //定位可以是第0個，也就是頭結點指針 return NULL; LinkNode<T> *current = first;int k=0; while(current != NULL && k < i)//雙條件控制後者其更多的作用 { current = current->next; k++; } //for(int k=0 ;k < i ;k++)//遍歷到第i個 // current = current->next; return current;//指向第i個元素的指針 } template<class T> bool List<T>::GetData(int i,T& x) const //參數中有下標值的一般先判斷其下標值是否合法 { if(i <= 0) return false; LinkNode<T> *current = Locate(i); if(current == NULL) return false; x = current->data; retrun true; } template<class T> bool List<T>::SetData(int i,T& x) { if(i <= 0) return false; LinkNode<T> *current = Locate(i); if(current == NULL) return false; current->data = x; return true; } template<class T> bool List<T>::Insert(int i,T& x) { if(i < 0 )//可以插入在第一個結點之前,有頭結點的好處代碼一致 return false; LinkNode<T> *current = Locate(i); return false; LinkNode<T> *newNode = new LinkNode<T>(x); if(newNode == NULL) return false; newNode->prior = current; //雙向鏈表插入的關鍵四步，順序不能變，最後一句必須最後執行 newNode->next = current->next; current->next->prior = newNode; current->next = newNode; return true; } template<class T> LinkNode<T>* List<T>::Remove(int i,T& x) { if(i <= 0) return NULL; LinkNode<T> *current = Locate(i);//和單鏈表不同的是,雙向鏈表有前指針可以指向前驅,所以定位到第i個就好 if(current ==NULL) return NULL; current->next->prior = current->prior;//雙向鏈表刪除操作較為簡單明了 current->prior->next = current->next;//重新搭鏈 x = current->data; delete current;//銷毀指針資源 } template<class T> bool List<T>::isEmpty() const { return ((first->next == NULL) ? true : false); } template<class T> void List<T>::input(T endTag) { LinkNode<T> *newNode,*last = first; T value; cin>>value; while(value != endTag) { newNode = new LinkNode<T>(value); newNode->prior = last; last->next = newNode; last = newNode; cin>>value; } } template<class T> void List<T>::output()//輸出 { cout<<"雙向鏈表輸出如下:"<<endl; LinkNode<T> *current = first->next; int count = 0; while(current != NULL) { cout<<"#"<<count+1<<":"<<current->data<<endl; current = current->next; count++; } } template<class T> void List<T>::Sort()//最小選擇 排序 { LinkNode<T> *current1,*current2;//下面連續取後繼指針把外層循環控制在倒數第二個結點 for(current1 = first->next ; current1->next != NULL ; current1 = current1->next) { for(current2 = current1->next ; current2 != NULL ; current2 = current2->next) { if(current1->data > current2->data) { T temp; temp = current1->data; current1->data = current2->data; current2->data = temp; } } } } template<class T> void List<T>::operator= (List<T> &L) { makeEmpty();//先全部銷毀指針資源 LinkNode<T> *srcptr = L.getHead() ->next; //獲取頭指針 用於遍歷 LinkNode<T> *destptr = first; //= new LinkNode<T>;//不用於賦值初始化,只用於復制,不用建立新頭結點 LinkNode<T> *newNode; T value; while(srcptr != NULL)//直到最後一個結點的尾指針為空結束 { value = srcptr->data; newNode = new LinkNode<T>(value); newNode->prior = destptr;//往新鏈表的後面插入 destptr->next = newNode; srcptr = srcptr->next;//後移 destptr = destptr->next; } }
