數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用之數(shù)據(jù)結(jié)構(gòu)講義Part1

1、數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用（用面向?qū)ο蠓椒ㄅcC描述）8/19/20221第一章 概述研究對象：信息的表示方法、數(shù)據(jù)的組織方法、操作算法設(shè)計意義地位：數(shù)據(jù)結(jié)構(gòu)算法程序 程序設(shè)計的基礎(chǔ) 系統(tǒng)軟件的核心發(fā)展過程：數(shù)值計算 非數(shù)值計算 建立數(shù)學(xué)模型 客體及其關(guān)系的表示 設(shè)計數(shù)值計算方法 數(shù)據(jù)的組織 操作算法的設(shè)計 非數(shù)值計算應(yīng)用的發(fā)展，促進了數(shù)據(jù)結(jié)構(gòu) 的研究和發(fā)展以及其體系的完善。8/19/20222基本術(shù)語數(shù) 據(jù)：描述客觀事物的且能由計算機處理的數(shù) 值、字符等符號數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常 作為一個整體進行考慮和處理（記錄、 結(jié)點、表目、元素）數(shù) 據(jù) 項：數(shù)據(jù)元素的某一屬性。數(shù)據(jù)元素可以由

2、若干數(shù)據(jù)項組成，數(shù)據(jù)項可以由若干 更小的款項（組合項、原子項）組成。 數(shù)據(jù)項又稱域、字段關(guān) 鍵 碼：能起唯一標識（數(shù)據(jù)元素）作用的數(shù)據(jù)項數(shù)據(jù)結(jié)構(gòu)：一組同類的數(shù)據(jù)元素、其間的關(guān)系及其上的 一組操作所構(gòu)成的整體，稱為一個數(shù)據(jù)結(jié)構(gòu)8/19/20223數(shù)據(jù)結(jié)構(gòu)的描述方式邏輯結(jié)構(gòu)：是對數(shù)據(jù)元素之間邏輯關(guān)系（拋開具體的關(guān)系含義以及存儲方式等）的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的幾個關(guān)系來表示。通?？捎脠D形表示，圓圈表示數(shù)據(jù)元素，箭頭表示關(guān)系：物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的具體表示和實現(xiàn)， 又稱存儲結(jié)構(gòu)E iE i+1數(shù)據(jù)元素數(shù)據(jù)元素關(guān)系8/19/20224數(shù)據(jù)結(jié)構(gòu)的分類按邏輯結(jié)構(gòu)分類： 純

3、集合型結(jié)構(gòu):數(shù)據(jù)元素之間除了“同屬于一個集合”這一 關(guān)系外，別無其他關(guān)系 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一個跟著一個”的序列關(guān)系 樹型結(jié)構(gòu)：數(shù)據(jù)元素之間存在“每個元素只能跟著一個元素 但可以有多個元素跟著它”的層次關(guān)系 圖狀結(jié)構(gòu)：任意兩個數(shù)據(jù)元素之間都可能存在關(guān)系按存儲結(jié)構(gòu)分類： 順序存儲結(jié)構(gòu) 鏈式存儲結(jié)構(gòu) 索引存貯結(jié)構(gòu)8/19/20225基本操作：任一數(shù)據(jù)結(jié)構(gòu)均有一組相應(yīng)的基本操作， 有時操作不同，用途迥異（如棧和隊列） 常用的基本操作有插入、 刪除、查找、 更新、排序等算 法：算法是為了解決給定的問題而規(guī)定的一個 有限長的操作步驟序列，則重于解決問題 的方法和步驟。當算法由計算機語言表示 時

4、稱為程序（代碼）算法設(shè)計目標：可維護性 可靠性（正確性、健壯行） 可讀性 高效率（時間、空間）8/19/20226第二章 線性表2。1 線性表的邏輯結(jié)構(gòu) 定義：由相同種類的數(shù)據(jù)元素組成的一個有窮序列稱為一個線性表?！耙粋€跟著一個” 符號表示法：L（e1,e2,en） 圖形表示法：e2ene18/19/20227其中： ei -表示線性表 L 的第 i 個數(shù)據(jù)元素 n -表示線性表 L 的表長（n=0） n=0 時的線性表稱為空表 ei-1 稱為 ei 的前驅(qū)，ei+1 稱為 ei 的后繼線性表的基本操作：（1）初始化（置空表）可由構(gòu)造函數(shù)實現(xiàn)（2）求表長（ Length ）（3）查找或定位（

