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

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)線性表結(jié)構(gòu)第二章第二章本章主要內(nèi)容本章主要內(nèi)容線性表的基本概念線性表的基本概念1線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)2線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)3線性表結(jié)構(gòu)的應(yīng)用線性表結(jié)構(gòu)的應(yīng)用42.1 線性表的基本概念線性表的基本概念A(yù)=（a1, a2, ai-1，ai, ai1 ，, an）1. 線性表的定義：線性表的定義：是是n個同類結(jié)點的有限序列。個同類結(jié)點的有限序列。n=0時稱為時稱為空表空表數(shù)據(jù)元素數(shù)據(jù)元素始始(首首)結(jié)點結(jié)點ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的序是元素的序號，表示元素在表號，表示元素在表中的位置中的位置n為元素總個

2、數(shù)，為元素總個數(shù)，即表長即表長終終(尾尾)結(jié)點結(jié)點v線性表的邏輯結(jié)構(gòu)特點線性表的邏輯結(jié)構(gòu)特點除第一個之外的數(shù)據(jù)元素均只有一個直接前驅(qū)除第一個之外的數(shù)據(jù)元素均只有一個直接前驅(qū) 存在唯一的一個被稱作存在唯一的一個被稱作“第一個第一個”的數(shù)據(jù)元素的數(shù)據(jù)元素 除最后一個之外的數(shù)據(jù)元素均只有一個直接后繼除最后一個之外的數(shù)據(jù)元素均只有一個直接后繼 數(shù)據(jù)元素的數(shù)據(jù)元素的 非空有限集非空有限集 存在唯一的一個被稱作存在唯一的一個被稱作“最后一個最后一個”的數(shù)據(jù)元素的數(shù)據(jù)元素線性表可以看作是除第一個元素?zé)o前驅(qū),最后一個元素?zé)o后繼外,其余元素都有唯一的直接前驅(qū)和直接后繼的元素構(gòu)成的集合2.1.1 線性表舉例線性表

3、舉例v 例例2 22 2：學(xué)生成績登記表：學(xué)生成績登記表學(xué)號學(xué)號姓名姓名政治政治成績成績數(shù)學(xué)數(shù)學(xué)成績成績英語英語成績成績信息技信息技術(shù)成績術(shù)成績數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)成績構(gòu)成績210806101陳敏敏7883689277210806102李學(xué)好8386868467210806103顧家新6594977891210806104黃玲玲90100756690210806105柯向民10079837374210806106王懷國7277619568210806107徐晶晶5684649979210806108余美美9873888777210806109張全理8899918588線性表中的數(shù)據(jù)元素可以是各種各樣

4、的，但同一線性線性表中的數(shù)據(jù)元素可以是各種各樣的，但同一線性 表中的元素必定具有相同特性（屬于同一數(shù)據(jù)對象）。表中的元素必定具有相同特性（屬于同一數(shù)據(jù)對象）。分析：數(shù)據(jù)元素分析：數(shù)據(jù)元素( (結(jié)點、記錄結(jié)點、記錄) )由由7 7個數(shù)據(jù)項個數(shù)據(jù)項( (字段、域字段、域) )組成。組成。v 例例2 21 1：1 1到到3030之間的質(zhì)數(shù)序列是一個線性表之間的質(zhì)數(shù)序列是一個線性表 P=( P=(2 2，3 3，5 5，7 7，1111，1313，1717，1919，2323，2929) )分析：分析： 數(shù)據(jù)元素都是質(zhì)數(shù)，數(shù)據(jù)元素都是質(zhì)數(shù)， 元素間關(guān)系是線性的，元素間關(guān)系是線性的， 表長是表長是111

5、1判斷指定線性表是否是空表。若為空則返回判斷指定線性表是否是空表。若為空則返回1 1，否則返回，否則返回0 0置指定線性表置指定線性表L L成空表，即清除所有原有的結(jié)點，并返回成空表，即清除所有原有的結(jié)點，并返回L L 2.1.2 線性表的基本操作線性表的基本操作同一種操作在數(shù)據(jù)的不同物理結(jié)構(gòu)下，執(zhí)行過程不同線性表的常用操作：線性表的常用操作：注意：注意：建立一個空線性表建立一個空線性表L L（即建立一個線性表結(jié)構(gòu)）（即建立一個線性表結(jié)構(gòu)）, ,并返回并返回L L統(tǒng)計指定線性表統(tǒng)計指定線性表L L中當(dāng)前結(jié)點個數(shù)，并返回個數(shù)中當(dāng)前結(jié)點個數(shù)，并返回個數(shù)用給定值用給定值x，在指定線性表，在指定線性表

