數(shù)據(jù)結(jié)構(gòu)cha2-1

1、第2章 線性表1. 了解線性結(jié)構(gòu)的了解線性結(jié)構(gòu)的特點(diǎn)。特點(diǎn)。2. 掌握掌握順序表的定義、查找、插入和順序表的定義、查找、插入和刪除。刪除。 3. 掌握掌握鏈表的定義、查找、插入和鏈表的定義、查找、插入和刪除。刪除。 4. 能夠能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。場(chǎng)合。 教學(xué)目標(biāo)教學(xué)目標(biāo)2第2章 線性表2.1 線性表的定義和特點(diǎn)線性表的定義和特點(diǎn) 2.3 線性表的類型定義線性表的類型定義2.4 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 2.5 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.6 線性表的

2、應(yīng)用線性表的應(yīng)用教學(xué)內(nèi)容教學(xué)內(nèi)容第第2 2章章線性表線性表3第2章 線性表（a1, a2, ai-1，ai, ai1 ，, an）線性表的線性表的定義定義：由：由n n(n0)(n0)個(gè)數(shù)據(jù)特征個(gè)數(shù)據(jù)特征相同相同的元的元素構(gòu)成的素構(gòu)成的有限有限序列。序列。a ai i的直接前趨的直接前趨a ai i的直接后繼的直接后繼4第一個(gè)元素第一個(gè)元素最后一個(gè)元素最后一個(gè)元素第2章 線性表（a1, a2, ai-1，ai, ai1 ，, an）線性表的線性表的定義定義：由：由n n(n0)(n0)個(gè)數(shù)據(jù)特征個(gè)數(shù)據(jù)特征相同相同的元的元素構(gòu)成的素構(gòu)成的有限有限序列。序列。n=0n=0時(shí)稱為時(shí)稱為下標(biāo)，下標(biāo)，是

3、數(shù)據(jù)元素是數(shù)據(jù)元素的的序序號(hào)號(hào)，表示元素，表示元素在線性表在線性表中的中的位置位置n n為數(shù)據(jù)元素為數(shù)據(jù)元素總個(gè)總個(gè)數(shù)數(shù)，即線性表即線性表表表長(zhǎng)長(zhǎng)空表空表5第2章 線性表非空非空線性表或線性結(jié)構(gòu)的特點(diǎn)線性表或線性結(jié)構(gòu)的特點(diǎn) 存在存在唯一唯一的一個(gè)被稱為的一個(gè)被稱為“第一個(gè)第一個(gè)”的數(shù)據(jù)元素；的數(shù)據(jù)元素； 存在存在唯一唯一的一個(gè)被稱為的一個(gè)被稱為“最后一個(gè)最后一個(gè)”的數(shù)據(jù)的數(shù)據(jù)元素；元素； 除第一除第一個(gè)元素之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均個(gè)元素之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均只有一個(gè)只有一個(gè)直接前驅(qū)直接前驅(qū)； 除最后一個(gè)元素之外除最后一個(gè)元素之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均只有一只

4、有一個(gè)個(gè)直接后繼直接后繼。6第2章 線性表 （ A, B, C, D, , ZA, B, C, D, , Z）根據(jù)線性表的定義和特點(diǎn)分析：根據(jù)線性表的定義和特點(diǎn)分析：1. 根據(jù)定義：數(shù)據(jù)特征相同：根據(jù)定義：數(shù)據(jù)特征相同：數(shù)據(jù)數(shù)據(jù)元素元素都是都是字符字符并且都并且都是是字母字母; 2. 根據(jù)特點(diǎn)：根據(jù)特點(diǎn)： 數(shù)據(jù)元素?cái)?shù)據(jù)元素間關(guān)系是間關(guān)系是線性線性結(jié)構(gòu)結(jié)構(gòu)7第2章 線性表學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)041810205041810205于春梅于春梅女女 18 180404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)1 1班班041810260041810260何仕鵬何仕鵬男男 20 200404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)2