5、Find ）（4）插入（ Insert ）（5）刪除（ Remove ）（6）排序（ Sort ）（7）判空（ IsEmpty）8/19/202282.2 線性表的順序存儲結(jié)構(gòu) 要實現(xiàn)在計算機內(nèi)表示一個數(shù)據(jù)結(jié)構(gòu)，要解決兩種信息的存貯問題：數(shù)據(jù)元素本身的存貯數(shù)據(jù)元素之間關(guān)系的存貯定義：利用內(nèi)存物理結(jié)構(gòu)上的鄰接特點，實現(xiàn)線性表 的“一個跟著一個”這一序列關(guān)系的存貯方式， 稱為線性表的順序存貯結(jié)構(gòu)，其上的線性表稱 為順序表。順序表的類定義：利用數(shù)組作為順序表的存儲結(jié)構(gòu)， 它被封裝在類的私有域中8/19/20229template class SeqList Public: SeqList(int M

6、axSize=defaultSize); SeqList( ) delete data; int Length( ) const return last+1; int Find(Type & x) const; int Insert(Type & x,int i); int Remove(Type & x); int IsEmpty( ) return last = = - 1; int Isfull( ) return last = =MaxSize 1 ; Type & Get( int i ) return i last ? NULL : datai; Private: Type * d

7、ata; / 用數(shù)組存放線性表順序存貯結(jié)構(gòu) int Maxsize; / 數(shù)組大小，但順序表的長度為 last+1 int last; / last 為表中最后元素的下標，last=-1 時表示空表8/19/202210上述順序表定義中的數(shù)據(jù)成員 Maxsize 是為判斷順序表是否為滿而設(shè)，last 是為便于判斷順序表是否為空、求表長、置空表而設(shè)：last=Maxsize 1表示順序表已滿，此時再進行插入操作會導(dǎo)致上溢錯誤；last=-1 表示順序表為空表，此時再進行刪除操作會導(dǎo)致下溢錯誤；last+1 代表順序表的表長；將 last 賦值為 1 可實現(xiàn)置空表操作。由上可知：合理地設(shè)置數(shù)據(jù)成員

8、可大大簡化算法的設(shè)計及提高算法的效率。順序表不僅僅包含存放其數(shù)據(jù)元素的數(shù)組，它還應(yīng)包括一些有用的數(shù)據(jù)成員，以及相應(yīng)的操作，它們是一個整體：8/19/202211順序表之整體概念： data01lastMaxsizelast數(shù)組下標 數(shù)組變量操作算法Maxsize-1初始化操作插入操作刪除操作查找操作排序操作 . . . . . . . . . . . . .8/19/202212順序表的基本操作（算法）（1）順序表初始化操作算法template Seqlist:Seqlist(int sz)/構(gòu)造函數(shù)，通過指定參數(shù) sz 定義數(shù)組的長度，并將 last 置為 1/即置空表if(sz0)Maxs

9、ize=sz;last=-1; / last+1=0 , 表明表中無元素，空表data=new TypeMaxsize;8/19/202213（2）順序表查找操作template int Seqlist:Find(Type & x) const/查找 x 在表中位置，若查找成功，函數(shù)返回 x 的位置/否則返回1int i=0;while(ilast) return 1;else return i;8/19/202214（3）順序表插入操作 為了把新元素 x 插入到 i 處，必須把從 i 到 last 的所有元素成塊向后移動一個元素位置，以空出第 i 個位置供 x 插入：x231先移動后面元素0

10、i-1ii+1last. . . . . . . . . . . . . .8/19/202215template int Seqlist:Insert(Type & x,int i)/將 x 插入表中 i 處，若成功返回 1 ，否則返回 0if (ilast+1|last=Maxsize-1) return 0;elselast+;for(int j=last;ji;j-) dataj=dataj-1;datai=x;return 1;8/19/202216（4）順序表刪除操作為了刪除第 i 個元素，必須把從 i1 到 last 的所有元素向前移動一個元素位置，把第 i 個元素覆蓋掉：12.

