數(shù)據(jù)結(jié)構(gòu)Chapter02線性表

1、算法與數(shù)據(jù)結(jié)構(gòu)12013.9-2013.12主講教師：張翠肖聯(lián)系方式：算法與數(shù)據(jù)結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲(chǔ)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)列隊(duì)列樹樹圖圖數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)( (物理結(jié)構(gòu)物理結(jié)構(gòu)) )數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。種特定關(guān)系的數(shù)據(jù)元素的集合。 邏輯結(jié)構(gòu)：結(jié)構(gòu)定義中的邏輯結(jié)構(gòu)：結(jié)構(gòu)定義中的“關(guān)系關(guān)系”描述的是數(shù)據(jù)描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此稱為數(shù)據(jù)的邏輯結(jié)構(gòu)元素之間的邏輯關(guān)系，因此稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：是數(shù)

2、據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）。存儲(chǔ)結(jié)構(gòu)：是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）。(2)算法與數(shù)據(jù)結(jié)構(gòu)3 第第2 2章章 線性表線性表 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 第第4 4章章 串、數(shù)組和廣串、數(shù)組和廣義表義表 線性結(jié)構(gòu)線性結(jié)構(gòu)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。直接前趨和一個(gè)直接后繼。可表示為可表示為：（：（a a1 1 , a, a2 2 , , , a, an n） （邏輯、存儲(chǔ)（邏輯、存儲(chǔ)和運(yùn)算）和運(yùn)算）算法與數(shù)據(jù)結(jié)構(gòu)4

3、 只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)； 除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。個(gè)直接后繼。線性結(jié)構(gòu)表達(dá)式：（線性結(jié)構(gòu)表達(dá)式：（a a1 1 , a, a2 2 , , , a, an n） 線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是組等等，其中，最典型、最常用的是線性表線性表簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一一對(duì)一 的的算法與數(shù)據(jù)結(jié)構(gòu)5第第2 2章章線性表線性表1. 了解線性結(jié)構(gòu)的特點(diǎn)了解線性結(jié)構(gòu)的特點(diǎn)

4、2.2.掌握順序表的定義、查找、插入和刪除掌握順序表的定義、查找、插入和刪除 3.3.掌握鏈表的定義、查找、插入和刪除掌握鏈表的定義、查找、插入和刪除 4.4.能夠從時(shí)間和空間復(fù)雜度的角度比較兩種能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合 教學(xué)目標(biāo)教學(xué)目標(biāo)算法與數(shù)據(jù)結(jié)構(gòu)62.1 線性表的類型定義線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 線性表的應(yīng)用線性表的應(yīng)用教學(xué)內(nèi)容教學(xué)內(nèi)容算法與數(shù)據(jù)結(jié)構(gòu)7（a1, a2, ai-1，ai, ai1 ，, an）線性表的定

5、義：線性表的定義：用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)a ai i的直接前趨的直接前趨a ai i的直接后繼的直接后繼下標(biāo)下標(biāo)，是元素的是元素的序號(hào)，表示元素序號(hào)，表示元素在表中的位置在表中的位置n n為元素總個(gè)為元素總個(gè)數(shù)，即表長(zhǎng)數(shù)，即表長(zhǎng)空表空表線性終點(diǎn)線性終點(diǎn)2.1 2.1 線性表的類型定義線性表的類型定義算法與數(shù)據(jù)結(jié)構(gòu)8 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)041810205041810205于春梅于春梅女女 18 180404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)1 1班班0418102600418

6、10260何仕鵬何仕鵬男男 20 200404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)2 2班班041810284041810284王王 爽爽女女 19 190404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)3 3班班041810360041810360王亞武王亞武男男 18 180404級(jí)計(jì)算機(jī)級(jí)計(jì)算機(jī)4 4班班： ：數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性元素間關(guān)系是線性數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性元素間關(guān)系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性抽象數(shù)據(jù)類型線性表線性表的定義如下：ADT List 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：D ai | ai ElemSet, i=1,2,.

7、,n, n0 稱 n 為線性表的表長(zhǎng)表長(zhǎng); 稱 n=0 時(shí)的線性表為空表空表。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱 i 為 ai 在線性表中的位序位序。算法與數(shù)據(jù)結(jié)構(gòu)10 基本操作：基本操作： 結(jié)構(gòu)初始化操作結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作 引用型操作引用型操作 加工型操作加工型操作 ADT List算法與數(shù)據(jù)結(jié)構(gòu)11 InitList( &L )操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的線性表L。初始化操作初始化操作算法與數(shù)據(jù)結(jié)構(gòu)12 結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作DestroyList( &

8、amp;L )初始條件：操作結(jié)果：線性表 L 已存在。銷毀線性表 L。算法與數(shù)據(jù)結(jié)構(gòu)13ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e)引用型操作引用型操作: :算法與數(shù)據(jù)結(jié)構(gòu)14 ListEmpty( L )初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）算法與數(shù)據(jù)結(jié)構(gòu)15ListLength( L )初始條件：操作結(jié)果：線性

