第2章(3)線性鏈表

河南科技大學計算機系第2章數據結構-線性鏈表軟件技術基礎第2頁本單元要點線性鏈表及其運算鏈棧鏈隊列循環(huán)鏈表第3頁（一）線性表的鏈式存儲結構線性表的順序存儲結構容易實現(xiàn)，可以隨機存取表中的任意元素。鏈表存儲結構在這兩個方面恰好是優(yōu)點：容易插入、刪除操作不需要預分空間。順序表缺點是：難于插入、刪除操作；需要預先分配空間，不管這些空間能否最大限度地利用。第4頁鏈式存儲結構特點其結點在存儲器中的位置是隨意的，即邏輯上相鄰的數據元素在物理上不一定相鄰。如何實現(xiàn)？通過指針來實現(xiàn)！讓每個存儲結點都包含兩部分：數據域和指針域指針數據指針數據指針或樣式：數據域：存儲元素數值數據指針域：存儲直接后繼或者直接前驅的存儲位置設計思想：犧牲空間效率換取時間效率1.鏈表的表示第5頁例：請畫出26個英文字母表的鏈式存儲結構。該字母表在內存中鏈式存放的樣式舉例如下：解：該字母表的邏輯結構為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1

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

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

指示。其直接前驅結點的鏈域的值指針域(鏈域)第6頁1）結點：數據元素的存儲映像。由數據域和指針域兩部分組成；2）鏈表：

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

結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。(2)與鏈式存儲有關的術語第7頁4）頭指針、頭結點和首元結點的區(qū)別頭指針頭結點首元結點a1heada2…infoan^頭指針是指向鏈表中第一個結點（或為頭結點、或為首元結點）的指針；頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息，它不計入表長度。首元結點是指鏈表中存儲線性表第一個數據元素a1的結點。示意圖如下：第8頁答：討論1.在鏈表中設置頭結點有什么好處？討論2.如何表示空表？頭結點即在鏈表的首元結點之前附設的一個結點，該結點的數據域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統(tǒng)一處理，編程更方便。答：無頭結點時，當頭指針的值為空時表示空表；^頭指針無頭結點^頭指針頭結點有頭結點有頭結點時，當頭結點的指針域為空時表示空表。頭結點不計入鏈表長度！第9頁上例鏈表的邏輯結構示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無頭結點②有頭結點頭結點不計入鏈表長度！第10頁討論:

鏈表的數據元素有兩個域，不再是簡單數據類型，編程時該如何表示？因每個結點至少有兩個分量，且數據類型通常不一致，所以要采用結構數據類型。答：以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’qp第11頁設p為指向鏈表的第i個元素的指針,則第i個元素的數據域寫為

，指針域寫為

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

node*p,*q;

//或用

struct

liuyu

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

liuyu

//liuyu是自定義結構類型名稱{chardata;//定義數據域的變量名及其類型

struct

liuyu*next;//定義指針域的變量名及其類型}node，*pointer;//node是liuyu結構類型的類型替代,

*pointer是指針型的liuyu結構類型的替代，也是數據類型*/補充：結構數據類型的C表示法第14頁單鏈表的抽象數據類型描述如下typedefstructLnode{ElemTypedata;//數據域

structLnode*next;//指針域}Lnode,*LinkList;//*LinkList為Lnode類型的指針如何具體編程來建立和訪問鏈表？——鏈表的實現(xiàn)第15頁typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;線性表的單鏈表存儲結構描述:問題討論：Q1：第一行的Lnode

與最后一行的Lnode是不是一回事？A1：不是。前者Lnode是結構名，后者Lnode是對整個struct類型的一種“縮寫”，是一種“新定義名”，它只是對現(xiàn)有類型名的補充，而不是取代。請注意：typedef不可能創(chuàng)造任何新的數據類型，而僅僅是在原有的數據類型中命名一個新名字，其目的是使你的程序更易閱讀和移植。第16頁TypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;Q2：為何兩處要同名(Lnode和Lnode）？A2：同名是為了表述起來方便。例如，若結構名為Lnode，其新定義名縮寫也最好寫成Lnode，因為描述的對象相同，方便閱讀和理解。Q3：結構體中間的那個struct

Lnode是何意？A3：在“縮寫”

Lnode還沒出現(xiàn)之前，只能用原始的structLnode來進行變量說明。此處說明了指針分量的數據類型是struct

Lnode。typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;第17頁2.鏈表的實現(xiàn)（1）單鏈表的建立和輸出（2）單鏈表的修改（3）單鏈表的插入（4）單鏈表的刪除第18頁（1）鏈表的動態(tài)生成鏈表是一種動態(tài)存儲結構。因此，建立鏈表的過程是動態(tài)生成的過程。

按鏈表結點建立的順序、方向不同，分為兩種方法：從前往后的動態(tài)生成法從后往前的動態(tài)生成法第19頁鏈表的動態(tài)生成（方法一）：從前往后算法操作步驟：step1初始化；頭指針置NULLstep2輸入結點數據,(非0)循環(huán)

1)使s指向新生成的結點，s->data=num2)若head=NULL(第1個結點),head=p=s，否則p->next=s3)指針p始終指向s,p=sstep3結束循環(huán),p->next=NULL,返回頭指針head。shead