5、 2班班041810284041810284王王 爽爽女女 19 190404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)3 3班班041810360041810360王亞武王亞武男男 18 180404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)4 4班班： ：例例2 2 分析分析學(xué)生情況登記表學(xué)生情況登記表8根據(jù)線性表的定義和特點(diǎn)分析：根據(jù)線性表的定義和特點(diǎn)分析：1. 根據(jù)定義數(shù)據(jù)特征相同：根據(jù)定義數(shù)據(jù)特征相同：數(shù)據(jù)數(shù)據(jù)元素元素都是都是記錄記錄; 2. 根據(jù)特點(diǎn)：根據(jù)特點(diǎn)： 數(shù)據(jù)元素?cái)?shù)據(jù)元素間關(guān)系是間關(guān)系是線性線性結(jié)構(gòu)。結(jié)構(gòu)。第2章 線性表抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types(ADTs: Abstrac

6、t Data Types) ) 更高層次的更高層次的數(shù)據(jù)抽象數(shù)據(jù)抽象 由用戶定義，用以表示應(yīng)用問(wèn)題的由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型數(shù)據(jù)模型 由基本的數(shù)據(jù)類型組成由基本的數(shù)據(jù)類型組成, , 并包括一組相關(guān)的并包括一組相關(guān)的操作操作9第2章 線性表抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types(ADTs: Abstract Data Types) ) 定義定義部分：部分：2.3 2.3 線性表的類型線性表的類型定義定義 表示表示部分部分 實(shí)現(xiàn)實(shí)現(xiàn)部分部分102.4 2.4 線性表線性表的順序的順序表示表示和和實(shí)現(xiàn)實(shí)現(xiàn)2.5 2.5 線性表線性表的鏈?zhǔn)降逆準(zhǔn)奖?/p>

7、示表示和和實(shí)現(xiàn)實(shí)現(xiàn) 第2章 線性表抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義定義可以定義可以用以下的用以下的三元組三元組來(lái)表示：來(lái)表示： ADT =ADT =（D D，R R，P P） 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D D上的關(guān)系集上的關(guān)系集 D D上的操作集上的操作集 11第2章 線性表ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： 基本基本操作操作： ADT ADT抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型名名抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義 ADT ADT常用定義格式常用定義格式12第2章 線性表ADT List ADT List 數(shù)據(jù)數(shù)據(jù)對(duì)象對(duì)象：D = D = a ai i| |a ai

8、iElemSetElemSet,i,i=1,2, ,=1,2, ,n,nn,n0 0 數(shù)據(jù)數(shù)據(jù)關(guān)系：關(guān)系：R R =a |a|ai-1 ,i-1 ,a ai i D,iD,i=2, ,n=2, ,n基本基本操作：操作：13抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義定義第2章 線性表1. 1. 初始化初始化線性表線性表L L InitListInitList(L)(L)操作操作結(jié)果：構(gòu)造一個(gè)空的線性表結(jié)果：構(gòu)造一個(gè)空的線性表L L 。 2. 2. 銷毀銷毀線性表線性表L L DestoryListDestoryList(L) (L) 初始條件：線性表初始條件：線性表L L已存在。已存在。操作操作結(jié)果：銷毀線性

9、表結(jié)果：銷毀線性表L L。 3. 3. 清清空線性表空線性表L L ClearListClearList(L) (L) 初始條件：線性表初始條件：線性表L L已存在已存在。操作操作結(jié)果：將結(jié)果：將L L重置為空表重置為空表。4. 4. 求線性表求線性表L L的長(zhǎng)度的長(zhǎng)度 ListLengthListLength(L)(L)初始條件：線性表初始條件：線性表L L已存在。已存在。操作操作結(jié)果：返回結(jié)果：返回L L中數(shù)據(jù)元素個(gè)數(shù)。中數(shù)據(jù)元素個(gè)數(shù)。基本操作：基本操作：14第2章 線性表5. 5. 判斷判斷線性表線性表L L是否為空是否為空 IsEmptyIsEmpty(L) (L) 初始條件：線性表初

10、始條件：線性表L L已存在。已存在。操作結(jié)果：若操作結(jié)果：若L L 為空表，則返回為空表，則返回TRUETRUE，否則返回，否則返回 FALSE FALSE。6. 6. 獲取獲取線性表線性表L L中的某個(gè)數(shù)據(jù)元素內(nèi)容中的某個(gè)數(shù)據(jù)元素內(nèi)容 GetElemGetElem( (L,i,eL,i,e) ) 初始條件：線性表初始條件：線性表L L已存在，已存在，1 1i iListLengthListLength(L)(L)操作結(jié)果：用操作結(jié)果：用e e返回返回L L中第中第i i個(gè)數(shù)據(jù)元素的值。個(gè)數(shù)據(jù)元素的值。7. 7. 檢索檢索值為值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素 LocateELemLocateEL

