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

1、1第二章第二章 線性表線性表22.1 線性表的類型定義線性表的類型定義2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)2.4 線性表的其它存儲(chǔ)方法線性表的其它存儲(chǔ)方法2.5 線性表應(yīng)用舉例線性表應(yīng)用舉例本章目錄本章目錄32.1 線性表的類型定義線性表的類型定義2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)2.4 線性表的其它存儲(chǔ)方法線性表的其它存儲(chǔ)方法2.5 線性表應(yīng)用舉例線性表應(yīng)用舉例本章目錄本章目錄42.1 線性表的類型定義線性表的類型定義5線性

2、表的定義線性表的定義其中，其中，a ai i（11i in n）稱為數(shù)據(jù)元素；）稱為數(shù)據(jù)元素；下角標(biāo)下角標(biāo) i i 表示該元素在線性表中的位置或序號(hào)表示該元素在線性表中的位置或序號(hào) 。6線性表的特征線性表的特征7線性表舉例線性表舉例8 8線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義9 9ADT ListADT List1010ADT ListADT List1111ADT ListADT List1212ADT ListADT List13ADT ListADT List14ADT ListADT List15關(guān)于基本操作集關(guān)于基本操作集162.2 2.2 線性表的順序存儲(chǔ)及其實(shí)現(xiàn)線性表的

3、順序存儲(chǔ)及其實(shí)現(xiàn)1717 a1 a2 ai-1 ai an線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)例：例：（34, 23, 67, 43）34236743 418 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長度長度Loc(ai)=Loc(a1) + (i - -1)l隨機(jī)存取隨機(jī)存?。涸谠贠(1)時(shí)間內(nèi)存取數(shù)據(jù)元素時(shí)間內(nèi)存取數(shù)據(jù)元素lLoc(ai)Loc(a1)元素位置元素位置19順序表順序表一維數(shù)組一維數(shù)組連續(xù)內(nèi)存申請(qǐng)連續(xù)內(nèi)存申請(qǐng)2020順序表類順序表類SqListSqList的定義的定義/模板類模板類2121SqListSqList的定義的定義22構(gòu)造函數(shù)構(gòu)造函

4、數(shù)23析構(gòu)函數(shù)析構(gòu)函數(shù)24模板類示例模板類示例25順序表初始化順序表初始化2626算法算法2.1 2.1 順序表初始化順序表初始化27異常處理異常處理2828算法算法2.2 2.2 銷毀順序表銷毀順序表2929線性表操作線性表操作 ListInsert(&L, i, e)ListInsert(&L, i, e)的實(shí)現(xiàn)：的實(shí)現(xiàn)：首先分析首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？算法算法2. 3 2. 3 順序表插入順序表插入30 (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an

5、)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加順序表元素插入順序表元素插入31算法算法2. 3 2. 3 順序表插入操作步驟順序表插入操作步驟 32順序表插入操作步驟順序表插入操作步驟step 1：如果表滿，無法插入 if ( length=listsize )if ( length=listsize ) throw throw 上溢上溢 ；step 2：如果插入位置i不合理，無法插入 if ( ilength+1 ) if ( ilength+1 ) throw throw “插入位置異常插入位置異常 ；step 3：將最后一個(gè)元素an至第i個(gè)元素ai，

6、共n-i+1 個(gè)元素，依次后移一個(gè)元素位置 for ( j=lengthfor ( j=length；j=ij=i；j-)j-) elemj=elemj-1 elemj=elemj-1； step 4：將元素值e填入位置i處 elemi-1=e elemi-1=e；step 5：表長增1+L.length;3333 順序表插入的類順序表插入的類C+C+語言描述語言描述 if ( length=listsize ) throw 上溢上溢； if ( ilength+1 ) throw “插入位置異常插入位置異常； for ( j=length；j=i；j-) /an至至ai依次后移依次后移 el

7、emj=elemj-1； elemi-1=e； length+； 34算法算法2. 3 2. 3 順序表插入順序表插入11)1(niiisinpE11) 1(11niisinnE2n不失一般性，假定在線性的任何位置上插入元素的不失一般性，假定在線性的任何位置上插入元素的概率是一樣的，因?yàn)楣灿懈怕适且粯拥?，因?yàn)楣灿衝+1n+1個(gè)可能插入的位個(gè)可能插入的位置置,p,pi i=1/(n+1)=1/(n+1)，因此，因此，35 (a1, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an) ai+1an, 表的長度減少a1 a2 ai-1 ai ai

