課件教案數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第2章線性表(完整版)

1、 第第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è)直接后繼?？杀硎緸榭杀硎緸椋海ǎ海╝ a1 1 , a, a2 2 , , a, , an n） （邏輯、存儲(chǔ)（邏輯、存儲(chǔ)和運(yùn)算）和運(yùn)算） 只有一個(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è)

2、直接前驅(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ì)一 的的第第2 2章線性表章線性表1. 1. 了解線性結(jié)構(gòu)的特點(diǎn)了解線性結(jié)構(gòu)的特點(diǎn)2. 2.掌握順序表的定義、查找、插入和刪除掌握順序表的定義、查找、插入和刪除 3. 3.掌握鏈表的定義、創(chuàng)建、查找、插入和刪除掌握鏈

3、表的定義、創(chuàng)建、查找、插入和刪除 4. 4.能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合構(gòu)的不同特點(diǎn)及其適用場(chǎng)合 教學(xué)目標(biāo)教學(xué)目標(biāo)2.1 2.1 線性表的定義和特點(diǎn)線性表的定義和特點(diǎn)2.2 2.2 案例引入案例引入2.3 2.3 線性的類型定義線性的類型定義2.4 2.4 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.5 2.5 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.6 2.6 順序表和鏈表的比較順序表和鏈表的比較2.7 2.7 線性表的應(yīng)用線性表的應(yīng)用2.8 2.8 案例分析與實(shí)現(xiàn)案例分析與實(shí)現(xiàn)教學(xué)內(nèi)容教學(xué)內(nèi)容（a1

4、, a2, ai-1，ai, ai1 ，, an）線性表的定義：線性表的定義：用數(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 線性表的定義和特點(diǎn)線性表的定義和特點(diǎn) （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)041810205041810205于春梅于春梅女女 18 180404級(jí)

5、計(jì)算機(jī)級(jí)計(jì)算機(jī)1 1班班041810260041810260何仕鵬何仕鵬男男 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)系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性2.2 2.2 案例引入案例引入Pn(x) = p0 + p1x + p2

6、x2 + + pnxn線性表線性表P = (p0,p1,p2,pn)指數(shù)（下標(biāo)i）01234系數(shù)pi105-432P(x) = 10 + 5x - 4x2 + 3x3 + 2x4數(shù)組表示數(shù)組表示（每一項(xiàng)的指數(shù)（每一項(xiàng)的指數(shù)i隱含隱含在其系數(shù)在其系數(shù)pi的序號(hào)中）的序號(hào)中）Rn(x) = Pn(x) + Qm(x)線性表線性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)稀疏多項(xiàng)式稀疏多項(xiàng)式S(x) = 1 + 3x10000 + 2x20000北京林業(yè)大學(xué)信息學(xué)院下標(biāo)i0123下標(biāo)i012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項(xiàng)

7、式非零項(xiàng)非零項(xiàng)的數(shù)組表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 線性表線性表P =(p1, e1), (p2, e2),(pm, em)l創(chuàng)建一個(gè)創(chuàng)建一個(gè)新數(shù)組新數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項(xiàng)的每一項(xiàng)指數(shù)相同指數(shù)相同，對(duì)應(yīng)系數(shù)相加，若其和不為零，則在，對(duì)應(yīng)系數(shù)相加，若其和不為零，則在c c中增加一個(gè)新項(xiàng)中增加一個(gè)新項(xiàng)指數(shù)不相同指數(shù)不相同，則將指數(shù)較小的項(xiàng)復(fù)制到，則將指數(shù)較小的項(xiàng)復(fù)制到c c中中l(wèi)一個(gè)多項(xiàng)式已遍歷一個(gè)多項(xiàng)式已遍歷完畢完畢時(shí)，將另一個(gè)剩余項(xiàng)依次復(fù)制到時(shí)，將另一個(gè)剩余項(xiàng)依次復(fù)制

8、到c c中即可中即可A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbl順序存儲(chǔ)結(jié)構(gòu)存在問(wèn)題順序存儲(chǔ)結(jié)構(gòu)存在問(wèn)題存儲(chǔ)空間分配不靈活存儲(chǔ)空間分配不靈活運(yùn)算的空間復(fù)雜度高運(yùn)算的空間復(fù)雜度高鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x

