數(shù)據(jù)結(jié)構(gòu)(c語言版)-嚴(yán)蔚敏版-第2章-線性表-信大(第2講)

緒論要點(diǎn)回顧數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用D_S=(D,S)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算

算法效率指標(biāo)——時(shí)間效率和空間效率數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)近期

上課

內(nèi)容第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

線性結(jié)構(gòu)(邏輯、存儲(chǔ)和運(yùn)算)

若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。可表示為：(a1,a2,……,an)線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；②除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是------簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一

的第二章線性表第2章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)圖2.1線性表的邏輯結(jié)構(gòu)2.1線性表的類型定義2.1.1線性表的邏輯結(jié)構(gòu)（a1,a2,…ai-1，ai,ai＋1

，…,an）線性表的定義：是n個(gè)數(shù)據(jù)元素的有限序列n=0時(shí)稱為數(shù)據(jù)元素表頭ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)空表表尾例1分析26個(gè)英文字母組成的英文表

（A,B,C,D,……,Z）例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性

線性表的特點(diǎn)可概括如下：同一性有窮性有序性

線性表是最常見的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榫仃?、?shù)組、字符串、堆棧、隊(duì)列等都符合線性條件。練：判斷下列敘述的正誤：1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。2.線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計(jì)算機(jī)。3.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。4.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的。5.一維向量是線性表，但二維或N維數(shù)組不是。6.“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。√×√√××例2-1兩個(gè)集合La和Lb的合并假設(shè)兩個(gè)集合La{7,2,3}Lb{8,4,5,6}怎樣將他們合并呢？1，首先知道La的長(zhǎng)度是3和Lb的長(zhǎng)度是42，之后把Lb集合中的元素依次和La中的元素進(jìn)行比對(duì)形成一個(gè)循環(huán)，首先Lb中的8與La的元素依次比對(duì)，8與所有La中元素不同，將8插入La中，3，2與2相同進(jìn)入Lb的下一個(gè)元素，都不相同，之后將元素合并到La中，例2-2兩個(gè)非遞減有序的線性表La和Lb的合并

如La{2,4,6}Lb{4,7,9,10}合并1，定義Lc,長(zhǎng)度是La長(zhǎng)度+Lb長(zhǎng)度2，La中2與Lb中4，把小La中的2的插入Lc，La進(jìn)入下一個(gè)元素3,La中4與Lb中4比較，把La的4插入Lc,LaLb都下一個(gè)元素4,La中6與Lb中7比較，把小的La中的6的插入Lc，La進(jìn)入下一個(gè)元素，無元素了5，就將Lb中剩余元素依次加入Lc中LaLbLc2.2線性表的順序表示和實(shí)現(xiàn)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組來實(shí)現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)定義：順序存儲(chǔ)方法：簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰線性表順序存儲(chǔ)特點(diǎn)：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計(jì)算方法是：設(shè)首元素a1的存放地址為L(zhǎng)OC(a1)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai)=LOC(a1)+L*(i-1)LOC(ai+1)=LOC(ai)+L它是一種隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。

注意：C語言中的數(shù)組的下標(biāo)從0開始，即：V[n]的有效范圍是V[0]～V[n-1]線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)L一個(gè)一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是98，則Ｍ[３]的第一個(gè)字節(jié)的地址是

113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）用數(shù)組V來存放26個(gè)英文字母組成的線性表(a，b，c，…，z)，寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。

