1、2.1 2.1 線性表概念及基本操作線性表概念及基本操作2.22.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.32.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 2.3.12.3.1 線性鏈表線性鏈表 2.3.22.3.2 循環(huán)鏈表循環(huán)鏈表 2.3.32.3.3 雙向鏈表雙向鏈表2.42.4 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加 在本課程介紹的幾種數(shù)據(jù)結(jié)構(gòu)中，線性表是在本課程介紹的幾種數(shù)據(jù)結(jié)構(gòu)中，線性表是最簡(jiǎn)單的，也是最常用的數(shù)據(jù)結(jié)構(gòu)，線性表在實(shí)最簡(jiǎn)單的，也是最常用的數(shù)據(jù)結(jié)構(gòu)，線性表在實(shí)際應(yīng)用中大量使用，并不是一個(gè)陌生的概念。際應(yīng)用中大量使用，并不是一個(gè)陌生的概念。 基本內(nèi)

2、容：基本內(nèi)容： 1 1 線性表的概念；線性表的概念； 2 2 線性表兩類存儲(chǔ)結(jié)構(gòu)和它們的類型定義；線性表兩類存儲(chǔ)結(jié)構(gòu)和它們的類型定義； 3 3 在兩類存儲(chǔ)結(jié)構(gòu)下，線性表基本操作的算法；在兩類存儲(chǔ)結(jié)構(gòu)下，線性表基本操作的算法； 學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)： 1 1 了解線性表邏輯結(jié)構(gòu)的特征；了解線性表邏輯結(jié)構(gòu)的特征； 2 2 重點(diǎn)掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它重點(diǎn)掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它們?nèi)绾伪磉_(dá)線性表中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系；如何用們?nèi)绾伪磉_(dá)線性表中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系；如何用C C語(yǔ)語(yǔ)言描述它們的類型定義；言描述它們的類型定義； 3 3 掌握在順序存儲(chǔ)結(jié)構(gòu)下，線性表的

3、基本操作的算法；掌握在順序存儲(chǔ)結(jié)構(gòu)下，線性表的基本操作的算法； 4 4 掌握在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下，線性表的基本操作的算法；掌握在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下，線性表的基本操作的算法； 5 5 能夠從時(shí)間復(fù)雜度的角度，比較線性表兩類存儲(chǔ)結(jié)構(gòu)能夠從時(shí)間復(fù)雜度的角度，比較線性表兩類存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及適用場(chǎng)合；的不同特點(diǎn)及適用場(chǎng)合； 線性表是線性表是n 個(gè)類型相同數(shù)據(jù)元素的有限序列，個(gè)類型相同數(shù)據(jù)元素的有限序列，通常記作通常記作:（a1, a2, a3, , an ）。）。 姓名姓名 電話號(hào)碼電話號(hào)碼 蔡穎蔡穎 63214444 陳紅陳紅 63217777 劉建平劉建平 63216666 王小林王小林 6321888

4、8 張力張力 63215555 . 2. 1 線性表的概念線性表的概念例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某單位的電話號(hào)碼簿。一、線性表的邏輯結(jié)構(gòu)一、線性表的邏輯結(jié)構(gòu) 電話號(hào)碼簿是數(shù)據(jù)元素電話號(hào)碼簿是數(shù)據(jù)元素的有限序列，每一數(shù)據(jù)的有限序列，每一數(shù)據(jù)元素包括兩個(gè)數(shù)據(jù)項(xiàng)，元素包括兩個(gè)數(shù)據(jù)項(xiàng)，一個(gè)是用戶姓名，一個(gè)一個(gè)是用戶姓名，一個(gè)是對(duì)應(yīng)的電話號(hào)碼。是對(duì)應(yīng)的電話號(hào)碼。說(shuō)明：說(shuō)明：設(shè)設(shè) A=（a1, a2, . , ai-1, ai , ai+1, , an ）是一線性表）是一線性表1） 線性表的數(shù)據(jù)元素可以是各種各樣的，

5、但同一線性表中的元線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素必須具有相同特性；素必須具有相同特性；2） 在表中在表中 ai-1 領(lǐng)先于領(lǐng)先于ai ，ai 領(lǐng)先于領(lǐng)先于ai+1 ，稱，稱ai-1 是是ai 的直接前趨的直接前趨，ai+1 是是ai 的直接后繼；的直接后繼；3） 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼，具有這種結(jié)都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)；構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)；4） 線性表中元素的個(gè)數(shù)線性表中元素

6、的個(gè)數(shù)n稱為線性表的長(zhǎng)度，稱為線性表的長(zhǎng)度，n=0時(shí)稱為空表；時(shí)稱為空表；5） ai是線性表的第是線性表的第i 個(gè)元素，稱個(gè)元素，稱i 為數(shù)據(jù)元素為數(shù)據(jù)元素ai 的序號(hào)，每一個(gè)的序號(hào)，每一個(gè)元素在線性表中的位置，僅取決于它的序號(hào)；元素在線性表中的位置，僅取決于它的序號(hào)； 線性表的其他表示方式線性表的其他表示方式 二元組表示二元組表示 L= ，其中，其中D= a1,a2, a3, . an S= R R=, , 圖示表示圖示表示a ai i+1a a1a ai-i-1a a2 2a ai ia an n頂點(diǎn)：表示數(shù)據(jù)頂點(diǎn)：表示數(shù)據(jù)邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系設(shè)設(shè)L

7、=（a1,a2, .ai-1, ai , ai+1, , an ）是一線性表）是一線性表1 初始化操作初始化操作 InitList(&L) 功能：建立空的線性表功能：建立空的線性表L；2 銷毀操作銷毀操作DestroyList(&L)功能：回收為線性表功能：回收為線性表L動(dòng)態(tài)分配的存儲(chǔ)空間；動(dòng)態(tài)分配的存儲(chǔ)空間；3 置空操作置空操作ClearList(&L)功能：功能：L中已存在，重新將其置成空表；中已存在，重新將其置成空表；4 判空操作判空操作ListEmpty(L)功能：判斷線性表功能：判斷線性表L是否為空表，若為空表返回是否為空表，若為空表返回TRUE，否則返回否則