9、表L已存在。返回L中元素個(gè)數(shù)。（求線性表的長(zhǎng)度）算法與數(shù)據(jù)結(jié)構(gòu)16 PriorElem( L, cur_e, &pre_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是第一個(gè)，則用pre_e 返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）算法與數(shù)據(jù)結(jié)構(gòu)17NextElem( L, cur_e, &next_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）算法與數(shù)據(jù)結(jié)構(gòu)18GetElem( L, i, &e )

10、初始條件： 操作結(jié)果：線性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 個(gè)元素的值。（求線性表中某個(gè)數(shù)據(jù)元素）算法與數(shù)據(jù)結(jié)構(gòu)19LocateElem( L, e)初始條件：操作結(jié)果：線性表L已存在，e為給定值返回L中第中第1個(gè)個(gè)與e相等相等的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)）算法與數(shù)據(jù)結(jié)構(gòu)20加工型操作加工型操作 ClearList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) 算法與數(shù)據(jù)結(jié)構(gòu)21ClearList( &L )初始條件：操作結(jié)果：線性表L

11、已存在。將L重置為空表。（線性表置空）算法與數(shù)據(jù)結(jié)構(gòu)22 ListInsert( &L, i, e )初始條件：操作結(jié)果：線性表L已存在， 且 1iLengthList(L)+1 。在L的第i個(gè)元素之前插入插入新的元素e，L的長(zhǎng)度增1。（插入數(shù)據(jù)元素）算法與數(shù)據(jù)結(jié)構(gòu)23ListDelete(&L, i, &e)初始條件：操作結(jié)果：線性表L已存在且非空， 1iLengthList(L) 。刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。（刪除數(shù)據(jù)元素）算法與數(shù)據(jù)結(jié)構(gòu)242.2 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為線性表的順序表示又稱

12、為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或或順序映像順序映像。簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰順序存儲(chǔ)方法：順序存儲(chǔ)方法：用用一組地址連續(xù)一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過線性表的元素，可通過數(shù)組數(shù)組VnVn來實(shí)現(xiàn)。來實(shí)現(xiàn)。順序存儲(chǔ)定義：順序存儲(chǔ)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。算法與數(shù)據(jù)結(jié)構(gòu)25元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容Loc(元

13、素元素i)=Lo+（i-1)*m順序存儲(chǔ)順序存儲(chǔ)算法與數(shù)據(jù)結(jié)構(gòu)26#define MAXSIZE 100 /#define MAXSIZE 100 /最大長(zhǎng)度最大長(zhǎng)度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向數(shù)據(jù)元素的基地址指向數(shù)據(jù)元素的基地址 int length; /int length; /線性表的當(dāng)前長(zhǎng)度線性表的當(dāng)前長(zhǎng)度 SqListSqList；順序表的類型定義順序表的類型定義數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：查找、插入、刪除查找、插入、刪除算法與數(shù)據(jù)結(jié)構(gòu)27malloc(mal

14、loc(m m) )：開辟：開辟m m字節(jié)長(zhǎng)度的地址空間，字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址并返回這段空間的首地址sizeof(sizeof(x x) )：計(jì)算變量：計(jì)算變量x x的長(zhǎng)度的長(zhǎng)度free(free(p p) )：釋放指針：釋放指針p p所指變量的存儲(chǔ)空間所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量，即徹底刪除一個(gè)變量補(bǔ)充：補(bǔ)充：C C語言的動(dòng)態(tài)分配函數(shù)（語言的動(dòng)態(tài)分配函數(shù)（ ）算法與數(shù)據(jù)結(jié)構(gòu)28new new 類型名類型名T T（初值列表）（初值列表）功能：功能：申請(qǐng)用于存放申請(qǐng)用于存放T T類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值結(jié)果值

15、：結(jié)果值：成功：成功：T T類型的指針，指向新分配的內(nèi)存類型的指針，指向新分配的內(nèi)存失?。菏。? 0（NULLNULL）int *p1= new int;或或 int *p1 = new int(10);delete delete 指針指針P P功能：功能：釋放指針釋放指針P P所指向的內(nèi)存。所指向的內(nèi)存。P P必須是必須是newnew操作的返回值操作的返回值delete p1;補(bǔ)充：補(bǔ)充：C+C+的動(dòng)態(tài)存儲(chǔ)分配的動(dòng)態(tài)存儲(chǔ)分配算法與數(shù)據(jù)結(jié)構(gòu)29n函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致型、個(gè)數(shù)、順序上保持一致n參數(shù)傳遞有兩種

16、方式參數(shù)傳遞有兩種方式n傳值方式傳值方式（參數(shù)為整型、實(shí)型、字符型等）（參數(shù)為整型、實(shí)型、字符型等）n傳地址傳地址參數(shù)為指針變量參數(shù)為指針變量參數(shù)為引用類型參數(shù)為引用類型參數(shù)為數(shù)組名參數(shù)為數(shù)組名補(bǔ)充：補(bǔ)充：C+C+中的參數(shù)傳遞中的參數(shù)傳遞算法與數(shù)據(jù)結(jié)構(gòu)30void main()float a,b; cinab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;傳值傳值方式方式把實(shí)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副把實(shí)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副本中本中，

17、函數(shù)使用這個(gè)副本執(zhí)行必要的功能。，函數(shù)使用這個(gè)副本執(zhí)行必要的功能。函數(shù)修改的是函數(shù)修改的是副本的值副本的值，實(shí)參的值不變實(shí)參的值不變算法與數(shù)據(jù)結(jié)構(gòu)31傳地址傳地址方式方式指針變量作參數(shù)指針變量作參數(shù)void main()float a,b,*p1,*p2; cinab; p1=&a; p2=&b; swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float t; t=*m; *m=*n; *n=t;形參變化影響實(shí)參形參變化影響實(shí)參算法與數(shù)據(jù)結(jié)構(gòu)32傳地址傳地址方式方式引用類型作參數(shù)引用類型作參數(shù)引