^...paiai-1a2a1第20頁鏈表的動態(tài)生成（方法二）：從后往前

算法操作步驟：Step1初始化；頭指針置NULLStep2輸入結點數據,(非0)循環(huán)

1)使s指向新生成的結點，2)s->data=num，s->next=head3)頭指針始終指向s，head=sstep3結束循環(huán),

返回頭指針head。shead

^...

aiai-1a1ai+1第21頁單鏈表的建立和輸出舉例例：從鍵盤輸入n個字符，以’0’作為結束標記，產生不帶表頭的單鏈表，請寫出C語言程序。（從后往前生成）實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結點開辟存儲空間并及時賦值，后繼結點的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！第22頁#include<stdio.h>#include<stdlib.h>TypedefstructLnode{chardata;structLnode*next;}Lnode,*LList;將全局變量及函數提前說明：intm=sizeof(Lnode);/*結構類型定義好之后，每個Lnode類型的長度就固定了，m求一次即可*/第23頁{ charch; Lnode*head,*s; /*s為工作指針，head為頭指針*/ head=NULL;

/*鏈表開始為空*/

printf(“pleaseinputdata,use‘0’astheendflag\n"); scanf(“%c”,&ch);/*輸入字符*/ while(ch!=‘0’) {s=(Lnode*)malloc(sizeof(Lnode));/*生成新結點*/ s->data=ch; s->next=head;/*置新結點的數據域和指針域*/ head=s; scanf("%c",&ch); } returnhead; /*返回頭指針*/}Lnode*Create(void)//字符鏈表的生成，從后往前生成或者：s=(Lnode*)malloc(m);或者：LListhead,s;第24頁{Lnode*p;p=head;while(p)//當指針不空時循環(huán)（僅限于無頭結點的情況）

{printf("%c",p->data);

p=p->next;

//讓指針不斷“順藤摸瓜”

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

sum++;sum=0;voiddisplay(Lnode*head)/*鏈表的輸出*/第25頁（2）單鏈表的修改(或讀取/查找）

舉例:設有數列{4,5,8,10,21,30,43,59}，長度為8，輸入一個結點值30，顯示該結點的位置。第26頁算法單鏈表查找算法

Lnode*get(Lnode*head,charx）｛Lnode*p=head;/*從頭結點開始比較*/intcount=1;while((p!=NULL)&&(p->data!=x))

/*直到p為NULL或p->data是x為止*/{p=p->next;count++;}

/*掃描下一結點*/if(p==NULL)printf("找不到該元素\n"); elseprintf("找到了，它的位置是:%d\n",count); returnp;}第27頁在鏈表中插入一個元素X的示意圖如下：Xsabp鏈表插入的核心語句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和2能互換么？X結點的生成方式：s=(Lnode*)malloc(m);s->data=X;s->next=?bap插入X（3）單鏈表的插入第28頁單鏈表的插入算法程序(將x插入到值為b的結點前）

LListinsert(Lnode*head,charb,charx){ Lnode*p,*q; p=(Lnode*)malloc(sizeof(Lnode));//申請一個新結點

p->data=x;//置新結點的數據域

if(head==NULL)//原鏈表為空

{head=p;p->next=NULL;returnhead;} if(head->data==b)//在第一個結點前插入

{p->next=head;head=p;returnhead;} q=head; while((q->next!=NULL)&&(((q->next)->data)!=b)) q=q->next;//尋找包含元素b的前一個結點q

p->next=q->next;q->next=p;//新結點p插入到結點q之后

returnhead;}第29頁在鏈表中刪除某元素b的示意圖如下：cabp刪除動作的核心語句（要借助輔助指針變量q）：q=p->next;//首先保存b的指針，靠它才能找到c；p->next=q->next;//將a、c兩結點相連，淘汰b結點；free(q)；//徹底釋放b結點空間p->next思考：省略free(q)語句行不行？(p->next)->next××q（4）單鏈表的刪除第30頁單鏈表的刪除算法程序(刪除單鏈表中值為b的結點）LListdelete(LListhead,charb){ Lnode*p,*q; if(head==NULL)returnhead;//鏈表為空，無刪除的元素

if((head->data)==b)//刪除第一個結點

{p=head->next;free(head);head=p;returnhead;}q=head; while((q->next!=NULL)&&(((q->next)->data)!=b)) q=q->next;//尋找包含元素b的前一個結點qif(q->next==NULL)returnhead;//鏈表中無刪除的元素

p=q->next;q->next=p->next;//刪除q的下一個結點pfree(p);//釋放結點p的存儲空間

returnhead;}第31頁3.鏈表的運算效率分析（1）查找

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

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

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

O(1)。但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅結點，所耗時間復雜度將是

O(n)。第32頁討論1：

順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？

順序存儲時，邏輯上相鄰的數據元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。

鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。

順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。第33頁討論2：什么是指針？指針的作用？

指針—即變量的內存地址。指針主要功能有二：①提供了一種快速訪問數組單元的途徑；②使C語言函數可以修改其調用的參數。

&---指針操作符（單目），返回操作數地址；

*---運算符（單目），是對&的補充，返回位于這個地址內的變量之值。例：q=*m意即“q取地址m中的值”。如果數值100存儲在內存地址2000中，而這一地址又存在m中，則q=(2000)=100討論3：與指針有關的符號&和*之間有何區(qū)別？第34頁預告第1次上機內容：單鏈表的運算（含鏈表的建立、輸出、查找、插入、刪除等）上機時間：待定上機地點：待定第35頁（二）鏈棧(1)鏈棧的構造方式——以頭指針為棧頂，在頭指針處插入或刪除.Node*st,*p;intm=sizeof(Node);棧頂棧底棧也可以用鏈式結構來表示，用鏈式結構來表示的棧就是鏈棧sta1a2an-1annextdata鏈棧中每個結點由兩個域構成：data域和next域，其定義為：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;第36頁Push(SElemTypee)

{p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->next=st;st=p;}}

StatusPop()

{if(st==NULL){下溢}else{e=st->data;p=st;st=st->next;

free(p);return(e);}}鏈棧入棧函數鏈棧出棧函數插入表頭從表頭刪除(2)操作由此可以看出：一個鏈棧由其棧頂指針唯一指定設st指向棧頂元素，當st=NULL時表示?？盏?7頁鏈棧不必設頭結點，因為棧頂（表頭）操作頻繁；鏈棧一般不會出現(xiàn)棧滿情況，除非沒有空間導致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂的插入與刪除操作，修改指針即可完成。幾點說明:第38頁鏈隊列類型定義：

typedefstruct{QueuePtrfront;//隊首指針

QueuePtrrear;//隊尾指針

}LinkQueue;結點類型定義：

typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結點的指針}Qnode,*QueuePtr;關于整個鏈隊的總體描述鏈隊中任一結點的結構（三）鏈隊列第39頁討論：空鏈隊的特征？Q(隊尾)(隊首)fronta1a2a3^rearpfront^rear③怎樣實現(xiàn)鏈隊的入隊和出隊操作？②鏈隊會滿嗎？front=rear一般不會，因為刪除時有free動作。除非內存不足！入隊（尾部插入）：rear->next=S;rear=S;出隊（頭部刪除）：front->next=p->next;SD^鏈隊示意圖：第40頁（1）單鏈表中存在的問題：在運算過程中對于空表與對第一個結點的處理必須單獨考慮，從而使空表與非空表的運算不統(tǒng)一。head...a1a2an（四）循環(huán)鏈表（2）循環(huán)鏈表的特點：增加了一個表頭結點，循環(huán)鏈表的頭指針指向表頭結點。最后一個結點的指針域不是空，而是指向表頭結點。循環(huán)鏈表示意圖：第41頁（3）循環(huán)鏈表的優(yōu)點：從任一結點出發(fā)可訪問到表中其它所有結點，線性單鏈表無法實現(xiàn)。任何情況下，循環(huán)鏈表中至少有一個結點存在，從而使空表與非空表運