8、返回FALSE；5 求表長(zhǎng)操作求表長(zhǎng)操作 ListLength(L)功能：返回線性表功能：返回線性表L的表長(zhǎng)；的表長(zhǎng)；6 取元素操作：取元素操作：GetElem(L, i, &e)功能：將線性表功能：將線性表L中第中第i 個(gè)元素賦值給個(gè)元素賦值給 e；二、線性表的基本操作二、線性表的基本操作7 查找操作查找操作 LocateElem (L, e,compare() )功能：在線性表功能：在線性表L中查找與元素中查找與元素e滿足滿足compare()的第的第1個(gè)元素，返回該元素個(gè)元素，返回該元素在表中的序號(hào)（或位置）在表中的序號(hào)（或位置），若表中不存在這樣的元素，則返回若表中不存在這樣的

9、元素，則返回0；8 前驅(qū)操作前驅(qū)操作 PriorElem(L,cur_e,&pre_e) 功能：若功能：若cur_e是是L的數(shù)據(jù)元素，且不是第一個(gè)，則用的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，返回它的前驅(qū)，否則操作失敗。否則操作失敗。9 后繼操作后繼操作 NextElem(L,cur_e,&next_e) 功能：若功能：若cur_e是是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后返回它的后繼，否則操作失敗。繼，否則操作失敗。10 插入操作插入操作 ListInsert(&L, i, e )功能：在線性表功能：在線

10、性表L的第的第i個(gè)元素之前插入一個(gè)新元素個(gè)元素之前插入一個(gè)新元素e;11 刪除操作刪除操作 ListDelete(&L, i, &e )功能：刪除線性表功能：刪除線性表L的第的第i個(gè)元素，并用個(gè)元素，并用e返回；返回；12 遍歷操作遍歷操作 ListTraverse (&L,visit( ) )功能：依次對(duì)線性表功能：依次對(duì)線性表L的每一個(gè)元素調(diào)用函數(shù)的每一個(gè)元素調(diào)用函數(shù)visit( )。若。若visit( )失敗，失敗，則返則返回回ERROR，否則返回，否則返回OK；說(shuō)明：說(shuō)明：1 上面列出的操作，只是線性表的一些常用的基本操作；上面列出的操作，只是線性表的一些常用的

11、基本操作；2 不同的應(yīng)用，基本操作可能是不同的；不同的應(yīng)用，基本操作可能是不同的； 例如：上面列出的刪除操作例如：上面列出的刪除操作Delete( &L, i, &e ), 功能是在功能是在線性表線性表L中刪除第中刪除第i個(gè)元素，并用個(gè)元素，并用e返回其值。返回其值。 在電話號(hào)碼查詢?cè)陔娫捥?hào)碼查詢系統(tǒng)中，一旦某用戶撤掉某部電話，則需在系統(tǒng)的電話號(hào)碼系統(tǒng)中，一旦某用戶撤掉某部電話，則需在系統(tǒng)的電話號(hào)碼簿中刪除該用戶對(duì)應(yīng)的數(shù)據(jù)，因此電話號(hào)碼查詢系統(tǒng)，需要簿中刪除該用戶對(duì)應(yīng)的數(shù)據(jù)，因此電話號(hào)碼查詢系統(tǒng)，需要提供這樣的功能，在電話號(hào)碼簿中刪除與給定元素提供這樣的功能，在電話號(hào)碼簿中刪除

12、與給定元素e值相同的值相同的數(shù)據(jù)元素；數(shù)據(jù)元素； 線性表的復(fù)雜操作可通過(guò)基本操作實(shí)現(xiàn)；線性表的復(fù)雜操作可通過(guò)基本操作實(shí)現(xiàn)； 這有點(diǎn)類似于數(shù)中情形，例如整數(shù)基本操作是這有點(diǎn)類似于數(shù)中情形，例如整數(shù)基本操作是+，-， ，/ 。如果要求某班同學(xué)的平均年齡則可利用如果要求某班同學(xué)的平均年齡則可利用+ / 實(shí)現(xiàn)：實(shí)現(xiàn)： 全班同學(xué)的平均年齡全班同學(xué)的平均年齡=(age1+age2+age3+)/全班同學(xué)人數(shù)全班同學(xué)人數(shù) 關(guān)于如何用線性表的基本操作實(shí)現(xiàn)復(fù)雜操作將在后面講解。關(guān)于如何用線性表的基本操作實(shí)現(xiàn)復(fù)雜操作將在后面講解。 現(xiàn)在我們已經(jīng)知道什么是線性表及線性表的一些基本操作，現(xiàn)在我們已經(jīng)知道什么是線性表及

13、線性表的一些基本操作，下一步要做什么呢？下一步要做什么呢？ 例如，我們要設(shè)計(jì)一個(gè)電話號(hào)碼查詢系統(tǒng)，顯然這個(gè)系統(tǒng)至例如，我們要設(shè)計(jì)一個(gè)電話號(hào)碼查詢系統(tǒng)，顯然這個(gè)系統(tǒng)至少要具備下列功能：少要具備下列功能：查詢某人的電話號(hào)碼；查詢某人的電話號(hào)碼；在電話號(hào)碼薄中，插入一新用戶姓名及電話號(hào)碼；在電話號(hào)碼薄中，插入一新用戶姓名及電話號(hào)碼；在電話號(hào)碼薄中，刪除已撤銷的用戶姓名及電話號(hào)碼；在電話號(hào)碼薄中，刪除已撤銷的用戶姓名及電話號(hào)碼； 由上我們知道，電話號(hào)碼薄可用線性表表示，上面列出的功由上我們知道，電話號(hào)碼薄可用線性表表示，上面列出的功能實(shí)際上就是對(duì)線性表的查找、插入、刪除操作。能實(shí)際上就是對(duì)線性表的查找

14、、插入、刪除操作。 顯然，首先需要將電話號(hào)碼薄上的信息存儲(chǔ)到計(jì)算機(jī)中，然顯然，首先需要將電話號(hào)碼薄上的信息存儲(chǔ)到計(jì)算機(jī)中，然后才可能對(duì)這些信息進(jìn)行加工處理，實(shí)現(xiàn)上述功能。后才可能對(duì)這些信息進(jìn)行加工處理，實(shí)現(xiàn)上述功能。 本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計(jì)算機(jī)上邏輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計(jì)算機(jī)上實(shí)現(xiàn)，即如何在計(jì)算機(jī)上存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)？如何在計(jì)算機(jī)上實(shí)現(xiàn)，即如何在計(jì)算機(jī)上存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)？如何在計(jì)算機(jī)上實(shí)現(xiàn)對(duì)數(shù)據(jù)結(jié)構(gòu)的各種操作？為此，我們將用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)對(duì)數(shù)據(jù)結(jié)構(gòu)的各種操作？為此，我們將用

