【正文】 環(huán)鏈表的示例 ? 帶表頭結點的循環(huán)鏈表 a0 a1 a2 an1 first an1 first a1 a0 first (空表 ) (非空表 ) 91 template class T struct CircLinkNode { //鏈表結點類定義 E data。 CircLinkNodeT *link。 CircLinkNode ( CircLinkNodeT *next = NULL ) { link = next。 } CircLinkNode ( T d, CircLinkNodeT *next = NULL ) { data = d。 link = next。 } bool Operator==(T x) { return == 。 } bool Operator!=(T x) { return != 。 } }。 循環(huán)鏈表類的定義 92 template class T //鏈表類定義 class CircList : public LinearListT { private: CircLinkNodeT *first, *last。 //頭指針 , 尾指針 public: CircList(const T x)。 //構造函數 CircList(CircListTamp。 L)。 //復制構造函數 ～ CircList()。 //析構函數 int Length() const。 //計算鏈表長度 bool IsEmpty() { return firstlink == first。 } //判表空否 CircLinkNodeT *getHead() const。 //返回表頭結點地址 93 void setHead ( CircLinkNodeT *p )。 //設置表頭結點地址 CircLinkNodeT *Search ( T x )。 //搜索 CircLinkNodeT *Locate ( int i )。 //定位 T *getData ( int i )。 //提取 void setData ( int i, T x )。 //修改 bool Insert ( int i, T x )。 //插入 bool Remove ( int i, Tamp。 x)。 //刪除 }。 ? 循環(huán)鏈表與單鏈表的操作實現，最主要的不同就是掃描到鏈尾，遇到的不是 NULL，而是表頭。 94 搜索不成功 循環(huán)鏈表的搜索算法 搜索 25 搜索成功 搜索 15 first 31 48 15 57 ? ? ? current current current first 31 48 15 57 ? ? ? ? current current current current current 95 循環(huán)鏈表的搜索算法 template class T, class E CircListNodeT, E * CircListT, E::Search( T x ) { //在鏈表中從頭搜索其數據值為 x 的結點 current = firstlink。 while ( current != first amp。amp。 currentdata != x ) current = currentlink。 return current。 } 96 帶尾指針的循環(huán)鏈表 rear 31 48 15 57 22 ? 如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結構。 ?在表尾插入，時間復雜性 O(1) ?在表尾刪除，時間復雜性 O(n) ?在表頭插入，相當于在表尾插入 ?在表頭刪除，時間復雜性 O(1) 97 用循環(huán)鏈表求解約瑟夫問題 ? 約瑟夫問題的提法 ? n 個人圍成一個圓圈，首先第 1 個人從 1 開始，一個人一個人順時針報數 , 報到第 m 個人，令其出列。然后再從下一 個人開始，從 1 順時針報數，報到第 m 個人，再令其出列， … ，如此下去 , 直到圓圈中只剩一個人為止。此人即 為優(yōu)勝者。 ? 用不帶表頭結點的循環(huán)鏈表來組織。 98 例如 n = 8 m = 3 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 99 n = 8 m = 3 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 100 求解 Josephus問題的算法 include include “” template class T, class E void Josephus(CircListT, Eamp。 Js, int n, int m) { CircLinkNodeT, E *p = (), *pre = NULL。 int i, j。 for ( i = 0。 i n1。 i++ ) { //執(zhí)行 n1次 for ( j = 1。 j m。 j++) //數 m1個人 { pre = p。 p = plink。 } cout “出列的人是” pdata endl。 101 prelink = plink。 delete p。 //刪去 p = prelink。 } }。 void main() { CircListint, int clist。 int i, n m。 cout “輸入游戲者人數和報數間隔 : ”。 cin n m。 for (i = 1。 i = n。 i++ ) (i, i)。 //約瑟夫環(huán) Josephus(clist, n, m)。 //解決約瑟夫問題 } 102 雙向鏈表 (Doubly Linked List) ? 雙向鏈表是指在前驅和后繼方向都能游歷（遍歷）的線性鏈表。 ? 雙向鏈表每個結點結構： ? 雙向鏈表通常采用帶表頭結點的循環(huán)鏈表形式。 前驅方向 ? ? 后繼方向 lLink data rLink 103 ? 結點指向 p == plLinkrLink == prLinklLink 非空表 空表 plLink prLink p lLink rLink first first 104 雙向循環(huán)鏈表類的定義 template class T struct DblNode { //鏈表結點類定義 T data。 //鏈表結點數據 DblNodeT *lLink, *rLink。 //前驅、后繼指針 DblNode ( DblNodeT *l = NULL, DblNodeT *r = NULL ) { lLink = l。 rLink = r。 } //構造函數 DblNode ( T value, DblNodeT *l = NULL, DblNodeT *r = NULL) { data = value。 lLink = l。 rLink = r。 } //構造函數 }。 105 template class T class DblList { //鏈表類定義 public: DblList ( T uniqueVal ) { //構造函數 first = new DblNodeT (uniqueVal)。 firstrLink = firstlLink = first。 }。 DblNodeT *getFirst () const { return first。 } void setFirst ( DblNodeT *ptr ) { first = ptr。 } DblNodeT *Search ( T x, int d)。 //在鏈表中按 d指示方向尋找等于給定值 x的結點 , //d=0按前驅方向 ,d≠0按后繼方向 106 DblNodeT *Locate ( int i, int d )。 //在鏈表中定位序號為 i(≥0)的結點 , d=0按前驅方 //向 ,d≠0按后繼方向 bool Insert ( int i, T x, int d )。 //在第 i個結點后插入一個包含有值 x的新結點 ,d=0 //按前驅方向 ,d≠0按后繼方向 bool Remove ( int i, Tamp。 x, int d )。 //刪除第 i個結點 bool IsEmpty() { return firstrlink == first。 } //判雙鏈表空否 private: DblNodeT *first。 //表頭指針 }。 107 雙向循環(huán)鏈表的搜索算法 搜索成功 搜索不成功 first first 31 31 48 48 15 15 57 57 搜索 15 ? ? ? 搜索 25 ? ? ? ? 108 雙向循環(huán)鏈表的搜索算法 template class T DblNodeT *DblListT::Search (T x, int d) { //在雙向循環(huán)鏈表中尋找其值等于 x的結點。 DblNodeT *current = (d == 0)? firstlLink : firstrLink。 //按 d確定搜索方向 while ( current != first amp。amp。 currentdata != x ) current = (d == 0) ? currentlLink : currentrLink。 if ( current != first ) return current。 //搜索成功 else return NULL。 //搜索失敗 }。 109 雙向循環(huán)鏈表的插入算法 (非空表 ) newNoderLink = currentrLink。 currentrLink = newNode。 newNoderLinklLink = newNode。 newNodelLink = current。 first first 31 48 15 后插入 25 current newNode 31 48 25 15 current 110 雙向循環(huán)鏈表的插入算法 (空表 ) first 后插入 25 curren