11、em( (L,eL,e) ) 初始條件：線性表初始條件：線性表L L已存在。已存在。操作結(jié)果：返回操作結(jié)果：返回L L中第中第1 1個(gè)與個(gè)與e e相同的元素在相同的元素在L L中中的位序。若這的位序。若這樣的數(shù)據(jù)元素不存在，則返回值樣的數(shù)據(jù)元素不存在，則返回值0 0。15基本操作：基本操作：第2章 線性表8. 8. 在線性表在線性表L L中插入一個(gè)數(shù)據(jù)元素中插入一個(gè)數(shù)據(jù)元素 ListInsertListInsert( (L,i,eL,i,e) )初始條件：線性表初始條件：線性表L L已存在，已存在，1 1i iListLengthListLength(L)+1(L)+1。操作結(jié)果：在操作結(jié)果：

12、在L L中第中第i i個(gè)位置之前插入新的數(shù)據(jù)元素個(gè)位置之前插入新的數(shù)據(jù)元素e e，L L的的長(zhǎng)度加長(zhǎng)度加1 1。9. 9. 刪除線性表刪除線性表L L中第中第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素 ListDeleteListDelete( (L,i,eL,i,e) )初始條件：線性表初始條件：線性表L L已存在且非空，已存在且非空，1 1i iListLengthListLength(L)(L)。操作結(jié)果：刪除操作結(jié)果：刪除L L的第的第i i個(gè)數(shù)據(jù)元素，并用個(gè)數(shù)據(jù)元素，并用e e返回其值，返回其值，L L的的長(zhǎng)度減長(zhǎng)度減1 1。16基本操作：基本操作：第2章 線性表ADT List數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：

13、D= D= a ai i|a|ai i ElemSet,iElemSet,i=1,2, ,=1,2, ,n,nn,n0 0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R= R=|a|ai-1 ,i-1 ,a ai i D D, ,i i=2, ,n =2, ,n 基本操作：基本操作：InitListInitList(L) (L) DestoryListDestoryList(L) (L) ClearListClearList(L) (L) ListLengthListLength(L) (L) IsEmptyIsEmpty(L) (L) GetElemGetElem( (L,i,eL,i,e) ) LocateEL

14、emLocateELem( (L,eL,e) ) ListInsertListInsert( (L,i,eL,i,e) )ADT List17第2章 線性表線性表的順序存儲(chǔ)表示：線性表的順序存儲(chǔ)表示： 定義： 用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)存儲(chǔ)線性線性表的數(shù)據(jù)表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)。稱這種存儲(chǔ)。稱這種存儲(chǔ)結(jié)構(gòu)的線性表為結(jié)構(gòu)的線性表為順序表順序表。 特點(diǎn)： 邏輯邏輯上相鄰，物理上也相鄰上相鄰，物理上也相鄰2.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示18第2章 線性表總結(jié)：第總結(jié)：第i i個(gè)元素的地址個(gè)

15、元素的地址LOC(LOC(a ai i)=LOC(a)=LOC(a1 1)+(i-1)L)+(i-1)L存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容數(shù)據(jù)元素在線數(shù)據(jù)元素在線性表中的位序性表中的位序192.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示假設(shè)：假設(shè)：1.線性表線性表的每個(gè)元的每個(gè)元素需占用素需占用L個(gè)存儲(chǔ)單個(gè)存儲(chǔ)單元。元。2.LOC(a1)為基地址為基地址（起始地（起始地址）。址）。MAXLENMAXLEN第2章 線性表 案例案例1 實(shí)現(xiàn)實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式的相加、相減和相乘的兩個(gè)一元多項(xiàng)式的相加、相減和相乘的運(yùn)算。運(yùn)算。 Pn(x)=p0+p1x+p2x2+.+pnxn Qm(x

16、)=q0+q1x+q2x2+.+qmxm (其中：其中：mn，每一項(xiàng)的指數(shù)，每一項(xiàng)的指數(shù)i隱含在其系數(shù)隱含在其系數(shù)pi和和qi的序號(hào)中的序號(hào)中)202.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示解決方法：解決方法：將兩個(gè)一元多項(xiàng)式將兩個(gè)一元多項(xiàng)式Pn(x)和和Qm(x)分別抽象為一個(gè)由分別抽象為一個(gè)由n+1個(gè)元個(gè)元素和一個(gè)由素和一個(gè)由m+1個(gè)元素組成的有序序列，分別用一個(gè)線性個(gè)元素組成的有序序列，分別用一個(gè)線性表表P和和Q來(lái)表示：來(lái)表示：Pn=（p0，p1，p2，.，pn）Qm=（q0，q1，q2，qm）兩個(gè)多項(xiàng)式相加的結(jié)果兩個(gè)多項(xiàng)式相加的結(jié)果Rn(x)= Pn(x)+ Qm

