第二章線性表

1、若結(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） 只有一個(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ì)列、字符串

2、、數(shù)線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是組等等，其中，最典型、最常用的是線性表線性表簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一一對一 的的第第2 2章線性表章線性表1. 1. 了解線性結(jié)構(gòu)的特點(diǎn)了解線性結(jié)構(gòu)的特點(diǎn)2. 2. 掌握順序表的定義、查找、插入和刪除掌握順序表的定義、查找、插入和刪除 3. 3. 掌握鏈表的定義、創(chuàng)建、查找、插入和刪除掌握鏈表的定義、創(chuàng)建、查找、插入和刪除 4. 4. 能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲結(jié)能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合構(gòu)的不同特點(diǎn)及其

3、適用場合 教學(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, a2, ai-1，ai, ai1 ，, an）線性表的定義：線性表的定義：用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元

4、素起點(diǎn)起點(diǎn)a ai i的直接前趨的直接前趨a ai i的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n n為元素總個(gè)為元素總個(gè)數(shù)，即表長數(shù)，即表長空表空表終點(diǎn)終點(diǎn)2.1 2.1 線性表的定義和特點(diǎn)線性表的定義和特點(diǎn) （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級141810205141810205于春梅于春梅女女 18 181414級計(jì)算機(jī)級計(jì)算機(jī)1 1班班141810260141810260何仕鵬何仕鵬男男 19 191414級計(jì)算機(jī)級計(jì)算機(jī)2 2班班141810284141810284王王 爽爽女女 19

5、191414級計(jì)算機(jī)級計(jì)算機(jī)3 3班班141810360141810360王亞武王亞武男男 18 181414級計(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 + p2x2 + + pnxn線性表線性表P = (p0,p1,p2,pn)指數(shù)（下標(biāo)i）01234系數(shù)pi105-432P(x) = 10 + 5x - 4x2 + 3x3 + 2x4數(shù)

6、組表示數(shù)組表示（每一項(xiàng)的指數(shù)（每一項(xiàng)的指數(shù)i隱含隱含在其系數(shù)在其系數(shù)pi的序號中）的序號中）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下標(biāo)i0123下標(biāo)i012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項(xiàng)式非零項(xiàng)非零項(xiàng)的數(shù)組表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 線性表線性表P =(p1, e1), (p2, e2),(pm,

7、em)l創(chuàng)建一個(gè)創(chuàng)建一個(gè)新數(shù)組新數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項(xiàng)的每一項(xiàng)指數(shù)相同指數(shù)相同，對應(yīng)系數(shù)相加，若其和不為零，則在，對應(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ù)制到c c中即可中即可（1 1）查找）查找（2 2）插入）插入（3 3）刪除）刪除（4 4）修改）修改（5 5）排序）排序（6 6）計(jì)數(shù)）計(jì)數(shù)圖書順序表圖書順序表圖書鏈表圖書鏈表線性表的重要基本操作線性

8、表的重要基本操作1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除2.3 2.3 線性表的類型定義線性表的類型定義2.4 2.4 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或或順序映像順序映像。簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也相鄰順序存儲方法：順序存儲方法：用用一組地址連續(xù)一組地址連續(xù)的存儲單元依次存儲的存儲單元依次存儲線性表的元素，可通過線性表的元素，可通過數(shù)組數(shù)組VnVn來實(shí)現(xiàn)。來實(shí)現(xiàn)。順序存儲定義：順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲

9、在物理把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。上相鄰的存儲單元中的存儲結(jié)構(gòu)。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲順序存儲#define MAXSIZE 100 /#define MAXSIZE 100 /最大長度最大長度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向數(shù)據(jù)元素的基地址指向數(shù)據(jù)元素的基地址 int length; /i

10、nt length; /線性表的當(dāng)前長度線性表的當(dāng)前長度 SqListSqList；順序表的類型定義順序表的類型定義#define MAXSIZE 10000/圖書表可能達(dá)到的最大長度圖書表可能達(dá)到的最大長度 typedef struct/圖書信息定義圖書信息定義 char no20;/圖書圖書ISBN char name50;/圖書名字圖書名字 float price; /圖書價(jià)格圖書價(jià)格Book; typedef struct Book *elem;/存儲空間的基地址存儲空間的基地址 int length;/圖書表中當(dāng)前圖書個(gè)數(shù)圖書表中當(dāng)前圖書個(gè)數(shù) SqList;/圖書表的順序存儲結(jié)構(gòu)類型

11、為圖書表的順序存儲結(jié)構(gòu)類型為SqList圖書表的順序存儲結(jié)構(gòu)類型定義圖書表的順序存儲結(jié)構(gòu)類型定義1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除線性表的重要基本操作線性表的重要基本操作重要基本操作的算法實(shí)現(xiàn)重要基本操作的算法實(shí)現(xiàn)初始化順序表初始化順序表 （參數(shù)用引用）（參數(shù)用引用）Status InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表L L.elem=new ElemTypeMAXSIZE; /為順序表分配空間為順序表分配空間 if(!L.elem) exit(OVERFLOW); /存

12、儲分配失敗存儲分配失敗 L.length=0; /空表長度為空表長度為0 return OK;1 1、初始化順序表、初始化順序表 （參數(shù)用指針）（參數(shù)用指針）Status InitList_Sq(SqList *L) /構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表L L- elem=new ElemTypeMAXSIZE; /為順序表分配空間為順序表分配空間 if(! L- elem) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 L- length=0; /空表長度為空表長度為0 return OK;銷毀順序表銷毀順序表void DestroyList(SqList &L)vo

13、id DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /釋放存儲空間釋放存儲空間 清空順序表清空順序表void ClearList(SqList &L) L.length=0; /將線性表的長度置為將線性表的長度置為0求順序表的長度求順序表的長度int GetLength(SqList L) return (L.length); 判斷順序表是否為空判斷順序表是否為空int IsEmpty(SqList L) if (L.length=0) return 1; else re

14、turn 0;補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除線性表的重要基本操作線性表的重要基本操作int 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值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORER

15、ROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的單元存儲著第的單元存儲著第i i個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) return OK;return OK; 2. 2. 取值取值（根據(jù)位置（根據(jù)位置i i獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）隨機(jī)存取獲取順序表中的某個(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

16、 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 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)

17、 return i+1; return 0;3. 3. 查找查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）2512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 個(gè)結(jié)點(diǎn)之前，移動個(gè)結(jié)點(diǎn)之前，移動 6 64+14+1 次次插在第插在第 i i 個(gè)結(jié)點(diǎn)之前，移動個(gè)結(jié)點(diǎn)之前，移動 n-i+1n-i+1 次次4. 4. 插入插入（插在第（插在第 i i 個(gè)結(jié)點(diǎn)之前）個(gè)結(jié)點(diǎn)之前）（1 1）判斷）判斷插入位置插入位置i i 是否合法是否合法。（2 2）判斷順序表的）

18、判斷順序表的存儲空間是否已滿存儲空間是否已滿。 （3 3）將第）將第n n至第至第i i 位的元素依次位的元素依次向后移動一個(gè)位置向后移動一個(gè)位置，空，空出第出第i i個(gè)位置。個(gè)位置。（4 4）將要插入的新元素）將要插入的新元素e e放入第放入第i i個(gè)位置個(gè)位置。（5 5）表長加表長加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)

19、return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /當(dāng)前存儲空間已滿當(dāng)前存儲空間已滿 for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /將新元素將新元素e放入第放入第i個(gè)位置個(gè)位置 +L.length; /表長增表長增1 return OK;【算法描述算法描述】221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN若插入在尾結(jié)點(diǎn)之后，則根本無需移動（特別快）；若插入在尾結(jié)點(diǎn)之后，則根

20、本無需移動（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共若要考慮在各種位置插入（共n+1n+1種可能）的平均移動次種可能）的平均移動次數(shù)，該如何計(jì)算？數(shù)，該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動元素的操作上算法時(shí)間主要耗費(fèi)在移動元素的操作上【算法分析算法分析】251247893614123456789251247361425124736142512473614刪除刪除5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）刪除第刪除第 4 4 個(gè)結(jié)點(diǎn)，移動個(gè)結(jié)點(diǎn)，移動 6 64 4 次次刪除第刪除第 i

21、 i 個(gè)結(jié)點(diǎn)，移動個(gè)結(jié)點(diǎn)，移動 n-in-i 次次（1 1）判斷）判斷刪除位置刪除位置i i 是否合法是否合法（合法值為（合法值為1in1in）。）。（2 2）將欲刪除的元素保留在）將欲刪除的元素保留在e e中。中。 （3 3）將第）將第i+1i+1至第至第n n 位的元素依次位的元素依次向前移動一個(gè)位置向前移動一個(gè)位置。（4 4）表長減表長減1 1，刪除成功返回，刪除成功返回OKOK。【算法步驟算法步驟】5. 5. 將線性表將線性表L L中第中第i i個(gè)數(shù)據(jù)元素刪除個(gè)數(shù)據(jù)元素刪除Status ListDelete_Sq(SqList &L,int i) if(iL.length) r

22、eturn ERROR; /i值不合法值不合法 for (j=i;jdata=ai, 則則p-next-data=ai+1 a1a2an.L2.5.2 2.5.2 單鏈表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除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 &a

23、mp;L) L=new LNode; L-next=NULL; return OK; 銷毀銷毀Status DestroyList_L(LinkList &L) LinkList p; while(L) p=L; L=L-next; delete p; return OK; 補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)清空清空Status ClearList(LinkList & & L) / / 將將L L重置為空表重置為空表 LinkList p,q; p=L-next; /p/p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) while(p) /沒到表尾沒到表尾

