《數(shù)據(jù)結(jié)構(gòu)(C++版)》第2章 線性表

1、第第2章章 線性表線性表2.1 線性表的類型定義線性表的類型定義2.1.2 線性表的定義線性表的定義線性表是一種線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素“一個(gè)接一個(gè)地排列”。在一個(gè)線性表中，數(shù)據(jù)元素的類型是相同的，或者說(shuō)線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。線性表是由n（n0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列，通常表示為L(zhǎng)=(a1, a2, ,ai1, ai, ai+1, , an)。其中，L為線性表名稱，ai為組成該線性表的數(shù)據(jù)元素，ai1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i=1, 2, , n1時(shí)，a

2、i有且僅有一個(gè)直接后繼元素；當(dāng)i=2, 3, , n時(shí)，ai有且僅有一個(gè)直接前驅(qū)元素。線性表的長(zhǎng)度就是線性表中元素的個(gè)數(shù)n（n0）。當(dāng)n=0時(shí)，稱為空表。在非空表中，每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素。i稱為數(shù)據(jù)元素ai在線性表中的位序。2.1.2 線性表的線性表的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述線性表的抽象數(shù)據(jù)類型描述見如下ADT。ADT List 數(shù)據(jù)集合： 數(shù)據(jù)關(guān)系： 數(shù)據(jù)操作：Init_List(&L) /初始化線性表輸入：空。返回結(jié)果：構(gòu)造一個(gè)空的線性表L。Destroy_List(&a

3、mp;L) /撤銷線性表輸入：線性表L。返回結(jié)果：撤銷線性表L。線性表的線性表的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型Clear_List(&L) /清空線性表輸入：線性表L。返回結(jié)果：將線性表L重置為空表。List_Empty(&L) /判斷線性表是否為空輸入：線性表L。返回結(jié)果：若線性表L為空表，則返回TRUE，否則返回FALSE。List_Length(&L) /求線性表的長(zhǎng)度輸入：線性表L。返回結(jié)果：線性表L中的數(shù)據(jù)元素個(gè)數(shù)。線性表的線性表的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型Get_Elem(&L，i，&e) /取線性表中第i個(gè)數(shù)據(jù)元素的值輸入：線性表L，1 i Lis