17、(x)Rn =（ p0 +q0，p1 +q1 ，p2 +q2 ，pm+qm ， pm+1, ., pn）第2章 線性表#define MAXSIZE 100 /順序表可能達(dá)到的最大長(zhǎng)度順序表可能達(dá)到的最大長(zhǎng)度typedef struct ElemType *elem; /指向數(shù)據(jù)元素的指向數(shù)據(jù)元素的基基地址地址 int length; /線性表的當(dāng)前線性表的當(dāng)前長(zhǎng)度長(zhǎng)度 SqList； 順序表的存儲(chǔ)順序表的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)表示表示說(shuō)明：說(shuō)明：1.1.類類C C語(yǔ)言中，數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義語(yǔ)言中，數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedeftypedef）描述；）描述；2.2

18、.數(shù)據(jù)元素類型約定為數(shù)據(jù)元素類型約定為ElemTypeElemType，由用戶在使用該數(shù)據(jù)類，由用戶在使用該數(shù)據(jù)類型時(shí)型時(shí)自行定義自行定義。3.3.lengthlength表示順序表中當(dāng)前表示順序表中當(dāng)前數(shù)據(jù)元素的個(gè)數(shù)數(shù)據(jù)元素的個(gè)數(shù)。212.4.1 2.4.1 線性表線性表的順序存儲(chǔ)表示的順序存儲(chǔ)表示結(jié)構(gòu)體：結(jié)構(gòu)體：構(gòu)造數(shù)據(jù)類型，將不構(gòu)造數(shù)據(jù)類型，將不同同類型的數(shù)據(jù)組合成一個(gè)整體類型的數(shù)據(jù)組合成一個(gè)整體結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名，相當(dāng)于簡(jiǎn)單，相當(dāng)于簡(jiǎn)單數(shù)據(jù)類型中的數(shù)據(jù)類型中的intint，floatfloat等等第2章 線性表 案例案例1 實(shí)現(xiàn)實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式的相加、相減和相乘的兩個(gè)一元多項(xiàng)式

19、的相加、相減和相乘的運(yùn)算。運(yùn)算。 Pn(x)=p0+p1x+p2x2+.+pnxn Qm(x)=q0+q1x+q2x2+.+qmxm (其中：其中：mn，每一項(xiàng)的指數(shù)，每一項(xiàng)的指數(shù)i隱含在其系數(shù)隱含在其系數(shù)pi和和qi的序號(hào)中的序號(hào)中)222.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示用順序表存儲(chǔ)案例用順序表存儲(chǔ)案例1的一元多項(xiàng)式數(shù)據(jù)時(shí)，其順序存儲(chǔ)分配的一元多項(xiàng)式數(shù)據(jù)時(shí)，其順序存儲(chǔ)分配情況如圖所示。情況如圖所示。elemelem00 elemelem11 elemelem22 elemelemlength-1length-1空閑區(qū)空閑區(qū)a a1 1a a2 2a a3 3a

20、alengthlength系數(shù)系數(shù)指數(shù)指數(shù)第2章 線性表232.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示elemelem00 elemelem11 elemelem22 elemelemlength-1length-1空閑區(qū)空閑區(qū)a a1 1a a2 2a a3 3a alengthlength系數(shù)系數(shù)指數(shù)指數(shù)#define MAXSIZE 100 /多項(xiàng)式可能達(dá)到多項(xiàng)式可能達(dá)到的最大長(zhǎng)度的最大長(zhǎng)度typedef struct float coef; /系數(shù)系數(shù) int expn; /指數(shù)指數(shù) polynomial；#define MAXSIZE 100 /順序表可能達(dá)到的