6、L中查找與中查找與x等值的結(jié)點。等值的結(jié)點。若存在則返回結(jié)點位置信息。若存在則返回結(jié)點位置信息。給定結(jié)點數(shù)據(jù)給定結(jié)點數(shù)據(jù)x和整數(shù)和整數(shù)i，向指定線性表向指定線性表L中第中第i個位置插入結(jié)點數(shù)據(jù)為個位置插入結(jié)點數(shù)據(jù)為x的新結(jié)點的新結(jié)點給定數(shù)據(jù)給定數(shù)據(jù)x和整數(shù)和整數(shù)i,用用x替換指定線性表替換指定線性表L中第中第i個結(jié)點的原數(shù)個結(jié)點的原數(shù)據(jù)，使其有新值據(jù)，使其有新值給定結(jié)點序號給定結(jié)點序號i，從指定線性表，從指定線性表L中讀出并返回該結(jié)點數(shù)據(jù)中讀出并返回該結(jié)點數(shù)據(jù)從指定線性表從指定線性表L中刪去第中刪去第i個結(jié)點。個結(jié)點。把兩個指定線性表把兩個指定線性表L1和和L2，按規(guī)定的要求連接成一個線性表，

7、按規(guī)定的要求連接成一個線性表 2.1.2 線性表的基本操作線性表的基本操作2.2 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)a2a3a1an.已已用用區(qū)區(qū)段段空空閑閑區(qū)區(qū)段段An+1A1A2AnAm把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。足夠大小、地址連續(xù)的單元構(gòu)成的一個存儲空間片。線性表的結(jié)點按它的邏輯結(jié)構(gòu)順序一個接一個地依次存儲 。2.2.1 順序表中元素存儲位置的計算順序表中元素存儲位置的計算線性表的第 1 個數(shù)據(jù)元素 a1從地址h h單元開始存儲a1 a2 ai-1 ai ai+1 an h單元假設(shè)線性表的每個元素需占 b b個存儲單

8、元，則第 i + 1 個 元素的存儲位置和第 i 個元素的存儲位置之間滿足關(guān)系： LOC(ai +1) = LOC(ai ) + b由此，所有數(shù)據(jù)元素的存儲位置均可通過基地址得到： LOC(ai ) = LOC(a1) + (i1) b=h+(i1)bh單元單元a2a3a1an.空空閑閑區(qū)區(qū)段段內(nèi)存狀態(tài)內(nèi)存狀態(tài)LOC(a1) LOC(a1)+b LOC(a1)+(n -1) b LOC(a1)+n b 存儲地址存儲地址123n數(shù)據(jù)元素在線數(shù)據(jù)元素在線 性表中的位序性表中的位序 順序表的特點：以物理位置相鄰表示邏輯關(guān)系順序表的特點：以物理位置相鄰表示邏輯關(guān)系 任一元素均可隨機(jī)存取。任一元素均可隨

9、機(jī)存取。 （優(yōu)點）（優(yōu)點）2.2.2 順序表存儲結(jié)構(gòu)的順序表存儲結(jié)構(gòu)的C語言描述語言描述用用C C的一維數(shù)組的一維數(shù)組 表示順序表表示順序表 類型相同類型相同 用一變量表示順序用一變量表示順序表的長度屬性表的長度屬性 線性表長可變（插入刪除）線性表長可變（插入刪除） 順序表的特點順序表的特點地址連續(xù)地址連續(xù) 隨機(jī)存取隨機(jī)存取 依次存放依次存放 一維數(shù)組一維數(shù)組 數(shù)組長度不可動態(tài)定義數(shù)組長度不可動態(tài)定義 #define m 100typedef struct int datam; int n; SEQUENLIST；說明：常量表達(dá)式中可以包含常量和說明：常量表達(dá)式中可以包含常量和 符號常量，符號

10、常量，不能包含變量不能包含變量。即。即 C 不允不允 許對數(shù)組的大小作動態(tài)定義。許對數(shù)組的大小作動態(tài)定義。 說明：說明：n表示順序表的長度。表示順序表的長度。 注意注意：區(qū)分元素的序號和數(shù)：區(qū)分元素的序號和數(shù)組的下標(biāo)，如組的下標(biāo)，如a1的序號為的序號為1，而其對應(yīng)的數(shù)組下標(biāo)為而其對應(yīng)的數(shù)組下標(biāo)為02.2.3 順序表的操作順序表的操作函數(shù)表示函數(shù)表示 操作含義操作含義 算法思路算法思路 算法描述算法描述 C C語言程序語言程序程序說明程序說明添加插入添加插入Phase 3uAPPEND(A，x) A A為順序表名；為順序表名； x x為新結(jié)點數(shù)據(jù)，為新結(jié)點數(shù)據(jù)， 可以是常數(shù)或變量可以是常數(shù)或變量

