第2章線性表-2015

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社第第 2 章章 線性表線性表 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表的順序存儲(chǔ)及實(shí)現(xiàn)線性表的順序存儲(chǔ)及實(shí)現(xiàn) 線性表的鏈接存儲(chǔ)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)及實(shí)現(xiàn) 順序表和鏈表的比較順序表和鏈表的比較 線性表的其他存儲(chǔ)方法線性表的其他存儲(chǔ)方法本章的基本內(nèi)容是：本章的基本內(nèi)容是：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.1 線性表的邏輯結(jié)構(gòu)線性

2、表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)元素之間的關(guān)系是什么？現(xiàn)實(shí)生活中，許多問題抽象出的數(shù)據(jù)模型是線性表，如何存儲(chǔ)現(xiàn)實(shí)生活中，許多問題抽象出的數(shù)據(jù)模型是線性表，如何存儲(chǔ)這種線性結(jié)構(gòu)并實(shí)現(xiàn)插入、刪除、查找等基本操作呢？這種線性結(jié)構(gòu)并實(shí)現(xiàn)插入、刪除、查找等基本操作呢？ 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社p 線性表：線性表：簡(jiǎn)稱表，是簡(jiǎn)稱表，是n（n0）個(gè)具有）個(gè)具有相同類型相同類型的的數(shù)據(jù)元素的數(shù)據(jù)元素的有限序有限序列列。p 線性表的長(zhǎng)度：線性表的長(zhǎng)度：線性表中數(shù)據(jù)元素的個(gè)數(shù)。線性表中數(shù)據(jù)元素的個(gè)數(shù)。p 空表：空表：長(zhǎng)度等于零的線性表，長(zhǎng)度等于零的線性表，記

3、為：記為：L=( )。p 非空表非空表記為：記為：L（a1, a2 , , ai-1, ai , , an)2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的定義線性表的定義其中，其中，ai（1in）稱為數(shù)據(jù)元素；）稱為數(shù)據(jù)元素；下角標(biāo)下角標(biāo) i 表示該元素在線性表中的位置或序號(hào)表示該元素在線性表中的位置或序號(hào) 。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社a1a3a4ana22.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的特性線性表的特性1. 有限性有限性：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。2. 相同性相同性：線性表中數(shù)據(jù)元素的類型是同

4、一的。：線性表中數(shù)據(jù)元素的類型是同一的。3. 順序性順序性：線性表中相鄰的數(shù)據(jù)元素：線性表中相鄰的數(shù)據(jù)元素ai-1和和ai之間存在之間存在序偶關(guān)系序偶關(guān)系(ai-1, ai)，即，即ai-1是是ai的前驅(qū)，的前驅(qū)， ai是是ai-1的后繼；的后繼；a1無前驅(qū)，無前驅(qū)，an無后繼，其它每個(gè)元素有且僅有一個(gè)前無后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。驅(qū)和一個(gè)后繼。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義ADT ListData 線性表中的數(shù)據(jù)元素具有相同類型，線性表中的數(shù)據(jù)元素具有相同類型， 相鄰元素具有前驅(qū)和后

5、繼關(guān)系相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitList 前置條件前置條件：表不存在：表不存在 輸入輸入：無：無 功能功能：表的初始化：表的初始化 輸出輸出： 無無 后置條件后置條件：建一個(gè)空表：建一個(gè)空表2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社DestroyList 前置條件前置條件：表已存在：表已存在 輸入輸入：無：無 功能功能：銷毀表：銷毀表 輸出輸出：無：無 后置條件后置條件：釋放表所占用的存儲(chǔ)空間：釋放表所占用的存儲(chǔ)空間Length 前置條件前置條件：表已存在：表已存在 輸入輸入：無：無 功能功能：求表的