15、計(jì)算機(jī)語(yǔ)言來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，用計(jì)算機(jī)語(yǔ)言來(lái)描述這些操作的來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，用計(jì)算機(jī)語(yǔ)言來(lái)描述這些操作的算法。算法。 本課程用類本課程用類C語(yǔ)言做為描述語(yǔ)言。語(yǔ)言做為描述語(yǔ)言。 2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)線性表的順序存儲(chǔ)和實(shí)現(xiàn) 一、線性表的順序存儲(chǔ)結(jié)構(gòu)一、線性表的順序存儲(chǔ)結(jié)構(gòu)順序表順序表 1 1 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) 2 2 順序表的類型定義順序表的類型定義 二、順序表的基本操作算法二、順序表的基本操作算法 三、利用基本操作實(shí)現(xiàn)線性表的其他操作三、利用基本操作實(shí)現(xiàn)線性表的其他操作為了存儲(chǔ)線性表，至少要保存兩類信息：為了存儲(chǔ)線性表，至少要保存兩類信息：1）線性表中的

16、數(shù)據(jù)元素；）線性表中的數(shù)據(jù)元素；2）線性表中數(shù)據(jù)元素的順序關(guān)系；）線性表中數(shù)據(jù)元素的順序關(guān)系； 在計(jì)算機(jī)內(nèi)部可以采用不同的方式來(lái)存儲(chǔ)一個(gè)線性在計(jì)算機(jī)內(nèi)部可以采用不同的方式來(lái)存儲(chǔ)一個(gè)線性表，其中最簡(jiǎn)單的方式就是線性表的順序存儲(chǔ)結(jié)構(gòu)表，其中最簡(jiǎn)單的方式就是線性表的順序存儲(chǔ)結(jié)構(gòu)。 線性表的順序存儲(chǔ)結(jié)構(gòu)，就是用一組線性表的順序存儲(chǔ)結(jié)構(gòu)，就是用一組連連續(xù)的續(xù)的內(nèi)存單元內(nèi)存單元依次依次存放線性表的數(shù)據(jù)元素。存放線性表的數(shù)據(jù)元素。用順序表存儲(chǔ)線性表時(shí)，數(shù)據(jù)元素之間的邏輯用順序表存儲(chǔ)線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系，是通過(guò)數(shù)據(jù)元素的存儲(chǔ)順序反映出來(lái)的關(guān)系，是通過(guò)數(shù)據(jù)元素的存儲(chǔ)順序反映出來(lái)的a a1 1a a2

17、 2a ai-1i-1a ai ia ai+1i+1a an n 線性表（線性表（a1,a2, a3, . an ）的順序存儲(chǔ)結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表表稱為順序表稱為順序表一、線性表的順序存儲(chǔ)結(jié)構(gòu)一、線性表的順序存儲(chǔ)結(jié)構(gòu)順序表順序表1、線性表的順序存儲(chǔ)結(jié)構(gòu)、線性表的順序存儲(chǔ)結(jié)構(gòu)說(shuō)明：說(shuō)明： 在順序存儲(chǔ)結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，可通過(guò)在順序存儲(chǔ)結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，可通過(guò)元素的存儲(chǔ)順序反映（表示）出來(lái)，所以只需存儲(chǔ)數(shù)據(jù)元素元素的存儲(chǔ)順序反映（表示）出來(lái)，所以只需存儲(chǔ)數(shù)據(jù)元素的信息的信息 假設(shè)線性表中每個(gè)數(shù)據(jù)元素占用假設(shè)線性表中每個(gè)數(shù)

18、據(jù)元素占用 k 個(gè)存儲(chǔ)單元，那么在順個(gè)存儲(chǔ)單元，那么在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第序存儲(chǔ)結(jié)構(gòu)中，線性表的第i個(gè)元素的存儲(chǔ)位置與第個(gè)元素的存儲(chǔ)位置與第1個(gè)元素的個(gè)元素的存儲(chǔ)位置的關(guān)系是：存儲(chǔ)位置的關(guān)系是：Loc(ai ) = Loc( a1 )+ ( i 1) k 這里這里 Loc(ai)是第是第 i 個(gè)元素的存儲(chǔ)位置，個(gè)元素的存儲(chǔ)位置， Loc( a1 ) 是第是第1個(gè)個(gè)元素的存儲(chǔ)位置，也稱為線性表的起始位置或基地址。元素的存儲(chǔ)位置，也稱為線性表的起始位置或基地址。怎樣在計(jì)算機(jī)上實(shí)現(xiàn)怎樣在計(jì)算機(jī)上實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)？線性表的順序存儲(chǔ)結(jié)構(gòu)？2、順序表的類型定義、順序表的類型定義 以上用自然語(yǔ)

19、言描述了線性表的順序存儲(chǔ)結(jié)構(gòu)，怎樣以上用自然語(yǔ)言描述了線性表的順序存儲(chǔ)結(jié)構(gòu)，怎樣將這種存儲(chǔ)方式在計(jì)算機(jī)上實(shí)現(xiàn)？我們知道將這種存儲(chǔ)方式在計(jì)算機(jī)上實(shí)現(xiàn)？我們知道C語(yǔ)言一維數(shù)組語(yǔ)言一維數(shù)組的機(jī)內(nèi)表示也是順序結(jié)構(gòu)，因此，可借用的機(jī)內(nèi)表示也是順序結(jié)構(gòu)，因此，可借用C語(yǔ)言的一維數(shù)組語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。實(shí)現(xiàn)線性表的順序存儲(chǔ)。順序表的類型定義順序表的類型定義#define LIST_INIT_SIZE 100 /線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲(chǔ)空間的分配增量線性表存儲(chǔ)空間的分配增量typedef structE

20、lemType * elem; /線性表存儲(chǔ)空間基址線性表存儲(chǔ)空間基址int length; /當(dāng)前線性表長(zhǎng)度當(dāng)前線性表長(zhǎng)度int listsize; /當(dāng)前分配的線性表存儲(chǔ)空間大小當(dāng)前分配的線性表存儲(chǔ)空間大小 /（以（以sizeof(ElemType)為單位）為單位）SqList;說(shuō)明：說(shuō)明：SqList 為類型名；為類型名；SqList類型的變量是結(jié)構(gòu)變量，三個(gè)域分別是：類型的變量是結(jié)構(gòu)變量，三個(gè)域分別是： *elem：存放線性存放線性表元素的一維數(shù)組基址，其存儲(chǔ)空間在初始化操作時(shí)動(dòng)態(tài)分配；表元素的一維數(shù)組基址，其存儲(chǔ)空間在初始化操作時(shí)動(dòng)態(tài)分配；length：存放線性表的表長(zhǎng)；存放線性表的