11、u要求把要求把x x作為一個新作為一個新結(jié)點插入到順序表結(jié)點插入到順序表A A的終結(jié)點的緊后一個的終結(jié)點的緊后一個位置位置u首先查看順序表空閑區(qū)首先查看順序表空閑區(qū)段是否還有空閑結(jié)點段是否還有空閑結(jié)點u若無則拒絕插入若無則拒絕插入( (稱為稱為上溢上溢); );否則把新結(jié)點存否則把新結(jié)點存儲到插入位置儲到插入位置u順序表長度加順序表長度加1 11.添加插入添加插入函函數(shù)數(shù)表表示示操操作作含含義義算算法法思思路路插入位置插入位置插入前：插入前： a1 a2 ai-1 ai ai+1 an-1 an A.mA.n插入后：插入后： a1 a2 ai-1 ai ai+1 an-1 an x A.mA.

12、n添加插入添加插入u APP1.上溢嗎？上溢嗎？若若n m ，則算法終止（失?。?，則算法終止（失?。?u APP2.計算查入位置計算查入位置 n n + 1 u APP3.插入插入x An x ，算法終止（成功），算法終止（成功）算法描述算法描述 SEQUENLIST append(SEQUENLIST A,int x)if(A.n=m) printf(Overflow!n);else A.n+; A.dataA.n-1=x;return(A);C語言程序語言程序xA.datan+1A.data1A.data2A.datanA.datamA.data1.A.data2A.datan線性表線性表

13、A待插入數(shù)待插入數(shù):x隨機(jī)插入隨機(jī)插入uINSSL(A，i，x) A A為順序表名；為順序表名； i i為指定的插入位置，為指定的插入位置， x x為新結(jié)點數(shù)據(jù)，常數(shù)為新結(jié)點數(shù)據(jù)，常數(shù) 或變量或變量u要求把要求把x x作為一個新結(jié)作為一個新結(jié)點插入到順序表點插入到順序表A A的第的第i1i1和第和第ii個結(jié)點之間的個結(jié)點之間的結(jié)點位置上結(jié)點位置上u首先查看位置號首先查看位置號i i是否合是否合法法u把第把第i i到第到第n n之間的所有之間的所有結(jié)點依次逐個向后移動結(jié)點依次逐個向后移動一個結(jié)點位置，使第一個結(jié)點位置，使第i i個個結(jié)點位置空出結(jié)點位置空出u把新結(jié)點存儲到第把新結(jié)點存儲到第i i

14、個結(jié)個結(jié)點位置上；并長度點位置上；并長度n n加加1 12.隨機(jī)插入隨機(jī)插入函數(shù)表示函數(shù)表示操作含義操作含義算法思路算法思路插入位置插入位置插入前：插入前：插入后：插入后：x a1 a2 ai-1 ai ai+1 an-1 an a1 a2 ai-1 ai ai+1 an-1 an A.mA.nA.n a1 a2 ai-1 ai ai+1 an-1 an 隨機(jī)插入隨機(jī)插入ISL1.插入非法？插入非法？ 若若n m 或或( i n + 1)， 則算法終止則算法終止(失敗失敗)；否則；否則 k n 。ISL2.移動結(jié)點移動結(jié)點 若若 k i，則，則Ak + 1 Ak，k k-1；轉(zhuǎn)；轉(zhuǎn)ISL2繼續(xù)

15、繼續(xù) 。ISL3.插入插入x Ai x ；n n+1；算法終止；算法終止(成功成功)算法思路算法思路 int a;if(iA.n+1|A.n=m) printf(i(location) is illegal!n); exit(0); a= A.n; for(;a=i;a-) A.dataa=A.dataa-1; A.datai-1=x; A.n+; return(A);C語言程序語言程序插入位插入位置置 an an-1 ai+1aixA.mA.n+1刪除算法刪除算法u DELSL(A，i) A A為順序表名；為順序表名； i i為結(jié)點位置號為結(jié)點位置號u要求把第要求把第ii個結(jié)點從順序個結(jié)點從

16、順序表中刪除掉表中刪除掉u首先查看順序表空閑區(qū)首先查看順序表空閑區(qū)段是否還有空閑結(jié)點段是否還有空閑結(jié)點u把第把第i+1i+1到第到第n n之間的所之間的所有結(jié)點依次逐個向前移有結(jié)點依次逐個向前移動一個結(jié)點位置動一個結(jié)點位置u并長度并長度減減1 13.刪除算法刪除算法函數(shù)表示函數(shù)表示操作含義操作含義算法思路算法思路要刪除的結(jié)點要刪除的結(jié)點刪除前：刪除前：刪除后：刪除后： a1 a2 ai-1 ai ai+1 an-1 an a1 a2 ai-1 ai an-1 an A.nA.nu DSL1.i合法嗎？合法嗎？ 若若i n，則算法終止（失?。?；否則，則算法終止（失?。?；否則 k i 。u DSL