9、+22x7-9x8181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb（1 1）查找）查找（2 2）插入）插入（3 3）刪除）刪除（4 4）修改）修改（5 5）排序）排序（6 6）計(jì)數(shù)）計(jì)數(shù)圖書順序表圖書順序表圖書鏈表圖書鏈表l線性表中數(shù)據(jù)元素的類型可以為簡(jiǎn)單類型，也可以為復(fù)雜類型。線性表中數(shù)據(jù)元素的類型可以為簡(jiǎn)單類型，也可以為復(fù)雜類型。l許多實(shí)際應(yīng)用問(wèn)題所涉的基本操作有很大相似性，不應(yīng)為每個(gè)具許多實(shí)際應(yīng)用問(wèn)題所涉的基本操作有很大相似性，不應(yīng)為每個(gè)具體應(yīng)用單獨(dú)編

10、寫一個(gè)程序。體應(yīng)用單獨(dú)編寫一個(gè)程序。l從具體應(yīng)用中從具體應(yīng)用中抽象出共性的邏輯結(jié)構(gòu)和基本操作抽象出共性的邏輯結(jié)構(gòu)和基本操作（抽象數(shù)據(jù)類抽象數(shù)據(jù)類型型），然后實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)和基本操作。），然后實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)和基本操作。線性表的重要基本操作線性表的重要基本操作1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除2.3 2.3 線性表的類型定義線性表的類型定義2.4 2.4 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或或順序映像順序映像。簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰簡(jiǎn)言之，邏

11、輯上相鄰，物理上也相鄰順序存儲(chǔ)方法：順序存儲(chǔ)方法：用用一組地址連續(xù)一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過(guò)線性表的元素，可通過(guò)數(shù)組數(shù)組VnVn來(lái)實(shí)現(xiàn)。來(lái)實(shí)現(xiàn)。順序存儲(chǔ)定義：順序存儲(chǔ)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲(chǔ)順序存儲(chǔ)#define MAXSIZE 100 /#define M

12、AXSIZE 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；順序表的類型定義順序表的類型定義#define MAXSIZE 10000/圖書表可能達(dá)到的最大長(zhǎng)度圖書表可能達(dá)到的最大長(zhǎng)度 typedef struct/圖書信息定義圖書信息定義 char no20;/圖書圖書ISBN char name50;/圖書名字圖書名字 float

13、 price; /圖書價(jià)格圖書價(jià)格Book; typedef struct Book *elem;/存儲(chǔ)空間的基地址存儲(chǔ)空間的基地址 int length;/圖書表中當(dāng)前圖書個(gè)數(shù)圖書表中當(dāng)前圖書個(gè)數(shù) SqList;/圖書表的順序存儲(chǔ)結(jié)構(gòu)類型為圖書表的順序存儲(chǔ)結(jié)構(gòu)類型為SqList圖書表的順序存儲(chǔ)結(jié)構(gòu)類型定義圖書表的順序存儲(chǔ)結(jié)構(gòu)類型定義malloc(malloc(m m) )：開辟：開辟m m字節(jié)長(zhǎng)度的地址空間，字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址并返回這段空間的首地址sizeof(sizeof(x x) )：計(jì)算變量：計(jì)算變量x x的長(zhǎng)度的長(zhǎng)度f(wàn)ree(free(p p) )：釋放指針：

14、釋放指針p p所指變量的存儲(chǔ)空間所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量，即徹底刪除一個(gè)變量補(bǔ)充：補(bǔ)充：C C語(yǔ)言的動(dòng)態(tài)分配函數(shù)（語(yǔ)言的動(dòng)態(tài)分配函數(shù)（ ）new new 類型名類型名T T（初值列表）（初值列表）功能：功能：申請(qǐng)用于存放申請(qǐng)用于存放T T類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值結(jié)果值：結(jié)果值：成功：成功：T T類型的指針，指向新分配的內(nèi)存類型的指針，指向新分配的內(nèi)存失?。菏。? 0（NULLNULL）int *p1= new int;或或 int *p1 = new int(10);delete delete 指針指針P P功能：功能：釋

