大学《数据结构》第二章：线性表-第三节-线性表的链式存储结构（二）

第三节线性表的链式存储结构（二）

二、单链表上的基本运算（考试最重要的内容）

1、单链表的建立

动态建立单链表的常用方法有两种：一种是头插法，另一种则是尾

插法。

（1）头插法建表：从一个空表开始，重复读入数据，生成新结

点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当

前链表的表头上，直到读入结束标志为止。

开始结点___________-手结点

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

z〃L一I1]।

算法描述:

LinkListCreateListF()

{LinkListhead;

ListNode*p;

charch;

head=NULL;〃置空单链表

ch=getchar();〃读入第一

个字符

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

是结束标志符时作循环

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

个类型为ListNode的结点的地址空问，并将其首地址存入指针变量p

中。

p->data=ch;〃数据域赋值

p->next=head;〃指针域赋值

head=p;〃头指针指向

新结点

ch=getchar();〃读入下一

个字符

)

returnhead;〃返回链表

的头指针

)

(2)尾插法：将新结点插入在当前链表的表尾上，因此需要增设

一个尾指针rear，使其始终指向链表的尾结点。

开始结点终端结点

re

head---------►1a|-|_A|b|T->1^|；|<~~力一¥

PL—41d|A|

算法描述：

LinkListCreateListR()

{LinkListhead,rear;

ListNode*p;

charch;

head=NULL;rear=NULL;〃置空

单链表

ch=getchar();〃读入

第一个字符

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

符不是结束标志符时作循环

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

请新结点

p->data=ch;〃数据

域赋值

if(head==NULL)head=p;〃新结

点*p插入空表

elserear->next=p;//新结

点*p插入到非空表的表尾结点*rear之后

rear=p,〃表尾指

针指向新的表尾结点

ch=getchar();〃读入

下一个字符

)

if(rear!=NULL)rear->next=NULL;〃终端结

点指针域置空

returnhead;

)

带头结点的单链表：作用是可以简化单链表的算法

在引入头结点之后，尾插法建立单链表的算法可简化为：

LinkListCreateLlstRIO〃尾插法

建立带头结点的单链表算法

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

请头结点

ListNode*p,*r;

DataTypech;

r=head;//尾指针初始

指向头结点

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

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

结点

p->data=ch;

r->next=p;〃新结点连接

到尾结点之后

r=p；〃尾指针指向新

结点

)

r->next=NULL;〃终端结点指针

域置空

returnhead;

)

真题选解

(例题・单选题)L在带头结点的单链表h中，若要向表头插入一

个由指针p所指向的结点，则执行()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

【解析】向表头插入，即在第一个结点之前插入，这就要把第一个

结点链接到p结点之后，而将p结点链接到头结点之后。

2、查找运算

(1)在单链表中要直找第i个结点

算法描述

ListNode*GetNodei(LinkListhead,inti)

{//head为带头结点的单链表的头指针，i为要查找的结点序号

ListNode*p;intj;

p=head->next;j=l;〃使P指向第一个结点，j置

1

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

向第i个结点或p为空为止

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

)

if(j==i)〃若查找成功，则返回查找结点

的存储地址(位置)，否则返回NULL

returnp;

else

returnNULL;

)

算法分析

①最好情况是查找第1个元素，循环执行0次

②最坏情况是查找第n+1个元素，循环执行n次。

③在等概率情况下，循环执行次数为：(n+(n-l)+(n-2)

+...+2+1+0)/(n+l)=n/2。故算法平均时间复杂性是O

(n)o

(2)在单链表中查找值为k的结点

算法描述

LiStNode*LocateNodek(LinkListhead,DataTypek)

{//head为带头结点的单链表的头指针，k为要查找的结点值

ListNode*p=head->next;//p指向开始结点

while(p&&p->data!=k)〃循环直到p等于NULL或

p->data等于k为止

p=p->next;〃指针指向下一个结点

returnp;〃若找到值为k的结点，则p指向该结点,否则p

为NULL

)

算法分析

①最好情