18、用：它用來給一個(gè)對(duì)象提供一個(gè)替代的名字。引用：它用來給一個(gè)對(duì)象提供一個(gè)替代的名字。#includevoid main()int i=5;int &j=i;i=7;couti=i j=ab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;傳地址傳地址方式方式引用類型作參數(shù)引用類型作參數(shù)算法與數(shù)據(jù)結(jié)構(gòu)34（1 1）傳遞引用給函數(shù)與傳遞指針的效果是一）傳遞引用給函數(shù)與傳遞指針的效果是一樣的，樣的，形參變化實(shí)參也發(fā)生變化形參變化實(shí)參也發(fā)生變化。（2 2）引用

19、類型作形參，在內(nèi)存中并沒有產(chǎn)生）引用類型作形參，在內(nèi)存中并沒有產(chǎn)生實(shí)參的副本，它實(shí)參的副本，它直接對(duì)實(shí)參操作直接對(duì)實(shí)參操作；而一般變；而一般變量作參數(shù)，形參與實(shí)參就占用不同的存儲(chǔ)單量作參數(shù)，形參與實(shí)參就占用不同的存儲(chǔ)單元，所以形參變量的值是實(shí)參變量的副本。元，所以形參變量的值是實(shí)參變量的副本。因此，當(dāng)因此，當(dāng)參數(shù)傳遞的數(shù)據(jù)量較大參數(shù)傳遞的數(shù)據(jù)量較大時(shí)，用引用時(shí)，用引用比用一般變量傳遞參數(shù)的時(shí)間和空間效率都比用一般變量傳遞參數(shù)的時(shí)間和空間效率都好。好。引用類型作形參的三點(diǎn)說明引用類型作形參的三點(diǎn)說明算法與數(shù)據(jù)結(jié)構(gòu)35（3）指針參數(shù)雖然也能達(dá)到與使用引用的效）指針參數(shù)雖然也能達(dá)到與使用引用的效果，

20、但在被調(diào)函數(shù)中需要重復(fù)使用果，但在被調(diào)函數(shù)中需要重復(fù)使用“* *指針指針變量名變量名”的形式進(jìn)行運(yùn)算，這很容易產(chǎn)生錯(cuò)的形式進(jìn)行運(yùn)算，這很容易產(chǎn)生錯(cuò)誤且程序的閱讀性較差；另一方面，在主調(diào)誤且程序的閱讀性較差；另一方面，在主調(diào)函數(shù)的調(diào)用點(diǎn)處，必須用函數(shù)的調(diào)用點(diǎn)處，必須用變量的地址作為實(shí)變量的地址作為實(shí)參參。引用類型作形參的三點(diǎn)說明引用類型作形參的三點(diǎn)說明算法與數(shù)據(jù)結(jié)構(gòu)36傳地址傳地址方式方式數(shù)組名作參數(shù)數(shù)組名作參數(shù)#includevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(char b )

21、 b =“world”;傳遞的是數(shù)組的首地址傳遞的是數(shù)組的首地址對(duì)形參數(shù)組所做的任何改變都將反映到實(shí)參數(shù)組中對(duì)形參數(shù)組所做的任何改變都將反映到實(shí)參數(shù)組中算法與數(shù)據(jù)結(jié)構(gòu)37 20:27 #include #define N 10int max(int a);void main ( ) int a10;int i,m;for(i=0;iai;m=max(a);coutthe max number is:m;int max(int b) int i,n; n=b0; for(i=1;iN;i+)if(nbi) n=bi; return n;用數(shù)組作函數(shù)的參數(shù)，求用數(shù)組作函數(shù)的參數(shù)，求10個(gè)整數(shù)的最大

22、數(shù)個(gè)整數(shù)的最大數(shù)算法與數(shù)據(jù)結(jié)構(gòu)38練習(xí)：練習(xí)：用數(shù)組作為函數(shù)的參數(shù)，將數(shù)組中用數(shù)組作為函數(shù)的參數(shù)，將數(shù)組中n個(gè)整數(shù)按相反的順序存?zhèn)€整數(shù)按相反的順序存放，要求輸入和輸出在主函數(shù)中完成放，要求輸入和輸出在主函數(shù)中完成#include #define N 10void sub(int b )int i,j,temp,m;m=N/2;for(i=0;im;i+) j=N-1-i; temp=bi; bi= bj; bj=temp;return ;void main ( ) int a10,i;for(i=0;iai;sub(a);for(i=0;iN;i+)cout elem=new ElemType

