Ch02 線性表03

1、循環(huán)鏈表 (Circular List)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的 link 指針不為 NULL，而是指向了表的前端。為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。1循環(huán)鏈表的示例(不帶頭結(jié)點(diǎn))帶表頭結(jié)點(diǎn)的循環(huán)鏈表 a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)2template struct CircLinkNode / 鏈表結(jié)點(diǎn)類定義 T data; CircLinkNode *link; CircLinkNode ( CircLinkNode *next =

2、 NULL) link = next; CircLinkNode ( T& d, CircLinkNode *next = NULL ) data = d; link = next; bool operator=(T& x) return data = x; bool operator!=(T& x) return data != x; ;循環(huán)鏈表類的定義3template / 鏈表類定義class CircList : public LinearList private: CircLinkNode *first, *last; / 頭指針, 尾指針public: CircList(const

3、 T& x); / 構(gòu)造函數(shù)CircList(CircList& L); / 復(fù)制構(gòu)造函數(shù) CircList( ); / 析構(gòu)函數(shù) int Length( )const; / 計(jì)算鏈表長度bool IsEmpty( )const return first-link = first; / 判表空否CircLinkNode *getHead( ) const; / 返回表頭結(jié)點(diǎn)地址4 void setHead ( CircLinkNode *p ); / 設(shè)置表頭結(jié)點(diǎn)地址 CircLinkNode *Search ( T& x ); / 搜索CircLinkNode *Locate ( int i

4、 ); / 定位 T *getData ( int i ); / 提取 void setData ( int i, T& x ); / 修改bool Insert ( int i, T& x ); / 插入 bool Remove ( int i, T& x); / 刪除;循環(huán)鏈表與單鏈表的操作實(shí)現(xiàn)，最主要的不同就是掃描到鏈尾，遇到的不是NULL，而是表頭。5搜索不成功循環(huán)鏈表的搜索算法搜索25搜索成功搜索15first31481557currentcurrentcurrentfirst31481557currentcurrentcurrentcurrentcurrent6循環(huán)鏈表的搜索算法t

5、emplate CircListNode * CircList:Search( T& x )const / 在鏈表中從頭搜索其數(shù)據(jù)值為 x 的結(jié)點(diǎn) CircListNode * current = first-link; while ( current != first & current-data != x ) current = current-link; if(current = first) return NULL; else return current;7帶尾指針的循環(huán)鏈表rear3148155722如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。在表尾插入，時(shí)間

6、復(fù)雜性 O(1)在表尾刪除，時(shí)間復(fù)雜性 O(n)在表頭插入，相當(dāng)于在表尾插入在表頭刪除，時(shí)間復(fù)雜性 O(1)8用循環(huán)鏈表求解約瑟夫問題約瑟夫問題的提法n 個(gè)人圍成一個(gè)圓圈，首先第 1 個(gè)人從 1 開始，一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù), 報(bào)到第 m 個(gè)人，令其出列。然后再從下一個(gè)人開始，從 1 順時(shí)針報(bào)數(shù)，報(bào)到第 m 個(gè)人，再令其出列，如此下去, 直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。用不帶表頭結(jié)點(diǎn)的循環(huán)鏈表來組織。9例如 n = 8 m = 3012345671234567801234567123456780123456712345678012345671234567801234567123456

7、78012345671234567810n = 8 m = 301234567123456780123456712345678012345671234567811求解 Josephus 問題的算法 #include #include CircList.htemplate void Josephus(CircList& Js, int n, int m) CircLinkNode *p = Js.getHead( ), *pre = NULL; int i, j; for ( i = 0; i n - 1; i+ ) / 執(zhí)行 n 1 次 for ( j = 1; j link; cout 出列