21、最大長(zhǎng)度順序表可能達(dá)到的最大長(zhǎng)度typedef struct polynomial *elem; /指向數(shù)據(jù)元素的指向數(shù)據(jù)元素的基基地址地址 int length; /多項(xiàng)式中當(dāng)前項(xiàng)的個(gè)數(shù)多項(xiàng)式中當(dāng)前項(xiàng)的個(gè)數(shù) SqList；結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名，相當(dāng)于簡(jiǎn)單，相當(dāng)于簡(jiǎn)單數(shù)據(jù)類型中的數(shù)據(jù)類型中的intint，floatfloat等等指針類型指針類型，存儲(chǔ)，存儲(chǔ)polynomialpolynomial類型數(shù)據(jù)的地址。類型數(shù)據(jù)的地址。第2章 線性表案例2 圖書信息管理系統(tǒng)出版社有一些圖書數(shù)據(jù)保存在一個(gè)文本文件出版社有一些圖書數(shù)據(jù)保存在一個(gè)文本文件book.txt book.txt 中，中，為簡(jiǎn)單起

22、見，在此假設(shè)每種圖書只包括為簡(jiǎn)單起見，在此假設(shè)每種圖書只包括三部分信息三部分信息：ISBNISBN、書名和價(jià)格，文件中的數(shù)據(jù)如圖所示?，F(xiàn)要求實(shí)現(xiàn)一個(gè)圖書名和價(jià)格，文件中的數(shù)據(jù)如圖所示?，F(xiàn)要求實(shí)現(xiàn)一個(gè)圖書信息管理系統(tǒng)，包括書信息管理系統(tǒng)，包括如下功能如下功能：查找、刪除、插入、排：查找、刪除、插入、排序、計(jì)數(shù)。序、計(jì)數(shù)。242.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示ISBN書名定價(jià)97873022789989程序設(shè)計(jì)基礎(chǔ)2597873022785778單片機(jī)技術(shù)及應(yīng)用3497873022785646匯編語(yǔ)言4397873022781365計(jì)算機(jī)操作系統(tǒng)33978730227

23、86794數(shù)據(jù)結(jié)構(gòu)1897873022783536數(shù)據(jù)庫(kù)原理23第2章 線性表252.4.1 2.4.1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示elemelem00 elemelem11 elemelem22 elemelemlength-1length-1空閑區(qū)空閑區(qū)a a1 1a a2 2a a3 3a alengthlengthISBNISBN書名書名價(jià)格價(jià)格#define MAXSIZE 1000 /圖書表可能達(dá)到圖書表可能達(dá)到的最大長(zhǎng)度的最大長(zhǎng)度typedef struct char no20; /圖書圖書ISBN char name50 /圖書名稱圖書名稱 float price

24、 /圖書價(jià)格圖書價(jià)格Book；typedef struct Book *elem; /指向存儲(chǔ)空間的指向存儲(chǔ)空間的基基地址地址 int length; /圖書表中當(dāng)前圖書個(gè)數(shù)圖書表中當(dāng)前圖書個(gè)數(shù) SqList；結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名，相當(dāng)于簡(jiǎn)單，相當(dāng)于簡(jiǎn)單數(shù)據(jù)類型中的數(shù)據(jù)類型中的intint，floatfloat等等指針類型指針類型，存儲(chǔ)，存儲(chǔ)BookBook類型數(shù)類型數(shù)據(jù)的地址。據(jù)的地址。第2章 線性表1.1. 初始化線性表初始化線性表L-L-構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表 算法2.1 順序表的初始化status InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的順

25、序表構(gòu)造一個(gè)空的順序表L L.elem=new ElemTypeMAXSIZE; /為順序表分配空間為順序表分配空間 if(!L.elem) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L.length=0; /空表長(zhǎng)度為空表長(zhǎng)度為0 return OK;算法說(shuō)明：算法說(shuō)明：1. C+在形參表中，以在形參表中，以“&”打頭的參數(shù)即為引用參數(shù)，傳打頭的參數(shù)即為引用參數(shù)，傳遞引用，形參變化實(shí)參也發(fā)生變化。遞引用，形參變化實(shí)參也發(fā)生變化。2. 指針變量指針變量=new 數(shù)據(jù)類型數(shù)據(jù)類型 作用：動(dòng)態(tài)分配內(nèi)存空間。作用：動(dòng)態(tài)分配內(nèi)存空間。262.4.2 2.4.2 順序表中基本操

