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

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

4１、單鏈式及表示方法(1)單鏈表:構成鏈表的結點只有一個指向直接后繼結點的指針。其結構特點：邏輯上相鄰的數據元素在物理上不一定相鄰。如何實現？通過指針來實現！讓每個存儲結點都包含兩部分：數據域和指針域指針域數據域nextdata或樣式：數據域：存儲元素數值數據指針域：存儲直接后繼的存儲位置設計思想：犧牲空間效率換取時間效率一、單鏈表的存儲結構5定義單鏈表結點的結構體如下:

typedef

structNode

{

DataTypedata;

structNode*next;

}SLNode;

其中,data域用來存放數據元素,next域用來存放指向下一個結點的指針。

6例：請畫出26個英文字母表的鏈式存儲結構。該字母表在內存中鏈式存放的樣式舉例如下：解：該字母表的邏輯結構為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1

：每個存儲結點都包含兩部分：數據域和

。討論2：在單鏈表中，除了首元結點外，任一結點的存儲位置由

指示。其直接前驅結點的鏈域的值指針域(鏈域)71）結點：數據元素的存儲映像。由數據域和指針域兩部分組成；2）鏈表：n個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構。3）單鏈表、雙鏈表、多鏈表、循環鏈表：結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環鏈表。a1heada2an……循環鏈表示意圖：head(2)與鏈式存儲有關的術語：84）頭指針、頭結點和首元結點的區別頭指針頭結點首元結點a1heada2…infoan^頭指針是指向鏈表中第一個結點（或為頭結點、或為首元結點）的指針；頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息，它不計入表長度。首元結點是指鏈表中存儲線性表第一個數據元素a０的結點。示意圖如下：9答：討論1.在鏈表中設置頭結點有什么好處？討論2.如何表示空表？頭結點即在鏈表的首元結點之前附設的一個結點，該結點的數據域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理，編程更方便。答：無頭結點時，當頭指針的值為空時表示空表；^頭指針無頭結點^頭指針頭結點有頭結點有頭結點時，當頭結點的指針域為空時表示空表。頭結點不計入鏈表長度！10一個線性表的邏輯結構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結構用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數據域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結點的指針，因此關鍵是要尋找第一個結點的地址。7ZHAOH31稱：頭指針H的值是31２、帶頭結點單鏈表和不帶頭結點單鏈表的比較例：11上例鏈表的邏輯結構示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區別：①無頭結點②有頭結點頭結點不計入鏈表長度！12

對比帶頭結點的單鏈表的插入、刪除過程和不帶帶頭結點的單鏈表的插入、刪除過程，可以得知：

若設計的單鏈表帶頭結點，則無論是在第一個數據元素結點前插入還是在其他數據元素結點前插入都不會改變頭指針的數值。

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

node.data＝'a'；node.next=q方式2：p指向結點首地址，然后p->data='a';p->next=q;方式3：p指向結點首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp14設p為指向鏈表的第i個元素的指針,則第i個元素的數據域寫為

，指針域寫為

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

SLNode*p,*q;//或用

struct

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

structNode//Node是自定義結構類型名稱{DataType

data;//定義數據域的變量名及其類型

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