11、 . .0i-1ii+1last-1last1. . . . . . . . . . .8/19/202217template int Seqlist:Remove(Type & x)/將 x 從表中刪除。若 x 在表中并成功刪除則返回 1，/否則返回 0int i=Find(x);if (i=0)last-;for (int j=i;j=last;j+) dataj=dataj+1;return 1;return 0;8/19/202218順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點：（1）算法簡單、可讀性好、開發(fā)代價低缺點：（1）插入、刪除操作時需要移動大量元素， 效率較低；（2）最大表長難以估計，太大了浪費

12、空間， 太小了容易溢出。8/19/202219順序表應(yīng)用舉例當將兩個順序表作集合考慮時的“并”與“交”操作算法template void Union(Seqlist & LA,Seqlist & LB)/ 合并順序表 LA 與 LB ，重復(fù)元素只留一個，結(jié)果在 LA 中。 int n=LA.Length();int m=LB.Length();for (int i=0;i=m-1;i+)Type x=LB.Get(i); / 從順序表 LB 中取一元素int k=LA.Find(x); / 在順序表 LA 中查找該元素if (k=-1) / 未找到 LA.Insert( x ,n); / 將該

13、元素追加到 LA 中 n+;8/19/202220template void Intersection( Seqlist & LA,Seqlist & LB)/ 求順序表 LA 與 LB 的共同元素，結(jié)果在 LA 中int n = LA.Length( );int m = LB.Length( );int i = 0;while ( i n )Type x = LA.Get( i ); / 從 LA 中取一元素int k = LB.Find( x ); / 在 LB 中查找該元素if ( k= - 1) / 未找到 LA.Remove( i ); n-; / 則從 LA 中刪除該元素else

14、i +;8/19/202221多項式及其運算A(x)=a0 x + a1x +a2x +an-1x + anx =B(x)=b0 x + b1x +b2x +bn-1x +bnx =A(x)+B(x)=實際應(yīng)用中，上述一元多項式中的很多系數(shù)有可能為零，即為稀疏多項式，如下式所示： aixi=0ni012n-1n012n-1n bixii=0 (ai+bi)xni=0iP (x)=1.2+51.3x +3.7x5050101P(x)=ci xi=0neic0=1.2 e0=0c1=51.3 e1=50c2=3.7 e2=1018/19/202222多項式的表示對于稀疏多項式，采用二元組表示法可以

15、大大節(jié)省存儲空間：（1）將稀疏多項式的每一項用二元組表示客體的表示方法（2）用一順序表（一維數(shù)組）來存放上述的二元組數(shù)據(jù)的組織方法c0c1cicne0e1eien系數(shù)指數(shù). . . . . . . . . .8/19/202223多項式二元組的類定義客體的表示方法class Polynomial; / 多項式類的前視聲明class term / 多項式中項（二元組）的類定義friend Polynomial; / 定義 Polynomial 類為 term 類的友元類private :float coef; / 系數(shù)int exp; / 指數(shù)8/19/202224多項式的類定義數(shù)據(jù)的表示方法c

16、lass Polynomialpublic :. . . / 成員函數(shù)聲明（構(gòu)造、釋構(gòu)、相加等函數(shù)）private :int MaxTerms ; /共享空間（順序表）的最大項數(shù)static term termArrayMaxTerms;/存放二元組的數(shù)組，存放多個多項式的共享空間static int free ; / 共享空間中自由空間之起始下標int start , finish ; / 多項式在共享空間中的首、尾下標8/19/202225多項式的相加 A(x)=aix B(x)=bjxC(x)=A(x)+B(x)nmi=0j=0e ie jA . Start A . finishB .

