課件線性表的鏈?zhǔn)酱鎯?chǔ)

單鏈表

1

2

3

4

5

6

7

datanext

邏輯上相鄰的兩個(gè)元素在物理位置上不相鄰單鏈表結(jié)點(diǎn)的定義：

typedefstructLNode{ //單鏈表結(jié)點(diǎn)類型

ElemTypedata; //數(shù)據(jù)域

structLNode*next; //指針域

}LNode,*LinkList;

單鏈表

L

a1

a2

a3

annull

頭指針

頭指針：鏈表中第一個(gè)結(jié)點(diǎn)的

頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)，為了操作上的方便。

位置，用來標(biāo)識(shí)單鏈表。

若鏈表有頭結(jié)點(diǎn)，則頭指針

空，頭指針是鏈表的必須元素，他標(biāo)識(shí)一個(gè)鏈表。

頭結(jié)點(diǎn)是為了操作的方便而設(shè)立的，其數(shù)據(jù)域一般為空，或者存放鏈表的長(zhǎng)度。有頭結(jié)點(diǎn)后，對(duì)在第一結(jié)點(diǎn)前插入和刪除第一結(jié)點(diǎn)的操作就統(tǒng)一了，不需要頻繁重置頭指針。但頭結(jié)點(diǎn)不是必須的。

指向頭結(jié)點(diǎn)，不論鏈表是否為空，頭指針均不為

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

缺點(diǎn)

插入和刪除操作不需要移動(dòng)元素，只需要修改指針。

不需要大量的連續(xù)

空間。

單鏈表附加指針域，也存在浪費(fèi)

查找操作時(shí)需要從表頭開始遍歷，依次查找，不能隨機(jī)存取。

空間的缺點(diǎn)。

插入操作

a1

p

q

p

q

（b）中間插入元素

ai-1

X

X

（a）表頭插入元素

ai

創(chuàng)建新結(jié)點(diǎn)代碼：q=(LNode*)malloc(sizeof(LNode))q->data=x;

(a)(b)操作的代碼：q->next=p->next;p->next=q;

p

an^

(c)操作的代碼：

q

>next=q;

>next=NULL;

//請(qǐng)分別用頭插法和法創(chuàng)建一個(gè)單鏈表

（c）表 入元素

刪除操作

a1

a2

p

q

（a）表頭刪除元素

ai-1

ai

ai+1

p

q

（b）中間刪除元素

(a)(b)(c)操作的代碼：

p=Geem(L,i-1);//查找刪除位置的前驅(qū)節(jié)點(diǎn)

q=p->next;

an^

X

^

p

q

p->next=q->next;(q);

（c）表尾刪除元素

查找操作

按序號(hào)查找結(jié)點(diǎn)值的算法如下：

LNode*p=L->next;

intj=1;while(p&&j<i){

p=p->next;j++;

}

returnp;

p

a2

a1

ai-1

a3

an

查找操作

按值查找結(jié)點(diǎn)的算法如下：

LNode*p=L->next;while(p!=NULL&&