26、作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表1.1. 初始化線性表初始化線性表L-L-構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表 算法2.1 順序表的初始化status InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表L *算法說(shuō)明：算法說(shuō)明： 3. #define OK 1#define ERROR 0#define OVERFLOW -2status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。即其是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。即其值可以是值可以是1、0、-2等。等。272.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章

27、 線性表2. 2. 銷毀銷毀線性表線性表L Lvoid DestroyList(SqList &L) if (L.elem) delete L.elem; /釋放存儲(chǔ)空間釋放存儲(chǔ)空間3. 3. 清清空線性表空線性表L Lvoid ClearList(SqList &L) L.length=0; /將線性表的長(zhǎng)度置為將線性表的長(zhǎng)度置為0算法說(shuō)明：算法說(shuō)明：指針指針變量變量=delete 指針指針變量變量 作用：釋放內(nèi)存空間作用：釋放內(nèi)存空間282.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表4. 4. 求線性表求線性表L L的長(zhǎng)度的長(zhǎng)度int G

28、etLength(SqList L) return (L.length); 5.5.判斷線性表判斷線性表L L是否為空是否為空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)29第2章 線性表6. 6. 取值：根據(jù)取值：根據(jù)指定位置序號(hào)指定位置序號(hào)i i，獲取相應(yīng)位置數(shù)據(jù)，獲取相應(yīng)位置數(shù)據(jù)元素的元素的內(nèi)容內(nèi)容。算法2.2 順序表的取值【算法思想算法思想】1.1.判斷指定的位置序號(hào)判斷指定的位置序號(hào)i i值是否合理，若不合理則返回值是否合理，若不合理則返

29、回ERROR; ERROR; 若若合理，則將第合理，則將第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素L.elemL.elemi-1i-1賦給參數(shù)賦給參數(shù)e,e,通過(guò)通過(guò)e e返回第返回第i i個(gè)數(shù)據(jù)元素的個(gè)數(shù)據(jù)元素的傳值。傳值?！舅惴ㄋ惴枋雒枋觥縤ntint GetElemGetElem( (SqListSqList L,intL,int i, i,ElemTypeElemType &e &e) ) if (_) return ERROR; if (_) return ERROR; / /判斷判斷i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=_; / e

30、=_; /第第i-1i-1的單元存儲(chǔ)著第的單元存儲(chǔ)著第i i個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) return OK; return OK; 302.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表6. 6. 取值：根據(jù)取值：根據(jù)指定位置序號(hào)指定位置序號(hào)i i，獲取相應(yīng)位置數(shù)據(jù)，獲取相應(yīng)位置數(shù)據(jù)元素的元素的內(nèi)容內(nèi)容算法2.2 順序表的取值【算法思想算法思想】1.1.判斷指定的位置序號(hào)判斷指定的位置序號(hào)i i值是否合理，若不合理則返回值是否合理，若不合理則返回ERROR; ERROR; 若若合理，則將第合理，則將第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素L.elemL.elemi-1i-1賦給參數(shù)賦給參

31、數(shù)e,e,通過(guò)通過(guò)e e返回第返回第i i個(gè)數(shù)據(jù)元素的傳值個(gè)數(shù)據(jù)元素的傳值. .【算法描述算法描述】intint GetElemGetElem( (SqListSqList L,intL,int i, i,ElemTypeElemType &e &e) ) if ( if (iiL.lengthL.length) ) return return ERROR; ERROR; / /判斷判斷i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e= e=L.elemL.elemi-1;i-1; / /第第i-1i-1的單元存儲(chǔ)著第的單元存儲(chǔ)著第i i個(gè)數(shù)據(jù)

32、個(gè)數(shù)據(jù) return OKreturn OK; ; 【算法分析算法分析】：時(shí)間復(fù)雜度時(shí)間復(fù)雜度T(n)= O(1)2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)31第2章 線性表順序順序25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 1616i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功7.7. 查找：在查找：在線性表線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素322.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性

33、表0 1 2 3 425 34 57 16 48 data查找查找5050i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失敗查找失敗337.7. 查找：在查找：在線性表線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表7.7.查找：在查找：在線性表線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素算法2.3 順序表的查找【算法思想算法思想】從第一個(gè)元素起從第一個(gè)元素起, ,依次和依次和e e相比較相比較, ,若

