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

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

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

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

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

5、Find ）（4）插入（ Insert ）（5）刪除（ Remove ）（6）排序（ Sort ）（7）判空（ IsEmpty）8/19/202282.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 要實(shí)現(xiàn)在計(jì)算機(jī)內(nèi)表示一個(gè)數(shù)據(jù)結(jié)構(gòu)，要解決兩種信息的存貯問題：數(shù)據(jù)元素本身的存貯數(shù)據(jù)元素之間關(guān)系的存貯定義：利用內(nèi)存物理結(jié)構(gòu)上的鄰接特點(diǎn)，實(shí)現(xiàn)線性表 的“一個(gè)跟著一個(gè)”這一序列關(guān)系的存貯方式， 稱為線性表的順序存貯結(jié)構(gòu)，其上的線性表稱 為順序表。順序表的類定義：利用數(shù)組作為順序表的存儲(chǔ)結(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ù)組大小，但順序表的長(zhǎng)度為 last+1 int last; / last 為表中最后元素的下標(biāo)，last=-1 時(shí)表示空表8/19/202210上述順序表定義中的數(shù)據(jù)成員 Maxsize 是為判斷順序表是否為滿而設(shè)，last 是為便于判斷順序表是否為空、求表長(zhǎng)、置空表而設(shè)：last=Maxsize 1表示順序表已滿，此時(shí)再進(jìn)行插入操作會(huì)導(dǎo)致上溢錯(cuò)誤；last=-1 表示順序表為空表，此時(shí)再進(jìn)行刪除操作會(huì)導(dǎo)致下溢錯(cuò)誤；last+1 代表順序表的表長(zhǎng)；將 last 賦值為 1 可實(shí)現(xiàn)置空表操作。由上可知：合理地設(shè)置數(shù)據(jù)成員

8、可大大簡(jiǎn)化算法的設(shè)計(jì)及提高算法的效率。順序表不僅僅包含存放其數(shù)據(jù)元素的數(shù)組，它還應(yīng)包括一些有用的數(shù)據(jù)成員，以及相應(yīng)的操作，它們是一個(gè)整體：8/19/202211順序表之整體概念： data01lastMaxsizelast數(shù)組下標(biāo) 數(shù)組變量操作算法Maxsize-1初始化操作插入操作刪除操作查找操作排序操作 . . . . . . . . . . . . .8/19/202212順序表的基本操作（算法）（1）順序表初始化操作算法template Seqlist:Seqlist(int sz)/構(gòu)造函數(shù)，通過指定參數(shù) sz 定義數(shù)組的長(zhǎng)度，并將 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 的所有元素成塊向后移動(dòng)一個(gè)元素位置，以空出第 i 個(gè)位置供 x 插入：x231先移動(dòng)后面元素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 個(gè)元素，必須把從 i1 到 last 的所有元素向前移動(dòng)一個(gè)元素位置，把第 i 個(gè)元素覆蓋掉：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順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：（1）算法簡(jiǎn)單、可讀性好、開發(fā)代價(jià)低缺點(diǎn)：（1）插入、刪除操作時(shí)需要移動(dòng)大量元素， 效率較低；（2）最大表長(zhǎng)難以估計(jì)，太大了浪費(fèi)

12、空間， 太小了容易溢出。8/19/202219順序表應(yīng)用舉例當(dāng)將兩個(gè)順序表作集合考慮時(shí)的“并”與“交”操作算法template void Union(Seqlist & LA,Seqlist & LB)/ 合并順序表 LA 與 LB ，重復(fù)元素只留一個(gè)，結(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多項(xiàng)式及其運(yùn)算A(x)=a0 x + a1x +a2x +an-1x + anx =B(x)=b0 x + b1x +b2x +bn-1x +bnx =A(x)+B(x)=實(shí)際應(yīng)用中，上述一元多項(xiàng)式中的很多系數(shù)有可能為零，即為稀疏多項(xiàng)式，如下式所示： 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多項(xiàng)式的表示對(duì)于稀疏多項(xiàng)式，采用二元組表示法可以

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

16、lass Polynomialpublic :. . . / 成員函數(shù)聲明（構(gòu)造、釋構(gòu)、相加等函數(shù)）private :int MaxTerms ; /共享空間（順序表）的最大項(xiàng)數(shù)static term termArrayMaxTerms;/存放二元組的數(shù)組，存放多個(gè)多項(xiàng)式的共享空間static int free ; / 共享空間中自由空間之起始下標(biāo)int start , finish ; / 多項(xiàng)式在共享空間中的首、尾下標(biāo)8/19/202225多項(xiàng)式的相加 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多項(xiàng)式AB算法思路：（1）保留A、B兩個(gè)多項(xiàng)式，將AB放人C中；（2）開始時(shí) C.start = free；（3）設(shè)置兩個(gè)指針 a 和 b 分別作為 A 與 B 的檢測(cè)指針，開始時(shí) 分別指向 A 與 B 的首項(xiàng)，即： a = A . start ; b = B . start；（4）當(dāng)兩個(gè)指針都未超出相應(yīng)多項(xiàng)式的最末位置時(shí)，比較它們所 指示的對(duì)應(yīng)項(xiàng)的指數(shù)： 若指數(shù)相等，則對(duì)應(yīng)項(xiàng)系數(shù)相加，若相加結(jié)果不為零，則在 C 中加入一個(gè)新項(xiàng) 若指數(shù)不等，則把指數(shù)小者拷貝到 C 中（5）當(dāng)兩個(gè)指針中有一個(gè)超出了相應(yīng)多項(xiàng)式的最

18、末位置，則將另 一個(gè)多項(xiàng)式的剩余部分拷貝到 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 )/ 把一個(gè)新的項(xiàng)（二元組 ）追加到多項(xiàng)式 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è)： 定義多項(xiàng)式類的求表長(zhǎng)、查找、插入、刪除、判空表判滿表、讀?。ǖ?i 個(gè)元素）等成員函數(shù)，并用這些函數(shù)實(shí)現(xiàn)前述的兩個(gè)多項(xiàng)式的相加操作。提示：（1）定義查找指數(shù)相等的元素的成員函數(shù)（2）仿照前述的順序表合并操作算法，先從多項(xiàng)式 B 中讀取一元素，在 A 中查找有無指數(shù)相等元素：若無，則有序插入 A 中；若有，則系數(shù)相加：若和為零，則從 A 中刪除相應(yīng)元素；否則用新系數(shù)構(gòu)造新元素，并插入 A 中相應(yīng)位置8/19/202230稀疏矩

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