17、Start B . finish free MaxTerm-18/19/202226多項式AB算法思路：（1）保留A、B兩個多項式，將AB放人C中；（2）開始時 C.start = free；（3）設(shè)置兩個指針 a 和 b 分別作為 A 與 B 的檢測指針，開始時 分別指向 A 與 B 的首項，即： a = A . start ; b = B . start；（4）當兩個指針都未超出相應(yīng)多項式的最末位置時，比較它們所 指示的對應(yīng)項的指數(shù)： 若指數(shù)相等，則對應(yīng)項系數(shù)相加，若相加結(jié)果不為零，則在 C 中加入一個新項 若指數(shù)不等，則把指數(shù)小者拷貝到 C 中（5）當兩個指針中有一個超出了相應(yīng)多項式的最

18、末位置，則將另 一個多項式的剩余部分拷貝到 C 中8/19/202227Polynomial Polynomial : Add ( Polynomial B ) Polynomial C; int a = start; int b =B.start; C.start = free; float c;while ( a = finish & b : NewTerm( termArrayb.coef , termArrayb.exp); b+ ; break ; case : NewTerm( termArraya.coef , termArraya.exp); a+ ; for ( ; a =

19、finish ; a+ ) NewTerm( termArraya.coef , termArraya.exp);for ( ; b = B.finish ; b+ ) NewTerm( termArrayb.coef , termArrayb.exp);C.finish=free-1;return C ; 8/19/202228void Polynomial : NewTerm( float c , int e )/ 把一個新的項（二元組 ）追加到多項式 C(x) 中if ( free = MaxTerms )cout “Too many terms in polynomials” endl

20、 ;return ;termArray free . coef = c ;termArray free . exp = e ;free + ;8/19/202229作業(yè)： 定義多項式類的求表長、查找、插入、刪除、判空表判滿表、讀?。ǖ?i 個元素）等成員函數(shù)，并用這些函數(shù)實現(xiàn)前述的兩個多項式的相加操作。提示：（1）定義查找指數(shù)相等的元素的成員函數(shù)（2）仿照前述的順序表合并操作算法，先從多項式 B 中讀取一元素，在 A 中查找有無指數(shù)相等元素：若無，則有序插入 A 中；若有，則系數(shù)相加：若和為零，則從 A 中刪除相應(yīng)元素；否則用新系數(shù)構(gòu)造新元素，并插入 A 中相應(yīng)位置8/19/202230稀疏矩

21、陣（Sparse Matrix）數(shù)值計算中的順序表設(shè)計 000220015 011000170A=000-6000000003909100000000280000矩陣 A 是一個 6 行 7 列的稀疏矩陣，只有 8 個非零元素，其他均為零。因此用二維數(shù)組來存儲稀疏矩陣的空間利用率較低，必須考慮對稀疏矩陣的壓縮存儲表示。8/19/202231稀疏矩陣的三元組表示法：（1）將稀疏矩陣的非零元素用三元組 表示（ 表示稀疏矩陣的 第 row 行、第 column 列的值為 value） 客體的表示方法（2）用一順序表（一維數(shù)組）來存放上述三元組 （每一個三元組即為順序表的一個數(shù)據(jù)元素） 并按行優(yōu)先順序

22、存放 數(shù)據(jù)的組織方法template class Tritupleprivate :int row, col;Type value;8/19/202232矩陣A的三元組表示：表下標行(row) 列(col) 值(value)0 03221 06152 11113 15174 23-65 35396 40917 52288/19/202233稀疏矩陣的類聲明：template class SparseMatrixpublic: SparseMatrix(int MaxTerms=defaultSize); SparseMatrix() delete smArray; SparseMatrix C

23、ompression(smData); SparseMatrix Transpose(); SparseMatrix Add(SparseMatrix b); SparseMatrix Multiply(SparseMatrix b);private: int Rows, Cols, Terms,MaxTerms; Trituple smArrayMaxTerms;8/19/202234說明： （1）壓縮前的稀疏矩陣為 Rows 行, Cols 列的矩陣 smData ，壓縮后的稀疏矩陣存放在一維數(shù)組 smArray 中，其中的元素為 Trituple 類型的對象。 聲明中的 Terms 對應(yīng)

24、于順序表定義中的 last， MaxTerms 對應(yīng)于順序表定義中的 Maxsize， smArray 對應(yīng)于順序表定義中的 data （2）為稀疏矩陣聲明了四種操作：壓縮（Compression）轉(zhuǎn)置（Transpose）相加（Add）相乘（Multiply）根據(jù)實際需要還可以聲明其他操作。 （3）數(shù)值計算與非數(shù)值計算的數(shù)據(jù)結(jié)構(gòu)中所定義的基本操作有很大的不同8/19/202235稀疏矩陣的轉(zhuǎn)置操作快速轉(zhuǎn)置算法思路：（1）引入兩個輔助數(shù)組 rowSize 和 rowStart rowSize i 表示稀疏矩陣第 i 列的非零元素個數(shù)rowStart i 表示稀疏矩陣第 i 列的第一個（行號最小

25、） 非零元素在轉(zhuǎn)置矩陣的三元組表中的位置。顯然應(yīng)有： rowStart i + rowSize i = rowStart i+1 . . . . . . .共有 rowSize i 個元素8/19/202236 上述公式表示，若已知稀疏矩陣第 i 列的第一個非零元素在轉(zhuǎn)置矩陣的三元組表中的位置 rowStart i , 以及稀疏矩陣第 i 列的非零元素個數(shù) rowSize i , 就可以算出第 i+1 列非零元素在轉(zhuǎn)置矩陣的三元組表中的位置 rowStart i+1 另外，根據(jù)轉(zhuǎn)置矩陣的定義可知： rowStart 0 = 0因此： rowStart 1 = rowSize 0 + rowSt

26、art 0 = rowSize 0 rowStart 2 = rowSize 1 + rowStart 1 . . . . . .因此，只要預(yù)先統(tǒng)計得到 rowSize i ( i = 0 , 1 , 2 , . . .)就可以得到第 i + 1 列非零元素在轉(zhuǎn)置矩陣的三元組表中的位置8/19/202237template SparseMatrix SparseMatrix:FastTranspos( )/ int *rowSize = new intCols; int *rowStart = new intCols;SparseMatrix b; b.Rows = Cols; b.Cols

27、= Rows; b.Terms = Terms;if (Terms 0 ) for (int i = 0; iCols; i +) rowSizei = 0;for (i=0;iTerms;i+) rowSizesmArrayi.col+;rowStart0=0;for (i=1;iCols;i+) rowStarti=rowStarti-1+rowSizei-1;for (i=0;i= 0 ) 個字符的有限序列通常可記為：S = a0 a1 a2 an-1 其中： 串名S串值引號中的內(nèi)容n串長，即串中的字符個數(shù)（不包括串結(jié)束符 0 ）空串 n = 0 的串（但包含串結(jié)束符）空白串僅由若干個空

28、格字符組成的串，其長度不為零子串從非空串中連續(xù)取出的若干個字符組成的串子串的位置子串的第0個字符在原串中的位置可以認為：串是限制數(shù)據(jù)元素為字符的順序表8/19/2022392.5.1 字符串抽象數(shù)據(jù)類型和類定義class Stringpublic: String(const String &);String(const char *const);String();String() delete ch;int Length() const return curLen；String & operator()(int pos,int len);int operator =(const String

29、& ob) const return strcmp(ch,ob.ch)=0;int operator !=(const String & ob) constreturn strcmp(ch,ob.ch)!=0;int operator ! () const return curLen=0；String & operator = (const String &);String & operator += (const String &);char & operator (int i );int Find(String pat) const;private:int curLen;char * ch

30、;8/19/202240有了上述的串類定義，就可以進行下列操作：String s1; String s2 ( “ Hello World ” );s1 = s2;String s3 ( “ ; nice to here ! ” );s1 + = s3;int len=s1.length();String s4;s4=s1(6,5);If (s1=s2)If (s1!=s2)If (! s1)Char c=s16;s16=w;8/19/202241文本編輯 計算機應(yīng)用中要涉及大量的文本文件，文本文件由大量的串（行）組成，在某些文本文件（如源程序）中，串（行）長差異 很大，若每行都用等長的串來存貯

31、，則會浪費存貯空間解決的辦法之一是建立一個很大的字符數(shù)組作為所有串的共享空間串值共享空間，再為每個串建立一個描述子，用于描述該串的長度以及該串在串值共享空間中的位置等信息，并將這些描述子存入一順序表中，參見下圖：8/19/202242 行表(linelist) 串值共享空間（space） MaxSize-1.free行號0 1 2 3 行長 位置行2行3行0行1. . . . . . . . .自由空間起始地址 0串值共享空間String（串）行表Seqlist（順序表）設(shè)計行內(nèi)字符插入、刪除操作算法設(shè)計整行插入、刪除操作算法8/19/202243第三章 鏈表順序表有下列缺點：（1）插入、刪除

32、操作時需要移動大量元素， 效率較低；（2）最大表長難以估計，太大了浪費空間， 太小了容易溢出。 因此，在插入和刪除操作是經(jīng)常性操作的應(yīng)用場合選用順序存儲結(jié)構(gòu)不太合適，此時可以選用鏈式存儲結(jié)構(gòu)。 定義：用指針來表示數(shù)據(jù)元素之間關(guān)系的存儲結(jié)構(gòu) 稱之為鏈式存儲結(jié)構(gòu)。8/19/202244定義：用由指針連接起來的一串結(jié)點來存儲一個線性表 的存儲結(jié)構(gòu)稱為線性鏈式存儲結(jié)構(gòu)，簡稱鏈表。 當每一結(jié)點中只有一個指針，并用來表示一個數(shù) 據(jù)元素到其后繼元素之間的接續(xù)關(guān)系，則稱這種 存儲結(jié)構(gòu)為單鏈表。注：此處的結(jié)點是指通過指針型變量動態(tài)索取到的存儲空間. . .firstfirst頭指針 指針域 (link) las

33、tlast 尾指針 數(shù)據(jù)元素域 (data) 空指針結(jié)點1頭結(jié)點結(jié)點0結(jié)點n-1e0e1en-18/19/202245 上述的單鏈表表頭設(shè)置了一頭結(jié)點，頭結(jié)點的數(shù)據(jù)域中可以為空，或者存放一些輔助數(shù)據(jù)。 設(shè)置頭結(jié)點的目的是為了簡化對空表的特殊處理，使得算法更簡單、更有效。 對于帶頭結(jié)點的單鏈表，可以很容易地表示空鏈表： 頭指針 頭結(jié)點 first last尾指針8/19/202246用模板定義的單鏈表類template class List; /單鏈表類的前視聲明template class ListNode /鏈表結(jié)點類的定義friend class List ; /將 List 類定義為 L

34、istNode 類的友元public:ListNode( );ListNode(const Type & item);ListNode *NextNode ( ) return link;/后繼結(jié)點指針void InsertAfter (ListNode * p); /將 *p 結(jié)點插入到當前結(jié)點之后ListNode * GetNode (const Type & item ,ListNode * next); /創(chuàng)建一個新結(jié)點ListNode * RemoveAfter ( ); /刪除后繼結(jié)點private:Type data;ListNode * link;datalink8/19/20

35、2247template class List/單鏈表類的定義public:List( ) last=first=new ListNode (value,NULL); /構(gòu)造函數(shù)，建立一個空鏈表List( );void MakeEmpty( );/刪除所有元素結(jié)點，將鏈表置為空鏈表int Length( ) const; /求單鏈表表長ListNode *Find(Type value); /查找值為 value 的結(jié)點ListNode *Find(int i); /查找結(jié)點 i , 返回結(jié)點 i 的指針int Insert(Type value,int i); /將值為 value 的新結(jié)點

36、插入結(jié)點 i 之前Type *Remove(int i);/刪除結(jié)點 iType Get(int i);/讀取結(jié)點 i 的值private:ListNode *first, *last;/頭指針，尾指針8/19/202248ListNode類（鏈表結(jié)點類）的成員函數(shù)的實現(xiàn)template void ListNode:ListNode( ):link(NULL)template void ListNode:ListNode(const Type & item)/構(gòu)造函數(shù)，創(chuàng)建一個新結(jié)點，該結(jié)點的值為 item , 指針域為NULLdata=item;link=NULL;template List

37、Node * ListNode:GetNode(const Type & item, ListNode * next=NULL)/創(chuàng)建一個新結(jié)點，該結(jié)點的值為 item , 指針域為NULL,并返回/該結(jié)點的指針ListNode *newnode=new ListNode(item,next);return newnode;8/19/202249InsertAfter( ) 函數(shù)template void ListNode:InsertAfter(ListNode *p)將 p 所指的結(jié)點（*p）鏈接成為當前結(jié)點（*this）的后繼結(jié)點p-link=link; /(1)link=p; /(2)

38、thisdatalinkdatalinkdatalinkpp-link=linklink=p(1)(2)當前結(jié)點8/19/202250RemoveAfter( )datalinkdatalinkdatalink 當前結(jié)點 要刪除的結(jié)點template ListNode *ListNode:RemoveAfter()/刪除當前結(jié)點 ( *this ) 的后繼結(jié)點,并返回該結(jié)點的指針ListNode *tempptr=link; /(1)if (link=NULL) return NULL;link=tempptr-link; /(2)return tempptr;：(1)tempptr=link

39、(2) link=tempptr-linkthis8/19/202251List類（鏈表類）的成員函數(shù)的實現(xiàn)template void List:MakeEmpty( )/ 將當前鏈表置為空表ListNode *q ;while (first -link != NULL) / 循環(huán)刪除頭結(jié)點的后繼結(jié)點，直到無后繼結(jié)點為止q=first -link ; first -link=q -link ; delete q ;last=first;/ 最后讓 last 指向頭結(jié)點，完成置空表操作first(1) q=first-link(2) first-link=q-link(最后) last頭結(jié)點8/

40、19/202252template int List:Insert(Type value,int i);/ 將值為 value 的新數(shù)據(jù)元素插入到鏈表中結(jié)點 i 之前ListNode *p = Find(i-1);/ 查找結(jié)點 i-1if (p=NULL) return 0;/ 結(jié)點 i-1 不存在，插入失敗ListNode *newnode=GetNode(value,p-link);/ 創(chuàng)建新結(jié)點 / 并使新結(jié)點指向結(jié)點 i (1)if (p-link=NULL) last=newnode;/ 若結(jié)點 i 不存在，則新結(jié)點將 / 是表尾結(jié)點p-link=newnode;/ 讓結(jié)點 i-1

41、指向新結(jié)點，實現(xiàn)插入 (2)return 1; 結(jié)點 i-1 結(jié)點 i 新結(jié)點 pnewnode(1)(2)8/19/202253template Type *List : Remove( int i )/ 刪除結(jié)點 i ,若成功，則返回該結(jié)點的數(shù)據(jù)元素（地址）， / 否則返回NULLListNode *p= Find(i-1) , *q ; / 查找結(jié)點 i-1if ( p=NULL | p-link=NULL) return NULL;/ 若結(jié)點 i-1 或者 / 結(jié)點 i 不存在，則返回 NULL , 刪除失敗q=p-link; / (1)p-link=q-link;/ (2)Type

42、value=q-data;if (q=last) last=p;delete q;return &value;結(jié)點 i-1 結(jié)點 i 結(jié)點 i+1 p q (1)(2)8/19/202254template ListNode *List:Find( int i ) / 查找結(jié)點 i , 若找到，則返回該結(jié)點的指針，否則返回NULLif ( i -1 ) return NULL;if ( i = -1 ) return first;/ 結(jié)點 1 即為頭結(jié)點ListNode *p=first-link;/ p 指向結(jié)點0int j=0;while(p!= NULL & jlink;j=j+;ret

43、urn p; 8/19/2022553.1.6 單鏈表的游標(Iterator)類 在實際應(yīng)用中經(jīng)常要對單鏈表進行打印、統(tǒng)計、檢索等需要向后搜索整個鏈表的操作，因此設(shè)計具有光標功能的，能夠記住當前位置并能得到其后繼結(jié)點的游標類是有意義的。 單鏈表的位置概念：current 是結(jié)點 i+1的位置有了單鏈表結(jié)點 i+1 的位置 current ，刪除結(jié)點 i+1 或在結(jié)點 i+1 前插入新結(jié)點就會簡單得多，無需查找過程。current結(jié)點 i結(jié)點 i+18/19/202256單鏈表游標類聲明Template class ListIteratorpublic:ListIterator(const L

44、ist & l):list(l),current(l.first) Boolean NotNull( ); / 檢查游標結(jié)點（指針 current / 所指的結(jié)點）是否為不空Boolean NextNotNull ( ); / 檢查游標結(jié)點的后繼結(jié)點是 /否為不空Type * First ( );/使游標指向頭結(jié)點Type * Next ( ); / 使游標指向后繼結(jié)點private:const List & list;ListNode * current;/游標（指針）8/19/202257單鏈表游標類成員函數(shù)的定義template Boolean ListIterator:NotNull(

45、 )/ 檢查游標結(jié)點（ current 所指的結(jié)點）是否為不空（注：/此處結(jié)點不空是指該結(jié)點的指針不空）。若不空，則返回真，/ 否則返回假if ( current != NULL ) return True;else return False;template Boolean ListIterator:NextNotNull( )/ 檢查游標結(jié)點（游標所指的結(jié)點）的后繼結(jié)點是否為不空。/ 若不空，則返回真；否則返回假if ( current != NULL & current-link != NULL ) return True;else return False;8/19/202258tem

46、plate ListNode * ListIterator:First( )/ 使游標指向頭結(jié)點if ( list.first-link != NULL ）current = list.first; / 若頭結(jié)點的指針 /域不空，即鏈表為非空表,則使游標指向頭結(jié)點else current = NULL; / 否則置空游標 return current;template ListNode * ListIterator:Next( )/ 使游標指向后繼結(jié)點if ( current != NULL & current-link != NULL )current=current-link;/ 若游標結(jié)

47、點及其后繼結(jié)點都不空，則/ 將游標指向后繼結(jié)點else current=NULL;/ 否則置空游標return current;8/19/202259游標類應(yīng)用舉例：int sum ( const List &l )/計算 int 型單鏈表 l 的累加和ListIterator li(l);/定義一個單鏈表對象 l 及其游標類對象 li ,并 /將游標指向單鏈表的頭結(jié)點（由構(gòu)造函數(shù)實現(xiàn)）if ( ! li.nextNotNull() return 0;/空鏈表，返回 0int retvalue=*li.First();/讀取頭結(jié)點的值，假定頭結(jié)點的值為 0while ( li.nextNotN

48、ull() retvalue += *li.Next();/若存在后繼結(jié)點，則循環(huán)累加return retvalue;課堂作業(yè)：使用游標類求 int 型單鏈表的最大結(jié)點。若單鏈表為空則返回NULL，否則返回最大結(jié)點的位置。8/19/2022603.2 循環(huán)鏈表（Circular List）e0e1en-1 循環(huán)鏈表的定義： （ P82P83）循環(huán)鏈表與單鏈表不同的是鏈表中表尾結(jié)點的 link 域不是NULL，而是鏈表頭結(jié)點的指針（鏈表指針） firstlast表頭結(jié)點firstlast空表8/19/202261循環(huán)鏈表（帶頭結(jié)點）的類定義：enum Boolean False,Truetemp

49、late class CircList;/循環(huán)鏈表類的前視聲明template class CircListNode/循環(huán)鏈表結(jié)點的類定義public:CircListNode (Type d=0, CircListNode * next=NULL):data ( d ), link ( next ) /構(gòu)造函數(shù)，創(chuàng)建一個循環(huán) /鏈表結(jié)點，并初始化數(shù)據(jù)域為 d , 指針域為 NULLprivate:Type data;CircListNode * link;datalink8/19/202262template class CircListpublic:CircList ( Type value );CircList ( );int Length ( ) const;Boolean IsEmpty ( ) return first-link = first; Boolean Find ( const Type & value );Type GetData ( ) const;/讀取游標結(jié)點（ *current )的數(shù)據(jù)域void Firster ( ) current=first; /將 current 指向頭結(jié)點Boolean First ( );/將 curre