4、t_Length(L)。返回結(jié)果：用e返回線性線L中第i個(gè)數(shù)據(jù)元素的值。Locate_Elem(&L，e，compare( ) /返回給定值在線性表中的位置輸入：線性表L，compare( )是數(shù)據(jù)元素相等判定函數(shù)。返回結(jié)果：線性表L中第1個(gè)與e滿足相等關(guān)系的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。Prev_Elem(&L，cur_e，&pre_e) /返回當(dāng)前元素的前一個(gè)元素值 輸入：線性表L。返回結(jié)果：若cur_e是線性表L中的數(shù)據(jù)元素，且不是第1個(gè)，則pre_e返回它的直接前驅(qū)元素；否則操作失敗，pre_e無(wú)定義。Next_Elem(& L，

5、cur_e，&next_e) /返回當(dāng)前元素的后一個(gè)元素值輸入：線性表L。返回結(jié)果：若cur_e是線性表L中的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的直接后繼元素；否則操作失敗，next_e無(wú)定義。List_Insert(&L，i，e) /在線性表的第i個(gè)位置之前插入數(shù)據(jù)元素e輸入：線性表L，1 i List_Length(L)+1。返回結(jié)果：在線性表L中的第i個(gè)位置之前插入新的數(shù)據(jù)元素e，線性表L的長(zhǎng)度加1。List_Delete(&L，i，&e) /刪除線性表中的第i個(gè)數(shù)據(jù)元素輸入：非空線性表L，1 i List_Length(L)。返回結(jié)果：刪除

6、L中的第i個(gè)數(shù)據(jù)元素，用e返回其值，線性表L的長(zhǎng)度減1。List_Traverse(&L，visit( ) /遍歷線性表輸入：線性表L。返回結(jié)果：依次對(duì)線性表L的每個(gè)數(shù)據(jù)元素調(diào)用visit( )函數(shù)進(jìn)行訪問。一旦visit( )訪問失敗，則操作失敗。ADT List例例21 假設(shè)有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示，即線性表中的數(shù)據(jù)元素為集合中的成員。試編寫一個(gè)算法求一個(gè)新的集合C=AB，即將兩個(gè)集合的并集放在線性表LC中。算法如下：void List_Merge(List LA，List LB，List &LC) int lena， lenb， le

7、nc，i； ElemType e； Init_List(LC)； for (i=1；i=List_Length(LA)；i+) /*將LA的所有元素插入到LC中*/ Get_Elem(LA，i，e)； List_Insert(LC，i，e)； lena=List_Length(LA)；/*求線性表的長(zhǎng)度*/lenb=List_Length(LB)；for (i=1；i=lenb；i+) /*取LB中的第i個(gè)數(shù)據(jù)元素并將其賦給e*/ Get_Elem(LB，i，e)；/*LA中不存在和e相同者，則插入到LC中*/if (!Locate_Elem(LA，e，compare() List_Inser

8、t(LC，+lena，e)；時(shí)間復(fù)雜度為：O(List_Length(LA)*List_Length(LB)2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1 順序表順序表線性表的順序存儲(chǔ)：是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素。設(shè)a1的存儲(chǔ)地址為L(zhǎng)oc(a1)，每個(gè)數(shù)據(jù)元素占用d個(gè)字節(jié)，則第i個(gè)數(shù)據(jù)元素的地址為L(zhǎng)oc(ai)=Loc(ai)+(i1)d，1in，如圖2.1所示。 a1 1 Loc (a1) 0 a a2 2 Loc (a1)+sizeof(ElemType) 1 線性表存儲(chǔ)空間線性表存儲(chǔ)空間 存儲(chǔ)地址存儲(chǔ)地址 下標(biāo)位置下標(biāo)位置 a ai i Loc (

9、a1)+(i-1)*sizeof(ElemType) i-1 a an n Loc (a1)+(n-1)*sizeof(ElemType) n - 1 Loc (a1)+(MaxSize-1)*sizeof(ElemType) MaxSize -1 圖2.1 線性表的順序存儲(chǔ) Loc(a1)通常稱作線性表的起始位置或基地址。只要確定了存儲(chǔ)線性表的起始位置，線性表中的任意一個(gè)數(shù)據(jù)元素都可以隨機(jī)存取。因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。線性表的這種機(jī)內(nèi)表示稱為線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映射。通常，稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。其特點(diǎn)是以數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性

10、表中數(shù)據(jù)元素之間的邏輯關(guān)系。例22 設(shè)一維數(shù)組A的下標(biāo)的取值范圍是0 - - 99，每個(gè)數(shù)組元素用相鄰的5個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素A0的第一個(gè)字節(jié)的地址是100，則A5的第一個(gè)字節(jié)的地址是 。解：第i個(gè)元素的存儲(chǔ)地址的計(jì)算公式為L(zhǎng)oc(ai) = Loc(a1) + (i1) d，1 i n。因此，Loc(A5)=100+ (50)5=125。數(shù)組A的第1個(gè)元素的下標(biāo)是0，即A0。線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的描述（了解）線性表的長(zhǎng)度可變，而且最大存儲(chǔ)空間隨問題的不同而不同，因此需要?jiǎng)討B(tài)地分配線性表的空間。在C+語(yǔ)言中，可用動(dòng)態(tài)分配的一維數(shù)組來(lái)表示，描述見如下程序：/文件L

11、ine_ListSqu.h，類Line_ListSqu#include#includetemplateclass Line_ListSqu public：Line_ListSqu(int MaxListSize=10)；/構(gòu)造函數(shù)Line_ListSqu( ) if (element) delete element； /析構(gòu)函數(shù)bool IsEmpty( ) const return length=0； int Length( ) const return length； bool Find(int i，T& x) const；/將第i個(gè)元素的值用x返回Line_List& D

12、elete(int i，T& x)；/刪除第i個(gè)元素的值，并且用x返回int Search(const T& x) const；/返回x中元素所處的位置Line_List& Insert(int i，const T& x)；/在第i個(gè)元素前面插入x void Output(ostream& out) const；protected： long length； long MaxSize； T *elem；/一維動(dòng)態(tài)數(shù)組，其元素類型為可變類型T2.2.2 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)初始化：初始化：順序表的初始化即構(gòu)造一個(gè)空表，操作比

13、較簡(jiǎn)單，代碼（算法21）如下所示：Template Line_ListSqu : Line_ListSqu(int MaxListSize) /線性表的構(gòu)造函數(shù) MaxSize=MaxListSize； elem=new TMaxSize； length=0；順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)按序號(hào)查找按序號(hào)查找：順序表是一種隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)，因此很容易在順序表中實(shí)現(xiàn)按序號(hào)查找元素。代碼（算法22）如下所示： template bool Line_ListSqu:Find(int i，T& x) const /在線性表中查找第i個(gè)元素并用x返回 if (ilengt

14、h) return false； x=elemi1； return true； 按序號(hào)查找元素的主要目的是返回待查元素，其時(shí)間復(fù)雜度為O(1) 。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)按值查找按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素，具體實(shí)現(xiàn)代碼（算法23）如下： template int Line_ListSqu: Search(const T& x) const int i = 0； if (IsEmpty( ) return 0；/線性表為空時(shí)返回0 while(ilength &!(x= =elemi) i+； if (elemi= =x) re

15、turn +i； else return 0； 上述算法的主要操作是比較，平均比較次數(shù)為(n+1)/2，算法的時(shí)間復(fù)雜度為O(n)。 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)輸出函數(shù)輸出函數(shù)的實(shí)現(xiàn)代碼（算法24）如下：Template void Line_ListSqu：Output(ostream& out)const for(int i=0；ilength；i+) outelemi“”；順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)為了在所有情形下都能引發(fā)一個(gè)異常，本節(jié)定義一個(gè)異常類NoMem，非法操作將會(huì)簡(jiǎn)單地引發(fā)一個(gè)類型為NoMem的異常。 #includec