8、+1 ana1 a2 ai-1 算法算法2.4 2.4 順序表元素刪除操作順序表元素刪除操作36順序表刪除元素操作步驟順序表刪除元素操作步驟37算法算法2.42.43838niidlinqE1)(nidlinnE1)(121n 在順序表中刪除某個(gè)位置元素的時(shí)間主要耗費(fèi)在在順序表中刪除某個(gè)位置元素的時(shí)間主要耗費(fèi)在移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于刪除位置。移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于刪除位置。假設(shè)假設(shè)qi是刪除第是刪除第i個(gè)元素的概率，則在長度為個(gè)元素的概率，則在長度為n的線的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值(平平均次數(shù)均次數(shù))為：為：

9、 不失一般性，假定在線性的任何位置上刪除元素不失一般性，假定在線性的任何位置上刪除元素的概率是一樣的，因?yàn)楣灿械母怕适且粯拥?，因?yàn)楣灿衝個(gè)可能刪除的位置，即：個(gè)可能刪除的位置，即： qi=1/n，因此，因此，算法算法2.4 2.4 ：刪除順序表中元素算法分析刪除順序表中元素算法分析3939templateint SqList：Locate (T e)/在順序表中查找值為在順序表中查找值為e的元素的元素 for(i=0；ilength；i+)if (elemi = = e) /表中元素依次與查找值表中元素依次與查找值e比較比較 return i+1；/找到，返回該元素在順序表中找到，返回該元素在

10、順序表中的序號(hào)的序號(hào)return 0；/未找到，返回未找到，返回0算法算法2.5 2.5 ：順序表按值查找類語言描述順序表按值查找類語言描述算法分析：算法分析：按值查找算法的平均時(shí)間復(fù)雜度為按值查找算法的平均時(shí)間復(fù)雜度為O(n)。402.3 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)及其實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)及其實(shí)現(xiàn)4141線性表的鏈?zhǔn)酱鎯?chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)4242 1、結(jié)點(diǎn)：結(jié)點(diǎn)：每個(gè)數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)指示其直接后繼或直接前驅(qū)的信信息之外，還需存儲(chǔ)指示其直接后繼或直接前驅(qū)的信息，用來表示息，用來表示ai與其后繼數(shù)據(jù)元素與其后繼數(shù)據(jù)元素ai+1或前

11、驅(qū)元素或前驅(qū)元素ai-1的邏輯關(guān)系。這兩部分信息組成了一個(gè)數(shù)據(jù)元素的邏輯關(guān)系。這兩部分信息組成了一個(gè)數(shù)據(jù)元素ai的的存儲(chǔ)映射，稱為結(jié)點(diǎn)存儲(chǔ)映射，稱為結(jié)點(diǎn)(Node)。 數(shù)據(jù)域數(shù)據(jù)域 指針域指針域 2、指針域：指針域：存儲(chǔ)后繼或前驅(qū)邏輯關(guān)系的部分存儲(chǔ)后繼或前驅(qū)邏輯關(guān)系的部分 3、線性鏈表線性鏈表 ：具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表 4、單鏈表單鏈表 ：在線性鏈表結(jié)點(diǎn)中只包含一個(gè)指針域在線性鏈表結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表的鏈表 Data next線性表的鏈?zhǔn)酱鎯?chǔ)有關(guān)概念線性表的鏈?zhǔn)酱鎯?chǔ)有關(guān)概念4343 線性鏈表由一系列稱為表的結(jié)點(diǎn)的對(duì)象組成。線性鏈表由一系列稱為表的結(jié)點(diǎn)的對(duì)象組成

12、。采用結(jié)構(gòu)類型描述結(jié)點(diǎn)。采用結(jié)構(gòu)類型描述結(jié)點(diǎn)。templatestruct Node T data； Node *next；單鏈表的實(shí)現(xiàn)：結(jié)點(diǎn)定義單鏈表的實(shí)現(xiàn)：結(jié)點(diǎn)定義Data next數(shù)據(jù)域數(shù)據(jù)域 指針域指針域4444單鏈表類的單鏈表類的C+語言描述如下：語言描述如下：template class LinkListprivate：Node *Head；public：LinkList() ；/構(gòu)造函數(shù)，構(gòu)造函數(shù)， 創(chuàng)建空鏈表創(chuàng)建空鏈表LinkList()；/析構(gòu)函數(shù)，刪除表空間析構(gòu)函數(shù)，刪除表空間void CreateList(int n)；/創(chuàng)建具有創(chuàng)建具有n 個(gè)元素的線性鏈表個(gè)元素的線性鏈

