在使用鏈表來解決約瑟夫問題的時候，用到了循環鏈表。循環鏈表又分為單向循環鏈表與雙向循環鏈表，約瑟夫問題采用單項循環鏈表可以得到很好的而解決了，但是單向鏈表的很大的缺陷仍然存在，那就是在刪除的時候需要兩個並排指針同步移動。雙向鏈表就可以解決這個問題，因為在雙向鏈表中的每一個結點都有兩個指針域來分別指向其前驅和後繼。這樣子在遍歷鏈表時不用兩個指針，直接使用一個就好，當鎖定位置後，取出其前驅然後再保存當前位置最後做刪除操作就好了。 結點類型不變，存在兩個指針： [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] template<class T> List<T>::List() { first = new LinkNode<T>;//構造函數中開辟頭結點 first->prior = first;//頭結點的前後指針均指向其本身 邏輯循環 first->next = first; } 在每一次的插入和刪除之後需要把首尾連接起來，其余操作可看做是普通鏈表。 #pragma once #include"LinkNode.h" #include<iostream> using namespace std; template<class T>//繼承的過程中，加上此句派生類依然為類模板 class List { protected: LinkNode<T>* first;//封裝 public: List(); 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>;//構造函數中開辟頭結點 first->prior = first;//頭結點的前後指針均指向其本身 邏輯循環 first->next = first; } template<class T> List<T>::List(List<T>& L) { LinkNode<T> *L_HEAD = L.getHead(); LinkNode<T> *srcptr = L_HEAD->next; //獲取頭指針 用於遍歷 LinkNode<T> *destptr = first = new LinkNode<T>;//建立頭結點 初始化 LinkNode<T> *newNode; T value; while(srcptr != L_HEAD)//直到循環到首指針w為結束 { value = srcptr->data; newNode = new LinkNode<T>(value); newNode->prior = destptr;//往新鏈表的後面插入 destptr->next = newNode; srcptr = srcptr->next;//後移 destptr = destptr->next; } destptr->next = first;//首尾相接 建立循環 first->prior = destptr; } template<class T> List<T>::~List() { makeEmpty(); } template<class T> void List<T>::makeEmpty() //全部銷毀指針資源 { LinkNode<T> *current = first->next; LinkNode<T> *del; while(current != first) { 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 != first)//與單鏈表的遍歷控制條件相同，當前結點後後繼是否為空 { 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++; } 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) { makeEmpty();//在輸入前先清空鏈表 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; } last->next = first; //重新首尾連接 first->prior = last; } template<class T> void List<T>::output()//輸出 { cout<<"雙向鏈表輸出如下:"<<endl; LinkNode<T> *current = first->next; int count = 0; while(current != first) { 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 != first ; current1 = current1->next) { for(current2 = current1->next ; current2 != first ; 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> *L_HEAD = L.getHead(); //獲取首指針 遍歷終止條件 LinkNode<T> *srcptr = L_HEAD->next; //獲取頭指針 用於遍歷 LinkNode<T> *destptr = first; //= new LinkNode<T>;//不用於賦值初始化,只用於復制,不用建立新頭結點 LinkNode<T> *newNode; T value; while(srcptr != L_HEAD)//直到最後一個結點的尾指針為空結束 { value = srcptr->data; newNode = new LinkNode<T>(value); newNode->prior = destptr;//往新鏈表的後面插入 destptr->next = newNode; srcptr = srcptr->next;//後移 destptr = destptr->next; } destptr->next = first;//首尾相接 循環 first->prior = destptr; }