23、MAXSIZE; /為順序表分配空間為順序表分配空間 if(! L- elem) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L- length=0; /空表長(zhǎng)度為空表長(zhǎng)度為0 return OK;算法與數(shù)據(jù)結(jié)構(gòu)422. 2. 銷毀線性表銷毀線性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /釋放存儲(chǔ)空間釋放存儲(chǔ)空間 3. 3. 清空線性表清空線性表L Lvoid ClearList(

24、SqList &L) L.length=0; /將線性表的長(zhǎng)度置為將線性表的長(zhǎng)度置為0算法與數(shù)據(jù)結(jié)構(gòu)434.4. 求線性表求線性表L L的長(zhǎng)度的長(zhǎng)度int GetLength(SqList L) return (L.length); 5.5.判斷線性表判斷線性表L L是否為空是否為空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;算法與數(shù)據(jù)結(jié)構(gòu)446. 6. 獲取線性表獲取線性表L L中的某個(gè)數(shù)據(jù)元素的內(nèi)容中的某個(gè)數(shù)據(jù)元素的內(nèi)容/根據(jù)指定位置，獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容根據(jù)指定位置，獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容i

25、nt GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.length) return ERROR; if (iL.length) return ERROR; / /判斷判斷i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的單元存儲(chǔ)著第的單元存儲(chǔ)著第i i個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) return OK;return OK; 算法與數(shù)據(jù)結(jié)構(gòu)45查找查找（根據(jù)指定數(shù)據(jù)查找，返回?cái)?shù)據(jù)

26、所在的位置）（根據(jù)指定數(shù)據(jù)查找，返回?cái)?shù)據(jù)所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功算法與數(shù)據(jù)結(jié)構(gòu)4625 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失敗查找失敗算法與數(shù)據(jù)結(jié)構(gòu)47例如：順序表23 75 41 38 54 62 17L.elemL.lengthL.

27、listsizee =38pppppi 1 2 3 4 1 850p可見，基本操作是：將順序表中的元素逐個(gè)和給定值 e 相比較。算法與數(shù)據(jù)結(jié)構(gòu)48查找算法時(shí)間效率分析查找算法時(shí)間效率分析7. 7. 在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素int LocateELem(SqList L,ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i+1; return 0;算法與數(shù)據(jù)結(jié)構(gòu)49niniicp 1=ACN212)(11)2(111=1nnnnnninni ACN查找算法時(shí)間效率分析查找算法時(shí)間效率分析

28、算法與數(shù)據(jù)結(jié)構(gòu)50 O( n )查找算法查找算法的的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為為： O( ListLength(L) )算法與數(shù)據(jù)結(jié)構(gòu)51線性表操作 ListInsert(&L, i, e)的實(shí)現(xiàn)：首先分析首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？算法與數(shù)據(jù)結(jié)構(gòu)52 (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長(zhǎng)度增加算法與數(shù)據(jù)結(jié)構(gòu)53算法算法1：在線性表中指定位置前插入一個(gè)元素：在線性表中指定位置前插入一個(gè)元素 插入元素時(shí)，線

29、性表的邏輯結(jié)構(gòu)由插入元素時(shí)，線性表的邏輯結(jié)構(gòu)由(a1, , ai-1, ai, , an)改變?yōu)楦淖優(yōu)?a1, , ai-1, b, ai, , an),在第在第i-1個(gè)數(shù)個(gè)數(shù)據(jù)元素和第據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入新的數(shù)據(jù)元素。個(gè)數(shù)據(jù)元素之間插入新的數(shù)據(jù)元素。 變成長(zhǎng)度為n+1的線性表niiaaeaaa,1,21 需將第i至第n共（n-i+1)個(gè)元素后移niiaaaaa,1,21內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1e, 算法與數(shù)據(jù)結(jié)構(gòu)551 1 2

30、1 1 2 2 1 3 2 1 3 3 2 1 3 2 1 4 2 4 4 2 4 5 2 8 5 2 5 6 3 0 6 2 8 7 4 2 7 3 0 8 7 7 8 4 2 9 7 7 圖圖 線性表插入前后的狀況線性表插入前后的狀況(a)(a)插入前插入前n=8; (b)n=8; (b)插入后插入后n=9n=9插入插入2525算法與數(shù)據(jù)結(jié)構(gòu)562512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 個(gè)結(jié)點(diǎn)之前，移動(dòng)個(gè)結(jié)點(diǎn)之前，移動(dòng) 6 64+14+1 次次插在第插在第 i

31、i 個(gè)結(jié)點(diǎn)之前，移動(dòng)個(gè)結(jié)點(diǎn)之前，移動(dòng) n-i+1n-i+1 次次插入插入（插在第（插在第 i i 個(gè)結(jié)點(diǎn)之前）個(gè)結(jié)點(diǎn)之前）算法與數(shù)據(jù)結(jié)構(gòu)57（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?！舅惴ㄋ枷胨惴ㄋ枷搿克惴ㄅc數(shù)據(jù)結(jié)構(gòu)588.

32、 8. 在線性表在線性表L L中第中第i i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e e 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-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /將新元素將新元素e放入第放入

33、第i個(gè)位置個(gè)位置 +L.length; /表長(zhǎng)增表長(zhǎng)增1 return OK;【算法描述算法描述】算法與數(shù)據(jù)結(jié)構(gòu)59若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共若要考慮在各種位置插入（共n+1n+1種可能）的平均移動(dòng)次種可能）的平均移動(dòng)次數(shù)，該如何計(jì)算？數(shù)，該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上【算法分析算法分析】考慮移動(dòng)元素的平均情況考慮移動(dòng)元素的平均情況: : 假設(shè)在第 i 個(gè)