15、放指針釋放指針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ǔ)分配n函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致型、個(gè)數(shù)、順序上保持一致n參數(shù)傳遞有兩種方式參數(shù)傳遞有兩種方式n傳值方式傳值方式（參數(shù)為整型、實(shí)型、字符型等）（參數(shù)為整型、實(shí)型、字符型等）n傳地址傳地址參數(shù)為指針變量參數(shù)為指針變量參數(shù)為引用類型參數(shù)為引用類型參數(shù)為數(shù)組名參數(shù)為數(shù)組名補(bǔ)充：補(bǔ)充：C+C+中的參數(shù)傳遞中的參數(shù)傳遞void main()float a,b;

16、 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)的副本中本中，函數(shù)使用這個(gè)副本執(zhí)行必要的功能。，函數(shù)使用這個(gè)副本執(zhí)行必要的功能。函數(shù)修改的是函數(shù)修改的是副本的值副本的值，實(shí)參的值不變實(shí)參的值不變傳地址傳地址方式方式指針變量作參數(shù)指針變量作參數(shù)void main()float a,b,*p1,*p2; cinab; p1=&a; p2=&b;

17、swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float t; t=*m; *m=*n; *n=t;形參變化影響實(shí)參形參變化影響實(shí)參 18:40 傳地址傳地址方式方式指針變量作參數(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í)參？形參變

18、化不影響實(shí)參？傳地址傳地址方式方式引用類型作參數(shù)引用類型作參數(shù)引用：它用來(lái)給一個(gè)對(duì)象提供一個(gè)替代的名字。引用：它用來(lái)給一個(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ù)（1 1）傳遞引用給函數(shù)與傳遞指針的效果是一）傳遞引用給函數(shù)與傳遞指針的效果是一樣的，樣的，形參變化實(shí)參也

19、發(fā)生變化形參變化實(shí)參也發(fā)生變化。（2 2）引用類型作形參，在內(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)說(shuō)明引用類型作形參的三點(diǎn)說(shuō)明（3）指針參數(shù)雖然也能達(dá)到與使用引用的效）指針參數(shù)雖

20、然也能達(dá)到與使用引用的效果，但在被調(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)說(shuō)明引用類型作形參的三點(diǎn)說(shuō)明傳地址傳地址方式方式數(shù)組名作參數(shù)數(shù)組名作參數(shù)#includevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(cha

21、r b ) b =“world”;傳遞的是數(shù)組的首地址傳遞的是數(shù)組的首地址對(duì)形參數(shù)組所做的任何改變都將反映到實(shí)參數(shù)組中對(duì)形參數(shù)組所做的任何改變都將反映到實(shí)參數(shù)組中北京林業(yè)大學(xué)信息學(xué)院#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ù)的最大數(shù)

22、個(gè)整數(shù)的最大數(shù)練習(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 ElemTypeMAXSIZE; /

23、為順序表分配空間為順序表分配空間 if(! L- elem) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L- length=0; /空表長(zhǎng)度為空表長(zhǎng)度為0 return OK; 銷毀線性表銷毀線性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /釋放存儲(chǔ)空間釋放存儲(chǔ)空間 清空線性表清空線性表L Lvoid ClearList(SqList &L) L.length=0; /將線

24、性表的長(zhǎng)度置為將線性表的長(zhǎng)度置為0補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)求線性表求線性表L L的長(zhǎng)度的長(zhǎng)度int GetLength(SqList L) return (L.length); 判斷線性表判斷線性表L L是否為空是否為空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除線性表的重要基本操作線性表的重要基本操作int

25、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; 2. 2. 取值取值（根據(jù)位置（根據(jù)位置i i獲取相應(yīng)位置數(shù)