6、長(zhǎng)度：求表的長(zhǎng)度 輸出輸出：表中數(shù)據(jù)元素的個(gè)數(shù)：表中數(shù)據(jù)元素的個(gè)數(shù) 后置條件后置條件：表不變：表不變2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社Get 前置條件前置條件：表已存在：表已存在 輸入輸入：元素的序號(hào)：元素的序號(hào)i 功能功能：在表中取序號(hào)為：在表中取序號(hào)為i的數(shù)據(jù)元素的數(shù)據(jù)元素 輸出輸出：若：若i合法，返回序號(hào)為合法，返回序號(hào)為i的元素值，否則拋出異常的元素值，否則拋出異常 后置條件后置條件：表不變：表不變Locate 前置條件前置條件：表已存在：表已存在 輸入輸入：數(shù)據(jù)

7、元素：數(shù)據(jù)元素x 功能功能：在線性表中查找值等于：在線性表中查找值等于x的元素的元素 輸出輸出：若查找成功，返回：若查找成功，返回x在表中的序號(hào)，否則返回在表中的序號(hào)，否則返回0 后置條件后置條件：表不變：表不變2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社Insert前置條件前置條件：表已存在：表已存在輸入輸入：插入：插入i；待插待插x功能功能：在表的第：在表的第i個(gè)位置處插入一個(gè)新元素個(gè)位置處插入一個(gè)新元素x輸出輸出：若插入不成功，拋出異常：若插入不成功，拋出異常 后置條件后置條

8、件：若插入成功，表中增加一個(gè)新元素：若插入成功，表中增加一個(gè)新元素Delete前置條件前置條件：表已存在：表已存在輸入輸入：刪除位置：刪除位置i功能功能：刪除表中的第：刪除表中的第i個(gè)元素個(gè)元素 輸出輸出：若刪除成功，返回被刪元素，否則拋出異常：若刪除成功，返回被刪元素，否則拋出異常 后置條件后置條件：若刪除成功，表中減少一個(gè)元素：若刪除成功，表中減少一個(gè)元素2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社Empty 前置條件前置條件：表已存在：表已存在 輸入輸入：無：無 功能功能：判

9、斷表是否為空：判斷表是否為空 輸出輸出：若是空表，返回：若是空表，返回1，否則返回，否則返回0 后置條件后置條件：表不變：表不變ADT進(jìn)一步說明進(jìn)一步說明: :（1 1）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定；）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定；（2）復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)；）復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)；（3）對(duì)不同的應(yīng)用，操作的接口可能不同。對(duì)不同的應(yīng)用，操作的接口可能不同。2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線

10、性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)例：例：（34, 23, 67, 43）34236743 4存儲(chǔ)要點(diǎn)存儲(chǔ)要點(diǎn)用一段地址用一段地址連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)線性表中的數(shù)據(jù)元素存儲(chǔ)線性表中的數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)例：例：（34, 23, 67, 43）34236743存儲(chǔ)空間的起始位置存儲(chǔ)空間的起始位置 4用什么屬性來描述順序表？用什么屬性來描述順序表？順序表的容量（最大長(zhǎng)度

11、）順序表的容量（最大長(zhǎng)度）順序表的當(dāng)前長(zhǎng)度順序表的當(dāng)前長(zhǎng)度數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)例：例：（34, 23, 67, 43）34236743 4如何實(shí)現(xiàn)順序表的內(nèi)存分配？如何實(shí)現(xiàn)順序表的內(nèi)存分配？順序表順序表一維數(shù)組一維數(shù)組數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長(zhǎng)度長(zhǎng)度2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順

12、序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲(chǔ)：的順序存儲(chǔ)：數(shù)組的長(zhǎng)度數(shù)組的長(zhǎng)度Max線性表的長(zhǎng)度線性表的長(zhǎng)度Length數(shù)組的長(zhǎng)度大于等于當(dāng)前線性表的長(zhǎng)度數(shù)組的長(zhǎng)度大于等于當(dāng)前線性表的長(zhǎng)度 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何求得任意元素的存儲(chǔ)地址？如何求得任意元素的存儲(chǔ)地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長(zhǎng)度長(zhǎng)度2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順