24、 q=p-next; delete p; p=q; L-next=NULL; /頭結(jié)點(diǎn)指針域?yàn)榭疹^結(jié)點(diǎn)指針域?yàn)榭?return OK; 補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)pLa1a2. pi01p2pn=NULLan求表長求表長p=L-next; i=0; while(p)i+;p=p-next; 補(bǔ)充：幾個(gè)簡單基本操作的算法實(shí)現(xiàn)補(bǔ)充：幾個(gè)簡單基本操作的算法實(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)求表長求表長int ListLength_L(LinkLi

25、st 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=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)判斷表是否為空判斷表是否為空int ListEmpty(LinkList L) / / /若若L L為空表，則返回為空表，則返回1 1，否則返回，否則返回0 0 if(L-next) / /

26、 /非空非空 return 0; else return 1; 1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 刪除刪除線性表的重要基本操作線性表的重要基本操作 思考：順序表里如何找到第思考：順序表里如何找到第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)容）獲

27、取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）64L211830754256pppj1 2 3pp1i=3i=156p7例：分別取出表中例：分別取出表中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)前掃描過的結(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)就是要

28、找的第所指的結(jié)點(diǎn)就是要找的第i i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)?！舅惴ú襟E算法步驟】/獲取線性表獲取線性表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ù)元