26、據(jù)元素的內(nèi)容）獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）隨機(jī)存取獲取線性表獲取線性表L L中的某個(gè)數(shù)據(jù)元素的內(nèi)容中的某個(gè)數(shù)據(jù)元素的內(nèi)容3.3.查找查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）（根據(jù)指定數(shù)據(jù)獲取數(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查找成功查找成功25 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

27、 16 48 i查找失敗查找失敗3. 3. 查找查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）查找算法時(shí)間效率分析查找算法時(shí)間效率分析在線性表在線性表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;3. 3. 查找查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）2512478936141234567892512479989361499插入插入25124

28、7893614251247893614251247893614插第插第 4 4 個(gè)結(jié)點(diǎn)之前，移動(dòng)個(gè)結(jié)點(diǎn)之前，移動(dòng) 6 64+14+1 次次插在第插在第 i i 個(gè)結(jié)點(diǎn)之前，移動(dòng)個(gè)結(jié)點(diǎn)之前，移動(dòng) n-i+1n-i+1 次次4. 4. 插入插入（插在第（插在第 i i 個(gè)結(jié)點(diǎn)之前）個(gè)結(jié)點(diǎn)之前）（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）將要插入的新元素）將要插入的新

29、元素e e放入第放入第i i個(gè)位置個(gè)位置。（5 5）表長(zhǎng)加表長(zhǎng)加1 1，插入成功返回，插入成功返回OKOK。【算法步驟算法步驟】4. 4. 在線性表在線性表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

30、+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /將新元素將新元素e放入第放入第i個(gè)位置個(gè)位置 +L.length; /表長(zhǎng)增表長(zhǎng)增1 return OK;【算法描述算法描述】221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共若要考慮在各種位置插入（共n+1n+1種可能）的平均移動(dòng)次種可能）的平均移動(dòng)

31、次數(shù)，該如何計(jì)算？數(shù)，該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上【算法分析算法分析】251247893614123456789251247361425124736142512473614刪除刪除5. 5. 刪除刪除（刪除第（刪除第 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 次次（1 1）判斷）判斷刪除位置刪除位置i i 是否合法是否合法（合法值為（合法值為1in1in）。）。（2 2）將欲刪除的元素保留在）將欲刪除的元素保留在e e中。中。 （3

32、3）將第）將第i+1i+1至第至第n n 位的元素依次位的元素依次向前移動(dòng)一個(gè)位置向前移動(dòng)一個(gè)位置。（4 4）表長(zhǎng)減表長(zhǎng)減1 1，刪除成功返回，刪除成功返回OKOK?！舅惴ú襟E算法步驟】5. 5. 將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除Status ListDelete_Sq(SqList &L,int i) if(iL.length) return ERROR; /i值不合法值不合法 for (j=i;jdata=ai, 則則p-next-data=ai+1 a1a2an.L 18:40 2.5.2 2.5.2 單鏈表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)1.

33、1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除 18:40 1.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; 18:40 銷毀銷毀Status DestroyList_L(LinkList &L) LinkLis

34、t p; while(L) p=L; L=L-next; delete p; return OK; 補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn) 18:40 清空清空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; 補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)補(bǔ)

35、充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn) 18:40 pLa1a2. pi01p2pn=NULLan求表長(zhǎng)求表長(zhǎng)p=L-next; i=0; while(p)i+;p=p-next; 補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡(jiǎn)單基本操作的算法實(shí)現(xiàn)“數(shù)數(shù)”結(jié)點(diǎn)：結(jié)點(diǎn)：指針指針p依次指向各個(gè)結(jié)點(diǎn)依次指向各個(gè)結(jié)點(diǎn)從第一個(gè)元素開始從第一個(gè)元素開始“數(shù)數(shù)” 一直一直“數(shù)數(shù)”到最后一個(gè)結(jié)點(diǎn)到最后一個(gè)結(jié)點(diǎn) 18:40 求表長(zhǎng)求表長(zhǎng)int ListLength_L(LinkList L)/返回返回L L中數(shù)據(jù)元素個(gè)數(shù)中數(shù)據(jù)元素個(gè)數(shù) LinkList p; p=L-next; /p/p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) i=

36、0; while(p)/遍歷單鏈表遍歷單鏈表, ,統(tǒng)計(jì)結(jié)點(diǎn)數(shù)統(tǒng)計(jì)結(jié)點(diǎn)數(shù) i+; p=p-next; return i; “數(shù)數(shù)”結(jié)點(diǎn)：結(jié)點(diǎn)：指針指針p依次指向各個(gè)結(jié)點(diǎn)依次指向各個(gè)結(jié)點(diǎn)從第一個(gè)元素開始從第一個(gè)元素開始“數(shù)數(shù)” 一直一直“數(shù)數(shù)”到最后一個(gè)結(jié)點(diǎn)到最后一個(gè)結(jié)點(diǎn) 18:40 判斷表是否為空判斷表是否為空int ListEmpty(LinkList L) / / /若若L L為空表，則返回為空表，則返回1 1，否則返回，否則返回0 0 if(L-next) / / /非空非空 return 0; else return 1; 1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找