17、2.移動結(jié)點移動結(jié)點 若若 k n，則，則Ak Ak + 1，k k+1；轉(zhuǎn)；轉(zhuǎn)DSL2繼續(xù)。繼續(xù)。u DSL3.長度減長度減1 n n-1；算法終止（成功）。；算法終止（成功）。算法思路算法思路 SEQUENLIST delsl(SEQUENLIST A,int i) if(iA.n) /*判斷判斷i值是否合法值是否合法*/ printf( is OverFlow !n); exit(0); /*非法算法終止非法算法終止*/ for (;i=A.n返回返回0合并算法合并算法u CONSL(A，B)其中其中，A A、 B B為順序表為順序表名名uA A、B B必須是同質(zhì)的順必須是同質(zhì)的順序表。

18、操作把序表。操作把A A、B B兩兩順序表進(jìn)行合并，順序表進(jìn)行合并，A A在在前前B B在后，并把合并結(jié)在后，并把合并結(jié)果仍存儲在果仍存儲在A A中中u首先要檢測首先要檢測A A的空閑區(qū)的空閑區(qū)段是否有足夠的空間存段是否有足夠的空間存儲儲B B的所有結(jié)點的所有結(jié)點u若無，則拒絕執(zhí)行本操若無，則拒絕執(zhí)行本操作作u若有，則把若有，則把B B中的所有中的所有結(jié)點逐個插入到結(jié)點逐個插入到A A的終的終結(jié)點緊后的空閑結(jié)點上結(jié)點緊后的空閑結(jié)點上5.合并算法合并算法函數(shù)表示函數(shù)表示操作含義操作含義算法思路算法思路順序表順序表A A：順序表順序表B B： a1 a2 ai an b1 b2 bi bk 合并后

19、合并后順序表順序表A A： a1 a2 ai an b1 b2 bi bk A.m合并算法合并算法 SEQUENLIST consl(SEQUENLIST A,SEQUENLIST B)int j; if(m-A.nB.n) /*判斷判斷A表空間是否足夠表空間是否足夠*/ printf( is OverFlow !n); exit(0); /*空間不夠算法終止空間不夠算法終止*/ for(j=0;jdata表示表示p指向結(jié)點的數(shù)據(jù)域指向結(jié)點的數(shù)據(jù)域(*p).linkp-next表示表示p指向結(jié)點的指針域指向結(jié)點的指針域?qū)ι鲜鼋Y(jié)構(gòu)的改進(jìn)對上述結(jié)構(gòu)的改進(jìn) 在單鏈單鏈表的首結(jié)結(jié)點前增加一個個附加結(jié)結(jié)

20、點，讓讓頭頭指針針始終終指向該該結(jié)結(jié)點 Data_1Data_2Data_nH頭結(jié)點頭結(jié)點稱為頭結(jié)點稱為頭結(jié)點帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表H帶頭結(jié)點的空單鏈表帶頭結(jié)點的空單鏈表有頭結(jié)點時，有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空當(dāng)頭結(jié)點的指針域為空時表示空表時表示空表需要澄清的幾個概念需要澄清的幾個概念指針變量指針變量指針?biāo)傅慕Y(jié)點指針?biāo)傅慕Y(jié)點結(jié)點域結(jié)點域頭結(jié)點頭結(jié)點首結(jié)點首結(jié)點首指針首指針頭指針頭指針指針指針 結(jié)點的存儲地址 存放指針的變量（如p），其值是指針 指針為地址存儲的結(jié)點 構(gòu)成結(jié)點的數(shù)據(jù)字段，包括指針域指向鏈表中第一個結(jié)點(頭結(jié)點或首元結(jié)點)的指針.單鏈表可由它唯一確定在鏈表的首結(jié)點