29、素的內(nèi)容）從第一個(gè)結(jié)點(diǎn)起，依次和從第一個(gè)結(jié)點(diǎn)起，依次和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ù)所在的位置）/在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元

30、素的數(shù)據(jù)元素LNode *LocateELem_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; 【算法描述算法描述】/在線性表在線性表L L中查找值為中查找值為e e的數(shù)據(jù)元素的數(shù)據(jù)元素int LocateELem_L (LinkList L，Elemtype e) /返回返回L中值為中值為e的數(shù)據(jù)元素的的數(shù)據(jù)元素的位置序號位置序號，查找失敗返回，查找失敗返回0 p=L-next; j=1

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

32、）生成一個(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/在在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大于表長大

33、于表長 + 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 【算法描述算法描述】 將表的第將表的第i i個(gè)結(jié)點(diǎn)刪去個(gè)結(jié)點(diǎn)刪去 步驟：步驟：（1 1）找到）找到a ai-1i-1存儲位置存儲位置p p（2 2）保存要刪除的結(jié)點(diǎn)的值）保存要刪除的結(jié)點(diǎn)的值（3 3）令）令p-p-nextnext指向指向a ai i的直接后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）釋放結(jié)點(diǎn)）釋放結(jié)點(diǎn)a ai i的

34、空間的空間5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）5. 5. 刪除刪除（刪除第（刪除第 i i 個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq刪除前刪除前刪除后刪除后【算法步驟算法步驟】（1 1）找到）找到a ai-1i-1存儲位置存儲位置p p（2 2）臨時(shí)保存結(jié)點(diǎn)）臨時(shí)保存結(jié)點(diǎn)a ai i的地址在的地址在q q中，以備釋放中，以備釋放（3 3）令）令p-nextp-next指向指向a ai i的直接后繼結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（4 4）將）將a ai i的

35、值保留在的值保留在e e中中（5 5）釋放）釋放a ai i的空間的空間北京林業(yè)大學(xué)信息學(xué)院/將線性表將線性表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-next=q-next; /改變刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的指針域改變

36、刪除結(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 【算法描述算法描述】1. 查找查找: 因線性鏈表只能順序存取，即在查找時(shí)要因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。2. 插入和刪除插入和刪除: 因線性鏈表不需要移動元素，只要因線性鏈表不需要移動元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行前插或刪除操作，但是

37、，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為 O(n) 。鏈表的運(yùn)算時(shí)間效率分析鏈表的運(yùn)算時(shí)間效率分析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 LpLanan-1anLp單鏈表的建立（前插法）單鏈表的建立（前插法）void Creat

38、eList_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 【算法描述算法描述】n從一個(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)

39、。每讀入一個(gè)數(shù)據(jù)元素則申請一均指向頭結(jié)點(diǎn)。每讀入一個(gè)數(shù)據(jù)元素則申請一個(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 void 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

40、(i=0;ip-data; /輸入元素值輸入元素值 p-next=NULL; r-next=p; /插入到表尾插入到表尾 r=p; /r指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) /CreateList_L 【算法描述算法描述】優(yōu)點(diǎn)優(yōu)點(diǎn)數(shù)據(jù)元素的個(gè)數(shù)可以自由擴(kuò)充數(shù)據(jù)元素的個(gè)數(shù)可以自由擴(kuò)充 插入、刪除等操作不必移動數(shù)據(jù)，只需插入、刪除等操作不必移動數(shù)據(jù)，只需修改鏈接指針，修改效率較高修改鏈接指針，修改效率較高鏈表的優(yōu)缺點(diǎn)鏈表的優(yōu)缺點(diǎn)缺點(diǎn)缺點(diǎn)存儲密度小存儲密度小存取效率不高，必須采用存取效率不高，必須采用順序存取順序存取，即存，即存取數(shù)據(jù)元素時(shí)，只能按鏈表的順序進(jìn)行訪問取數(shù)據(jù)元素時(shí)，只能按鏈表的順序進(jìn)行訪問（順

41、藤摸瓜）（順藤摸瓜）鏈表的優(yōu)缺點(diǎn)鏈表的優(yōu)缺點(diǎn)練習(xí)練習(xí)1.1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 2.2.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。適宜于進(jìn)行隨機(jī)存取。3.3.順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。入、刪除運(yùn)算效率高。4.4.線性表若采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)之間和結(jié)線性表若采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)之間和結(jié)點(diǎn)內(nèi)部的存儲空間都是可以不連續(xù)的。點(diǎn)內(nèi)部的存儲空間都是可以不連續(xù)的。 5.5.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類

42、型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型 2.5.3 2.5.3 循環(huán)鏈表循環(huán)鏈表L-next=L.H(a) (a) 非空單循環(huán)鏈表非空單循環(huán)鏈表LH(b) (b) 空表空表L說明說明從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)的位置都可從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)的位置都可以找到其他所有結(jié)點(diǎn)，而單鏈表做不到；以找到其他所有結(jié)點(diǎn)，而單鏈表做不到；循環(huán)條件：循環(huán)條件：p!=NULLp!=L p-next!=NULLp-next!=L循環(huán)鏈表中沒有明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán).H對循環(huán)鏈表，有時(shí)不給出頭指針，而給出對循環(huán)鏈表，有時(shí)不給出頭指針，而給出