37、4. 4. 插入插入5. 5. 刪除刪除線性表的重要基本操作線性表的重要基本操作 18:40 思考：順序表里如何找到第思考：順序表里如何找到第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)2. 2. 取值取值（根據(jù)位置（根據(jù)位置i i獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容） 18:40 85L211830754256pppj1 2 3pp1i=3i=156p7例

38、：分別取出表中例：分別取出表中i=3和和i=15的元素的元素從第從第1 1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（L-nextL-next）順鏈掃描，用指針）順鏈掃描，用指針p p指向當(dāng)指向當(dāng)前掃描到的結(jié)點(diǎn)，前掃描到的結(jié)點(diǎn)，p p初值初值p p = = L-nextL-next。j j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)，做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(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)?！舅惴ú襟E算法步驟】 18:40 北京林業(yè)大學(xué)信息學(xué)

39、院/獲取線性表獲取線性表L L中的某個(gè)數(shù)據(jù)元素的內(nèi)容中的某個(gè)數(shù)據(jù)元素的內(nèi)容Status GetElem_L(LinkList L,int i,ElemType &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 2. 2. 取值取值（根據(jù)位置（根據(jù)位置i i獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容） 18:40 從第一個(gè)結(jié)點(diǎn)起，依次和從第一個(gè)結(jié)點(diǎn)起，依次和

40、e e相比較。相比較。如果找到一個(gè)其值與如果找到一個(gè)其值與e e相等的數(shù)據(jù)元素，則返回其相等的數(shù)據(jù)元素，則返回其在鏈表中的在鏈表中的“位置位置”或地址或地址；如果查遍整個(gè)鏈表都沒有找到其值和如果查遍整個(gè)鏈表都沒有找到其值和e e相等的元素相等的元素，則返回，則返回0 0或或“NULLNULL”。L211830753056pj1x=30p2p3找到，返回找到，返回i ix=51p1p6p7未找到，返回03.3.查找查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置） 18:40 /在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素LNode *LocateE

41、Lem_L (LinkList L，Elemtype e) /返回返回L中值為中值為e的數(shù)據(jù)元素的的數(shù)據(jù)元素的地址地址，查找失敗返回，查找失敗返回NULL p=L-next; while(p &p-data!=e) p=p-next; return p; 【算法描述算法描述】 18:40 /在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素int LocateELem_L (LinkList L，Elemtype e) /返回返回L中值為中值為e的數(shù)據(jù)元素的的數(shù)據(jù)元素的位置序號(hào)位置序號(hào)，查找失敗返回，查找失敗返回0 p=L-next; j=1; while(p &am

42、p;p-data!=e) p=p-next; j+; if(p) return j; else return 0; 【算法描述算法描述】 18:40 將值為將值為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之間之間3. 3. 插入插入（插在第（插在第 i i 個(gè)結(jié)點(diǎn)之前）個(gè)結(jié)點(diǎn)之前）s-next=p-next; p-next=s思考：步驟思考：步驟1 1和和2 2能互換么？能互換么？ 18:40 【算法步驟算法步驟】（1 1）找到）找到a ai-1i-1存儲(chǔ)位置存儲(chǔ)位置p p（2 2）生成一個(gè)新結(jié)點(diǎn)）生成

43、一個(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 18:40 /在在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) if(!p|ji1)return ERROR;/i大

44、于表長(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 【算法描述算法描述】 18:40 將表的第將表的第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的直接后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）釋放結(jié)點(diǎn)）釋

45、放結(jié)點(diǎn)a ai i的空間的空間5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)） 18:40 5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)） 18:40 5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq刪除前刪除前刪除后刪除后 18:40 【算法步驟算法步驟】（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-next指向指向a ai

46、 i的直接后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）將）將a ai i的值保留在的值保留在e e中中（5 5）釋放）釋放a ai i的空間的空間 18:40 /將線性表將線性表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)的地址以備釋放臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放 p-ne

47、xt=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 【算法描述算法描述】 18:40 1. 查找查找: 因線性鏈表只能順序存取，即在查找時(shí)要因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。2. 插入和刪除插入和刪除: 因線性鏈表不需要移動(dòng)元素，只要因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為修改指針，一般情況下時(shí)