13、序存儲(chǔ)：的順序存儲(chǔ)：cLoc(ai)Loc(a1)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長(zhǎng)度長(zhǎng)度Loc(ai)=Loc(a1) + (i - -1)c隨機(jī)存取隨機(jī)存?。涸谠贠(1)時(shí)間內(nèi)存取數(shù)據(jù)元素時(shí)間內(nèi)存取數(shù)據(jù)元素2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲(chǔ)：的順序存儲(chǔ)：cLoc(ai)Loc(a1)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.

14、2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示；存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示；存取結(jié)構(gòu)是在一個(gè)數(shù)據(jù)結(jié)構(gòu)上對(duì)查找操作的時(shí)間性存取結(jié)構(gòu)是在一個(gè)數(shù)據(jù)結(jié)構(gòu)上對(duì)查找操作的時(shí)間性能的一種描述。能的一種描述。存儲(chǔ)結(jié)構(gòu)和存取結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和存取結(jié)構(gòu) “順序表是一種順序表是一種隨機(jī)存取隨機(jī)存取的的存儲(chǔ)存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)”的含義為：的含義為：在順序表這種存儲(chǔ)結(jié)構(gòu)上進(jìn)行的查找操作，其時(shí)間在順序表這種存儲(chǔ)結(jié)構(gòu)上進(jìn)行的查找操作，其時(shí)間性能為性能為O(1)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 順序表類的聲明順序表類的聲明cons

15、t int MaxSize=100; template /模板類模板類class SeqList public: SeqList( ) ; /構(gòu)造函數(shù)構(gòu)造函數(shù) SeqList(DataType a , int n); SeqList( ) ; /析構(gòu)函數(shù)析構(gòu)函數(shù) int Length( ); DataType Get(int i); int Locate(DataType x ); void Insert(int i, DataType x); DataType Delete(int i); private: DataType dataMaxSize; int length;2.2 線性表的順

16、序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社操作接口：操作接口：SeqList( )( ) 算法描述：算法描述：SeqList :SeqList( ) length = 0; 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)無參構(gòu)造函數(shù)無參構(gòu)造函數(shù) datalength0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社操作接口：操作接口：SeqList( (DataType a , int n) )順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)有參構(gòu)造函數(shù)有參構(gòu)造函數(shù)2.2 線性表的順序存儲(chǔ)

17、結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表順序表 數(shù)組數(shù)組a351224334253512243342數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template SeqList :SeqList( (DataType a , int n) ) if ( (n MaxSize) ) throw 參數(shù)非法參數(shù)非法; for ( (i = 0; i =MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序號(hào)）指的是元素的序號(hào)）2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入 435122442a1a

18、2a3a40 1 2 3 4422412335什么時(shí)候不能插入什么時(shí)候不能插入？注意邊界條件注意邊界條件數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社1. 如果表滿了，則拋出如果表滿了，則拋出上溢上溢異常異常;2. 如果元素的插入位置不合理，則拋出如果元素的插入位置不合理，則拋出位置位置異常異常;3. 將最后一個(gè)元素至第將最后一個(gè)元素至第i個(gè)元素分別向后移動(dòng)一個(gè)位置；個(gè)元素分別向后移動(dòng)一個(gè)位置；4. 將元素將元素x填入位置填入位置i處；處；5. 表長(zhǎng)加表長(zhǎng)加1；算法描述算法描述偽代碼偽代碼2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)

19、現(xiàn)插入插入數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template void SeqList:Insert( (int i, DataType x) ) if ( (length = MaxSize) ) throw 上溢上溢; if ( (i length + 1) ) throw 位置位置; for ( (j = length; j = i; j-)-) dataj = dataj- -1; datai- -1 = x; length+;算法描述算法描述C+描述描述2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入基本

20、語句基本語句？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社最好最好情況（情況（ i=n+1）：）： 基本語句執(zhí)行基本語句執(zhí)行0次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(1)。最壞最壞情況（情況（ i=1）：）： 基本語句執(zhí)行基本語句執(zhí)行n+1次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(n)。平均平均情況（情況（1in+1）：）： 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)。時(shí)間性能分析時(shí)間性能分析2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn

21、2n=O(n)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社操作接口：操作接口： DataType Delete(int i)刪除前：刪除前：( (a1, , ai- -1, ,ai, ,ai+1,an) )刪除后：刪除后：( (a1,ai- -1, ,ai+1, ,an) ) 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)刪刪 除除2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化存儲(chǔ)位置要反映這個(gè)變化數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第

22、版）第2版版清華大學(xué)出版社清華大學(xué)出版社例：（例：（35, 33, 12, 24, 42），），刪除刪除i=2的數(shù)據(jù)元素。的數(shù)據(jù)元素。仿照順序表的插入操作，完成：仿照順序表的插入操作，完成：1. 分析邊界條件；分析邊界條件；2. 分別給出偽代碼和分別給出偽代碼和C+描述的算法；描述的算法；3. 分析時(shí)間復(fù)雜度。分析時(shí)間復(fù)雜度。2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)刪刪 除除 535a1a2a3a40 1 2 3 4422412334a5122442數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)按位查找

23、按位查找操作接口：操作接口： DataType Get(int i) 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 n算法描述：算法描述：template DataType SeqList :Get( int i ) if (i = 1 & i = length) return i-1; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)按值查找按值查找操作接口：操作接口： int Locate(DataType x ) 2.2 線性表

24、的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35, 33, 12, 24, 42） 中查找值為中查找值為12的元素，的元素，返回在表中的序號(hào)。返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系注意序號(hào)和下標(biāo)之間的關(guān)系數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template int SeqList :Locate( (DataType x) ) for ( (i = 0; i length; i+) ) if ( (datai = x) ) return i + 1; return 0;

25、2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)按值查找按值查找算法描述：算法描述：時(shí)間復(fù)雜度時(shí)間復(fù)雜度？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序表的優(yōu)缺點(diǎn)順序表的優(yōu)缺點(diǎn) 順序表的優(yōu)點(diǎn)：順序表的優(yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；存儲(chǔ)空間； 隨機(jī)存取：可以快速地存取表中任一位置的元素。隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑亍?順序表的缺點(diǎn)：順序表的缺點(diǎn)： 插入和刪除操作需要移動(dòng)大量元素；插入和刪除操作需要移動(dòng)大量元素； 表的容量難以確定，表的容量難以擴(kuò)

26、充；表的容量難以確定，表的容量難以擴(kuò)充； 造成存儲(chǔ)空間的造成存儲(chǔ)空間的碎片碎片。 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表：?jiǎn)捂湵恚壕€性表的鏈接存儲(chǔ)結(jié)構(gòu)。線性表的鏈接存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)思想：存儲(chǔ)思想：用一組用一組任意任意的存儲(chǔ)單元存放線性表的元素。的存儲(chǔ)單元存放線性表的元素。2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配 順序表順序表事先確定容量事先確定容量 鏈鏈 表表動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配 運(yùn)行時(shí)分配空間運(yùn)行時(shí)分配空間 連續(xù)連續(xù)不連續(xù)不連續(xù)零散分布零

27、散分布數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社0200020803000325存儲(chǔ)特點(diǎn)：存儲(chǔ)特點(diǎn)： 邏輯次序和物理次序邏輯次序和物理次序 不一定相同。不一定相同。 2.元素之間的邏輯關(guān)系元素之間的邏輯關(guān)系 用指針表示。用指針表示。2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)例：例：(a1, a2 ,a3, a4)的存儲(chǔ)示意圖的存儲(chǔ)示意圖單鏈表單鏈表 a10200 a20325 a30300 a4 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表020002

28、0803000325 a10200 a20325 a30300 a4 結(jié)點(diǎn)結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)域指針域指針域單鏈表是由若干結(jié)點(diǎn)構(gòu)成的；單鏈表是由若干結(jié)點(diǎn)構(gòu)成的；單鏈表的結(jié)點(diǎn)只有一個(gè)指針域。單鏈表的結(jié)點(diǎn)只有一個(gè)指針域。data：存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)數(shù)據(jù)元素next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址存儲(chǔ)指向后繼結(jié)點(diǎn)的地址 data next單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：?jiǎn)捂湵淼慕Y(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域數(shù)據(jù)域指針域指針域數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template struct Node DataType data; Node *next; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及

29、實(shí)現(xiàn)單鏈表單鏈表 data next單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：?jiǎn)捂湵淼慕Y(jié)點(diǎn)結(jié)構(gòu)：如何申請(qǐng)一個(gè)結(jié)點(diǎn)如何申請(qǐng)一個(gè)結(jié)點(diǎn)？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社s=new Node ;template struct Node DataType data; Node *next; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表 data next單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：?jiǎn)捂湵淼慕Y(jié)點(diǎn)結(jié)構(gòu)： sNode數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社s=new Node ;2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈

30、表 data next sNode如何引用數(shù)據(jù)元素如何引用數(shù)據(jù)元素？s-data ;*s.data ;data如何引用指針域如何引用指針域？nexts-next;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表使用單鏈表時(shí)，由于我們重點(diǎn)關(guān)注的使用單鏈表時(shí)，由于我們重點(diǎn)關(guān)注的是它所表示的線性性表中的數(shù)據(jù)元素是它所表示的線性性表中的數(shù)據(jù)元素之間的邏輯關(guān)系，所以，我們可以將之間

31、的邏輯關(guān)系，所以，我們可以將實(shí)際存儲(chǔ)示意圖抽象地表示為：實(shí)際存儲(chǔ)示意圖抽象地表示為：什么是單鏈表的存儲(chǔ)結(jié)構(gòu)什么是單鏈表的存儲(chǔ)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表頭指針：頭指針：指向第一個(gè)結(jié)點(diǎn)的地址。指向第一個(gè)結(jié)點(diǎn)的地址。尾標(biāo)志：尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭?。終端結(jié)點(diǎn)的指針域?yàn)榭铡?shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)

32、出版社2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不統(tǒng)一，缺點(diǎn)？空表和非空表不統(tǒng)一，缺點(diǎn)？如何將空表與非空表統(tǒng)一如何將空表與非空表統(tǒng)一？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社頭結(jié)點(diǎn)：頭結(jié)點(diǎn)：在在單鏈表的第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類單鏈表的第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)，以便空表和非空表處理統(tǒng)一。型相同的結(jié)點(diǎn)，以便空表和非空表處理統(tǒng)一。 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線

33、性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表單鏈表非空表非空表firsta1a2an空表空表first數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template class LinkList public: LinkList( )( )； LinkList( (DataType a , int n) ); LinkList( )( ); int Length( )( ); DataType Get( (int i) ); int Locate( (DataType x) ); void Insert( (int i, DataType x) ); DataType Delete(

34、 (int i) ); void PrintList( )( ); private: Node *first; ;單鏈表類的聲明單鏈表類的聲明2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)遍歷操作遍歷操作操作接口：操作接口： void PrintList( ); v核心操作（關(guān)鍵操作）：核心操作（關(guān)鍵操作）：工作指針后移工作指針后移。從頭結(jié)點(diǎn)。從頭結(jié)點(diǎn)（或開始結(jié)點(diǎn)）出發(fā)，通過工作指針的反復(fù)后移而將（或開始結(jié)點(diǎn)）出發(fā)，通過工作指針的反復(fù)后移而將整個(gè)單鏈表整個(gè)單鏈表“審視審視”一遍的方法稱為

35、一遍的方法稱為掃描掃描（或遍歷）（或遍歷）。2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1pa2panaippp數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)遍歷操作遍歷操作操作接口：操作接口： void PrintList( ); 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template void LinkList : PrintList( ) p = first-next; while (p != NULL) cout data; p = p-next; p+能否完成指針后移？能否完成指針后移？

36、a1a2pp+p-next數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)按位查找按位查找操作接口：操作接口： DataType Get(int i);2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1a2anaipp查找失敗查找失敗1. 工作指針工作指針p初始化初始化; 累加器累加器count初始化初始化;2. 重復(fù)執(zhí)行下述操作，直到重復(fù)執(zhí)行下述操作，直到p為空或?yàn)榭栈騪指向第指向第i個(gè)結(jié)點(diǎn)：個(gè)結(jié)點(diǎn)： 2.1 工作指針工作指針p后移后移; 2.2 count+;3. 返回累加器返回累加器count的值；的值；pcount