8、的人是: data link = p-link; delete p; / 刪去 p = pre-link; ;void main(void) CircList clist; int i, n, m; cout n m; for (i = 1; i lLink-rLink = p-rLink-lLink非空表 空表p-lLinkp-rLinkplLinkrLinkfirstfirst15雙向循環(huán)鏈表類的定義template struct DblNode / 鏈表結(jié)點(diǎn)類定義 T data;/ 鏈表結(jié)點(diǎn)數(shù)據(jù) DblNode *lLink, *rLink; / 前驅(qū)、后繼指針 DblNode ( Db

9、lNode *l = NULL, DblNode *r = NULL ) lLink = l; rLink = r; / 構(gòu)造函數(shù) DblNode ( T& value, DblNode *l = NULL, DblNode *r = NULL) data = value; lLink = l; rLink = r; ;16template class DblList / 鏈表類定義private: DblNode *first; / 表頭指針public:DblList ( T& uniqueVal ) / 構(gòu)造函數(shù) assert(first = new DblNode (uniqueVal

10、); first-rLink = first-lLink = first;DblNode *getFirst ( ) const return first; void setFirst ( DblNode *ptr ) first = ptr; 17 DblNode *Search ( T& x, int d = 1)const; / 在鏈表中按 d 指示方向?qū)ふ业扔诮o定值 x 的 / 結(jié)點(diǎn), d = 0按前驅(qū)方向, d 0按后繼方向 DblNode *Locate ( int i, int d = 1)const; / 在鏈表中定位序號(hào)為 i (0)的結(jié)點(diǎn) bool Insert ( int

11、 i, T& x, int d = 1); / 在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)包含有值 x 的新結(jié)點(diǎn) bool Remove ( int i, T& x, int d = 1); / 刪除第 i 個(gè)結(jié)點(diǎn) bool IsEmpty( )const return first-rlink = first; / 判雙鏈表空否;18雙向循環(huán)鏈表的搜索算法搜索成功搜索不成功firstfirst3131484815155757搜索15搜索2519雙向循環(huán)鏈表的搜索算法template DblNode *DblList:Search (T& x, int d)const / 在雙向循環(huán)鏈表中尋找其值等于 x 的結(jié)

12、點(diǎn)。 DblNode *current = (d = 0)? first-lLink : first-rLink; / 按 d 確定搜索方向while ( current != first & current-data != x ) current = (d = 0) ? current-lLink : current-rLink;if ( current != first ) return current; / 搜索成功else return NULL; / 搜索失敗;20雙向循環(huán)鏈表的插入算法 (非空表)newNode-rLink = current-rLink; current-rLin

13、k = newNode;newNode-rLink-lLink = newNode; newNode-lLink = current;firstfirst314815后插入25currentnewNode31482515current21雙向循環(huán)鏈表的插入算法 (空表)first后插入25currentnewNode25firstcurrentnewNode-rLink = current-rLink (newNode-rLink = first); current-rLink = newNode;newNode-rLink -lLink = newNode; ( first-lLink =

14、newNode ) newNode-lLink = current;22雙向循環(huán)鏈表的插入算法template bool DblList:Insert ( int i, T& x, int d ) / 建立一個(gè)包含有值 x 的新結(jié)點(diǎn), 并將其按 d 指定的/ 方向插入到第 i 個(gè)結(jié)點(diǎn)之后。 DblNode *current = Locate(i, d); / 按 d 指示方向查找第 i 個(gè)結(jié)點(diǎn) if ( current = NULL ) return false; / 插入失敗 DblNode *newNd = new DblNode(x); if (d = 0) / 前驅(qū)方向：插在第 i 個(gè)

15、結(jié)點(diǎn)左側(cè)newNd-lLink = current-lLink; / 鏈入lLink鏈 current-lLink = newNd;23 newNd-lLink-rLink = newNd; / 鏈入rLink鏈 newNd-rLink = current; else / 后繼方向:插在第i個(gè)結(jié)點(diǎn)后面 newNd-rLink = current-rLink;/ 鏈入rLink鏈 current-rLink = newNd; newNd-rLink-lLink = newNd;/ 鏈入lLink鏈 newNd-lLink = current;return true; / 插入成功; 24刪除48

16、雙向循環(huán)鏈表的刪除算法firstfirst非空表314815current3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;25雙向循環(huán)鏈表的刪除算法template bool DblList:Remove( int i, T& x, int d ) / 在雙向循環(huán)鏈表中按 d 所指方向刪除第 i 個(gè)結(jié)點(diǎn)。 DblNode *current = Locate (i, d); if (current = NULL) return false; / 刪除失敗current-rLink-lLink = current-lLink;current-lLink-rLink = current-rLink; / 從lLink鏈和rLink鏈中摘下 x = current-data; delete current; / 刪除 return true; / 刪除成功;26靜態(tài)鏈表為數(shù)組中每一個(gè)元素附加一個(gè)鏈接指針，就形成靜態(tài)鏈表結(jié)構(gòu)。處理時(shí)可以不改變數(shù)組中各元素的物理位置，只要重新鏈接就能改變這些元素的邏輯順序。它是利用數(shù)組定義的，在整個(gè)運(yùn)算