48、間復(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í)間效率分析 18:40 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 18:

49、40 LpLanan-1anLp單鏈表的建立（前插法）單鏈表的建立（前插法） 18:40 void CreateList_F(LinkList &L,int n) L=new LNode; L-next=NULL; /先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表先建立一個(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 【算法描述算法描述】 18:40 n從一個(gè)空表從一個(gè)空表L開始，將新結(jié)點(diǎn)逐個(gè)插入到鏈表的尾部，

50、尾指開始，將新結(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)，將新結(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 18:40 void CreateList_L(LinkList &L,int n) /正位序輸入正位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表個(gè)元素的

51、值，建立帶表頭結(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; /插入到表尾插入到表尾 r=p; /r指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) /CreateList_L 【算法描述算法描述】 18:40 2.5.3 2.5.3 循環(huán)鏈表循環(huán)鏈表L-next=L.H(a) (a) 非空單循環(huán)鏈表非空單循環(huán)鏈表LH(b) (b) 空表空表L說(shuō)明說(shuō)明從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)的位置都可從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)的位置都可以找到其他所有結(jié)點(diǎn)，而

52、單鏈表做不到；以找到其他所有結(jié)點(diǎn)，而單鏈表做不到；循環(huán)條件：循環(huán)條件：p!=NULLp!=L p-next!=NULLp-next!=L循環(huán)鏈表中沒有明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán).H 18:40 對(duì)循環(huán)鏈表，有時(shí)不給出頭指針，而給出對(duì)循環(huán)鏈表，有時(shí)不給出頭指針，而給出尾指針尾指針可以更方便的找到可以更方便的找到第一個(gè)和最后一個(gè)第一個(gè)和最后一個(gè)結(jié)點(diǎn)結(jié)點(diǎn)reara1ai-1anai如何查找開始結(jié)點(diǎn)和終端結(jié)點(diǎn)？如何查找開始結(jié)點(diǎn)和終端結(jié)點(diǎn)？開始結(jié)點(diǎn)：開始結(jié)點(diǎn)：rear-next-next終端結(jié)點(diǎn)：終端結(jié)點(diǎn)：rear說(shuō)明說(shuō)明TaTaa a1 1a an nTbTbb

53、b1 1b bn n循環(huán)鏈表的合并循環(huán)鏈表的合并a a1 1a an nb b1 1b bn npTaTaTbTb示例示例 18:40 a a1 1a an nb b1 1b bn npTaTaTbTbLinkList Connect(LinkList Ta,LinkList Tb)/假設(shè)假設(shè)Ta、Tb都是非空的單循環(huán)鏈表都是非空的單循環(huán)鏈表 /p p存表頭結(jié)點(diǎn)存表頭結(jié)點(diǎn) /TbTb表頭連結(jié)表頭連結(jié)TaTa表尾表尾 /釋放釋放TbTb表頭結(jié)點(diǎn)表頭結(jié)點(diǎn) /修改指針修改指針 return Tb;p=Ta-next;Ta-next=Tb-next-next;deleteTb-next; Tb-nex

54、t=p; 示例示例 18:40 著名猶太歷史學(xué)家著名猶太歷史學(xué)家 Josephus在羅馬人占領(lǐng)喬塔帕特后在羅馬人占領(lǐng)喬塔帕特后39 個(gè)猶太人與個(gè)猶太人與Josephus及他的朋友躲及他的朋友躲到一個(gè)洞中到一個(gè)洞中39個(gè)猶太人決定寧愿死也不要被敵人個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式抓到，于是決定了一個(gè)自殺方式41個(gè)人個(gè)人排成一個(gè)圓圈，由第排成一個(gè)圓圈，由第1個(gè)人開個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止所有人都自殺身亡為止然而然而Josephus 和他的朋友

55、并不想遵從和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第他將朋友與自己安排在第16個(gè)與第個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲 約瑟夫問(wèn)題約瑟夫問(wèn)題約瑟夫問(wèn)題約瑟夫問(wèn)題void Josephus ( int n, int m ) Firster ( ); /檢驗(yàn)指針指向第一個(gè)結(jié)點(diǎn)檢驗(yàn)指針指向第一個(gè)結(jié)點(diǎn) for ( int i = 0; i n- -1; i+ ) /執(zhí)行執(zhí)行n- -1次次 for ( int j = 0; j m- -1; j+ ) Next ( ); /循環(huán)循環(huán)m次使次使current指