34、找到與若找到與e e相同的元素相同的元素L.elemL.elemi,i,則查找成功則查找成功, ,則返回該元素在表中的位置序號(hào)則返回該元素在表中的位置序號(hào); ;若查找失敗若查找失敗, ,則返回則返回0.0.【算法描述算法描述】int LocateELem(SqList L , ElemType e) for (i=0;iL.length;i+) if (_) return i+1; return 0;342.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表7.7.查找：在查找：在線性表線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素算法2.3 順序表的查

35、找【算法思想算法思想】從第一個(gè)元素起從第一個(gè)元素起, ,依次和依次和e e相比較相比較, ,若找到與若找到與e e相同的元素相同的元素L.elemL.elemi,i,則查找成功則查找成功, ,則返回該元素在表中的位置序號(hào)則返回該元素在表中的位置序號(hào); ;若查找失敗若查找失敗, ,則返回則返回0.0.【算法描述算法描述】int LocateELem(SqList L , ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i+1; return 0;352.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性

36、表查找成功的平均比較次數(shù)查找成功的平均比較次數(shù)(p(pi i為各項(xiàng)的查找概率，為各項(xiàng)的查找概率，c ci i為查找成為查找成功的比較次數(shù)功的比較次數(shù)) ) 若若查找概率相等查找概率相等,pi=1/n，則，則查找查找不成功不成功, 數(shù)據(jù)比較數(shù)據(jù)比較 n 次次綜上：順序表按值查找算法的平均時(shí)間復(fù)雜度為綜上：順序表按值查找算法的平均時(shí)間復(fù)雜度為O(n)。iniicp 1=ASL212)(11)2(111=1nnnnnninni ?7.7.查找：在線性表查找：在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素算法2.3 順序表的查找【算法分析算法分析】36 + +2.4.2 2.4.2 順序

37、表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表 算法2.4 順序表的插入【算法思想算法思想】（1 1）判斷）判斷插入位置插入位置i i是否是否合法合法。（2 2）判斷順序表的）判斷順序表的存儲(chǔ)空間是否已滿存儲(chǔ)空間是否已滿。 （3 3）將第）將第n n至第至第i i位的元素依次位的元素依次向后移動(dòng)一個(gè)位置向后移動(dòng)一個(gè)位置，空出第，空出第i i個(gè)位置。個(gè)位置。（4 4）將要插入的新元素）將要插入的新元素e e放入第放入第i i個(gè)位置個(gè)位置。（5 5）表長(zhǎng)加表長(zhǎng)加1 1，插入成功返回，插入成功返回OKOK。8.8.插入：插入：在在線性表線性表L L中第中第i i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素個(gè)數(shù)

38、據(jù)元素之前插入數(shù)據(jù)元素e e 372.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表 算法2.4 順序表的插入【算法描述算法描述】Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1) return ERROR; /i值值不合法不合法 if(L.length=MAXSIZE) return ERROR; /當(dāng)前存儲(chǔ)空間當(dāng)前存儲(chǔ)空間已滿已滿 for(j=L.length;j=i;j-) L.elemj=L.elemj-1; /插入位置及之后的元素后移插入位置及之后的元素后移 L.e

39、lemi-1=e; /將新元素將新元素e放入第放入第i個(gè)位置個(gè)位置 +L.length; /表長(zhǎng)增表長(zhǎng)增1 return OK;388.8. 插入：在線性表插入：在線性表L L中第中第i i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e e 2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表2512478936141234567892512479989361499插入插入251247893614251247893614251247893614插在第插在第4 4 個(gè)結(jié)點(diǎn)之前，移動(dòng)個(gè)結(jié)點(diǎn)之前，移動(dòng) 6-4+1=36-4+1=3 次次插在插在第第i i個(gè)個(gè)結(jié)點(diǎn)