16、lass NoMem public： NoMem( ) cout“memory is not enough”；順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)如果表中不存在第m個(gè)元素，則應(yīng)出現(xiàn)一個(gè)越界異常，定義為OutOfBounds，每當(dāng)正在執(zhí)行的函數(shù)中的參數(shù)超出所期望的范圍時(shí)，就會(huì)引發(fā)這種類型的異常。class OutOfBounds public： OutOfBounds( ) cout”out of bounds”； ；順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)線性表的插入操作線性表的插入操作是指在線性表的第m1個(gè)數(shù)據(jù)元素和第m個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素x，其結(jié)果

17、是使長(zhǎng)度為n的線性表(a1, a2 , am1, am, an)變成長(zhǎng)度為n+1的線性表(a1, a2 , am1, x, am, an)，并且數(shù)據(jù)元素am1和am之間的邏輯關(guān)系發(fā)生了變化。 實(shí)現(xiàn)步驟如下：(1)合法性判斷：插入位置i是否合法?表是否已滿?(2)將第i至第n位的元素向后移動(dòng)一個(gè)位置；(3)將要插入的元素寫到第i個(gè)數(shù)據(jù)元素的位置；(4)表長(zhǎng)加1。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)具體算法（算法25）描述如下：templateLine_ListSqu& Line_ListSqu:Insert(int i，T& x) if (ilength+1) t

18、hrow OutOfBounds( )； if (length=MaxSize) throw NoMem( )； for(int j=length1；j=i1；j ) elemj+1=elemj； elemi1=x； length+； return *this；l 順序表上的插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上，在第m個(gè)位置上插入x，從am到an都要向下移動(dòng)一個(gè)位置，共需移動(dòng)n m+1個(gè)元素，而m的取值范圍為：1 m n+1，即有n+1個(gè)位置可以插入。在順序表上做插入操作平均需要移動(dòng)表中的一半數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n) 。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)線性表的刪除操作

