第 七 講 單鏈表、循環(huán)鏈表、雙向鏈表 10 23

1、循 環(huán) 鏈 表、雙向鏈表時 間：2013 10 - 231 勸 學(xué) 語玩 物 喪 志，玩 人 喪 德。 尚書 讀 書須用意，一字值千金。 弟 子 規(guī) 2只要有了積極主動的態(tài)度， 沒有什么目標是不能達到的。 李 開 復(fù)3第 七 次 上 課 內(nèi) 容1、 循環(huán)鏈表 P 392、雙向鏈表 P 433、線性表的應(yīng)用 P554本節(jié)課學(xué)習(xí)目標 1、循環(huán)表的定義 2、雙向表的定義 3、線性表的應(yīng)用5數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)6第 2 章 線 性 表7循環(huán)鏈表 (Circular List)8循環(huán)鏈表是單鏈表的變形唯一一個區(qū)別： 循環(huán)鏈表最后一個結(jié)點的next指針不為 0 (

2、NULL)，而是指向了表的前端。增加一個標記： 為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。循 環(huán) 表 特 點： 循環(huán)鏈表的特點是：只要知道表中某一結(jié)點的地址，就可搜尋到所有其他結(jié)點的地址。9循 環(huán) 鏈 表 示 例10/ 簡單循環(huán)鏈表類template class SimpleCircLinkList protected:/ 循環(huán)鏈表實現(xiàn)的數(shù)據(jù)成員:Node *head;/ 頭結(jié)點指針/ 輔助函數(shù)Node *GetElemPtr(int position) const;/ 返回指向第position個結(jié)點的指針void Init();/ 初始化線性表11public:/ 抽象數(shù)據(jù)類型方法聲明及重

3、載編譯系統(tǒng)默認方法聲明:SimpleCircLinkList();/ 無參數(shù)的構(gòu)造函數(shù)virtual SimpleCircLinkList();/ 析構(gòu)函數(shù)int Length() const;/ 求線性表長度bool Empty() const;/ 判斷線性表是否為空void Clear();/ 將線性表清空void Traverse(void (*Visit)(const ElemType &) const;/ 遍歷線性表StatusCode GetElem(int position, ElemType &e) const;/ 求指定位置的元素StatusCode SetElem(int

4、position, const ElemType &e);/ 設(shè)置指定位置的元素值12StatusCode Delete(int position, ElemType &e);/ 刪除元素StatusCode Insert(int position, const ElemType &e);/ 插入元素SimpleCircLinkList(const SimpleCircLinkList ©); / 復(fù)制構(gòu)造函數(shù)SimpleCircLinkList &operator =(const SimpleCircLinkList ©);/ 賦值語句重載;13用循環(huán)鏈表求解約瑟夫問題約瑟夫

5、問題的提法 n 個人圍成一個圓圈，首先第1個人從1開始一個人一個人順時針報數(shù), 報到第m 個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，如此下去, 直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。例如 n = 8 m = 314/ 文件路徑名:s2_5alg.h void Josephus(int n, int m)/ 操作結(jié)果:n個人圍成一個圓圈，首先第1個人從1開始一/ 個人一個人順時針報數(shù),報到第m個人，令其出列。/然后再從下一個人開始，從1順時針報數(shù)報到第m/個人，再令其出列，如此下去, 直到圓圈中只/剩一個人為止。此人即為優(yōu)勝者 SimpleCircLin

6、kList la;/ 定義空循環(huán)鏈表int position = 0;/ 報數(shù)到的人在鏈表中序號int out, winer;for (int k = 1; k = n; k+) la.Insert(k, k);/ 建立數(shù)據(jù)域為1,2,.,n的循環(huán)鏈表15cout 出列者:; for (int i = 1; i n; i+)/ 循環(huán)n-1次，讓n-1個個出列for (int j = 1; j la.Length()position = 1;la.Delete(position-, out);/ 報數(shù)到m的人出列cout out ;la.GetElem(1, winer);/ 剩下的一個人為優(yōu)勝

7、者cout endl 優(yōu)勝者: winer endl;16雙向鏈表 (Doubly Linked List)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個結(jié)點結(jié)構(gòu)： 前驅(qū)方向 后繼方向雙向鏈表通常采用帶表頭結(jié)點的循環(huán)鏈表形式。17雙向循環(huán)鏈表示例18雙向鏈表的實現(xiàn)一、數(shù)據(jù)結(jié)點類模板 template struct DbNode ElemType data; DbNode *back; DbNode *next; DbNode (); DbNode(); DbNode (DbNode *linkback, DbNode *linknext) 19雙向鏈表類模板Templat

8、eClass DbLinkListProtected: DbNode *head; DbNode *GetElemPtr(int pos);Public: DbLinkList(); DbLinkList(); int Length() const; Bool Empty()const;20 Bool Empty() const; Void Clear(); bool GetElem(int pos,ElemType &e); bool SetElem(int pos ,ElemType e); bool Delete(int pos ,ElemType &e); bool Insert(in

9、t pos ,ElemType &e); ;21在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù) 前面講解了三種線性表的三種鏈式存儲結(jié)構(gòu)，這三種結(jié)構(gòu)實現(xiàn)比較一致，處理簡單，特別適合于初學(xué)者，但許多應(yīng)用程序是按順序處理線性表的中數(shù)據(jù)元素的，也就是處理完一個數(shù)據(jù)元素后再處理下一個數(shù)據(jù)元素，也可能要幾次引用同一個數(shù)據(jù)元素，比如在訪問下一個數(shù)據(jù)元素之前做GetElem和SetElem操作，對于這類應(yīng)用程序，前面的鏈表實現(xiàn)效率低下，這時最好在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù)。 22Mutable修飾符mutable 可以用來指出，即使結(jié)構(gòu)或者類變量為const，其某個成員也可以被修改 。 例 如： Class A c