21、之前附設(shè)的一個結(jié)點;數(shù)據(jù)域內(nèi)只放標(biāo)志等信息;是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點指向首結(jié)點的指針（鏈表的頭指針或頭結(jié)點中的指針） 2.3.2單鏈表的操作單鏈表的操作鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)很適合涉及到插入或刪除的操作.合并合并刪除刪除定位定位按值、按號按值、按號創(chuàng)建創(chuàng)建頭插頭插,尾插尾插插入插入求表長度求表長度單鏈表單鏈表基本操作基本操作創(chuàng)建創(chuàng)建LINKLIST *inill() LINKLIST *L L=( LINKLIST *)malloc(sizeof(LINKLIST); L-next=NULL; L-data=-1; return(L);1.申請結(jié)點空間申請結(jié)點空間 new(L)。

22、2.設(shè)置頭結(jié)點設(shè)置頭結(jié)點 data(L) -1 ，next (L) “”。帶頭結(jié)帶頭結(jié)點點單鏈單鏈表初始化算法表初始化算法頭插入法頭插入法一、建立一個“空表”；二、輸入數(shù)據(jù)元素a11，建立結(jié)點并在Q的首結(jié)點后插入；三、輸入數(shù)據(jù)元素a2 1 ，建立結(jié)點并在Q的首結(jié)點插入；a1a1a2四、依次類推，直至輸入1為止。p-next=Q-next;Q-next=p;程序見書中P程序22。Q1pp-data=a2;p1Q-next=p;1QQ尾插入法尾插入法一、建立一個“空表”；二、輸入數(shù)據(jù)元素a11，建立結(jié)點并在Q的終結(jié)點后插入；a1Q1p1r-next=p;三、輸入數(shù)據(jù)元素a2 1 ，建立結(jié)點并在Q的

23、終結(jié)點插入；rrQr=p;a11Qr a2p-data=a2;pp-next=NULL;r-next=p;r=p;四、依次類推，直至輸入1為止。程序見書中P程序22。按號定位按號定位單鏈表中，為找第單鏈表中，為找第 i i 個數(shù)據(jù)元素，必須從單鏈表的頭指針出發(fā)，沿著鏈指針方向?qū)Y(jié)點個數(shù)據(jù)元素，必須從單鏈表的頭指針出發(fā)，沿著鏈指針方向?qū)Y(jié)點順序逐個掃描、計數(shù)；當(dāng)計數(shù)值等于順序逐個掃描、計數(shù)；當(dāng)計數(shù)值等于i i時，定位完成。時，定位完成。令指令指針針 p p 始始終終指向指向線線性表中第性表中第 j j 個數(shù)個數(shù)據(jù)元素?fù)?jù)元素例如：例如：算法搜索表算法搜索表Q Q，找出第，找出第i i結(jié)結(jié)點的指點的

24、指針輸針輸出出 211830754256pppj1 2 3Qi=3因此，查找第因此，查找第 i 個數(shù)據(jù)元素的基本操作為：移動指針，比較個數(shù)據(jù)元素的基本操作為：移動指針，比較 j 和和 i 。程序見書中P。按值定位按值定位算法搜索表算法搜索表Q Q，找出，找出結(jié)結(jié)點點數(shù)數(shù)據(jù)據(jù)與與x x值值相等的相等的結(jié)結(jié)點，點，并輸并輸出出該結(jié)該結(jié)點指點指針針 當(dāng)遇到結(jié)點數(shù)據(jù)與當(dāng)遇到結(jié)點數(shù)據(jù)與x x 值相等時，或比較完所有結(jié)點時，即結(jié)束掃描。值相等時，或比較完所有結(jié)點時，即結(jié)束掃描。因此，查找值為因此，查找值為x x結(jié)點的基本操作為：移動指針，比較結(jié)點的基本操作為：移動指針，比較 p-datap-data和和

25、x x 。 211830754256Qx=30ppppppppppp p-data=x返回返回px=53p=NULL返回返回p例如：例如：程序見書中P。求表長求表長只要設(shè)一個移動指針沿著鏈指針方向?qū)Y(jié)點順序逐個掃描、計數(shù)；當(dāng)掃描完所有結(jié)點，計只要設(shè)一個移動指針沿著鏈指針方向?qū)Y(jié)點順序逐個掃描、計數(shù)；當(dāng)掃描完所有結(jié)點，計數(shù)完成。數(shù)完成。例如：例如：p p為為移移動動指指針針 ，j j為計數(shù)為計數(shù)器器統(tǒng)計單鏈統(tǒng)計單鏈表表L L中中結(jié)結(jié)點的點的個數(shù)個數(shù)，并輸并輸出出因此，求表長的基本操作為：移動指針，計數(shù)器自加因此，求表長的基本操作為：移動指針，計數(shù)器自加 。程序見書中P。211830754256p

26、ppj1 2 3Qppp4 5 6next(p)=,next(p)=,結(jié)束結(jié)束掃描，返回掃描，返回j j的值的值 插入插入xs s next = p next; p next = s; p ai ai 1 插入該新結(jié)點，使之成為單鏈表插入該新結(jié)點，使之成為單鏈表Q的第的第i個結(jié)點個結(jié)點 1u首先找到首先找到 ai -1 的存儲位置的存儲位置 p 2u生成一個數(shù)據(jù)域為生成一個數(shù)據(jù)域為 x 的新結(jié)點的新結(jié)點3u插入新結(jié)點：、結(jié)點插入新結(jié)點：、結(jié)點 ai -1的指針域指向新結(jié)點的指針域指向新結(jié)點 、新結(jié)點的指針域指向結(jié)點、新結(jié)點的指針域指向結(jié)點 ai 程序見書中P。刪除刪除把第把第i個結(jié)點從單鏈表個