19、線性表的刪除操作是使長(zhǎng)度為n的線性表(a1, a2, am1, am,an)變?yōu)殚L(zhǎng)度為n1的線性表(a1, a2, am1, am+1,an)，并且數(shù)據(jù)元素am1、am和am+1之間的邏輯關(guān)系也會(huì)發(fā)生變化，需要把第m+1n個(gè)元素（共nm個(gè)元素）依次向前移動(dòng)一個(gè)位置來(lái)反映這種變化。具體實(shí)現(xiàn)步驟如下：判斷刪除位置i是否合法，合法則將該位置元素放入x中，否則拋出異常；將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)具體算法（算法26）描述如下：template Line_ListSqu& Line_ListSqu：Delete(int

20、i，T& x) if (Find(i，x) for(int j=i；jlength；j+) elemj1=elemj； length ； return *thiselse throw OutOfBounds( )； 與插入操作相同，刪除操作的時(shí)間也主要消耗在移動(dòng)表中的元素上，刪除第m個(gè)元素時(shí)，其后面的元素am+1到an都要向前移動(dòng)一個(gè)位置，共移動(dòng)了nm個(gè)元素，該算法的時(shí)間復(fù)雜度也為O(n)。 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)應(yīng)用舉例應(yīng)用舉例例23 應(yīng)用舉例：已知一個(gè)線性表中的元素按元素值非遞減有序排列，試設(shè)計(jì)算法刪除表中值相同的多余元素。 解：算法一： void purgelist(Line_

21、ListSqu A) int i=0；/i是掃描指示器，賦初值0 while(i=A.length2) if (A.elemi!=A.elemi+1) i+；/繼續(xù)往后掃描 else for(int j=i+2；j=A.length1；j+) A.elemj1=A.elemj；/刪除重復(fù)元素 A.length； /修改表長(zhǎng) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)應(yīng)用舉例應(yīng)用舉例算法二： void purgelist(Line_ListSqu A) int j=0，i=1； while(i=A.length1) if (A.elemi!=A.elemj) /將元素移至正確的位置上 A.elemj+1=A.el

22、emi；j+； i+；/繼續(xù)往后掃描 A.length=j+1；/修改表長(zhǎng) 算法一的時(shí)間復(fù)雜度為O(n2)，算法二的時(shí)間復(fù)雜度為O(n)。由此可見，算法一的時(shí)間效率比算法二的時(shí)間效率要低。2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1 線性鏈表線性鏈表線性鏈表的定義 鏈表是通過一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素的，對(duì)每個(gè)數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素自身的信息ai之外，還需要和ai一起存放其后繼元素ai+1所在的存儲(chǔ)單元的地址，這兩部分信息組成一個(gè)“結(jié)點(diǎn)”。存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼元素地址的稱為指針域，指針域中存儲(chǔ)的信息稱為指針或鏈。結(jié)點(diǎn)結(jié)構(gòu)如書上圖2.2所

23、示。n個(gè)結(jié)點(diǎn)ai (1 i n)鏈接成一個(gè)鏈表，即為線性表（a1，a2，an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于此鏈表中的每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域，故又稱線性鏈表或單鏈表。例如， 圖2.3所示為學(xué)生信息線性表（張躍，朱炳，李雪，張方，趙欣，宋亮，董琴，李輝）的單鏈表存儲(chǔ)結(jié)構(gòu)。整個(gè)鏈表的存取由頭指針H開始進(jìn)行，它指向鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針為“空”（NULL）。 存儲(chǔ)地址數(shù)據(jù)域指針域3張方169朱炳6016趙欣4826董琴4233張躍942李輝NULL48宋亮2660李雪333頭指針H圖2.3 學(xué)生信息線性表通常我們把鏈表畫成用箭頭相鏈接的結(jié)點(diǎn)序列，結(jié)點(diǎn)之間的箭頭表示鏈域中的指

24、針。圖2.3的線性表可畫成如圖2.4所示的形式。為了簡(jiǎn)化對(duì)鏈表的操作，人們經(jīng)常在鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)。這樣可以免去對(duì)鏈表第一個(gè)結(jié)點(diǎn)的特殊處理。將圖2.4加上頭結(jié)點(diǎn)如圖2.5所示。張躍 朱炳 李雪 張方 趙欣 宋亮 董琴 李輝 Header 8 張躍 朱炳 李雪 趙欣 宋亮 董琴 李輝 圖2.5 帶頭結(jié)點(diǎn)的單鏈表張方 圖2.4 線性表的指針表示線性表的單鏈表存儲(chǔ)結(jié)構(gòu)的類定義單鏈表的類定義通常使用兩個(gè)類：一個(gè)結(jié)點(diǎn)類Line_ListNode和一個(gè)單向鏈表類Line_ListLink。一個(gè)鏈表包含了0、一個(gè)或多個(gè)結(jié)點(diǎn)，一個(gè)類型為L(zhǎng)ine_ListLink的對(duì)象包含0、一個(gè)或多個(gè)類型為L(zhǎng)