43、尾指針尾指針可以更方便的找到可以更方便的找到第一個(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說明說明TaTaa a1 1a an nTbTbb b1 1b bn n循環(huán)鏈表的合并循環(huán)鏈表的合并a a1 1a an nb b1 1b bn npTaTaTbTb示例示例a a1 1a an nb b1 1b bn npTaTaTbTbLinkList Connect(LinkList Ta,LinkList Tb)/假設(shè)假設(shè)Ta、Tb都是非空的單循

44、環(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-next=p; 示例示例priordatanextdatanexttypedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList2.5.4 2.5.4 雙向鏈表雙向鏈表L(a) (

45、a) 空雙向循環(huán)鏈表空雙向循環(huán)鏈表LABC(b) (b) 雙向循環(huán)鏈表雙向循環(huán)鏈表d-next-prior = d-prior-next = dL-next=Lab.pxs雙向鏈表的插入雙向鏈表的插入1. s-prior=p-prior;雙向鏈表的插入雙向鏈表的插入a ab bx x.1 1p ps s雙向鏈表的插入雙向鏈表的插入1. s-prior=p-prior;2. p-prior-next=s;abx.12ps雙向鏈表的插入雙向鏈表的插入abx.123ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p;雙向鏈表的插入雙向鏈表的插入4.

46、p-prior=s;abx.1234ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p;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;雙向鏈表的插入雙向鏈表的插入ab.pc雙向鏈表的刪除雙向鏈表的刪除ab.1pc1. p-p

47、rior-next=p-next;雙向鏈表的刪除雙向鏈表的刪除雙向鏈表的刪除雙向鏈表的刪除ab.12pc1. p-prior-next=p-next;2. p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) if(!(p=GetElemP_DuL(L,i) return ERROR; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; delete p; return OK;雙向鏈表的刪除雙向鏈表的刪除北京林業(yè)大學(xué)信息學(xué)院2.

48、6 2.6 順序表和鏈表的比較順序表和鏈表的比較存儲結(jié)構(gòu)比較項(xiàng)目順序表鏈表空間存儲空間預(yù)先分配，會導(dǎo)致空間閑置或溢出現(xiàn)象動態(tài)分配，不會出現(xiàn)存儲空間閑置或溢出現(xiàn)象存儲密度不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷，存儲密度等于1需要借助指針來體現(xiàn)元素間的邏輯關(guān)系，存儲密度小于1時(shí)間存取元素隨機(jī)存取，按位置訪問元素的時(shí)間復(fù)雜度為O(1)順序存取，按位置訪問元素時(shí)間復(fù)雜度為O(n)插入、刪除平均移動約表中一半元素，時(shí)間復(fù)雜度為O(n)不需移動元素，確定插入、刪除位置后，時(shí)間復(fù)雜度為O(1)適用情況 表長變化不大，且能事先確定變化的范圍 很少進(jìn)行插入或刪除操作，經(jīng)常按元素位置序號訪問數(shù)據(jù)元素 長度

49、變化較大 頻繁進(jìn)行插入或刪除操作2.7 2.7 線性表的應(yīng)用線性表的應(yīng)用2.7.1 2.7.1 線性表的合并線性表的合并問題描述：問題描述： 假設(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) .依次取出依次取出Lb Lb 中的每個(gè)元素，執(zhí)行以下操作：中的每個(gè)元素，執(zhí)行以下操作：在在LaLa中查找該元素中查找該元素如果找不到，則將其插入如果找不到，則將其插入La的最后的最后【算法步驟算法步驟】v

50、oid union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i+) GetElem(Lb,i,e); if(!LocateElem(La,e) ListInsert(&La,+La_len,e); )()(LBListLengthLAListLengthO【算法描述算法描述】問題描述：問題描述： 已知線性表已知線性表La La 和和LbLb中的數(shù)據(jù)元素按值中的數(shù)據(jù)元素按值非遞減非遞減有有序排列序排列, ,現(xiàn)要求將現(xiàn)要求將LaLa和和LbLb歸并為一個(gè)新的線

51、性表歸并為一個(gè)新的線性表LcLc, ,且且LcLc中的數(shù)據(jù)元素仍按值非遞減有序排列中的數(shù)據(jù)元素仍按值非遞減有序排列. .La=(1 ,7, 8)Lb=(2, 4, 6, 8, 10, 11)Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) 2.7.2 2.7.2 有序表的合并有序表的合并(1) (1) 創(chuàng)建一個(gè)空表創(chuàng)建一個(gè)空表LcLc(2) 依次從依次從 La La 或或 Lb Lb 中中“摘取摘取”元素值較小元素值較小的結(jié)點(diǎn)插入到的結(jié)點(diǎn)插入到 Lc Lc 表的最后，直至其中一個(gè)表表的最后，直至其中一個(gè)表變空為止變空為止(3) (3) 繼續(xù)將繼續(xù)將 La La 或或 Lb L

52、b 其中一個(gè)表的剩余結(jié)點(diǎn)其中一個(gè)表的剩余結(jié)點(diǎn)插入在插入在 Lc Lc 表的最后表的最后【算法步驟算法步驟】有序的順序表合并有序的順序表合并void MergeList_Sq(SqList LA,SqList LB,SqList &LC) pa=LA.elem; pb=LB.elem; /指針指針pa和和pb的初值分別指向兩個(gè)表的第一個(gè)元素的初值分別指向兩個(gè)表的第一個(gè)元素 LC.length=LA.length+LB.length; /新表長度為待合并兩表的長度之和新表長度為待合并兩表的長度之和 LC.elem=new ElemTypeLC.length; /為合并后的新表分配一個(gè)數(shù)組空

53、間為合并后的新表分配一個(gè)數(shù)組空間 pc=LC.elem; /指針指針pc指向新表的第一個(gè)元素指向新表的第一個(gè)元素 pa_last=LA.elem+LA.length-1; /指針指針pa_last指向指向LA表的最后一個(gè)元素表的最后一個(gè)元素 pb_last=LB.elem+LB.length-1; /指針指針pb_last指向指向LB表的最后一個(gè)元素表的最后一個(gè)元素 while(pa=pa_last & pb=pb_last) /兩個(gè)表都非空兩個(gè)表都非空 if(*pa=*pb) *pc+=*pa+; /依次依次“摘取摘取”兩表中值較小的結(jié)點(diǎn)兩表中值較小的結(jié)點(diǎn) else *pc+=*pb

54、+; while(pa=pa_last) *pc+=*pa+; /LB表已到達(dá)表尾表已到達(dá)表尾 while(pbdata data )pc-next = pa;PaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data data )pc-next = pa;pc= pa;1PcLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data data )pc-next = pa;pc= pa;1Pcpa = pa-next;PaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next