27、結(jié)點從單鏈表Q中刪除掉中刪除掉1u 首先找到首先找到 ai -1 的存儲位置的存儲位置 p 2u 令令 pnext 指向指向 ai 1 3u 釋放結(jié)點釋放結(jié)點ai的空間的空間p next = p next next; p ai 1 ai ai+1 程序見書中P。合并合并操作把操作把A A、B B兩單鏈表進(jìn)行合并，兩單鏈表進(jìn)行合并，A A在前在前B B在后，并把合并結(jié)果仍存儲在在后，并把合并結(jié)果仍存儲在A A中中分析：分析： 對鏈表來說，對鏈表來說，“插入插入”和和“刪除刪除”僅需修改指針即可完成，并且由于前僅需修改指針即可完成，并且由于前 m m 個元素之間和后個元素之間和后 n n 個元素之

28、間的鏈接關(guān)系分別都不需要改變，則算法的個元素之間的鏈接關(guān)系分別都不需要改變，則算法的實際操作為：實際操作為： 找到找到A A的終點，修改的終點，修改A A的終點指針，即的終點指針，即將將 (b1, b2, , bn) 鏈接到鏈接到am之后之后；A a1a2am b1b2bn B A a1a2am b1b2bn B P P P 程序見書中P。2.3.3循環(huán)鏈表和雙向鏈表循環(huán)鏈表和雙向鏈表 d1dn非空環(huán)鏈表非空環(huán)鏈表 (使用頭指針使用頭指針) H循環(huán)鏈表：循環(huán)鏈表：是一種首尾相接的鏈表是一種首尾相接的鏈表(即：即：把終結(jié)點指針域的值為把終結(jié)點指針域的值為“空空”改為改為指向頭結(jié)點，整個鏈表形成一

29、個環(huán)指向頭結(jié)點，整個鏈表形成一個環(huán)),簡稱環(huán)鏈簡稱環(huán)鏈表表創(chuàng)建空表時，其創(chuàng)建空表時，其頭結(jié)點指針域的指針值就是頭指針頭結(jié)點指針域的指針值就是頭指針 空表空表(使用頭指針使用頭指針) H 特點：從表的任意結(jié)點出發(fā)，都可以通過后移指針的方法找到表中所有結(jié)點特點：從表的任意結(jié)點出發(fā)，都可以通過后移指針的方法找到表中所有結(jié)點 沒有沒有 指針指針如何判別終如何判別終結(jié)點？結(jié)點？改進(jìn)的循環(huán)鏈表改進(jìn)的循環(huán)鏈表 d1dn非空環(huán)鏈表非空環(huán)鏈表 (使用尾指針使用尾指針) R由于查找終結(jié)點必須掃描全表才能找到，時間效率不高由于查找終結(jié)點必須掃描全表才能找到，時間效率不高 如何改進(jìn)如何改進(jìn)呢？呢？改進(jìn)的辦法是設(shè)置一個