34、元素之前插入的概率為 ， 則在長(zhǎng)度為n 的線性表中插入一個(gè)元素所需插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值移動(dòng)元素次數(shù)的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個(gè)位置上進(jìn)行插入插入的概率的概率都是相等相等的，則移動(dòng)元素的期望值移動(dòng)元素的期望值為：算法與數(shù)據(jù)結(jié)構(gòu)61插入插入 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度為為: :O( ListLength(L) ) O( n )算法與數(shù)據(jù)結(jié)構(gòu)62線性表操作 ListDelete(&L, i, &e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？算法與數(shù)據(jù)結(jié)構(gòu)63 (a1

35、, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1 an, 表的長(zhǎng)度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 算法與數(shù)據(jù)結(jié)構(gòu)64251247893614123456789251247361425124736142512473614刪除刪除刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）刪除第刪除第 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-in-i 次次算法與數(shù)據(jù)結(jié)構(gòu)65（1 1）判斷）判斷刪除位置刪除位置i i 是否合法是否合法（合法值為

36、（合法值為1in1in）。）。（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?！舅惴ㄋ枷胨惴ㄋ枷搿克惴ㄅc數(shù)據(jù)結(jié)構(gòu)669. 9. 將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1

37、; /將欲刪除的元素保留在將欲刪除的元素保留在e中中 for (j=i;jdata=ai, 則則p-next-data=ai+1 a1a2an.L算法與數(shù)據(jù)結(jié)構(gòu)931. 1. 初始化線性表初始化線性表L InitList(L) L InitList(L) 2. 2. 銷毀線性表銷毀線性表L DestoryList(L) L DestoryList(L) 3. 3. 清空線性表清空線性表L ClearList(L) L ClearList(L) 4. 4. 求線性表求線性表L L的長(zhǎng)度的長(zhǎng)度 ListLength(L)ListLength(L)5. 5. 判斷線性表判斷線性表L L是否為空是否為

38、空 IsEmpty(L) IsEmpty(L) 6. 6. 獲取線性表獲取線性表L L中的某個(gè)數(shù)據(jù)元素內(nèi)容中的某個(gè)數(shù)據(jù)元素內(nèi)容 GetElem(L,i,e) GetElem(L,i,e) 7. 7. 檢索值為檢索值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素 LocateELem(L,e)LocateELem(L,e) 8. 8. 在線性表在線性表L L中插入一個(gè)數(shù)據(jù)元素中插入一個(gè)數(shù)據(jù)元素 ListInsert(L,i,e)ListInsert(L,i,e)9. 9. 刪除線性表刪除線性表L L中第中第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素 ListDelete(L,i,e)ListDelete(L,i,e)2.3.2

39、2.3.2 單鏈表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)941.1.初始化初始化( (構(gòu)造一個(gè)空表構(gòu)造一個(gè)空表 )【算法思想算法思想】（1）生成新結(jié)點(diǎn)作頭結(jié)點(diǎn)，用頭指針）生成新結(jié)點(diǎn)作頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)。指向頭結(jié)點(diǎn)。（2）頭結(jié)點(diǎn)的指針域置空。）頭結(jié)點(diǎn)的指針域置空。L【算法描述算法描述】Status InitList_L(LinkList &L) L=new LNode; L-next=NULL; return OK; 算法與數(shù)據(jù)結(jié)構(gòu)952.2.銷毀銷毀Status DestroyList_L(LinkList &L) LinkList p; while(L)

40、p=L; L=L-next; delete p; return OK; 算法與數(shù)據(jù)結(jié)構(gòu)963.3.清空清空Status ClearList(LinkList & & L) / / 將將L L重置為空表重置為空表 LinkList p,q; p=L-next; /p/p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) while(p) /沒到表尾沒到表尾 q=p-next; delete p; p=q; L-next=NULL; /頭結(jié)點(diǎn)指針域?yàn)榭疹^結(jié)點(diǎn)指針域?yàn)榭?return OK; 算法與數(shù)據(jù)結(jié)構(gòu)974.4.求表長(zhǎng)求表長(zhǎng)int ListLength_L(LinkList L)/返回返回L L中數(shù)

41、據(jù)元素個(gè)數(shù)中數(shù)據(jù)元素個(gè)數(shù) LinkList p; p=L-next; /p/p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) i=0; while(p) /遍歷單鏈表遍歷單鏈表, ,統(tǒng)計(jì)結(jié)點(diǎn)數(shù)統(tǒng)計(jì)結(jié)點(diǎn)數(shù) i+; p=p-next; return i; 算法與數(shù)據(jù)結(jié)構(gòu)985. 5. 判斷表是否為空判斷表是否為空int ListEmpty(LinkList L) /若若L L為空表，則返回為空表，則返回1 1，否則返回，否則返回0 0 if(L-next) /非空非空 return 0; else return 1; 算法與數(shù)據(jù)結(jié)構(gòu)99 按序號(hào)查找按序號(hào)查找 按值查找按值查找查找查找算法與數(shù)據(jù)結(jié)構(gòu)100 思考：順序