25、ine_ListNode的對(duì)象。Line_ListLink定義為L(zhǎng)ine_ListNode的一個(gè)友類，所以Line_List Link可訪問Line_ListNode的所有成員，也包括私有成員。 以下給出鏈表結(jié)點(diǎn)類和單鏈表類的類定義描述：#include template class Line_ListLink；/Line_ListNode類的友元 template class Line_ListNode friend class Line_ListLink； private： Line_ListNode *link； T data； public： Line_ListNode(Line_Li

26、stNode *ptrlink=NULL) link=ptrlink； Line_ListNode(const T& item，Line_ListNode *ptrlink=NULL) data=item；link=ptrlink； Line_ListNode(void) /析構(gòu)函數(shù) templateclass Line_ListLinkpublic：Line_ListLink( ) first=0；Line_ListLink( )；bool IsEmpty( ) const return first= =0；int Length( ) const；bool Find(int i，T&

27、amp; x) const；/將第i個(gè)結(jié)點(diǎn)的值用x返回Line_ListLink& Delete(int i，T& x)；/刪除第i個(gè)結(jié)點(diǎn)的值，并用x返回int Search(const T& x) const；Line_ListLink& Insert(int i，const T& x)；/在第i個(gè)結(jié)點(diǎn)的前面插入x void Output(ostream& out) const；Line_ListNode *GetFirst( ) return first；private： Line_ListNode *first；2.3.2 線性表線性表基本

28、操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)求表長(zhǎng)求表長(zhǎng)運(yùn)算從頭指針開始，將其賦值給指針變量cur。當(dāng)cur不為NULL時(shí)，計(jì)數(shù)器變量length的值加1，逐步后移cur指針，每后移一個(gè)結(jié)點(diǎn)，長(zhǎng)度值加1，直到cur指向NULL結(jié)束，返回length值即為表的長(zhǎng)度值。代碼（算法27）如下所示：templateint Line_ListLink：length( ) const Line_ListNode *cur=first； int length=0； while(cur) length+； cur=curlink； return length；查找第查找第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，也是從頭指針開始，依次后移到第i個(gè)結(jié)點(diǎn)，代

29、碼（算法28）如下所示：templatebool Line_ListLink：Find(int i，T& x) const if (i1) return false； Line_ListNode *cur=first； int j=1； while(jlink；j+ if (cur) x=curdata；return true； else return false； 查找給定值查找給定值所在所在的結(jié)點(diǎn)的序號(hào)的結(jié)點(diǎn)的序號(hào)，即定位操作。具體代碼（算法29）如下： templateint Line_ListLink：Search(const T& x) const Line_List

30、Node *cur=first； int j=1； while(curdata!=x & cur!=NULL) cur=curlink；j+ if (cur) return j； else return 0； 上述算法的主要操作是比較并后移指針，兩個(gè)查找算法的平均比較次數(shù)為(n+1)/2，求表長(zhǎng)算法的移動(dòng)次數(shù)為n，故3個(gè)算法的時(shí)間復(fù)雜度均為O(n)。輸出函數(shù)的實(shí)現(xiàn)代碼如下：templatevoid Line_ListLink：Output(ostream& out)const Line_ListNode *cur； for(cur=first；cur；cur=curlink)

31、outdatanext=pnext；pnext=s；abpbapxs（a)插入前（b)插入后圖2.6 在單鏈表中插入結(jié)點(diǎn)snext=pnext；pnext=s； 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)之前的位置上。先在單鏈表中找到第i1個(gè)結(jié)點(diǎn)，再在其后插入新結(jié)點(diǎn)。具體算法代碼（算法210）如下所示： templateLine_ListLink& Line_ListLink：Insert(int i，const T& x) if (i0) throw OutOfBounds( )；/插入位置不合法 Line_ListNode *p=first； int j=1； wh