30、尾指針，而不設(shè)置頭指針。改進(jìn)的辦法是設(shè)置一個尾指針，而不設(shè)置頭指針。這樣的好處是：只設(shè)置一個指針，但獲得頭結(jié)點指針和終結(jié)點這樣的好處是：只設(shè)置一個指針，但獲得頭結(jié)點指針和終結(jié)點next(R)實際上就是頭指針，首結(jié)點指針是實際上就是頭指針，首結(jié)點指針是next(next() 空表空表(使用頭指針使用頭指針) R這種改進(jìn)為某些操作提供許多方便這種改進(jìn)為某些操作提供許多方便例如：若例如：若A、B為使用尾指針的循環(huán)鏈表，則上面的合并算法只需兩步就完成了為使用尾指針的循環(huán)鏈表，則上面的合并算法只需兩步就完成了 a1an A b1bn Bpnext(B) next(B)next(A) next(A)nex

31、t(p) AB a1an b1bn AB雙向鏈表雙向鏈表雙向鏈表的結(jié)點除數(shù)據(jù)域外含有兩個指針域雙向鏈表的結(jié)點除數(shù)據(jù)域外含有兩個指針域后繼指針域后繼指針域nextnext和前繼指針域和前繼指針域priorprior，分別存放指向后繼結(jié)點和前繼結(jié)點，分別存放指向后繼結(jié)點和前繼結(jié)點為什么要討為什么要討論雙向鏈表論雙向鏈表呢？呢？單鏈表的結(jié)點單鏈表的結(jié)點有指示后繼的指針域有指示后繼的指針域找后繼結(jié)點方便；找后繼結(jié)點方便； 無指示前驅(qū)的指針域無指示前驅(qū)的指針域找前驅(qū)結(jié)點難：從表頭出發(fā)查找。找前驅(qū)結(jié)點難：從表頭出發(fā)查找。 前驅(qū)指針前驅(qū)指針結(jié)點數(shù)據(jù)結(jié)點數(shù)據(jù)后繼指針后繼指針datanextprior Type

32、def struct dnode Int data； Struct dnode *prior，*next； DOUBLELINKLIST；雙向循環(huán)鏈表雙向循環(huán)鏈表 空雙向鏈表空雙向鏈表 H H雙向鏈表結(jié)構(gòu)雙向鏈表結(jié)構(gòu)和單鏈的循環(huán)表類似，雙向鏈表也可以有循環(huán)表，讓頭結(jié)點的前驅(qū)指針指向鏈表的最后一個結(jié)點，讓最后一個結(jié)點的后繼指針指向頭結(jié)點，所以又稱雙向循環(huán)鏈表 空表如何定空表如何定義？義？雙向鏈表的對稱性雙向鏈表的對稱性雙向鏈表是一種對稱結(jié)構(gòu)雙向鏈表是一種對稱結(jié)構(gòu)(設(shè)指針設(shè)指針 p 指向某一結(jié)點指向某一結(jié)點)：ppriornext= p =pnextprior pnext(p)prior(p)ne

33、xt(prior (p) prior( next (p) 特點：可以雙向查找表中結(jié)點，特點：可以雙向查找表中結(jié)點，“插入插入” 和和“刪除刪除”時需要時需要同同時修改兩個方向時修改兩個方向上的指針上的指針例如：例如： 刪除結(jié)點刪除結(jié)點 a b c p-prior -next = p-next;pnextprior=p priorp雙向鏈表操作演示雙向鏈表操作演示 x 在在p所指結(jié)點前插入所指結(jié)點前插入 p a b t next(t)=p prior(t)=prior(p) prior(p)=t next(prior(p)=t x 在在p所指結(jié)點后插入所指結(jié)點后插入p a b t next(t)

34、=next(p) prior(next(p)=t next(p)=t prior(t)=p鏈?zhǔn)酱鎯Y(jié)構(gòu)小結(jié)鏈?zhǔn)酱鎯Y(jié)構(gòu)小結(jié)鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點：結(jié)點空間可以動態(tài)申請和釋放；數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，插入和刪除時不需要移動數(shù)據(jù)元素。(事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間)鏈?zhǔn)酱鎯Y(jié)構(gòu)的缺點：存儲密度小，存儲空間利用率低(每個結(jié)點的指針域需額外占用存儲空間。當(dāng)數(shù)據(jù)域所占字節(jié)不多時，指針域所占存儲空間的比重顯得很大)。鏈表是非隨機(jī)存取結(jié)構(gòu)。對任一結(jié)點的操作都要從頭指針依鏈查找該結(jié)點，這增加了算法的復(fù)雜度。 不便于在表尾插入元素：需遍歷整個表才能找到位置。 2.4線性表結(jié)構(gòu)

35、的應(yīng)用線性表結(jié)構(gòu)的應(yīng)用用鏈?zhǔn)酱鎯蝽樞虼鎯τ面準(zhǔn)酱鎯蝽樞虼鎯€性表排序線性表排序線性表查找線性表查找數(shù)據(jù)查重數(shù)據(jù)查重2.4.1數(shù)據(jù)查重數(shù)據(jù)查重清理性查重清理性查重 當(dāng)有當(dāng)有“相同相同”結(jié)點存儲結(jié)點存儲時只保留其一（通常是時只保留其一（通常是順序上的第一個），其順序上的第一個），其余結(jié)點統(tǒng)統(tǒng)摘除余結(jié)點統(tǒng)統(tǒng)摘除查重目的查重目的不同不同統(tǒng)計性查重統(tǒng)計性查重分別統(tǒng)計每一結(jié)點在表分別統(tǒng)計每一結(jié)點在表中重復(fù)出現(xiàn)的次數(shù)中重復(fù)出現(xiàn)的次數(shù).基本思想基本思想提取表中一個結(jié)點（將保留在表中）提取表中一個結(jié)點（將保留在表中）用該結(jié)點的結(jié)點數(shù)據(jù)與其他結(jié)點進(jìn)行比較用該結(jié)點的結(jié)點數(shù)據(jù)與其他結(jié)點進(jìn)行比較若有相同者將其從表中

36、刪除掉若有相同者將其從表中刪除掉(或?qū)χ貜?fù)結(jié)點計數(shù)或?qū)χ貜?fù)結(jié)點計數(shù) ) 第第5次掃描次掃描 S5=41 2 3 5 4n=5實例演示實例演示設(shè)有順序表設(shè)有順序表S =（1，2，3，1，1，5，2，4，2，4），），n=10查重的執(zhí)行過程是：查重的執(zhí)行過程是：第第1次掃描次掃描 S1=11 2 3 5 2 4 2 4n=8第第2次掃描次掃描 S2=21 2 3 5 4 4n=6第第3次掃描次掃描 S3=31 2 3 5 4 4n=6查重結(jié)點查重結(jié)點 查重結(jié)果表查重結(jié)果表第第4次掃描次掃描 S4=51 2 3 5 4 4n=6初態(tài)初態(tài)1 2 3 1 1 5 2 4 2 4n=10算法的核心操算法的

