線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其運(yùn)算

2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其運(yùn)算一、單鏈表的存儲(chǔ)結(jié)構(gòu)二、單鏈表的操作實(shí)現(xiàn)三、鏈表的運(yùn)算效率分析12.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的順序表示的特點(diǎn)是用物理位置上的鄰接關(guān)系來表示結(jié)點(diǎn)間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)存取表中的任一結(jié)點(diǎn)，但它也使得插入和刪除操作會(huì)移動(dòng)大量的結(jié)點(diǎn).為避免大量結(jié)點(diǎn)的移動(dòng)，我們介紹線性表的另一種存儲(chǔ)方式，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈表(LinkedList)。22.3.1線性鏈表鏈表是指用一組任意的存儲(chǔ)單元來依次存放線性表的結(jié)點(diǎn)，特點(diǎn)：這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：datalink3

其中：data域是數(shù)據(jù)域，用來存放結(jié)點(diǎn)的值。next是指針域（亦稱鏈域），用來存放結(jié)點(diǎn)的直接后繼的地址（或位置）。鏈表正是通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。

4１、單鏈?zhǔn)郊氨硎痉椒?1)單鏈表:構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針。其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針域數(shù)據(jù)域nextdata或樣式：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率一、單鏈表的存儲(chǔ)結(jié)構(gòu)5定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下:

typedef

structNode

{

DataTypedata;

structNode*next;

}SLNode;

其中,data域用來存放數(shù)據(jù)元素,next域用來存放指向下一個(gè)結(jié)點(diǎn)的指針。

6例：請(qǐng)畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1

：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和

。討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由

指示。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)71）結(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……循環(huán)鏈表示意圖：head(2)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：84）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭結(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)等信息，它不計(jì)入表長(zhǎng)度。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a０的結(jié)點(diǎn)。示意圖如下：9答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長(zhǎng)度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；^頭指針無頭結(jié)點(diǎn)^頭指針頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！10一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31２、帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較例：11上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！12

對(duì)比帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程和不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程，可以得知：

若設(shè)計(jì)的單鏈表帶頭結(jié)點(diǎn)，則無論是在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入都不會(huì)改變頭指針的數(shù)值。

若設(shè)計(jì)的單鏈表不帶頭結(jié)點(diǎn)，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入其算法的處理方法不同。在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。因此，單鏈表一般構(gòu)造成帶頭結(jié)點(diǎn)的單鏈表。13討論:鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型指針型設(shè)每個(gè)結(jié)點(diǎn)用變量node表示，其指針用p表示，兩個(gè)分量分別用data和*next表示，這兩個(gè)分量如何賦值？p*nextdatanode方式1：直接表示為

node.data＝'a'；node.next=q方式2：p指向結(jié)點(diǎn)首地址，然后p->data='a';p->next=q;方式3：p指向結(jié)點(diǎn)首地址，然后(*p).data='a'；(*p).next＝q‘a(chǎn)’‘b’qp14設(shè)p為指向鏈表的第i個(gè)元素的指針,則第i個(gè)元素的數(shù)據(jù)域?qū)憺?/p>

，指針域?qū)憺?/p>

。練習(xí)：p->dataai的值p->nextai+1的地址附1：介紹C的三個(gè)有用的庫(kù)函數(shù)/算符（都在<stdlib.h>中）：sizeof(x)——計(jì)算變量x的長(zhǎng)度（字節(jié)數(shù)）；malloc(m)—開辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；free(p)——釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。15sizeof(x)——計(jì)算x的長(zhǎng)度malloc(m)—開m字節(jié)空間free(p)——?jiǎng)h除一個(gè)變量問1：自定義結(jié)構(gòu)類型變量node的長(zhǎng)度m是多少？問2：結(jié)構(gòu)變量node的首地址(指針p）是多少？問3：怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長(zhǎng)度為m字節(jié)pm＝sizeof(node)//單位是字節(jié)p＝(node*)malloc(m)free(p)//只能借助node的指針刪除！P->data=‘a(chǎn)’;p->next=q16②對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：

SLNode*p,*q;//或用

struct

SLNode*p,*q;//注：上面已經(jīng)定義了SLNode為用戶自定義的Node類型。①類型定義和變量說明可以合寫為：typedef

structNode//Node是自定義結(jié)構(gòu)類型名稱{DataType

data;//定義數(shù)據(jù)域的變量名及其類型

structNode*next;//定義指針域的變量名及其類型}S