21、表長(zhǎng)； listsize：用于存放當(dāng)前分配（存放線用于存放當(dāng)前分配（存放線性表元素）的存儲(chǔ)空間的大小。性表元素）的存儲(chǔ)空間的大小。順順序序表表圖圖示示a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nL.lengthL.lengthL.listsizeL.listsizeL.elemL.elemn nLIST_INIT_SIZELIST_INIT_SIZE存放線性表元素存放線性表元素 的一維數(shù)組的一維數(shù)組設(shè)設(shè) A = （a1,a2 , a3 , . an ）是一線性表，）是一線性表，L是是SqList 類型的結(jié)類型的結(jié)構(gòu)變量，用于存放線性表構(gòu)變量，用于存放線性

22、表A，則，則L在內(nèi)存中的狀態(tài)如圖所示：在內(nèi)存中的狀態(tài)如圖所示：二、順序表的基本操作算法二、順序表的基本操作算法 現(xiàn)在，我們已為線性表設(shè)計(jì)好了一種存儲(chǔ)結(jié)構(gòu)，下面將看到用這種現(xiàn)在，我們已為線性表設(shè)計(jì)好了一種存儲(chǔ)結(jié)構(gòu)，下面將看到用這種存儲(chǔ)方式存儲(chǔ)線性表時(shí)，線性表的各種基本操作算法。存儲(chǔ)方式存儲(chǔ)線性表時(shí)，線性表的各種基本操作算法。 在介紹基本操作的算法之前，先回顧一下本書算法中常用到的兩個(gè)在介紹基本操作的算法之前，先回顧一下本書算法中常用到的兩個(gè)C函數(shù)。函數(shù)。1) malloc(int size) 功能：功能：在系統(tǒng)內(nèi)存中分配在系統(tǒng)內(nèi)存中分配size個(gè)存儲(chǔ)單元，并返回該空間的基址。個(gè)存儲(chǔ)單元，并返回該

23、空間的基址。 使用方法：使用方法： . int m = 100； float *p; p = (float *) malloc(m*sizeof(float ); 執(zhí)行語(yǔ)句執(zhí)行語(yǔ)句p = (float *) malloc(m*sizeof(float)，計(jì)算機(jī)將按，計(jì)算機(jī)將按float 類型類型變量所占空間的大小（一般為變量所占空間的大小（一般為32bit）分配）分配m* sizeof(float)個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元,并并將其基址賦值給指針變量將其基址賦值給指針變量p;0 0 1 1 2 2 9999p p執(zhí)行執(zhí)行 p = (float *) malloc(m*sizeof(float) 圖

24、示 調(diào)用free ( p ) 0 0 1 1 2 2 9999p p 調(diào)用調(diào)用free ( p ) 圖示圖示2) free ( p ) 功能：功能：將指針變量將指針變量p所指示的存儲(chǔ)空間，回收到系統(tǒng)內(nèi)存空間中去。所指示的存儲(chǔ)空間，回收到系統(tǒng)內(nèi)存空間中去。使用方法：使用方法： . int m = 100; float *p; p = (float*) malloc(m*sizeof(float); / 一旦一旦p所指示的內(nèi)存空間不再使用，所指示的內(nèi)存空間不再使用， /調(diào)用調(diào)用free( ) 回收之回收之 free(p);如何在順序表如何在順序表上實(shí)現(xiàn)線性表的基本操作？上實(shí)現(xiàn)線性表的基本操作？如何

25、建空表？如何求表長(zhǎng)？如何建空表？如何求表長(zhǎng)？如何插入？刪除？如何插入？刪除？ 設(shè)線性表用設(shè)線性表用順序表順序表L存儲(chǔ)，下面我們介紹用順序表存儲(chǔ)存儲(chǔ)，下面我們介紹用順序表存儲(chǔ)線性表時(shí)，各種基本操作的算法。當(dāng)線性表用順序表存儲(chǔ)線性表時(shí)，各種基本操作的算法。當(dāng)線性表用順序表存儲(chǔ)時(shí)，對(duì)線性表各種基本操作實(shí)際上就是對(duì)存儲(chǔ)在內(nèi)存中的時(shí)，對(duì)線性表各種基本操作實(shí)際上就是對(duì)存儲(chǔ)在內(nèi)存中的順序表進(jìn)行操作。順序表進(jìn)行操作。1）初始化操作）初始化操作 InitList_Sq( SqList &L)參數(shù)參數(shù)：L是存放線性表的結(jié)構(gòu)變量（稱是存放線性表的結(jié)構(gòu)變量（稱L為順序表為順序表）, 因?yàn)橐驗(yàn)椴迦氩僮鲗?duì)順序表插

26、入操作對(duì)順序表L進(jìn)行了修改，所以用了引用參數(shù)進(jìn)行了修改，所以用了引用參數(shù)&L功能：功能：建立空的順序表建立空的順序表L主要步驟：主要步驟：調(diào)用調(diào)用malloc ( )為順序表分配一預(yù)定大小為順序表分配一預(yù)定大小(LIST_INIT_SIZE）的空間，并將其基址賦值給）的空間，并將其基址賦值給L.elem 順序表初始化0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1L.lengthL.lengthL.listsizeL.listsizeL.elemL.elem 0 0LIST_INIT_SIZELIST_INIT_SIZE初始化操作算法：初始化操作算法：Sta

27、tus InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (! L.elem) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗L. length=0; /空表長(zhǎng)度為空表長(zhǎng)度為0L.listsize=LIST_INIT_SIZE; /初始存儲(chǔ)容量初始存儲(chǔ)容量Return OK;/InitList_Sq 算法算法2.3 銷毀順序表銷毀順序表L.lengthL.lengthL.listsizeL.listsizeL.elemL

28、.elem0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n n nLIST_INIT_SIZELIST_INIT_SIZE0 00 0=null=null2）銷毀操作）銷毀操作 DestroyList ( SqList &L) 功能：功能：回收為順序表動(dòng)態(tài)分配的存儲(chǔ)空間回收為順序表動(dòng)態(tài)分配的存儲(chǔ)空間主要步驟：主要步驟：調(diào)用調(diào)用free( ) 回收為順序表動(dòng)態(tài)分配的存儲(chǔ)空間回收為順序表動(dòng)態(tài)分配的存儲(chǔ)空間銷毀操作算法：銷毀操作算法：Status DestroyList_Sq (

29、SqList &L) if (!L.elem) return ERROR; / 若表若表L不存在不存在 free (L.elem); / 若表若表L已存在，回收動(dòng)態(tài)分配的存儲(chǔ)空間已存在，回收動(dòng)態(tài)分配的存儲(chǔ)空間 L.elem = null; L.length = 0; L.Listsize = 0; return OK;/ DestroyList_Sq3）置空操作）置空操作ClearList_Sq ( SqList &L) 功能：功能：若若L已存在，重新將其置成空表已存在，重新將其置成空表算法：算法： Status ClearList_Sq ( SqList &L) if

30、 (!L.elem) return ERROR; / 若表若表L不存在不存在 L.length = 0; /若表若表L已存在，將已存在，將L置空置空 return OK;/ ClearList_SqL.lengthL.lengthL.listsizeL.listsizeL.elemL.elem0 01 1 99 99a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n n nLIST_INIT_SIZELIST_INIT_SIZE 0 0 置空操作圖示置空操作圖示置空置空4）取元素操作）取元素操作 GetElem_Sq ( SqList L, int i, El

31、emType &e )功能：功能：將順序表中第將順序表中第i 個(gè)元素賦值給個(gè)元素賦值給 e算法：算法：Status GetElem_Sq ( SqList &L, int i, ElemType &e ) if (i L.length ) return ERROR; / i 非法非法 e = L.elem i-1 ; /將順序表中第將順序表中第i 個(gè)元素賦值給個(gè)元素賦值給 e return OK;/ GetElem_Sq 由于由于C語(yǔ)言的一維數(shù)組下標(biāo)從語(yǔ)言的一維數(shù)組下標(biāo)從0開(kāi)始開(kāi)始, 故線性表的第一個(gè)元故線性表的第一個(gè)元素放在素放在L.elem0，第，第i個(gè)元素放個(gè)元素

32、放L.elemi-1中，最后一個(gè)元素放中，最后一個(gè)元素放在在 L.elemL.length-1中。中。 取元素操作取元素操作e ea ai iL.lengthL.lengthL.listsizeL.listsizeL.elemL.elem0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nn n LIST_INIT_SIZE LIST_INIT_SIZE5）插入操作）插入操作 ListInsert_Sq ( &L, i, e ) 參數(shù)：參數(shù)：L ：順序表：順序表 ， i 插入位置

33、，插入位置， e 被插入元素；被插入元素； 因?yàn)椴逡驗(yàn)椴迦氩僮鲗?duì)順序表進(jìn)行修改，所以用了引用參數(shù)入操作對(duì)順序表進(jìn)行修改，所以用了引用參數(shù)&L； 功能：功能：在順序表在順序表L的第的第i個(gè)元素之前插入一個(gè)新元素個(gè)元素之前插入一個(gè)新元素e 0 a11 a2i-2 ai-1i-1 aii ai+1n-1 an插插 入入 前前0 a11 a2i-2 ai-1i-1 ei aii+1 ai+1n-1 an插插 入入 后后插入操作示意圖插入操作示意圖 為初學(xué)者易于理解插入算法主要步驟，這里簡(jiǎn)化了書為初學(xué)者易于理解插入算法主要步驟，這里簡(jiǎn)化了書上的插入算法上的插入算法2.42.4，對(duì)插入算法中表空間