42、表里如何找到第思考：順序表里如何找到第i i個(gè)元素？個(gè)元素？ 鏈表的查找：要從鏈表的頭指針出發(fā)，鏈表的查找：要從鏈表的頭指針出發(fā)，順著鏈域順著鏈域nextnext逐個(gè)結(jié)點(diǎn)往下搜索，直至逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第搜索到第i i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)隨機(jī)存取結(jié)構(gòu)按序號(hào)查找按序號(hào)查找算法與數(shù)據(jù)結(jié)構(gòu)101L 線性表的操作 GetElem(L, i, &e)在單鏈表中的實(shí)現(xiàn):211830754256pppj1 2 3算法與數(shù)據(jù)結(jié)構(gòu)102從第從第1 1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（L-nextL-next）順鏈掃描，用指針）順鏈掃描，用指針p p指向指向當(dāng)前掃描到的

43、結(jié)點(diǎn)，當(dāng)前掃描到的結(jié)點(diǎn)，p p初值初值p p = = L-nextL-next。用用j j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)，做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)，j j初值為初值為1 1。當(dāng)當(dāng)p p指向掃描到的下一結(jié)點(diǎn)時(shí)，計(jì)數(shù)器指向掃描到的下一結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j j加加1 1。當(dāng)當(dāng)j j= = i i時(shí)，時(shí)，p p所指的結(jié)點(diǎn)就是要找的第所指的結(jié)點(diǎn)就是要找的第i i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)?！舅惴ㄋ枷胨惴ㄋ枷搿堪葱蛱?hào)查找按序號(hào)查找算法與數(shù)據(jù)結(jié)構(gòu)1036.6.獲取線性表獲取線性表L L中的某個(gè)數(shù)據(jù)元素的內(nèi)容中的某個(gè)數(shù)據(jù)元素的內(nèi)容Status GetElem_L(LinkList L,int i,ElemType

44、&e) p=L-next; j=1; /初始化初始化 while(p&jnext; +j; if(!p | ji)return ERROR; /第第i個(gè)元素不存在個(gè)元素不存在 e=p-data; /取第取第i個(gè)元素個(gè)元素 return OK; /GetElem_L 按序號(hào)查找按序號(hào)查找【算法描述算法描述】算法與數(shù)據(jù)結(jié)構(gòu)104復(fù)雜度分析復(fù)雜度分析 查找第查找第 i 個(gè)數(shù)據(jù)元素的基本操作為：個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)移動(dòng)指針，比較指針，比較 j 和和 i 若若1i n,頻度為頻度為i-1. 若若in,頻度為頻度為n O(n)算法與數(shù)據(jù)結(jié)構(gòu)105從第一個(gè)結(jié)點(diǎn)起，依次和從第一個(gè)結(jié)點(diǎn)起

45、，依次和e e相比較。相比較。如果找到一個(gè)其值與如果找到一個(gè)其值與e e相等的數(shù)據(jù)元素，則返回其相等的數(shù)據(jù)元素，則返回其在鏈表中的在鏈表中的“位置位置”；如果查遍整個(gè)鏈表都沒有找到其值和如果查遍整個(gè)鏈表都沒有找到其值和e e相等的元素相等的元素，則返回，則返回“NULLNULL”。【算法思想算法思想】按值查找按值查找算法與數(shù)據(jù)結(jié)構(gòu)1067.7.在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素LNode *LocateELem_L (LinkList L，Elemtype e) p=L-next; while(p &p-data!=e) p=p-next; retur

46、n p; /返回返回L中值為中值為e的數(shù)據(jù)元素的位置，查找失敗返回的數(shù)據(jù)元素的位置，查找失敗返回NULL 按值查找按值查找【算法描述算法描述】O(n)算法與數(shù)據(jù)結(jié)構(gòu)107ai-1 線性表的操作 ListInsert(&L, i, e) 在單鏈表中的實(shí)現(xiàn)： 有序?qū)τ行驅(qū)?改變?yōu)楦淖優(yōu)?和和 eaiai-1算法與數(shù)據(jù)結(jié)構(gòu)108 因此，在單鏈表中第因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為行插入的基本操作為: 找到線性表中第找到線性表中第i-1i-1個(gè)結(jié)點(diǎn)，然后修改個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。其指向后繼的指針。 可見，在鏈表中插入結(jié)點(diǎn)只需要修改可見，在鏈表中插入

47、結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第指針。但同時(shí)，若要在第 i 個(gè)結(jié)點(diǎn)之前個(gè)結(jié)點(diǎn)之前插入元素，修改的是第插入元素，修改的是第 i-1 個(gè)結(jié)點(diǎn)的指?jìng)€(gè)結(jié)點(diǎn)的指針。針。算法與數(shù)據(jù)結(jié)構(gòu)109 將值為將值為x x的新結(jié)點(diǎn)插入到表的第的新結(jié)點(diǎn)插入到表的第i i個(gè)結(jié)點(diǎn)的位個(gè)結(jié)點(diǎn)的位置上，即插入到置上，即插入到a ai-1i-1與與a ai i之間之間插入插入（插在第（插在第 i i 個(gè)結(jié)點(diǎn)之前）個(gè)結(jié)點(diǎn)之前）s-next=p-next; p-next=s思考：步驟思考：步驟1 1和和2 2能互換么？能互換么？算法與數(shù)據(jù)結(jié)構(gòu)110 20:27 【算法思想算法思想】（1 1）找到）找到a ai-1i-1存儲(chǔ)位置存