56、向被刪除結(jié)點(diǎn)指向被刪除結(jié)點(diǎn) cout “出列的人是出列的人是” GetElem_L ( ) next-prior = d-prior-next = dL-next=L 18:40 ab.pxs雙向鏈表的插入雙向鏈表的插入 18:40 1. s-prior=p-prior;雙向鏈表的插入雙向鏈表的插入a ab bx x.1 1p ps s 18:40 雙向鏈表的插入雙向鏈表的插入1. s-prior=p-prior;2. p-prior-next=s;abx.12ps 18:40 雙向鏈表的插入雙向鏈表的插入abx.123ps1. s-prior=p-prior;2. p-prior-next=

57、s;3. s-next=p; 18:40 雙向鏈表的插入雙向鏈表的插入4. p-prior=s;abx.1234ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p; 18:40 Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) if(!(p=GetElemP_DuL(L,i) return ERROR; s=new DuLNode; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK;

58、雙向鏈表的插入雙向鏈表的插入 18:40 ab.pc雙向鏈表的刪除雙向鏈表的刪除 18:40 ab.1pc1. p-prior-next=p-next;雙向鏈表的刪除雙向鏈表的刪除 18:40 雙向鏈表的刪除雙向鏈表的刪除ab.12pc1. p-prior-next=p-next;2. p-next-prior=p-prior; 18:40 Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) if(!(p=GetElemP_DuL(L,i) return ERROR; e=p-data; p-prior-next=p-n

59、ext; p-next-prior=p-prior; delete p; return OK;雙向鏈表的刪除雙向鏈表的刪除北京林業(yè)大學(xué)信息學(xué)院2.6 2.6 順序表和鏈表的比較順序表和鏈表的比較存儲(chǔ)結(jié)構(gòu)比較項(xiàng)目順序表鏈表空間存儲(chǔ)空間預(yù)先分配，會(huì)導(dǎo)致空間閑置或溢出現(xiàn)象動(dòng)態(tài)分配，不會(huì)出現(xiàn)存儲(chǔ)空間閑置或溢出現(xiàn)象存儲(chǔ)密度不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)開銷，存儲(chǔ)密度等于1需要借助指針來(lái)體現(xiàn)元素間的邏輯關(guān)系，存儲(chǔ)密度小于1時(shí)間存取元素隨機(jī)存取，按位置訪問(wèn)元素的時(shí)間復(fù)雜度為O(1)順序存取，按位置訪問(wèn)元素時(shí)間復(fù)雜度為O(n)插入、刪除平均移動(dòng)約表中一半元素，時(shí)間復(fù)雜度為O(n)不需移動(dòng)元素，確定

60、插入、刪除位置后，時(shí)間復(fù)雜度為O(n)適用情況 表長(zhǎng)變化不大，且能事先確定變化的范圍 很少進(jìn)行插入或刪除操作，經(jīng)常按元素位置序號(hào)訪問(wèn)數(shù)據(jù)元素 長(zhǎng)度變化較大 頻繁進(jìn)行插入或刪除操作 18:40 2.7 2.7 線性表的應(yīng)用線性表的應(yīng)用 18:40 2.7.1 2.7.1 線性表的合并線性表的合并問(wèn)題描述：?jiǎn)栴}描述： 假設(shè)利用兩個(gè)線性表假設(shè)利用兩個(gè)線性表LaLa和和LbLb分別表示兩分別表示兩個(gè)集合個(gè)集合A A和和B,B,現(xiàn)要求一個(gè)新的集合現(xiàn)要求一個(gè)新的集合 A=ABLa=(7, 5, 3, 11)Lb=(2, 6, 3)La=(7, 5, 3, 11, 2, 6) . 18:40 依次取出依次取出Lb Lb 中的每個(gè)元素，執(zhí)行以下操作：中的每個(gè)元素，執(zhí)行以下操作：在在LaLa中查找該元素中查找該元素如果找不到，則將其插入如果找不到，則將其插入La的最后的最后【算法步驟算法步驟】 18:40 void union(List &La, List Lb) La_