voidbuild()/*字母線性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

V[i]=V[i-1]+1;

}核心語句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例2voidbuild();voiddisplay();#define n26intV[n];voidmain(void)/*主函數(shù)，字母線性表的生成和輸出*/{

build();

display();}voiddisplay()/*字母線性表的顯示，即讀表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",V[i]);printf("\n");}執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz26個(gè)字母另一種寫法#include<stdio.h>intmain(){ inti; for(i=0;i<26;i++) if(i%2==0) printf("%c",'A'+i); else printf("%c",'a'+i); printf("\n"); return0;}2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算回憶：數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：

修改、插入、刪除、查找、排序1.修改操作

通過數(shù)組的下標(biāo)便可訪問某個(gè)特定元素并修改之。核心語句:

V[i]=x;顯然，順序表修改操作的時(shí)間效率是T(n)=O(1)2.存取操作在這種結(jié)構(gòu)中容易實(shí)現(xiàn)隨機(jī)存取第i個(gè)數(shù)據(jù)元素，C語言中數(shù)組的下標(biāo)從0開始，所以ai應(yīng)在L.elem[i-1]中存取。

3.插入操作在表的第i(1≤i≤n+1)個(gè)位置，插入一個(gè)新元素e，使長(zhǎng)度為n的線性表(e1，…，ei-1，ei，…，en)變成長(zhǎng)度為n+1的線性表（e1，…,ei-1，e，ei，…，en）。實(shí)現(xiàn)步驟：將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫到第i個(gè)位置；表長(zhǎng)加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?長(zhǎng)度為n的線性表變?yōu)殚L(zhǎng)度為n+1的線性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）

例如：已知線性表(4,9,15,28,30,30,42,51,62)，需在第4個(gè)元素之前插入一個(gè)元素“21”，則需要將第9個(gè)位置到第4個(gè)位置的元素依次后移一個(gè)位置，然后將“21”插入到第4個(gè)位置，如圖2.3所示。請(qǐng)注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo)。圖2.3順序表中插入元素

插入元素時(shí)，時(shí)間主要耗費(fèi)在移動(dòng)元素上。移動(dòng)個(gè)數(shù)取決于插入位置。for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;//元素后移一個(gè)位置//插入x//表長(zhǎng)加1

4.刪除操作指將表的第i(1≤i≤n)個(gè)元素刪去，使長(zhǎng)度為n的線性表(e1，…,ei-1，ei，ei+1，…，en)變成長(zhǎng)度為n-1的線性表(e1，…,ei-1，ei+1，…，en)。

實(shí)現(xiàn)步驟：將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。注意：事先需要判斷，刪除位置i是否合法?圖2.4順序表中刪除元素例如：線性表(4,9,15,21,28,30,30,42,51,62)刪除第5個(gè)元素，則需將第6個(gè)元素到第10個(gè)元素依次向前移動(dòng)一個(gè)位置，如圖2.4所示。for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一個(gè)位置//表長(zhǎng)減1核心語句：線性表順序表示的優(yōu)點(diǎn)是：(1）無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間（因?yàn)檫壿嬌舷噜彽脑仄浯鎯?chǔ)的物理位置也是相鄰的）；(2）可方便地隨機(jī)存取表中的任一元素。其缺點(diǎn)是：（1）插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低;（2）預(yù)分配空間（浪費(fèi)）；（3）表的擴(kuò)充不方便。

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)注意：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：

數(shù)據(jù)域和指針域例1畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存的鏈?zhǔn)酱娣攀疽鈭D如下：

解：該字母表的邏輯結(jié)構(gòu)為：(a,b,…,y,z)aheadb/\z……各結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)；指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置。指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：

n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置2.3.1單鏈表由于鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，故將這種鏈表又稱為單鏈表。單鏈表中第一個(gè)結(jié)點(diǎn)無前趨，應(yīng)設(shè)一個(gè)頭指針H指向第一個(gè)結(jié)點(diǎn)。單鏈表中最后一個(gè)結(jié)點(diǎn)沒有直接后繼，則指定最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL）。

整個(gè)鏈表的存取必須從頭指針開始。

例如：圖2.5所示為線性表（A,B,C,D,E,F,G）的單鏈表存儲(chǔ)結(jié)構(gòu)，整個(gè)鏈表的存取需從頭指針開始進(jìn)行，依次順著每個(gè)結(jié)點(diǎn)的指針域找到線性表的各個(gè)元素。圖2.5單鏈表的示例圖圖2.6單鏈表的邏輯狀態(tài)圖2.7帶頭結(jié)點(diǎn)單鏈表圖示一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是多少？例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)答：討論1.

在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.

如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。^頭指針^頭指針頭結(jié)點(diǎn)無頭結(jié)點(diǎn)有頭結(jié)點(diǎn)討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。答：討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)體數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書寫表達(dá)？——補(bǔ)充C語言內(nèi)容

頭結(jié)點(diǎn)的數(shù)據(jù)域H補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型及其C語言表示法①類型定義和變量說明可以合寫為：typedefstructCh{chardata;//定義數(shù)據(jù)域的變量名及其類型structCh*next;//定義指針域的變量名及其類型}test，*head;/*test是Ch結(jié)構(gòu)類型的變量,*head是Ch結(jié)構(gòu)類型的頭指針*/以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：假設(shè)每個(gè)結(jié)點(diǎn)用變量test表示，其中兩個(gè)分量分別用data和*next表示，則：*nextdatatest補(bǔ)充：結(jié)構(gòu)類型的C語言表示法②對(duì)于指向結(jié)構(gòu)變量test首地址的指針，還可說明為：structtest*p,*q;(或用structCh*L；)//注：剛才已經(jīng)定義了test為用戶自定義的Ch類型③每個(gè)結(jié)點(diǎn)的分量如何表示？*nextdatatestp方式1：直接用test.data＝'a'；test.next=q方式2：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：

