線性表的鏈式存儲結(jié)構(gòu)及其運算

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

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

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

typedef

structNode

{

DataTypedata;

structNode*next;

}SLNode;

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

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

：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和

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

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

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

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

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

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

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

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