37、=1pcount =2p查找成功查找成功count =i數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template int LinkList : Get(int i) p = first-next; count = 1; while (p != NULL & count next; count+; if(!p) throw “位置異常位置異?！?/退出循環(huán)表明查找失敗退出循環(huán)表明查找失敗 else return count; /查找成功，返回序號(hào)查找成功，返回序號(hào) 或者返回或者返回p-data2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單

38、鏈表的實(shí)現(xiàn)按位查找按位查找算法描述算法描述C+描述描述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template int LinkList : Locate(DataType x) p = first-next; count = 1; while (p != NULL) if (p-data = x) return count; /查找成功，返回序號(hào)查找成功，返回序號(hào) p = p-next; count+; return 0; /退出循環(huán)表明查找失敗退出循環(huán)表明查找失敗2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)按值查找按值查

39、找算法描述算法描述C+描述描述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)插入插入操作接口：操作接口： void Insert(int i, DataType x); 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何實(shí)現(xiàn)結(jié)點(diǎn)如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、x和和ai之間邏輯關(guān)系的變化？之間邏輯關(guān)系的變化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社注意分析注意分析邊界邊

40、界情況情況表頭、表尾。表頭、表尾。 單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)插入插入2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1anaipxs算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;pxs由于單鏈表帶頭結(jié)點(diǎn)，由于單鏈表帶頭結(jié)點(diǎn)，表頭、表中、表尾三種表頭、表中、表尾三種情況的操作語句一致。情況的操作語句一致。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社算法描述算法描述偽代碼偽代碼 1. 工作指針工作指針p初始化；初始化； 2. 查找第查找第i-1個(gè)結(jié)點(diǎn)并使工作指針個(gè)結(jié)點(diǎn)并使工作指針p指

41、向該結(jié)點(diǎn)；指向該結(jié)點(diǎn)； 3. 若查找不成功，則插入位置不合理，拋出插入位置異常；若查找不成功，則插入位置不合理，拋出插入位置異常； 否則，否則， 3.1 生成一個(gè)元素值為生成一個(gè)元素值為x的新結(jié)點(diǎn)的新結(jié)點(diǎn)s； 3.2 將新結(jié)點(diǎn)將新結(jié)點(diǎn)s插入到結(jié)點(diǎn)插入到結(jié)點(diǎn)p之后；之后；2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)插入插入數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 template void LinkList : Insert(int i, DataType x) p = first ; count = 0; /工作指針工作指針

42、p應(yīng)指向頭結(jié)點(diǎn)應(yīng)指向頭結(jié)點(diǎn) while (p != NULL & count next; count+; if (p = NULL) throw 位置位置; /沒有找到第沒有找到第i 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) else s = new Node; s-data = x; /申請(qǐng)一個(gè)結(jié)點(diǎn)申請(qǐng)一個(gè)結(jié)點(diǎn)s s-next = p-next; p-next = s; /結(jié)點(diǎn)結(jié)點(diǎn)s插入結(jié)點(diǎn)插入結(jié)點(diǎn)p之后之后 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)插入插入基本語句？時(shí)間復(fù)雜度？基本語句？時(shí)間復(fù)雜度？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈

43、表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面 。算法描述：算法描述：first=new Node; first-next=NULL; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組數(shù)組a3512243342初始化初始化first數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點(diǎn)

44、插在頭結(jié)點(diǎn)的后面將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面 。2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組數(shù)組a3512243342算法描述：算法描述：s=new Node; s-data=a0;s-next=first-next;first-next=s; 插入第一個(gè)元素結(jié)點(diǎn)插入第一個(gè)元素結(jié)點(diǎn)first35s數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面 。2.3 線性表的鏈接

45、存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組數(shù)組a3512243342算法描述：算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s; 依次插入每一個(gè)結(jié)點(diǎn)依次插入每一個(gè)結(jié)點(diǎn)12sfirst35數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template LinkList : LinkList(DataType a , int n) first = new Node; first-next = NULL; for (i = 0; i data = ai; s-next = first-next; first-

46、next = s; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社尾插法：尾插法：將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：first=new Node; rear=first;數(shù)組數(shù)組a3512243342初始化初始化firstrear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)