32、ile(p & jlink；+j； /查找第i1個(gè)結(jié)點(diǎn) if (i0 & !p) throw OutOfBounds( )；/沒有第i1個(gè)結(jié)點(diǎn) Line_ListNode *s=new Line_ListNode； sdata=x； if (i1) slink=plink；plink=s； else /插入結(jié)點(diǎn)為第一個(gè)元素 slink=first；first=s； return *this；在線性表中刪除元素在線性表中刪除元素b時(shí)時(shí)，為了實(shí)現(xiàn)3個(gè)元素a、b和c之間邏輯關(guān)系的變化，僅需修改結(jié)點(diǎn)a中的指針域即可。假設(shè)p為其單鏈表存儲(chǔ)結(jié)構(gòu)中指向結(jié)點(diǎn)a的指針，刪除過程如圖2.7所示。指

33、針修改核心語(yǔ)句描述為：pnext=pnextnext；等價(jià)語(yǔ)句為：q = pnext；pnext = qnext；abpcabpc圖2.7 在單鏈表中刪除結(jié)點(diǎn)(a)刪除前(b)刪除后指針修改核心語(yǔ)句描述為：pnext=pnextnext；等價(jià)語(yǔ)句為：q = pnext；pnext = qnext；刪除運(yùn)算是將單鏈表的第刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i1個(gè)結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼（算法211）如下所示：templateLine_ListLink& Line_ListLink：Delete(int i，T& x) if (i1 | !f

34、irst) throw OutOfBounds( )；/刪除位置不合法 Line_ListNode *p=first； if (i=1) first=firstlink； else Line_ListNode *q=first； int j=1； /查找第i個(gè)結(jié)點(diǎn) while(q & jlink；+j； if (!q | !qlink) throw OutOfBounds( )；/沒有第i個(gè)結(jié)點(diǎn) p=qlink；qlink=plink； x=pdata；delete p； return *this；2.3.3 靜態(tài)鏈表靜態(tài)鏈表為了便于在不設(shè)“指針”類型的高級(jí)程序設(shè)計(jì)語(yǔ)言中使用鏈表結(jié)構(gòu)，

35、有時(shí)也可借用一維數(shù)組來(lái)描述線性鏈表。數(shù)組中的一個(gè)分量表示一個(gè)結(jié)點(diǎn)，同時(shí)使用游標(biāo)（指示器cur即為偽指針）代替指針以指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。數(shù)組中的第0個(gè)分量可以看成頭結(jié)點(diǎn)，其指針域指示鏈表的第一個(gè)結(jié)點(diǎn)。為了和“指針”類型描述的線性鏈表相區(qū)別，我們稱這種用數(shù)組描述的鏈表為靜態(tài)鏈表。見教材P40圖2.8靜態(tài)鏈表2.3.4 循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域不再為空，而是指向表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中的任意一個(gè)結(jié)點(diǎn)出發(fā)均可找到鏈表中的其他結(jié)點(diǎn)。如圖2.8所示為單循環(huán)鏈表。循環(huán)鏈表的操作和線性鏈表基本一致，差別在于，判別鏈表中最后

36、一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。Headera1anHeader圖2.8 單循環(huán)鏈表(a) 非空表(b) 空表2.3.5 雙向鏈表雙向鏈表在需要頻繁地同時(shí)訪問前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)時(shí)，可采用另一種鏈表結(jié)構(gòu)，即雙向鏈表。所謂雙向鏈表，就是每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼結(jié)點(diǎn)，另一個(gè)指針域指向直接前驅(qū)結(jié)點(diǎn)。圖2.9給出了雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)。指向前驅(qū)結(jié)點(diǎn)的指針域數(shù)據(jù)域指向后繼結(jié)點(diǎn)的指針域plinkdatanlink圖2.9 給出了雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)雙向鏈表的類定義：雙向鏈表的類定義通常也使用兩個(gè)類：一個(gè)結(jié)點(diǎn)類DLine_ListNode和一個(gè)雙向鏈表類DLine_

37、ListLink。以下給出雙向鏈表結(jié)點(diǎn)類和雙向鏈表類的類定義描述：#include template class DLine_ListLink；/作為DLine_ListNode類的友元，需要提前聲明 template class DLine_ListNode friend class DLine_ListLink； private： DLine_ListNode *plink，*nlink； T data；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) public： DLine_ListNode(DLine_ListNode*prior=NULL， DLine_ListNode*next=NUL

38、L) plink=prior；nlink=next；DLine_ListNode(const T& item，DLine_ListNode*prior=NULL，DLine_ListNode *next=NULL) data=item；plink=prior；nlink=next； DLine_ListNode(void) /析構(gòu)函數(shù) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)templateclass DLine_ListLinkpublic：DLine_ListLink( ) first=last=0；DLine_ListLink( )； int Length( ) const； b