48、儲(chǔ)位置p p（2 2）生成一個(gè)新結(jié)點(diǎn)）生成一個(gè)新結(jié)點(diǎn)* *s s（3 3）將新結(jié)點(diǎn)）將新結(jié)點(diǎn)* *s s的數(shù)據(jù)域置為的數(shù)據(jù)域置為x x（4 4）新結(jié)點(diǎn)）新結(jié)點(diǎn)* *s s的指針域指向結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)a ai i（5 5）令結(jié)點(diǎn)）令結(jié)點(diǎn)* *p p的指針域指向新結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)* *s s算法與數(shù)據(jù)結(jié)構(gòu)1118.8.在在L L中第中第i i個(gè)元素之前插入數(shù)據(jù)元素個(gè)元素之前插入數(shù)據(jù)元素e e Status ListInsert_L(LinkList &L,int i,ElemType e) p=L;j=0; while(p&jnext;+j;/尋找第尋找第i1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)

49、 if(!p|ji1)return ERROR;/i大于表長(zhǎng)大于表長(zhǎng) + 1或者小于或者小于1 s=new LNode;/生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s s-data=e; /將結(jié)點(diǎn)將結(jié)點(diǎn)s的數(shù)據(jù)域置為的數(shù)據(jù)域置為e s-next=p-next; /將結(jié)點(diǎn)將結(jié)點(diǎn)s插入插入L中中 p-next=s; return OK; /ListInsert_L 【算法描述算法描述】 eai-1aiai-1sp算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為:O(ListLength(L)算法與數(shù)據(jù)結(jié)構(gòu)112線性表的操作ListDelete (&L, i, &e)在鏈表中的實(shí)現(xiàn):有序?qū)τ行驅(qū)?和和 改變?yōu)楦淖優(yōu)?a

50、i-1aiai+1ai-1算法與數(shù)據(jù)結(jié)構(gòu)113 在單鏈表中刪除第刪除第 i i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的基本基本操作操作為:找到線性表中第找到線性表中第i-1i-1個(gè)結(jié)點(diǎn)，修個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。改其指向后繼的指針。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq算法與數(shù)據(jù)結(jié)構(gòu)114 將表的第將表的第i i個(gè)結(jié)點(diǎn)刪去個(gè)結(jié)點(diǎn)刪去 步驟：步驟：（1 1）找到）找到a ai-1i-1存儲(chǔ)位置存儲(chǔ)位置p p（2 2）保存要?jiǎng)h除的結(jié)點(diǎn)的值）保存要?jiǎng)h除的結(jié)點(diǎn)的值（3 3）令）令p-p-nextnext指向指向a ai i的直接

51、后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）釋放結(jié)點(diǎn)）釋放結(jié)點(diǎn)a ai i的空間的空間刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）算法與數(shù)據(jù)結(jié)構(gòu)115刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）算法與數(shù)據(jù)結(jié)構(gòu)116刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq刪除前刪除前刪除后刪除后算法與數(shù)據(jù)結(jié)構(gòu)117【算法思想算法思想】（1 1）找到）找到a ai-1i-1存儲(chǔ)位置存儲(chǔ)位置p p（2 2）臨時(shí)保存結(jié)點(diǎn)）臨時(shí)保存結(jié)點(diǎn)a ai i的地址在的地址在q q中，以備釋放中，以備釋放（3 3）令）令p-nextp

52、-next指向指向a ai i的直接后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）將）將a ai i的值保留在的值保留在e e中中（5 5）釋放）釋放a ai i的空間的空間算法與數(shù)據(jù)結(jié)構(gòu)118 20:27 9.9.將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除 Status ListDelete_L(LinkList &L,int i,ElemType &e) p=L;j=0; while(p-next &jnext; +j; if(!(p-next)|ji-1) return ERROR; /刪除位置不合理刪除位置不合理 q=p-next; /臨時(shí)保存被刪結(jié)點(diǎn)的

53、地址以備釋放臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放 p-next=q-next; /改變刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的指針域改變刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的指針域 e=q-data; /保存刪除結(jié)點(diǎn)的數(shù)據(jù)域保存刪除結(jié)點(diǎn)的數(shù)據(jù)域 delete q; /釋放刪除結(jié)點(diǎn)的空間釋放刪除結(jié)點(diǎn)的空間 return OK; /ListDelete_L 【算法描述算法描述】算法與數(shù)據(jù)結(jié)構(gòu)1191. 查找查找: 因線性鏈表只能順序存取，即在查找時(shí)要因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。2. 插入和刪除插入和刪除: 因線性鏈表不需要移動(dòng)元素，只要因線性鏈表不需要移動(dòng)元素，

54、只要修改指針，一般情況下時(shí)間復(fù)雜度為修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行前插或刪除操作，但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為 O(n) 。鏈表的運(yùn)算時(shí)間效率分析鏈表的運(yùn)算時(shí)間效率分析算法與數(shù)據(jù)結(jié)構(gòu)120如何從線性表得到單鏈表？如何從線性表得到單鏈表？ (創(chuàng)建單鏈表創(chuàng)建單鏈表)鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此予分配空間，因此生成鏈表的過程生成鏈表的過程是一個(gè)結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)“逐個(gè)插入逐個(gè)插入” ” 的過程。的過程。算法與數(shù)據(jù)結(jié)構(gòu)121