34、已滿的情況，只，對(duì)插入算法中表空間已滿的情況，只簡(jiǎn)單的返回出錯(cuò)（簡(jiǎn)單的返回出錯(cuò)（ERRORERROR），），在在2.22.2節(jié)的最后部分給出完整節(jié)的最后部分給出完整的插入算法。當(dāng)然，應(yīng)用中對(duì)各種情況如何處理，要根據(jù)的插入算法。當(dāng)然，應(yīng)用中對(duì)各種情況如何處理，要根據(jù)實(shí)際問(wèn)題的需要來(lái)決定。實(shí)際問(wèn)題的需要來(lái)決定。注意注意插入操作主要步驟：插入操作主要步驟：1）i 是否合法，若合法轉(zhuǎn)是否合法，若合法轉(zhuǎn)2），否則算法結(jié)束，并返回），否則算法結(jié)束，并返回ERROR；2）L是否已滿，若未滿轉(zhuǎn)是否已滿，若未滿轉(zhuǎn)3），否則算法結(jié)束，并返回），否則算法結(jié)束，并返回ERROR；3）將順序表）將順序表ai 及之后的所

35、有元素后移一個(gè)位置；及之后的所有元素后移一個(gè)位置；4) 將新元素寫入空出的位置；將新元素寫入空出的位置；5）表長(zhǎng)）表長(zhǎng)+1 。 Status ListInsert_Sq(SqList &L, int i , ElemType e) /在順序表在順序表L中第中第i個(gè)位置之前插入新的元素個(gè)位置之前插入新的元素e, / i的合法值為的合法值為1iL.lL.length+1,當(dāng)當(dāng)i =L.lL.length+1時(shí)時(shí)e插在表尾插在表尾 if (iL.length+1) return ERROR; / i值不合法值不合法 if (L.length=L.listsize) return ERROR;

36、 /順序表已滿順序表已滿 for ( j=L.length-1 ; j= i-1; -j) L.elemj+1= L.elem j; /插入位置及其之后的元素后移一個(gè)位置插入位置及其之后的元素后移一個(gè)位置 L.elemi-1 =e; /插入插入e +L.length; /表長(zhǎng)增表長(zhǎng)增1 return OK;/ListInsert_Sq 算法算法2.4 a 插入操作算法插入操作算法為初學(xué)者易于理解插入算為初學(xué)者易于理解插入算法，這里通過(guò)下標(biāo)引用法，這里通過(guò)下標(biāo)引用L L.elem.elem中的元素。中的元素。Status ListInsert_Sq(SqList &L, int i, E

37、lemType e) /在順序表在順序表L中第中第i個(gè)位置之前插入新的元素個(gè)位置之前插入新的元素e, /i的合法值為的合法值為1iL.lL.length+1 if (iL.length+1) return ERROR; /i值不合法值不合法 if (L.length=L.listsize) return ERROR; /順序表已滿順序表已滿 q=&(L.elem i-1); /q為插入位置為插入位置 for (p=&(L. elemL.length-1) ; p=q; -p) *(p+1)=*p; /插入位置及之后的元素后移一個(gè)位置插入位置及之后的元素后移一個(gè)位置 *q=e;