47、（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社尾插法：尾插法：將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;數(shù)組數(shù)組a3512243342插入第一個(gè)元素結(jié)點(diǎn)插入第一個(gè)元素結(jié)點(diǎn)firstrear35srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社尾插法：尾插法：將待

48、插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s=new Node; s-data=a1;rear-next=s;rear=s;數(shù)組數(shù)組a3512243342依次插入每一個(gè)結(jié)點(diǎn)依次插入每一個(gè)結(jié)點(diǎn)first35rear12srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社尾插法：尾插法：將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。將待插入結(jié)點(diǎn)插在終端結(jié)點(diǎn)的后面。 2.3

49、 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：rear-next=NULL;數(shù)組數(shù)組a3512243342最后一個(gè)結(jié)點(diǎn)插入后最后一個(gè)結(jié)點(diǎn)插入后first3542srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template LinkList : LinkList(DataType a , int n) first = new Node; /生成頭結(jié)點(diǎn)生成頭結(jié)點(diǎn) r = first; /尾指針初始化尾指針初始化 for

50、(i = 0; i data = ai; r-next = s; r = s; r-next = NULL; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)算法描述：算法描述：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)刪除刪除操作接口：操作接口： DataType Delete(int i); 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)p如何實(shí)現(xiàn)結(jié)點(diǎn)如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1和和ai之間邏輯關(guān)系的變化？之間邏輯關(guān)系的變化？firsta1ai-1ai+1ai算法描述：算法描述：q

51、=p-next; x=q-data;p-next=q-next; delete q;q數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)刪除刪除2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;注意分析注意分析邊界邊界情況情況表頭、表尾。表頭、表尾。 pqpq表尾的特殊情況：表尾的特殊情況：雖然被刪結(jié)點(diǎn)不存在，雖然被刪結(jié)點(diǎn)不存在，但其前驅(qū)結(jié)點(diǎn)卻存在。但其前驅(qū)結(jié)點(diǎn)卻存在。 p-next=NULLfirsta1ana2數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C

52、+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社算法描述算法描述偽代碼偽代碼 1.工作指針工作指針p初始化；初始化； 2. 查找第查找第i-1個(gè)結(jié)點(diǎn)并使工作指針個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；指向該結(jié)點(diǎn)； 3. 若若p不存在或不存在或p不存在后繼結(jié)點(diǎn)，則拋出位置異常；不存在后繼結(jié)點(diǎn)，則拋出位置異常； 否則，否則， 3.1 暫存被刪結(jié)點(diǎn)和被刪元素值；暫存被刪結(jié)點(diǎn)和被刪元素值； 3.2 摘鏈，將結(jié)點(diǎn)摘鏈，將結(jié)點(diǎn)p的后繼結(jié)點(diǎn)從鏈表上摘下；的后繼結(jié)點(diǎn)從鏈表上摘下； 3.3 釋放被刪結(jié)點(diǎn)；釋放被刪結(jié)點(diǎn)； 3.4 返回被刪元素值；返回被刪元素值； 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)

53、現(xiàn)單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)刪除刪除數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template DataType LinkList : Delete(int i) p = first ; count = 0; while (p != NULL & count next; count+; if (p = NULL | p-next = NULL) throw 位置位置; else q = p-next; x = q-data; p-next = q-next; delete q; return x; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)

54、現(xiàn)單鏈表的實(shí)現(xiàn)刪除刪除數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)析構(gòu)函數(shù)析構(gòu)函數(shù)析構(gòu)函數(shù)將單鏈表中所有結(jié)點(diǎn)的存儲(chǔ)空間釋放。析構(gòu)函數(shù)將單鏈表中所有結(jié)點(diǎn)的存儲(chǔ)空間釋放。 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)操作接口：操作接口：LinkList( );firsta1a2anaiq算法描述：算法描述：q = first; first = first-next;delete q;first注意：保證鏈表未處理的部分不斷開注意：保證鏈表未處理的部分不斷開 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社單鏈表

