【正文】 環(huán)鏈表的示例 ? 帶表頭結(jié)點(diǎn)的循環(huán)鏈表 a0 a1 a2 an1 first an1 first a1 a0 first (空表 ) (非空表 ) 91 template class T struct CircLinkNode { //鏈表結(jié)點(diǎn)類定義 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)。 //構(gòu)造函數(shù) CircList(CircListTamp。 L)。 //復(fù)制構(gòu)造函數(shù) ～ CircList()。 //析構(gòu)函數(shù) int Length() const。 //計(jì)算鏈表長(zhǎng)度 bool IsEmpty() { return firstlink == first。 } //判表空否 CircLinkNodeT *getHead() const。 //返回表頭結(jié)點(diǎn)地址 93 void setHead ( CircLinkNodeT *p )。 //設(shè)置表頭結(jié)點(diǎn)地址 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)鏈表與單鏈表的操作實(shí)現(xià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 ) { //在鏈表中從頭搜索其數(shù)據(jù)值為 x 的結(jié)點(diǎn) 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)鏈表結(jié)構(gòu)。 ?在表尾插入，時(shí)間復(fù)雜性 O(1) ?在表尾刪除，時(shí)間復(fù)雜性 O(n) ?在表頭插入，相當(dāng)于在表尾插入 ?在表頭刪除，時(shí)間復(fù)雜性 O(1) 97 用循環(huán)鏈表求解約瑟夫問題 ? 約瑟夫問題的提法 ? n 個(gè)人圍成一個(gè)圓圈，首先第 1 個(gè)人從 1 開始，一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù) , 報(bào)到第 m 個(gè)人，令其出列。然后再?gòu)南乱? 個(gè)人開始，從 1 順時(shí)針報(bào)數(shù)，報(bào)到第 m 個(gè)人，再令其出列， … ，如此下去 , 直到圓圈中只剩一個(gè)人為止。此人即 為優(yōu)勝者。 ? 用不帶表頭結(jié)點(diǎn)的循環(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++) //數(shù) m1個(gè)人 { pre = p。 p = plink。 } cout “出列的人是” pdata endl。 101 prelink = plink。 delete p。 //刪去 p = prelink。 } }。 void main() { CircListint, int clist。 int i, n m。 cout “輸入游戲者人數(shù)和報(bào)數(shù)間隔 : ”。 cin n m。 for (i = 1。 i = n。 i++ ) (i, i)。 //約瑟夫環(huán) Josephus(clist, n, m)。 //解決約瑟夫問題 } 102 雙向鏈表 (Doubly Linked List) ? 雙向鏈表是指在前驅(qū)和后繼方向都能游歷（遍歷）的線性鏈表。 ? 雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)： ? 雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式。 前驅(qū)方向 ? ? 后繼方向 lLink data rLink 103 ? 結(jié)點(diǎn)指向 p == plLinkrLink == prLinklLink 非空表 空表 plLink prLink p lLink rLink first first 104 雙向循環(huán)鏈表類的定義 template class T struct DblNode { //鏈表結(jié)點(diǎn)類定義 T data。 //鏈表結(jié)點(diǎn)數(shù)據(jù) DblNodeT *lLink, *rLink。 //前驅(qū)、后繼指針 DblNode ( DblNodeT *l = NULL, DblNodeT *r = NULL ) { lLink = l。 rLink = r。 } //構(gòu)造函數(shù) DblNode ( T value, DblNodeT *l = NULL, DblNodeT *r = NULL) { data = value。 lLink = l。 rLink = r。 } //構(gòu)造函數(shù) }。 105 template class T class DblList { //鏈表類定義 public: DblList ( T uniqueVal ) { //構(gòu)造函數(shù) 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指示方向?qū)ふ业扔诮o定值 x的結(jié)點(diǎn) , //d=0按前驅(qū)方向 ,d≠0按后繼方向 106 DblNodeT *Locate ( int i, int d )。 //在鏈表中定位序號(hào)為 i(≥0)的結(jié)點(diǎn) , d=0按前驅(qū)方 //向 ,d≠0按后繼方向 bool Insert ( int i, T x, int d )。 //在第 i個(gè)結(jié)點(diǎn)后插入一個(gè)包含有值 x的新結(jié)點(diǎn) ,d=0 //按前驅(qū)方向 ,d≠0按后繼方向 bool Remove ( int i, Tamp。 x, int d )。 //刪除第 i個(gè)結(jié)點(diǎn) 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的結(jié)點(diǎn)。 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