40、之前，移動(dòng)結(jié)點(diǎn)之前，移動(dòng) n-i+1n-i+1 次次8.8.插入：在線性表插入：在線性表L L中第中第i i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e e1次次2次次3次次392.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表221)(1)(10)1(11 )(11)(p11innnnnn1inn1in1ni1ni?若插入在若插入在尾結(jié)點(diǎn)之后，尾結(jié)點(diǎn)之后，則根本則根本無(wú)需移動(dòng)（特別快）；無(wú)需移動(dòng)（特別快）；若插入在若插入在首結(jié)點(diǎn)之前，首結(jié)點(diǎn)之前，則表中元素則表中元素全部后移（特別慢）；全部后移（特別慢）；若要考慮在若要考慮在各種位置插入（共各種位置插

41、入（共n+1n+1種可能）種可能）的的平均移動(dòng)次數(shù)平均移動(dòng)次數(shù)，該如，該如何計(jì)算？何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上綜上：順序表插入算法的平均時(shí)間復(fù)雜度為綜上：順序表插入算法的平均時(shí)間復(fù)雜度為8.8.插入插入：在線性表：在線性表L L中第中第i i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e e 【算法分析算法分析】402.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表 算法2.5 順序表的刪除【算法思想算法思想】（1 1）判斷）判斷刪除位置刪除位置i i 是否合法是否合法（合法值為（合法值為1in1in）。）

42、。（2 2）將欲刪除的元素）將欲刪除的元素保留在保留在e e中。中。 （3 3）將第）將第i+1i+1至第至第n n 位的元素依次位的元素依次向前移動(dòng)一個(gè)位置向前移動(dòng)一個(gè)位置。（4 4）表長(zhǎng)減表長(zhǎng)減1 1，刪除成功返回，刪除成功返回OKOK。9.9.刪除刪除: :將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除412.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表【算法描述算法描述】Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERRO

43、R; /i值不合法值不合法 e=L.elemi-1; /將欲刪除的元素保留在將欲刪除的元素保留在e中中 for (j=i;j=L.length-1;j+) L.elemj-1=L.elemj; /被刪除元素之后的元素前移被刪除元素之后的元素前移 -L.length; /表長(zhǎng)減表長(zhǎng)減1 return OK; 429.9.刪除刪除: :將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表251247893614123456789251247361425124736142512473614刪除刪除 9 9.

44、 .刪除：將線性表刪除：將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除刪除第刪除第 4 4 個(gè)結(jié)點(diǎn)，移動(dòng)個(gè)結(jié)點(diǎn)，移動(dòng) 6 64 4 次次刪除第刪除第 i i 個(gè)結(jié)點(diǎn)，移動(dòng)個(gè)結(jié)點(diǎn)，移動(dòng) n-n-i i 次次432.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表若刪除若刪除尾結(jié)點(diǎn)，尾結(jié)點(diǎn)，則根本則根本無(wú)需移動(dòng)（特別快）；無(wú)需移動(dòng)（特別快）；若刪除若刪除首結(jié)點(diǎn)，首結(jié)點(diǎn)，則表中則表中n-1n-1個(gè)元素個(gè)元素全部全部前移（特別慢）；前移（特別慢）；若要考慮在若要考慮在各種位置各種位置刪除刪除（共（共n n種可能）種可能）的的平均移動(dòng)次數(shù)，平均移動(dòng)次數(shù)，該如該如何

45、計(jì)算？何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上nininnnninnin11i2121)(1)(1)(p=delE綜上：順序表刪除算法的平均時(shí)間復(fù)雜度為綜上：順序表刪除算法的平均時(shí)間復(fù)雜度為【算法分析算法分析】449.9.刪除刪除: :將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除2.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表1.1.順序表查找、插入、刪除算法的平均順序表查找、插入、刪除算法的平均時(shí)間時(shí)間復(fù)復(fù)雜度為雜度為 T(n)= T(n)= (n(n) )2.2.順序表的順序表的空間空間復(fù)雜度為復(fù)雜度

46、為 S(n)= S(n)=(1)(1) （因?yàn)椋ㄒ驗(yàn)闆]有占用輔助空間）沒有占用輔助空間）總結(jié)總結(jié)452.4.2 2.4.2 順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)第2章 線性表（1 1）利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素）利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致。一致。順序表（順序存儲(chǔ)結(jié)構(gòu)）的特點(diǎn)：順序表（順序存儲(chǔ)結(jié)構(gòu)）的特點(diǎn)：這種存取元素的方法被稱為這種存取元素的方法被稱為隨機(jī)存取法隨機(jī)存取法（2 2）在訪問(wèn)線性表時(shí)，可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元）在訪問(wèn)線性表時(shí)，可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。因此可以粗略地認(rèn)為，素的存儲(chǔ)地址。因此可以粗略地認(rèn)為，訪問(wèn)每個(gè)元素所花訪問(wèn)每個(gè)元素所花時(shí)間相等時(shí)間相等?？偨Y(jié)總結(jié)46第2章 線性表順序表的優(yōu)缺