55、 = pb;1PcpaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2La(Lcb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2pb =pb-next;pbLa(Lc)12467881011有序鏈表合并有序鏈表合并pc- next=pa?pa:pb; pa(NULL)pbpcLa(Lc)12467881011合并后合并后delete Lb;有序鏈表合并有序鏈表合并void MergeList_L

56、(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La-next; pb=Lb-next; pc=Lc=La; /用用La的頭結(jié)點(diǎn)作為的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) while(pa & pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /插入剩余段插入剩余段 delete Lb; /釋放釋放Lb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) T(n)=S(n)= O(1)()(LBListLengt

57、hLAListLengthO【算法描述算法描述】有序的鏈表合并有序的鏈表合并思考思考1：要求合并后的表無重復(fù)數(shù)據(jù)，如何實(shí)現(xiàn)？：要求合并后的表無重復(fù)數(shù)據(jù)，如何實(shí)現(xiàn)？提示：要單獨(dú)考慮提示：要單獨(dú)考慮pa-data = =pb-data La(Lc)12467881011要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間間, , 不另外占用其它的存儲空間。不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。表中允許有重復(fù)的數(shù)據(jù)。 思考思考2：將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞：將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表，如何實(shí)現(xiàn)？增的有序鏈表，如何實(shí)現(xiàn)？(1)Lc(1

58、)Lc指向指向LaLa(2) 依次從依次從 La La 或或 Lb Lb 中中“摘取摘取”元素值較小元素值較小的結(jié)點(diǎn)插入到的結(jié)點(diǎn)插入到 Lc Lc 表的表的表頭結(jié)點(diǎn)之后表頭結(jié)點(diǎn)之后，直至其，直至其中一個(gè)表變空為止中一個(gè)表變空為止(3) (3) 繼續(xù)將繼續(xù)將 La La 或或 Lb Lb 其中一個(gè)表的剩余結(jié)點(diǎn)其中一個(gè)表的剩余結(jié)點(diǎn)插入在插入在 Lc Lc 表的表的表頭結(jié)點(diǎn)之后表頭結(jié)點(diǎn)之后(4) (4) 釋放釋放 Lb Lb 表的表頭結(jié)點(diǎn)表的表頭結(jié)點(diǎn)【算法步驟算法步驟】2.8 2.8 案例分析與實(shí)現(xiàn)案例分析與實(shí)現(xiàn)指數(shù)（下標(biāo)i）01234系數(shù)pi105-432P(x) = 10 + 5x - 4x2

59、+ 3x3 + 2x4數(shù)組表示數(shù)組表示（每一項(xiàng)的指數(shù)（每一項(xiàng)的指數(shù)i隱含隱含在其系數(shù)在其系數(shù)pi的序號中）的序號中）Rn(x) = Pn(x) + Qm(x)線性表線性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)北京林業(yè)大學(xué)信息學(xué)院下標(biāo)i0123下標(biāo)i012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項(xiàng)式非零項(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ù)組新

60、數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項(xiàng)的每一項(xiàng)指數(shù)相同指數(shù)相同，對應(yīng)系數(shù)相加，若其和不為零，則在，對應(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ù)制到c c中即可中即可A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABl順序存儲結(jié)構(gòu)存在問題順序存儲結(jié)構(gòu)存在問題存儲空間分配不靈活存儲空間分配不靈活運(yùn)算的空間復(fù)雜度高運(yùn)算的空間復(fù)雜度高鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)typedef struct PNode float coef;/系數(shù)系數(shù) int expn;/指數(shù)指數(shù) struct PNode *next;/指針域指針域PNode,*Polynomial; 創(chuàng)建一個(gè)只有頭結(jié)點(diǎn)