大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第二章：線性表-第三節(jié)-線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（二）

第三節(jié)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（二）

二、單鏈表上的基本運(yùn)算（考試最重要的內(nèi)容）

1、單鏈表的建立

動(dòng)態(tài)建立單鏈表的常用方法有兩種：一種是頭插法，另一種則是尾

插法。

（1）頭插法建表：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)

點(diǎn)，將讀入的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)

前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。

開始結(jié)點(diǎn)___________-手結(jié)點(diǎn)

迷ad/c|T-----?!bI—I-----?!aIA

z〃L一I1]?

算法描述:

LinkListCreateListF()

{LinkListhead;

ListNode*p;

charch;

head=NULL;〃置空單鏈表

ch=getchar();〃讀入第一

個(gè)字符

while(ch!='\n')〃讀入字符不

是結(jié)束標(biāo)志符時(shí)作循環(huán)

{p=(ListNode*)malloc(sizeof(ListNode));〃分配一

個(gè)類型為ListNode的結(jié)點(diǎn)的地址空問，并將其首地址存入指針變量p

中。

p->data=ch;〃數(shù)據(jù)域賦值

p->next=head;〃指針域賦值

head=p;〃頭指針指向

新結(jié)點(diǎn)

ch=getchar();〃讀入下一

個(gè)字符

)

returnhead;〃返回鏈表

的頭指針

)

(2)尾插法：將新結(jié)點(diǎn)插入在當(dāng)前鏈表的表尾上，因此需要增設(shè)

一個(gè)尾指針rear，使其始終指向鏈表的尾結(jié)點(diǎn)。

開始結(jié)點(diǎn)終端結(jié)點(diǎn)

re

head---------?1a|-|_A|b|T->1^|；|<~~力一￥

PL—41d|A|

算法描述：

LinkListCreateListR()

{LinkListhead,rear;

ListNode*p;

charch;

head=NULL;rear=NULL;〃置空

單鏈表

ch=getchar();〃讀入

第一個(gè)字符

while(ch!='\n')〃讀入字

符不是結(jié)束標(biāo)志符時(shí)作循環(huán)

{p=(ListNode*)malloc(Sizeof(ListNode));〃申

請新結(jié)點(diǎn)

p->data=ch;〃數(shù)據(jù)

域賦值

if(head==NULL)head=p;〃新結(jié)

點(diǎn)*p插入空表

elserear->next=p;//新結(jié)

點(diǎn)*p插入到非空表的表尾結(jié)點(diǎn)*rear之后

rear=p,〃表尾指

針指向新的表尾結(jié)點(diǎn)

ch=getchar();〃讀入

下一個(gè)字符

)

if(rear!=NULL)rear->next=NULL;〃終端結(jié)

點(diǎn)指針域置空

returnhead;

)

帶頭結(jié)點(diǎn)的單鏈表：作用是可以簡化單鏈表的算法

在引入頭結(jié)點(diǎn)之后，尾插法建立單鏈表的算法可簡化為：

LinkListCreateLlstRIO〃尾插法

建立帶頭結(jié)點(diǎn)的單鏈表算法

{LinkListhead=(ListNode*)malloc(Sizeof(ListNode));〃申

請頭結(jié)點(diǎn)

ListNode*p,*r;

DataTypech;

r=head;//尾指針初始

指向頭結(jié)點(diǎn)

while((ch=getchar())!='\n')

{p=(ListNode*)malloc(sizeof(ListNode));〃申請新

結(jié)點(diǎn)

p->data=ch;

r->next=p;〃新結(jié)點(diǎn)連接

到尾結(jié)點(diǎn)之后

r=p；〃尾指針指向新

結(jié)點(diǎn)

)

r->next=NULL;〃終端結(jié)點(diǎn)指針

域置空

returnhead;

)

真題選解

(例題?單選題)L在帶頭結(jié)點(diǎn)的單鏈表h中，若要向表頭插入一

個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行()o

A.h=p;p->next=h;B.p->next=h;h=p;

C.p->next=h;p=h;D.p->next=h->next;

h->next=p;

隱藏答案

【答案】D

【解析】向表頭插入，即在第一個(gè)結(jié)點(diǎn)之前插入，這就要把第一個(gè)

結(jié)點(diǎn)鏈接到p結(jié)點(diǎn)之后，而將p結(jié)點(diǎn)鏈接到頭結(jié)點(diǎn)之后。

2、查找運(yùn)算

(1)在單鏈表中要直找第i個(gè)結(jié)點(diǎn)

算法描述

ListNode*GetNodei(LinkListhead,inti)

{//head為帶頭結(jié)點(diǎn)的單鏈表的頭指針，i為要查找的結(jié)點(diǎn)序號

ListNode*p;intj;

p=head->next;j=l;〃使P指向第一個(gè)結(jié)點(diǎn)，j置

1

while(p!=NULL&&j<i)〃順指針向后查找，直到p指

向第i個(gè)結(jié)點(diǎn)或p為空為止

{p=p->next;++j;

)

if(j==i)〃若查找成功，則返回查找結(jié)點(diǎn)

的存儲地址(位置)，否則返回NULL

returnp;

else

returnNULL;

)

算法分析

①最好情況是查找第1個(gè)元素，循環(huán)執(zhí)行0次

②最壞情況是查找第n+1個(gè)元素，循環(huán)執(zhí)行n次。

③在等概率情況下，循環(huán)執(zhí)行次數(shù)為：(n+(n-l)+(n-2)

+...+2+1+0)/(n+l)=n/2。故算法平均時(shí)間復(fù)雜性是O

(n)o

(2)在單鏈表中查找值為k的結(jié)點(diǎn)

算法描述

LiStNode*LocateNodek(LinkListhead,DataTypek)

{//head為帶頭結(jié)點(diǎn)的單鏈表的頭指針，k為要查找的結(jié)點(diǎn)值

ListNode*p=head->next;//p指向開始結(jié)點(diǎn)

while(p&&p->data!=k)〃循環(huán)直到p等于NULL或

p->data等于k為止

p=p->next;〃指針指向下一個(gè)結(jié)點(diǎn)

returnp;〃若找到值為k的結(jié)點(diǎn)，則p指向該結(jié)點(diǎn),否則p

為NULL

)

算法分析

①最好情