37、核心操作是作是比較比較和和刪刪除除。最多。最多n-1次次掃描掃描每一次新掃描都是在上一次每一次新掃描都是在上一次查重結(jié)果表的基礎(chǔ)上執(zhí)行的查重結(jié)果表的基礎(chǔ)上執(zhí)行的注意注意：有序表查重有序表查重 原始表原始表S =（1，1，1，2，2，2，3，4，4，5）n = 10 第第1 1結(jié)點結(jié)點S1 = 1，查重后查重后S =（1，2，2，2，3，4，4，5）n = 8 第第2結(jié)點結(jié)點S2 = 2，查重后，查重后S =（1，2， 3，4，4，5）n = 6 第第3結(jié)點結(jié)點S3 = 3，查重后查重后S =（1，2，3，4，4，5） n = 6 第第4結(jié)點結(jié)點S4 = 4，查重后查重后S =（1，2， 3，4

38、，5） n = 5當(dāng)遇到不相同結(jié)點時，就從當(dāng)遇到不相同結(jié)點時，就從下一結(jié)點下一結(jié)點開始重復(fù)上述操作開始重復(fù)上述操作查重過程：查重過程： 2.4.2基于線性表排序基于線性表排序43512什么是什么是排序排序排序結(jié)果排序結(jié)果排序操作排序操作排序?qū)ο笈判驅(qū)ο笈判蚍较蚺判蚍较蚺判驑?biāo)準(zhǔn)排序標(biāo)準(zhǔn)(關(guān)鍵字關(guān)鍵字)直接插入排序直接插入排序直接插入排序的基本思想：直接插入排序的基本思想：把待排序序列一分為二：“已排好序子序列”和“待排序子序列” 依次將各個數(shù)據(jù)插入已排序好的有序子表中有序序列有序序列 a1 . a i -1 ai無序序列無序序列 aai i . An有序序列有序序列 a1 . a i 無序序列無

39、序序列 ai +1 . An排序結(jié)果仍存儲在原序排序結(jié)果仍存儲在原序列的空間上，原序列不列的空間上，原序列不再存在了再存在了最簡單的一種排序方法 新元素插在新元素插在哪？哪？實例演示實例演示設(shè)有序列設(shè)有序列41，25，17，12，28，14，23，16，直接插入排序的過程，直接插入排序的過程 01234567初始劃分初始劃分4125171228142316第第1次插入次插入2541171228142316第第2次插入次插入1725411228142316第第3次插入次插入1217254128142316第第4次插入次插入1217252841142316第第5次插入次插入121417252841

40、2316第第6次插入次插入1214172325284116第第7次插入次插入1214161723252841改進(jìn)改進(jìn)設(shè)待排序順序表設(shè)待排序順序表S，為了提高效率，我們附設(shè)一個哨兵結(jié)點，為了提高效率，我們附設(shè)一個哨兵結(jié)點S0，使得，使得S0始終存放當(dāng)前待插入的記錄始終存放當(dāng)前待插入的記錄哨兵結(jié)點的哨兵結(jié)點的作用？作用？初始狀態(tài)初始狀態(tài)4125171228142316 S0 S1 S2 S3 S4 S5 S6 S7 i =3 1725411228142316 i =4 1217254128142316 i =6 3817252897122316i =7 1723252841121416i =8 1

41、617252841121423i =2 4938171228142316 4125254125171241i =5 12172528411423162828144125411725121741252814144117252841232316172528412316該算法的要點是：該算法的要點是：使用監(jiān)視哨使用監(jiān)視哨s0臨時保臨時保存待插入的記錄。存待插入的記錄。從后往前查找應(yīng)插入從后往前查找應(yīng)插入的的 位置。位置。查找與移動用同一循查找與移動用同一循環(huán)環(huán) 完成。完成。 簡單交換排序簡單交換排序基本思路：基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。選擇最小結(jié)點的方法是，從終結(jié)點Rn開始順序向上兩個兩個地比較優(yōu)點優(yōu)點：每趟結(jié)束時，不僅能擠出一個最小值到最前面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序前提前提：順序存儲結(jié)構(gòu) 排序過程：排序過程：簡單交換排序過程實例簡單交換排序過程實例1214161723252841第第7趟趟掃掃描描2523171216412814待待排排序序序序列列2523171216412814第第1趟趟掃掃描描1225231714164128第第2趟趟掃掃描描1214252317162841第第3趟趟掃掃描描142814411416121