38、/插入插入e +L.length; /表長(zhǎng)加表長(zhǎng)加1 return OK;/ListInsert_Sq 算法算法2.4 b算法算法2.4b2.4b與算法與算法2.4a 2.4a 唯唯一的不同是一的不同是通過(guò)指針通過(guò)指針p p引引用用L L.elem.elem中的元素。中的元素。Status ListInsert_Sq(SqList &L, int i, ElemType e) /在順序線性表在順序線性表L中第中第i個(gè)位置之前插入新的元素個(gè)位置之前插入新的元素e, / i的合法值為的合法值為1iListLength_Sq(L)+1 if (iL.length+1) return ERRO

39、R; /i值不合法值不合法 if (L.length=L.listsize) /當(dāng)前存儲(chǔ)空間已滿，重新分配空間當(dāng)前存儲(chǔ)空間已滿，重新分配空間 newbase=(ElemType*) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L. elem=newbase; /新基址新基址 L.listsize+=LISTINCREMENT; /增加存儲(chǔ)容量增加存儲(chǔ)容量 q=&(L.elemi-1); /q為插入位置為插入位置 for

40、(p=&(L. elemL.length-1); p=q ; -p)*(p+1) = *p; /插入位置及之后的元素右移插入位置及之后的元素右移 *q=e; /插入插入e +L.length; /表長(zhǎng)增表長(zhǎng)增1 return OK;/ListInsert_Sq 算法算法2.4表空間已表空間已滿情況的滿情況的處理處理現(xiàn)在給出完整的插入操作算法！現(xiàn)在給出完整的插入操作算法！在插入數(shù)據(jù)前查看表空間是否已滿在插入數(shù)據(jù)前查看表空間是否已滿L.listsizena a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nL.elem01n01n+10a a1 1a a2 2

41、a ai-1i-1a ai ia ai+1i+1a an nn+10將新空間長(zhǎng)度賦給將新空間長(zhǎng)度賦給L.listsize若滿，若滿，調(diào)用調(diào)用realloc()分配一個(gè)更大的分配一個(gè)更大的存儲(chǔ)空間存儲(chǔ)空間將數(shù)據(jù)復(fù)制到將數(shù)據(jù)復(fù)制到新的空間中新的空間中L.lengthn順序表插入對(duì)表空間已滿情況的處理順序表插入對(duì)表空間已滿情況的處理 插入位置插入位置 移動(dòng)元素個(gè)數(shù)移動(dòng)元素個(gè)數(shù) 1 n 2 n-1 i n-i+1 n 1 n+1 0插入算法時(shí)間復(fù)雜度分析插入算法時(shí)間復(fù)雜度分析 順序表的插入算法順序表的插入算法2.4a或或2.4b中，基本操作是移動(dòng)元素中，基本操作是移動(dòng)元素，算法時(shí)間復(fù)雜度取決于移動(dòng)元素

42、的個(gè)數(shù)算法時(shí)間復(fù)雜度取決于移動(dòng)元素的個(gè)數(shù)，即算法時(shí)間復(fù)雜，即算法時(shí)間復(fù)雜度取決于算法中循環(huán)體執(zhí)行的次數(shù)。移動(dòng)元素的個(gè)數(shù)不僅與度取決于算法中循環(huán)體執(zhí)行的次數(shù)。移動(dòng)元素的個(gè)數(shù)不僅與表長(zhǎng)有關(guān)，而且與插入位置有關(guān)。表長(zhǎng)有關(guān)，而且與插入位置有關(guān)。由此可見(jiàn)：由此可見(jiàn)：在順序表中插入一個(gè)元素在順序表中插入一個(gè)元素 ，平均要移動(dòng)表中一半元素。，平均要移動(dòng)表中一半元素。表長(zhǎng)為表長(zhǎng)為n的順序表，插入算法的時(shí)間復(fù)雜度為的順序表，插入算法的時(shí)間復(fù)雜度為 O（n）。）。假設(shè)在線性表的任何位置插入元素的概率相同，即假設(shè)在線性表的任何位置插入元素的概率相同，即pi= 1/(n+1)，則則：若用若用pi表示在順序表的第表示在

43、順序表的第i個(gè)元素之前插入元素的概率，在長(zhǎng)個(gè)元素之前插入元素的概率，在長(zhǎng)度為度為n的順序表中插入一個(gè)元素，所需移動(dòng)元素個(gè)數(shù)的數(shù)學(xué)期的順序表中插入一個(gè)元素，所需移動(dòng)元素個(gè)數(shù)的數(shù)學(xué)期望值為：望值為： 11(1)nisiiEpni111(1)12nisinEnin6）刪除操作）刪除操作 ListDelete_sq ( SqList &L, int i, ElemType &e ) 功能：功能：刪除順序表刪除順序表L中第中第i個(gè)元素，并用個(gè)元素，并用e返回返回0 a11 a2i - 2 ai - 1i - 1 aii ai + 1n - 1 an刪刪 除除 前前0 a11 a2i -

44、2 ai - 1i - 1 ai + 1i ai + 2i + 1 ai + 3n - 1 an刪刪 除除 后后aie刪除操作圖示刪除操作圖示 刪除操作主要步驟刪除操作主要步驟 ：1）i 不合法或表空，算法結(jié)束，并返回不合法或表空，算法結(jié)束，并返回ERROR；否則轉(zhuǎn)否則轉(zhuǎn)2）2）將）將ai賦值給賦值給e; 3）將順序表中）將順序表中ai后面的元素依次向前移動(dòng)一個(gè)位置后面的元素依次向前移動(dòng)一個(gè)位置;4）表長(zhǎng)）表長(zhǎng)-1。刪除操作算法刪除操作算法Status ListDelete_Sq(SqList &L, int i, ElemType &e) /在順序表在順序表L中刪除第中刪除第