p->data='a';p->next=q;方式3：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：(*p).data='a'；(*p).next＝q單鏈表可以由頭指針唯一確定。單鏈表的存儲(chǔ)結(jié)構(gòu)描述如下：typedef

struct

LNode

{

ElemType

data;struct

LNode

*next;}LNode

,*LinkList;/*LinkList為結(jié)構(gòu)指針類型*/

假設(shè)L是LinkList型的變量，則L是一個(gè)結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。若L=NULL（對(duì)于帶頭結(jié)點(diǎn)的單鏈表為L(zhǎng)->next=NULL），則表示單鏈表為一個(gè)空表，其長(zhǎng)度為0。若不是空表，對(duì)于帶頭結(jié)點(diǎn)的單鏈表L，p=L->next指向表中的第一個(gè)結(jié)點(diǎn)a1，即p->data=a1，而p->next->data=a2。其余依此類推。1.查找算法描述：查找第i個(gè)結(jié)點(diǎn)，從頭指針L出發(fā)，順著鏈域掃描。用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)。當(dāng)j==i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。2.3.2單鏈表上的基本運(yùn)算2.單鏈表插入操作算法描述：

要在第i個(gè)位置插入元素e，需要找到第i-1個(gè)結(jié)點(diǎn)并由指針p指示，然后申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由指針s指示，其數(shù)據(jù)域的值為e。

修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向s，使s結(jié)點(diǎn)的指針域指向原第i個(gè)結(jié)點(diǎn)。插入：s->next=p->next;

p->next=s;在鏈表中插入一個(gè)元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結(jié)點(diǎn)應(yīng)預(yù)先生成：s=(LinkList)malloc(m);s->data=x;s->next=p->next;p->next=s;3.刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點(diǎn)相連free(q)；//刪除b結(jié)點(diǎn)，徹底釋放p->next思考：省略free(q)語句行不行？(p->next)->next××4.建立單鏈表圖2.10頭插法建立單鏈表圖示2）尾插法建表圖2.11尾插法建表圖示5.應(yīng)用舉例：兩個(gè)鏈表的歸并(教材P31)算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表LC存儲(chǔ)。假設(shè)：A=(3，5，8，11)，B=(2，6，8，9，11)預(yù)測(cè)：合并后C=(2,3,5,6,8,8,9,11，11)用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？6，其他形式的鏈表討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？答：能。只要定義一個(gè)結(jié)構(gòu)類型(含數(shù)據(jù)域和指示域)數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。具體實(shí)現(xiàn)過程見教材P31-34。討論2：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。特別：帶頭結(jié)點(diǎn)的空循環(huán)鏈表樣式H參見教材P35

特點(diǎn)：

1、從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。

2、操作僅有一點(diǎn)與單鏈表不同：循環(huán)條件單鏈表-----p=NULL或p->next=NULL循環(huán)鏈表-----p=head或p->next=head圖2.13循環(huán)鏈表討論3：?jiǎn)捂湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？答：能。只要把單鏈表再多開一個(gè)指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)(如樹結(jié)構(gòu))中將大量使用。這種有兩個(gè)指針的鏈表稱為雙向鏈表。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)。參見教材P35—39。特別：帶頭結(jié)點(diǎn)的空雙向鏈表樣式：圖2.14雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)

由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)與直接后繼結(jié)點(diǎn)變得非常方便。

設(shè)指針p指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立：p->prior->next=p=p->next->prior圖2.15雙向循環(huán)鏈表圖示1.雙向鏈表的前插操作圖2.16雙向鏈表插入操作2.雙向鏈表的刪除操作算法描述：圖2.17雙向鏈表的刪除操作要點(diǎn)回顧鏈表的表示(包括有關(guān)術(shù)語、結(jié)構(gòu)數(shù)據(jù)類型等)鏈表的實(shí)現(xiàn)(建表、輸出、修改、插入、刪除)