10、onst int data; bool Set(int da) const data =da; 23/ 線性鏈表類template class LinkList protected:/ 鏈表實現(xiàn)的數(shù)據(jù)成員:Node *head;/ 頭結(jié)點指針mutable int curPosition;/ 當前位置的序號mutable Node * curPtr;/ 指向當前位置的指針int count;/ 元素個數(shù)24/ 輔助函數(shù)Node *GetElemPtr(int position) const;/ 返回指向第position個結(jié)點的指針void Init();/ 初始化線性表public:/ 抽象

11、數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認方法聲明:LinkList();/ 無參數(shù)的構(gòu)造函數(shù)virtual LinkList();/ 析構(gòu)函數(shù)int Length() const;/ 求線性表長度bool Empty() const;/ 判斷線性表是否為空void Clear();/ 將線性表清空void Traverse(void (*Visit)( const ElemType &) const;/ 遍歷線性表25StatusCode GetElem(int position, ElemType &e) const;/ 求指定位置的元素StatusCode SetElem(int positio

12、n, const ElemType &e);/ 設(shè)置指定位置的元素值StatusCode Delete(int position, ElemType &e);/ 刪除元素StatusCode Insert(int position, const ElemType &e); / 插入元素LinkList(const LinkList ©); / 復(fù)制構(gòu)造函數(shù)LinkList &operator =(const LinkList ©); / 賦值語句重載;26重寫 GetElemPtr函數(shù)Node *LinkList:GetElemPtr(int pos) const if(cur

13、Pos pos) curPose =0; curPtr = head; For( ; curPosnext; return curPtr;27在計算機中，可以用一個線性表來表示: P = (p0, p1, ，pn)多項的鏈表表示一元多項式但是對于形如 S(x) = 1 + 3x10000 2x20000的多項式，上述表示方法是否合適？28 一般情況下的一元稀疏多項式可寫成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指數(shù)為ei 的項的非零系數(shù)， 0 e1 e2 em = n可以下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ）29 P

14、999(x) = 7x3 - 2x12 - 8x999例 如:可用線性表 ( (7, 3), (-2, 12), (-8, 999) )表示30/ 多項式類class Polynomialprotected:/ 多項式實現(xiàn)的數(shù)據(jù)成員:LinkList polyList;/ 多項式組成的線性表public:/ 抽象數(shù)據(jù)類型方法聲明:Polynomial();/ 無參構(gòu)造函數(shù)Polynomial();/ 析構(gòu)函數(shù)int Length() const;/ 求多項式的項數(shù)31bool IsZero() const;/ 判斷多項式是否為0void SetZero();/ 將多項式置為0void Display();/ 顯示多項式void InsItem( const PolyItem &item);/ 插入一項Polynomial operator +(const Polynomial &p) const; / 加法運算符重載Polynomial operator -(const Polynomial &p) const; / 減法運算符重載Polynomial operator *(const Polynomial &p) const; / 乘法運算符重載Polynomial(const Polynomial ©);/ 復(fù)制構(gòu)造函