13、表單鏈表類的單鏈表類的C+C+語言描述語言描述 45續(xù)續(xù)46基本操作實(shí)現(xiàn)舉例與分析基本操作實(shí)現(xiàn)舉例與分析4747算法算法2.6 2.6 初始化一個(gè)單鏈表初始化一個(gè)單鏈表4848templateLinkList：LinkList() /析構(gòu)函數(shù)，刪除表空間析構(gòu)函數(shù)，刪除表空間while(Head)p=Head；Head=Head-next； delete p；Head=NULL；算法算法2.7 2.7 銷毀一個(gè)單鏈表銷毀一個(gè)單鏈表4949templatetemplateT LinkListT LinkList：GetElem(int i)GetElem(int i) / /獲取第獲取第i i個(gè)元

14、素的值個(gè)元素的值 p=Head-next p=Head-next；/工作指針，從首元結(jié)點(diǎn)開工作指針，從首元結(jié)點(diǎn)開始始, , /也可以從頭結(jié)點(diǎn)開始也可以從頭結(jié)點(diǎn)開始 j=1 j=1； /計(jì)數(shù)器，初值為計(jì)數(shù)器，初值為1 1。如果工作指針。如果工作指針從從 /頭結(jié)點(diǎn)開始，頭結(jié)點(diǎn)開始，j j初值為初值為0 0 算法算法2.8 2.8 單鏈表按位查找類單鏈表按位查找類50續(xù)續(xù)51ai-1 eaiai-1算法算法2.9 2.9 單鏈表插入元素單鏈表插入元素在單鏈表中的實(shí)現(xiàn)：在單鏈表中的實(shí)現(xiàn)： 有序?qū)τ行驅(qū)?改變?yōu)楦淖優(yōu)?和和52Node *s；s=new Node；s-data=e；s-next=p-ne

15、xt； p-next=s；/ 結(jié)點(diǎn)結(jié)點(diǎn)S鏈接到鏈接到p結(jié)點(diǎn)之后結(jié)點(diǎn)之后 eai-1aiai-1sp算法算法2.9 2.9 單鏈表插入元素單鏈表插入元素53算法算法2.9 2.9 單鏈表插入元素操作步驟單鏈表插入元素操作步驟54算法算法2.9 2.9 單鏈表插入元素類單鏈表插入元素類55續(xù)續(xù)56ai-1aiai+1ai-1算法算法2.10 2.10 單鏈表刪除元素單鏈表刪除元素在鏈表中的實(shí)現(xiàn)在鏈表中的實(shí)現(xiàn): :有序?qū)τ行驅(qū) 和和 a 改變?yōu)楦淖優(yōu)?a 57ai-1aiai+1ai-1q = p-next; p-next = q-next; x = q-data; delete q ;pq 單鏈

16、表的刪除操作是將第單鏈表的刪除操作是將第i i個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)從個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)從單鏈表中摘除，需在斷開鏈之前暫存刪除結(jié)點(diǎn)位置單鏈表中摘除，需在斷開鏈之前暫存刪除結(jié)點(diǎn)位置q q，并將工作指針并將工作指針p p定位到定位到q q的前驅(qū)，進(jìn)行下列操作：的前驅(qū)，進(jìn)行下列操作：算法算法2.10 2.10 單鏈表刪除元素單鏈表刪除元素58算法算法2.10 2.10 單鏈表刪除元素單鏈表刪除元素59 算法算法2.10 2.10 單鏈表刪除元素單鏈表刪除元素60 續(xù)續(xù)61方法一：方法一： 頭插法頭插法 頭插法指每次將新申請(qǐng)的結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面。頭插法指每次將新申請(qǐng)的結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面。算法算法2.11