45、 i個(gè)元素，并用個(gè)元素，并用e返回其值返回其值 /i的合法值為的合法值為1iL.lL.length，表空，表空L.length=0 則則i L.lL.length if (iL.length) return ERROR; / i值不合法或表空值不合法或表空 e = L.elemi-1; /被刪除元素的值賦給被刪除元素的值賦給e for ( j= i; j L.length if(iL.Length) return ERROR; / i值不合法或表空值不合法或表空 p=&(L.elemi-1); /p為被刪除元素的位置為被刪除元素的位置 e=*p; / 被刪除元素的值賦給被刪除元素的值賦

46、給e q=L.elemL.length-1; / 表尾元素的位置表尾元素的位置 for (+p; p=q;+p)*(p-1)=*p; /被刪除元素之后的元素前移被刪除元素之后的元素前移 -L.length; /表長(zhǎng)減表長(zhǎng)減1 return OK;/ListDelete_Sq 算法算法2.5 b算法算法2.5b2.5b與算法與算法2.5a 2.5a 唯唯一的不同是一的不同是通過(guò)指針通過(guò)指針p p引引用用L L.elem.elem中的元素。中的元素。刪除操作算法刪除操作算法例：將兩個(gè)有序線性表歸并成一個(gè)有序線性表。例：將兩個(gè)有序線性表歸并成一個(gè)有序線性表。設(shè)線性表設(shè)線性表A、B分別用分別用La 、

47、 Lb 的兩個(gè)順序表存儲(chǔ)，兩順序表中的兩個(gè)順序表存儲(chǔ)，兩順序表中元素元素按非遞減按非遞減順序排列，編寫算法：將順序排列，編寫算法：將La 、 Lb歸并得到順序歸并得到順序表表Lc, Lc中的元素也按值非遞減順序排列。中的元素也按值非遞減順序排列。實(shí)現(xiàn)上述功能的算法有很多，如：實(shí)現(xiàn)上述功能的算法有很多，如： 1）將）將Lb并入并入La;2）將）將La并入并入Lb;3）將）將La,Lb并入并入Lc (順序表順序表Lc中的空間是新分配的存儲(chǔ)空間）中的空間是新分配的存儲(chǔ)空間） ;此處采用第三種，其基本思想：同時(shí)對(duì)此處采用第三種，其基本思想：同時(shí)對(duì)La.elem, Lb.elem 進(jìn)行掃進(jìn)行掃描，在掃描

48、過(guò)程中按照兩表描，在掃描過(guò)程中按照兩表當(dāng)前元素當(dāng)前元素的大小，依次將其插入到的大小，依次將其插入到Lc的表尾。的表尾。三、利用基本操作實(shí)現(xiàn)線性表的其他操作三、利用基本操作實(shí)現(xiàn)線性表的其他操作 現(xiàn)在來(lái)回答現(xiàn)在來(lái)回答2.1中提到的問(wèn)題中提到的問(wèn)題, 如何利用已有基本操作實(shí)現(xiàn)線性表如何利用已有基本操作實(shí)現(xiàn)線性表的其他操作。的其他操作。Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知順序表已知順序表La和和Lb中的數(shù)據(jù)元素按值非遞減排列，中的數(shù)據(jù)元素按值非遞減排列， /歸并歸并La和和Lb得到新的順序表得到新的順序表Lc，Lc的數(shù)據(jù)

49、元素也按值非遞減排列。的數(shù)據(jù)元素也按值非遞減排列。 InitList_Sq(Lc)； i=j=1;k=0; La_len=Listength_Sq(La); Lb_len=ListLength_Sq(Lb); While(i=La_len)&(j=Lb_len) /La和和Lb均非空均非空GetElem_Sq(La, i, ai); GetElem_Sq(Lb, j, bj);if(ai=bj) ListInsert_Sq(Lc, +k, ai); +.i;else ListInsert_Sq(Lc, +k, bj); +j; while(i=La_len) GetElem_Sq(La

50、, .i+, ai); ListInsert_Sq(Lc, +k, ai); while(j=Lb_len) GetElem_Sq(Lb, .j+, bj); ListInsert_Sq (Lc, +k,bj); /MergeList_Sq 算法算法2.7 aLc.elemLc.lengthLc.listsize順序表的歸并圖示順序表的歸并圖示（算法算法2.7a)0199La.elem358La.length3 100 100La.listsize0199Lb.elem2689Lb.length4 100 100Lb.listsize01992356889 100 100建空表建空表LcLc0

51、La,LbLa,Lb歸并歸并7void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知順序表已知順序表La和和Lb的元素按值非遞減排列的元素按值非遞減排列 /歸并歸并La和和Lb得到新的順序表得到新的順序表Lc,Lc的元素也按值非遞減排列的元素也按值非遞減排列 pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem)