22、存放 數(shù)據(jù)的組織方法template class Tritupleprivate :int row, col;Type value;8/19/202232矩陣A的三元組表示：表下標(biāo)行(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 類型的對(duì)象。 聲明中的 Terms 對(duì)應(yīng)

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

25、） 非零元素在轉(zhuǎn)置矩陣的三元組表中的位置。顯然應(yīng)有： rowStart i + rowSize i = rowStart i+1 . . . . . . .共有 rowSize i 個(gè)元素8/19/202236 上述公式表示，若已知稀疏矩陣第 i 列的第一個(gè)非零元素在轉(zhuǎn)置矩陣的三元組表中的位置 rowStart i , 以及稀疏矩陣第 i 列的非零元素個(gè)數(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)計(jì)得到 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 ) 個(gè)字符的有限序列通?？捎洖椋篠 = a0 a1 a2 an-1 其中： 串名S串值引號(hào)中的內(nèi)容n串長(zhǎng)，即串中的字符個(gè)數(shù)（不包括串結(jié)束符 0 ）空串 n = 0 的串（但包含串結(jié)束符）空白串僅由若干個(gè)空

28、格字符組成的串，其長(zhǎng)度不為零子串從非空串中連續(xù)取出的若干個(gè)字符組成的串子串的位置子串的第0個(gè)字符在原串中的位置可以認(rèn)為：串是限制數(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有了上述的串類定義，就可以進(jìn)行下列操作：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文本編輯 計(jì)算機(jī)應(yīng)用中要涉及大量的文本文件，文本文件由大量的串（行）組成，在某些文本文件（如源程序）中，串（行）長(zhǎng)差異 很大，若每行都用等長(zhǎng)的串來存貯

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

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

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

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

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

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

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

38、thisdatalinkdatalinkdatalinkpp-link=linklink=p(1)(2)當(dāng)前結(jié)點(diǎn)8/19/202250RemoveAfter( )datalinkdatalinkdatalink 當(dāng)前結(jié)點(diǎn) 要?jiǎng)h除的結(jié)點(diǎn)template ListNode *ListNode:RemoveAfter()/刪除當(dāng)前結(jié)點(diǎn) ( *this ) 的后繼結(jié)點(diǎn),并返回該結(jié)點(diǎn)的指針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ù)的實(shí)現(xiàn)template void List:MakeEmpty( )/ 將當(dāng)前鏈表置為空表ListNode *q ;while (first -link != NULL) / 循環(huán)刪除頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)，直到無后繼結(jié)點(diǎn)為止q=first -link ; first -link=q -link ; delete q ;last=first;/ 最后讓 last 指向頭結(jié)點(diǎn)，完成置空表操作first(1) q=first-link(2) first-link=q-link(最后) last頭結(jié)點(diǎn)8/

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

41、指向新結(jié)點(diǎn)，實(shí)現(xiàn)插入 (2)return 1; 結(jié)點(diǎn) i-1 結(jié)點(diǎn) i 新結(jié)點(diǎn) pnewnode(1)(2)8/19/202253template Type *List : Remove( int i )/ 刪除結(jié)點(diǎn) i ,若成功，則返回該結(jié)點(diǎn)的數(shù)據(jù)元素（地址）， / 否則返回NULLListNode *p= Find(i-1) , *q ; / 查找結(jié)點(diǎn) i-1if ( p=NULL | p-link=NULL) return NULL;/ 若結(jié)點(diǎn) i-1 或者 / 結(jié)點(diǎn) 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é)點(diǎn) i-1 結(jié)點(diǎn) i 結(jié)點(diǎn) i+1 p q (1)(2)8/19/202254template ListNode *List:Find( int i ) / 查找結(jié)點(diǎn) i , 若找到，則返回該結(jié)點(diǎn)的指針，否則返回NULLif ( i -1 ) return NULL;if ( i = -1 ) return first;/ 結(jié)點(diǎn) 1 即為頭結(jié)點(diǎn)ListNode *p=first-link;/ p 指向結(jié)點(diǎn)0int j=0;while(p!= NULL & jlink;j=j+;ret

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

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

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

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

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

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

49、late class CircList;/循環(huán)鏈表類的前視聲明template class CircListNode/循環(huán)鏈表結(jié)點(diǎn)的類定義public:CircListNode (Type d=0, CircListNode * next=NULL):data ( d ), link ( next ) /構(gòu)造函數(shù)，創(chuàng)建一個(gè)循環(huán) /鏈表結(jié)點(diǎn)，并初始化數(shù)據(jù)域?yàn)?d , 指針域?yàn)?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;/讀取游標(biāo)結(jié)點(diǎn)（ *current )的數(shù)據(jù)域void Firster ( ) current=first; /將 current 指向頭結(jié)點(diǎn)Boolean First ( );/將 curre