17、創(chuàng)建一個(gè)單鏈表創(chuàng)建一個(gè)單鏈表62類類C+C+語言描述：語言描述：templatevoid LinkList：CreateList(int n)/頭插法頭插法(逆位序逆位序)創(chuàng)建具有創(chuàng)建具有n個(gè)元素的線性表個(gè)元素的線性表for(int i=1；i=n；i+) s=new Node；/新建元素結(jié)點(diǎn)新建元素結(jié)點(diǎn) cins-data；/輸入新建數(shù)據(jù)元素值輸入新建數(shù)據(jù)元素值 s-next=Head-next；/新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后 head-next=s； 算法算法2.11 創(chuàng)建一個(gè)單鏈表創(chuàng)建一個(gè)單鏈表頭插法頭插法63尾插法指每次將新申請(qǐng)的結(jié)點(diǎn)插在尾結(jié)點(diǎn)的后面尾插法指每次將新申請(qǐng)的結(jié)

18、點(diǎn)插在尾結(jié)點(diǎn)的后面方法二：方法二：尾插法尾插法64templatevoid LinkList：CreateList(int n) /尾插法尾插法(正位序正位序)創(chuàng)建具有創(chuàng)建具有n個(gè)元素的線性表個(gè)元素的線性表Node *p,*s；/設(shè)置工作指針，設(shè)置工作指針，p指向尾結(jié)點(diǎn)指向尾結(jié)點(diǎn)p=Head；for(int i=1；i=n；i+)s=new Node；/新建元素結(jié)點(diǎn)新建元素結(jié)點(diǎn) cins-data；/輸入新建數(shù)據(jù)元素值輸入新建數(shù)據(jù)元素值s-next=p-next；/新結(jié)點(diǎn)鏈入表尾新結(jié)點(diǎn)鏈入表尾p-next=s；p=s；算法算法2.11 創(chuàng)建一個(gè)單鏈表創(chuàng)建一個(gè)單鏈表頭插法頭插法65其它形式的單鏈

19、表其它形式的單鏈表66循環(huán)鏈表循環(huán)鏈表67雙向鏈表雙向鏈表68雙循環(huán)鏈表雙循環(huán)鏈表69雙向鏈表特性雙向鏈表特性70雙向鏈表中插入結(jié)點(diǎn)雙向鏈表中插入結(jié)點(diǎn)71(2) 雙向鏈表中結(jié)點(diǎn)的刪除雙向鏈表中結(jié)點(diǎn)的刪除722.4 2.4 線性表的其它存儲(chǔ)方式線性表的其它存儲(chǔ)方式73順序存儲(chǔ)優(yōu)、缺點(diǎn)順序存儲(chǔ)優(yōu)、缺點(diǎn)74鏈?zhǔn)酱鎯?chǔ)優(yōu)、缺點(diǎn)鏈?zhǔn)酱鎯?chǔ)優(yōu)、缺點(diǎn)75靜態(tài)鏈表靜態(tài)鏈表76(a) 空鏈表空鏈表 (b) 某一時(shí)刻的靜態(tài)鏈表某一時(shí)刻的靜態(tài)鏈表靜態(tài)鏈表示意靜態(tài)鏈表示意77 (c) 在表頭插入元素在表頭插入元素e (d) 刪除元素刪除元素a2 續(xù)續(xù)78間接尋址間接尋址79間接尋址特點(diǎn)間接尋址特點(diǎn)802.5 線性表應(yīng)用舉

20、例線性表應(yīng)用舉例集合并集合并多項(xiàng)式求和多項(xiàng)式求和81例例2.1 集合并集合并 擴(kuò)大線性表 LA，將存在于線性表存在于線性表LB LB 中中而不存在于線性表不存在于線性表 LA LA 中中的數(shù)據(jù)元素插入到線插入到線性表性表 LA LA 中中去。821. 1.從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;2.2.依值在線性表LA中進(jìn)行查訪; 3.3.若不存在，則插入之。GetElem( LB, i )GetElem( LB, i )e e LocateElem( LA, e, equal( ) )LocateElem( LA, e, equal( ) )Insert ( LA, n+1, e )Insert ( LA, n+1, e )操作步驟操作步驟83算法算法2.1類類C+語言描述語言描述84例例2.2: 一元多項(xiàng)式的表示和運(yùn)算一元多項(xiàng)式的表示和運(yùn)算nnnxpxpxppxP2210)(nnnxpxpxppxP2210)(nnnxpxpxppxP2210)(nnnxpxpxp