39、ool Find(int i，T& x) const；/將第i個(gè)結(jié)點(diǎn)的值用x返回DLine_ListLink& Delete(int i，T& x)；/刪除第i個(gè)結(jié)點(diǎn)的值，用x返回int Search(const T& x) const；/在第i個(gè)結(jié)點(diǎn)的前面插入x DLine_ListLink& Insert(int i，const T& x)；void Output(ostream& out) const； private： DLine_ListNode *first，*last；在雙向鏈表中，結(jié)點(diǎn)的插入和刪除操作涉及前后結(jié)點(diǎn)的兩個(gè)指針

40、域的變化。圖2.10和圖2.11分別顯示了插入和刪除結(jié)點(diǎn)時(shí)指針的修改情況，它們的算法分別如算法2-12和2-13所示，兩者的時(shí)間復(fù)雜度均為O(n) 。xab1243pqabcp圖2.10 插入操作圖2.11 刪除操作 設(shè)p指向雙向鏈表中的第i個(gè)結(jié)點(diǎn)，q指向待插入的值為x的結(jié)點(diǎn)，則插入的主要操作如下： qplink=pplink； pplinknlink=q； qnlink=p； pplink=q；設(shè)p指向雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則刪除操作的主要步驟如下：pplinknlink=pnlink；pnlinkplink=pplink；delete p；插入算法插入算法(算法2-12)： templa

41、teDLine_ListLink& DLine_ListLink：Insert(int i，const T& x) if (i0) throw OutOfBounds( )；/插入位置不合法 DLine_ListNode *p=first； int j=1； while(p & jnlink；+j； /查找第i個(gè)結(jié)點(diǎn) if (i0 & !p) throw OutOfBounds( )；/沒有第i個(gè)結(jié)點(diǎn) DLine_ListNode *q=new DLine_ListNode； qdata=x； if (i1) qplink=pplink；pplinknlink=

42、q； qnlink=p；pplink=q； else /插入結(jié)點(diǎn)為第一個(gè)元素 qnlink=q；qplink=q；first=q； return *this；刪除算法刪除算法(算法2-13)：templateDLine_ListLink& DLine_ListLink：Delete(int i，T& x) if (i1 | !first) throw OutOfBounds( )；/刪除位置不合法 DLine_ListNode *p； if (!p=Get_Elem(k) return false； x=pdata； pplinknlink=pnlink； pnlinkplin

43、k=pplink； delete p； return *this； 2.4 線性表的應(yīng)用線性表的應(yīng)用例例25 試比較兩個(gè)線性表的大小。兩個(gè)線性表的比較依據(jù)下列方法：設(shè)A、B是兩個(gè)線性表，表長(zhǎng)分別為m和n。Aq和Bq分別為 A 和 B 中除去最大共同前綴后的子表。例如，A=(x，y，x，z，x，z)，B=(x，y，x，z，y，x，x，z)，兩個(gè)表的最大共同前綴為 (x，y，x，z) 。則Aq=(x，z)，Bq=(y，x，x，z)。若Aq=Bq=空表，則A=B；若Aq=空表且Bq空表，或兩者均不空且Aq的首元素小于Bq的首元素，則AB。算法思路：首先找出A、B的最大共同前綴；然后求出Aq和Bq，之

44、后再按比較規(guī)則進(jìn)行比較，AB 則返回1；A=B則返回0；AB則返回1。選用順序存儲(chǔ)結(jié)構(gòu)，具體算法如下：templateint compare(Line_ListSqu A，Line_ListSqu B，int m，int n) Line_ListSqu Aq，Bq； int i=0，j=0，ml=0，nl=0； while (A.elemi= =B.elemi) i+； /找最大共同前綴 for (j=i；jm；j+) Aq.elemji=A.elemj；ml+； /求Aq，ml為Aq的長(zhǎng)度 for (j=i；j0 | m10 & n10 & Aq.elem0Bq.elem0)

45、 return 1； else return 1；例26 已知單鏈表H為一個(gè)用帶頭結(jié)點(diǎn)的鏈表表示的線性表，寫一算法將其倒置。算法描述如下：templatevoid Line_ListLink：Reverse ( ) Line_ListNode *p，*head=new Line_ListNode( )； while(first!=NULL) p=first；first=firstlink； plink=headlink；headlink=p； first=headlink； delete head；例題2.7 一元多項(xiàng)式相加/多項(xiàng)式類定義class Node public： float ef；int exp；class Polynomial public： Polynomial(Line_ListLink *list