52、exit(OVERFLOW);/存儲(chǔ)分配失敗存儲(chǔ)分配失敗 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last &pb=pb_last) /歸并歸并 if(*pa=*pb)*pc+=*pa+; else *pc+=*pb+; while (pa=pa_last)*pc+=*pa+; /插入插入La的剩余元素的剩余元素 while (pbnext = null; return OK;/ InitList_L 1、初始化操作、初始化操作InitList_L (LinkList &L) 功

53、能：功能： 建空線性鏈表建空線性鏈表L參數(shù)：參數(shù)： L為線性鏈表的頭指針為線性鏈表的頭指針主要步驟：主要步驟：調(diào)用調(diào)用malloc ( )分配一結(jié)點(diǎn)的空間分配一結(jié)點(diǎn)的空間,并將其地址并將其地址賦值給賦值給L2、取元素操作、取元素操作 GetElem_L ( LinkList L, int i, ElemType &e )功能：功能：將線性鏈表中第將線性鏈表中第i 個(gè)元素賦值給個(gè)元素賦值給 e取元素操作主要步驟：取元素操作主要步驟：1）查找鏈表中第）查找鏈表中第 i個(gè)元素結(jié)點(diǎn)；個(gè)元素結(jié)點(diǎn)；2）將第）將第i個(gè)元素結(jié)點(diǎn)中的數(shù)據(jù)元素賦值給個(gè)元素結(jié)點(diǎn)中的數(shù)據(jù)元素賦值給e;e eaiai-1aia

54、2a1ai+1nanL L 取元素元素操作圖示取元素元素操作圖示取元素操作算法：取元素操作算法：Status GetElem_L(LinkList L, int i, ElemType &e) /L為帶頭結(jié)點(diǎn)單鏈表的頭指針，當(dāng)?shù)跒閹ь^結(jié)點(diǎn)單鏈表的頭指針，當(dāng)?shù)趇個(gè)元素存在時(shí)，個(gè)元素存在時(shí)， /其值賦給其值賦給e并返回并返回OK，否則返回，否則返回ERROR p=L-next; j=1; /初始化，初始化，p指向第一個(gè)結(jié)點(diǎn)，指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器為計(jì)數(shù)器 while(p& jnext; +j; if (!p | ji) return ERROR; /第第i個(gè)元素不存在個(gè)元素不存

55、在 e=p-data; /取第取第i個(gè)元素個(gè)元素 return OK;/GetElem_L 算法算法 2.83、插入操作、插入操作 ListInsert_L(LinkList &L, int i, ElemType e)功能：功能：在線性鏈表在線性鏈表L的第的第i個(gè)元素結(jié)點(diǎn)之前插入一個(gè)新元素結(jié)點(diǎn)個(gè)元素結(jié)點(diǎn)之前插入一個(gè)新元素結(jié)點(diǎn)插入前插入前ai-1aia2a1ai+1nanL L插入后插入后 ai-1aia2a1ai+1naneL L插入操作圖示：插入操作圖示：插入操作算法：插入操作算法：Status ListInsert_L(LinkList &L, int i, ElemTy

56、pe e) /在帶頭結(jié)點(diǎn)的線性鏈表在帶頭結(jié)點(diǎn)的線性鏈表L中第中第i個(gè)結(jié)點(diǎn)之前插入元素個(gè)結(jié)點(diǎn)之前插入元素e p=L; j=0; while (p & jnext; +j; /尋找第尋找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if(!p | jj-1) return ERROR; / i小于小于1或者大于表長(zhǎng)或者大于表長(zhǎng) s=(LinkList) malloc(sizeof(LNode); / 分配新結(jié)點(diǎn)分配新結(jié)點(diǎn) s-data=e; s-next=p-next; p-next=s; /插入新結(jié)點(diǎn)插入新結(jié)點(diǎn) return OK;/LinstInsert_L 算法算法 2.9插入操作主要步驟：插入操作主要步驟

57、：1）查找鏈表）查找鏈表L的第的第 i-1個(gè)元素結(jié)點(diǎn)；個(gè)元素結(jié)點(diǎn)；2）為新元素建立結(jié)點(diǎn)；）為新元素建立結(jié)點(diǎn)；3）修改新元素結(jié)點(diǎn)指針和第）修改新元素結(jié)點(diǎn)指針和第 i-1個(gè)元素結(jié)點(diǎn)的指針完成插入個(gè)元素結(jié)點(diǎn)的指針完成插入；4、刪除操作、刪除操作 ListDelete_L(LinkList &L, int i, ElemType &e) 功能：功能：在線性鏈表在線性鏈表L中刪除第中刪除第i個(gè)元素，并且用個(gè)元素，并且用e 返回其值返回其值刪除前刪除前ai-1aia2a1ai+1nanL L刪除后刪除后ai-1aia2a1ai+1nanL L 刪除操作圖示：刪除操作圖示：刪除操作主要步驟：

58、刪除操作主要步驟：1）查找線性鏈表）查找線性鏈表L的第的第 i-1個(gè)元素結(jié)點(diǎn)；個(gè)元素結(jié)點(diǎn)；2）修改第）修改第 i-1個(gè)元素結(jié)點(diǎn)的指針，刪除第個(gè)元素結(jié)點(diǎn)的指針，刪除第i個(gè)元素結(jié)點(diǎn)；個(gè)元素結(jié)點(diǎn)；3) 將第將第i個(gè)元素結(jié)點(diǎn)中的數(shù)據(jù)元素賦值給個(gè)元素結(jié)點(diǎn)中的數(shù)據(jù)元素賦值給e;4）回收被刪除結(jié)點(diǎn)空間；）回收被刪除結(jié)點(diǎn)空間；刪除操作算法：刪除操作算法：Status ListDelete_L(LinkList &L, int i, ElemType &e) /在帶頭結(jié)點(diǎn)的單鏈線性表在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第中，刪除第i個(gè)元素并由個(gè)元素并由e返回其值返回其值 p=L; j=0; whil

59、e (p-next&jnext; +j; if (!(p-next) | ji-1) return ERROR; /表中無(wú)第表中無(wú)第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) q=p-next; p-next=q-next; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn) e =q-data; free(q); /回收（回收（釋放）結(jié)點(diǎn)空間釋放）結(jié)點(diǎn)空間 return OK;/LinstDelete_L 算法算法 2.10三、靜態(tài)鏈表三、靜態(tài)鏈表1、靜態(tài)鏈表的概念、靜態(tài)鏈表的概念 用一維數(shù)組表示的線性鏈表，稱為靜態(tài)鏈表。用一維數(shù)組表示的線性鏈表，稱為靜態(tài)鏈表。SLinkList：數(shù)組的類型名；數(shù)組的類型名；SLinkList類型的數(shù)組變量是

60、結(jié)構(gòu)數(shù)組，每一數(shù)組分量包括類型的數(shù)組變量是結(jié)構(gòu)數(shù)組，每一數(shù)組分量包括兩個(gè)域：兩個(gè)域：data：用于存儲(chǔ)線性表元素用于存儲(chǔ)線性表元素cur： 用于存儲(chǔ)直接后繼元素在數(shù)組中的位置（下標(biāo)）用于存儲(chǔ)直接后繼元素在數(shù)組中的位置（下標(biāo)）2、靜態(tài)鏈表的類型定義、靜態(tài)鏈表的類型定義#define MAXSIZE 1000 /鏈鏈表的最大長(zhǎng)度表的最大長(zhǎng)度typedef structElemType data; int cur; component, SLinkListMAXSIZE;靜態(tài)鏈表圖示靜態(tài)鏈表圖示0123456789107a40a32a19a24a a4 4a a3 3a a1 1a a2 2 nullnull101010101024102410141014101010121014101610181020102210241026線性鏈表圖示線性鏈表圖示數(shù)組數(shù)組下標(biāo)下標(biāo)地址地址靜態(tài)鏈表與靜態(tài)鏈表與線性鏈表線性鏈表的區(qū)別？的區(qū)別？3、靜態(tài)鏈表圖示、靜態(tài)鏈表圖示0123456789101ZHAO2QIAN3SUN4LI9ZHOU6WU7ZHENG8WANG0SHI50123456789101ZHAO2QIAN3SUN