第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)1鏈式存儲結(jié)構(gòu)2.2節(jié)小結(jié)線性表順序存儲結(jié)構(gòu)特點：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；優(yōu)點：可以隨機存取表中任一元素，方便快捷；O(1)缺點：在插入或刪除某一元素時，需移動大量元素O(n)解決問題的思路：改用另一種線性存儲方式：22.3線性表的鏈式表示和實現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實現(xiàn)2.3.3鏈表的運算效率分析3其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實現(xiàn)？通過指針來實現(xiàn)！讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和指針域指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼或者直接前驅(qū)的存儲位置設(shè)計思想：犧牲空間效率換取時間效率2.3.1鏈表的表示(1)鏈式存儲結(jié)構(gòu)特點：4例：請畫出26個英文字母表的鏈式存儲結(jié)構(gòu)。該字母表在內(nèi)存中鏈式存放的樣式舉例如下：解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）鏈表存放示意圖下：a1heada2/\an……討論1：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和討論2：在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由

指示。其直接前驅(qū)結(jié)點的鏈域的值指針域(鏈域)51）結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：

n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：

結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……循環(huán)鏈表示圖：head(2)與鏈式存儲有關(guān)的術(shù)語：64）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭結(jié)點首元結(jié)點a1heada2…infoan^頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息，它不計入表長度。首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。示意圖如下：7答：討論1.在鏈表中設(shè)置頭結(jié)點有什么好處？討論2.如何表示空表？頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理，編程更方便。答：無頭結(jié)點時，當頭指針的值為空時表示空表；^頭指針無頭結(jié)點^頭指針頭結(jié)點有頭結(jié)點有頭結(jié)點時，當頭結(jié)點的指針域為空時表示空表。頭結(jié)點不計入鏈表長度！8例1：一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。7ZHAOH31稱：頭指針H的值是31（3）舉例9上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點②有頭結(jié)點頭結(jié)點不計入鏈表長度！10線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一個具有五個元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲在下列100～119號地址空間中，每個結(jié)點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)）組成，如下圖所示。其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點起始地址為多少？末結(jié)點的起始地址為多少？Z47Y31V23X17U05100119104108116112116NULL/0100108112答：X=

Y=

Z=

,首址=

末址=

。例2：和11②對于指向結(jié)構(gòu)類型的指針變量，可說明為：

node*p,*q;

或用struct

liuyu

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

//liuyu是自定義結(jié)構(gòu)類型名稱{chardata;//定義數(shù)據(jù)域的變量名及其類型structliuyu*next;//定義指針域的變量名及其類型}node，*pointer;//node是liuyu結(jié)構(gòu)類型的類型替代

//

*pointer是指針型的liuyu結(jié)構(gòu)類型的替代附:補充結(jié)構(gòu)數(shù)據(jù)類型的C表示法12討論:

鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：以26個字母的鏈表為例，每個結(jié)點都有兩個分量：字符型指針型設(shè)每個結(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’qp13設(shè)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所指變量的存儲空間，即徹底刪除一個變量。14sizeof(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=q151.單鏈表如何實現(xiàn)———建表和輸出例：用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲空間并及時賦值，后繼結(jié)點的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”16#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;將全局變量及函數(shù)提前說明：node*p,*q,*head;//一般需要3個指針變量intn;//數(shù)據(jù)元素的個數(shù)intm=sizeof(node);/*結(jié)構(gòu)類型定義好之后，每個node類型的長度就固定了，m求一次即可*/17新手特別容易忘記??！{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i<26;i++)//因尾結(jié)點要特殊處理，故i≠26{p->data=i+‘a(chǎn)’-1;//第一個結(jié)點值為字符ap->next=(node*)malloc(m);//為后繼結(jié)點“挖坑”！p=p->next；}

//讓指針變量P指向后一個結(jié)點p->data=i+‘a(chǎn)’-1;//最后一個元素要單獨處理p->next=NULL;}//單鏈表尾結(jié)點的指針域要置空！voidbuild()//字母鏈表的生成。要一個個慢慢鏈入18{p=head;while(p)//當指針不空時循環(huán)（僅限于無頭結(jié)點的情況）{

printf("%c",p->data);p=p->next;//讓指針不斷“順藤摸瓜”

}}討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？

sum++;sum=0;voiddisplay()//字母鏈表的輸出192.單鏈表的修改(或讀?。┧悸罚阂薷牡趇個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針p，然后才能：p>data=new_value。缺點：想尋找單鏈表中第i個元素，只能從頭指針開始逐一查詢（順藤摸瓜），無法隨機存取。讀取第i個數(shù)據(jù)元素的核心語句是：StatusGetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=1;

//假設(shè)是帶有頭結(jié)點的鏈表while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;}203.單鏈表的插入在鏈表中插入一個元素X的示意圖如下：Xsabp鏈表插入的核心語句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和2能互換么？X結(jié)點的生成方式：S=(node*)malloc(m);S->data=X;S->next=p->nextbap插入X214.單鏈表的刪除在鏈表中刪除某元素b的示意圖如下：cabp刪除動作的核心語句（要借助輔助指針變量q）：q=p->next;//首先保存b的指針，靠它才能找到c；p->next=q->next;//將a、c兩結(jié)點相連，淘汰b結(jié)點；free(q)；//徹底釋放b結(jié)點空間p->next思考：省略free(q)語句行不行？(p->next)->next××q22

5.雙鏈表

討論：單鏈表只能查找結(jié)點的直接后繼，若想查找結(jié)點的直接前驅(qū)，該如何設(shè)計？答：只要把單鏈表再多開一個指針域即可(例如用*next和*prior)。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。priordatanext這種鏈表稱為雙向鏈表。其特點是可以雙向查找表中結(jié)點。23雙向鏈表的插入操作：設(shè)p已指向第i元素，請在第i元素前插入元素x①ai-1的后繼從ai(指針是p)變?yōu)閤（指針是s):s->next=p;

p->prior->next=s;

②ai的前驅(qū)從ai-1(指針是p->prior)變?yōu)閤(指針是s);s->prior=p->prior;p->prior=s;

注意：要修改雙向指針！x

sai-1

ai

p指針域的變化：24指針域的變化：后繼方向：ai-1的后繼由ai(指針p)變?yōu)閍i+1(指針p->next

);

p->prior->next

=

p->next;前驅(qū)方向：ai+1的前驅(qū)由ai(指針p)變?yōu)閍i-1(指針p->prior

);

p->next->prior

=p->prior;

ai-1

ai+1

ai

p雙向鏈表的刪除操作：設(shè)p指向第i個元素，刪除第i個元素注意：要修改雙向指針！252.3.3.鏈表的運算效率分析1.查找

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為

O(n)。時間效率分析2.插入和刪除

因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為

O(1)。

但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是O(n)。26例題：在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的