55、的實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)析構(gòu)函數(shù)析構(gòu)函數(shù)template LinkList : LinkList( ) while (first != NULL) q = first; first = first-next; delete q; 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)算法描述：算法描述：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社啟示：算法設(shè)計(jì)的一般過程啟示：算法設(shè)計(jì)的一般過程算法設(shè)計(jì)的一般步驟：算法設(shè)計(jì)的一般步驟：第一步：確定第一步：確定入口入口（已知條件）、（已知條件）、出口出口（結(jié)果）；（結(jié)果）；第二步：根據(jù)一個(gè)小實(shí)例畫出第二步：根據(jù)一個(gè)小實(shí)例畫

56、出示意圖示意圖；第三步：第三步： 正向思維正向思維：選定一個(gè)思考問題的起點(diǎn)，逐：選定一個(gè)思考問題的起點(diǎn)，逐步提出問題、解決問題；步提出問題、解決問題； 逆向思維逆向思維：從結(jié)論出發(fā)分：從結(jié)論出發(fā)分析為達(dá)到這個(gè)結(jié)論應(yīng)該先有什么；析為達(dá)到這個(gè)結(jié)論應(yīng)該先有什么； 正逆結(jié)合正逆結(jié)合；第四步：寫出第四步：寫出頂層頂層較抽象算法，分析較抽象算法，分析邊界邊界情況；情況；第五步：第五步：驗(yàn)證驗(yàn)證第四步的算法；第四步的算法；第六步：寫出第六步：寫出具體具體算法；算法；第七步：第七步：進(jìn)一步進(jìn)一步驗(yàn)證，手工運(yùn)行。驗(yàn)證，手工運(yùn)行。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社循環(huán)鏈表循環(huán)鏈

57、表firsta1ai-1anaip從單鏈表中某結(jié)點(diǎn)從單鏈表中某結(jié)點(diǎn)p出發(fā)如何找到其前驅(qū)？出發(fā)如何找到其前驅(qū)？將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針改為指向頭結(jié)點(diǎn)，構(gòu)成改為指向頭結(jié)點(diǎn)，構(gòu)成單循環(huán)鏈表單循環(huán)鏈表，簡(jiǎn)稱，簡(jiǎn)稱循環(huán)鏈表循環(huán)鏈表。2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社循環(huán)鏈表循環(huán)鏈表空表和非空表的處理一致空表和非空表的處理一致附設(shè)頭結(jié)點(diǎn)附設(shè)頭結(jié)點(diǎn)first空循環(huán)鏈表空循環(huán)鏈表firsta1ai-1anai非空循環(huán)鏈表非空循環(huán)鏈表2.3 線性表的

58、鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社firsta1ai-1anai循環(huán)鏈表循環(huán)鏈表插入插入xspxspxsp算法描述：算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 template void LinkList :Insert(int i, DataType x) p = first ; count = 0; while (p !=

59、first & count next; count+; if (p = NULL) throw 位置位置; else s = new Node; s-data = x; s-next = p-next; p-next = s; 循環(huán)鏈表循環(huán)鏈表插入插入與單鏈表的插入操作相比，差別是什么？與單鏈表的插入操作相比，差別是什么？2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社循環(huán)條件：循環(huán)條件：p != NULLp != firstp-next != NULLp-next != first循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表中沒有

60、明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán)2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何查找開始結(jié)點(diǎn)和終端結(jié)點(diǎn)？如何查找開始結(jié)點(diǎn)和終端結(jié)點(diǎn)？循環(huán)鏈表循環(huán)鏈表firsta1ai-1anai開始結(jié)點(diǎn)：開始結(jié)點(diǎn)：first-next 終端結(jié)點(diǎn)：將單鏈表掃描一遍，時(shí)間為終端結(jié)點(diǎn)：將單鏈表掃描一遍，時(shí)間為O(n)2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社reara1ai-1anai開始結(jié)點(diǎn)：開始結(jié)點(diǎn)：rear