55、n從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：u生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)u將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中u將該新結(jié)點(diǎn)插入到鏈表的前端將該新結(jié)點(diǎn)插入到鏈表的前端單鏈表的建立（前插法）單鏈表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d 算法與數(shù)據(jù)結(jié)構(gòu)122LpLanan-1anLp單鏈表的建立（前插法）單鏈表的建立（前插法）算法與數(shù)據(jù)結(jié)構(gòu)123void CreateList_F(LinkList &L,int n) L=new LNode; L-next=NULL; /先建立一個(gè)帶頭結(jié)點(diǎn)的

56、單鏈表先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for(i=n;i0;-i) p=new LNode; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) cinp-data; /輸入元素值輸入元素值 p-next=L-next;L-next=p; /插入到表頭插入到表頭 /CreateList_F 【算法描述算法描述】算法與數(shù)據(jù)結(jié)構(gòu)124n從一個(gè)空表從一個(gè)空表L開始，將新結(jié)點(diǎn)逐個(gè)插入到鏈表的尾部，尾指開始，將新結(jié)點(diǎn)逐個(gè)插入到鏈表的尾部，尾指針針r指向鏈表的尾結(jié)點(diǎn)。指向鏈表的尾結(jié)點(diǎn)。n初始時(shí)，初始時(shí)，r同同L均指向頭結(jié)點(diǎn)。每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一均指向頭結(jié)點(diǎn)。每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)新結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到尾結(jié)點(diǎn)后，個(gè)新結(jié)點(diǎn)，將新

57、結(jié)點(diǎn)插入到尾結(jié)點(diǎn)后，r指向新結(jié)點(diǎn)。指向新結(jié)點(diǎn)。單鏈表的建立（尾插法）單鏈表的建立（尾插法） L L L L L L a r r a b r a c r b a e r b c d a d r b c 算法與數(shù)據(jù)結(jié)構(gòu)125void CreateList_L(LinkList &L,int n) /正位序輸入正位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表L L=new LNode; L-next=NULL; r=L; /尾指針尾指針r指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn) for(i=0;ip-data; /輸入元素值輸入元素值 p-next=NULL; r-next=p;

58、 /插入到表尾插入到表尾 r=p; /r指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) /CreateList_L 【算法描述算法描述】算法與數(shù)據(jù)結(jié)構(gòu)126思考思考 鏈表的輸出算法與數(shù)據(jù)結(jié)構(gòu)127不帶頭結(jié)點(diǎn)的單鏈表不帶頭結(jié)點(diǎn)的單鏈表( (自學(xué)自學(xué)) )算法與數(shù)據(jù)結(jié)構(gòu)1281 建立單鏈表建立單鏈表: 設(shè)成員數(shù)據(jù)域?yàn)樽址停?）頭插法建表頭插法建表：依次插入新結(jié)點(diǎn)，并置于表頭 a head b a head b c a head b c 規(guī)律：新增加的結(jié)點(diǎn)指針域指向原h(huán)ead指向的結(jié)點(diǎn)，然后將原h(huán)ead指向新結(jié)點(diǎn)算法與數(shù)據(jù)結(jié)構(gòu)129頭插法建立單鏈表頭插法建立單鏈表head 建立新節(jié)點(diǎn) 向新節(jié)點(diǎn)中添入內(nèi)容 使新節(jié)點(diǎn)指

59、向鏈?zhǔn)?改變頭指針s算法與數(shù)據(jù)結(jié)構(gòu)130頭插法建立單鏈表頭插法建立單鏈表linklist *CREATELIST() char ch; linklist *head,*s;headNULL; chgetchar(); while (ch!=$) smalloc(sizeof(linklist); s-datach; s-nexthead; heads; chgetchar(); return(head);head從鍵盤輸入 o產(chǎn)生一個(gè)指針變量s1s1的數(shù)據(jù)域?yàn)閛head指向s1再輸入k產(chǎn)生指針變量s2s2的數(shù)據(jù)域?yàn)閗s2的指針域?yàn)閟1head指向s2算法與數(shù)據(jù)結(jié)構(gòu)131(2) 尾插法建表尾插法

60、建表：插入的新結(jié)點(diǎn)置于表尾 產(chǎn)生一個(gè)新結(jié)點(diǎn)； 新結(jié)點(diǎn)的數(shù)據(jù)域?yàn)椴迦胱址?原尾結(jié)點(diǎn)（由尾指針指定）的指針域?yàn)樾陆Y(jié)點(diǎn)； 尾指針指向新結(jié)點(diǎn)； 新結(jié)點(diǎn)的指針域?yàn)榭?a head a head b a head b c tailtailtail算法與數(shù)據(jù)結(jié)構(gòu)132尾插法建立單鏈表尾插法建立單鏈表head 建立新節(jié)點(diǎn) 向新節(jié)點(diǎn)中添入內(nèi)容 將新節(jié)點(diǎn)鏈入鏈尾 改變尾指針s算法與數(shù)據(jù)結(jié)構(gòu)133linklist *CREATELISTR() char ch; linklist *head,*s,*r; headNULL; rNULL; chgetchar(); while(ch!=$) smalloc(sizeof(linklist); s-datach; if (head=NULL) heads; else r-nexts; rs; chgetchar(); 尾插法建立單鏈表尾插法建立單鏈表 if (r!=NULL) r-nextNULL; return head;算法與數(shù)據(jù)結(jié)構(gòu)134 算法與數(shù)據(jù)結(jié)構(gòu)135算法與數(shù)據(jù)結(jié)構(gòu)136 單鏈表特點(diǎn)單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)