资源简介

(共21张PPT)
二、 链表及其基本操作
信息技术 选择性必修1 数据与数据结构
第二章　数组与链表
知识过关
1. 链表的概念
(1)链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。
(2)每个节点一般包括两个区域:数据区域和指针区域。
(3)每个链表有一个表头——head(也称头指针),是链表的入口,也便于循环链表在数据处理时的边界判断和处理。
(4)链表的形式。
链表的形式主要有单向链表、双向链表和循环链表。
①单向链表:只有一个指针用来指向其后继节点。单向链表如图所示。
②双向链表:有两个指针分别用于指向其前驱节点和后继节点。双向链表如图所示。
③循环链表:第一个节点和最后一个节点使用指针链接。循环链表如图所示。
2. 链表的特性
(1)同一链表中每个节点的结构均相同,由数据区域和指针区域组成。
(2)每个链表必定有一个头指针,以实现对链表的引用和边界处理。
(3)链表占用的空间不固定。
可根据需求增删节点,提高存储空间的利用率。
3. 链表的基本操作
(1)链表的创建。
(2)链表节点的访问。
链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。
(3)链表节点的插入与删除。
插入操作:
插入datax节点
删除data2节点
(4)链表节点的访问与遍历。
访问链表中的节点时,只能通过头指针进入链表并通过指针链接依次访问,直到找到目标位置上的节点。
*4. 链表的类实现
在Python中,链表除了可以使用列表来实现,还可以使用“类”来实现。“类”是一种抽象的数据结构,它将数据及其操作封装在一起。构造单向链表类的具体实现过程如下:
(1)自定义单向链表的节点类:
class Node:　　　#定义单链表节点类
　　def_init_(self,data,next_=None):
#初始化节点包含两个域self.data、self.next
　　　self.data=data　#self.data域保存数据
　　　self.next=next　#self.next域保存指针,缺省值为None
(2)构造单向链表类:
class Link:　　　#定义单向链表类Link
　　def_init_(self):　#初始化空链表
　　　　self._head=None　#空链表头指针指向为空
典例精选
【例1】 下列关于链表的说法,错. 误. 的是(　　)
A. 插入、删除操作不需要移动数据元素
B. 增加或减少节点会改变链表占用的存储空间
C. 可随机快速访问任何一个数据元素
D. 同一链表中每个节点的结构均相同
【解析】 可随机快速访问数据元素的是数组结构,原因是数组结构不仅在逻辑上相邻,其物理存储位置也相邻。但链表的物理存储位置可能是随机的,C符合题意。
C
【例2】 (2024·浙江6月选考)使用列表d模拟链表结构(节点数n>0),如图1所示,每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,最终保持节点链接关系不变,结果如图2所示。实现上述功能的Python程序段如下,方框中应填入的代码是(　　)
　　p,i = h,0
　　while p!=－1:
　　　　tp = d[p][1]
　　　　if p == i:
　　　　　　i+= 1
　　　　elif p>i:
　　　　　　d[i][0],d[p][0] = d[p][0],d[i][0]
　　　　　　　　　　　　
　　　　　　i+= 1
　　　　p = tp
# 调整头指针h及指针区域,保持节点链接关系不变,代码略
图2
图1
(　　)
A. d[i][1] = d[p][1]
d[p][1] = i
B. d[p][1] = d[i][1]
d[i][1] = p
C. d[i][1] = p
d[p][1] = d[i][1]
D. d[p][1] = i
d[i][1] = d[p][1]
B
【解析】 本题考查链表的节点操作。根据题意可知,当前节点为p节点,p从头结点开始进行遍历。而变量i是从0开始顺序增加的,当p和i相等时,意味着链表是按链表顺序依次存放到d[0][0]、d[1][0]…d[n－1][0]的,即已经符合题意,此时只需依次进行简单的迭代即可。若p和i不相等,即数据的存放不符合题意,由于i是从0开始的,因此若p和i不等则肯定是p>i,此时由代码可知将节点i和节点p的数据域进行交换,由于在链表中p的位置比节点i更加靠前,即p→i。而数据交换后两者的关系刚好逆转了,即i→p,因此可以先删除节点i,然后将节点i插入到p节点的前面,这样即可实现题意,故先执行代码 d[p][1]=d[i][1],删除节点i,然后再将节点i指向节点p,故代码为d[i][1]=p。以此类推直到循环结束。至此，链表已实现按照顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,但循环结束后,还需要修改头指针h的值,以及重新调整每个节点的指针域数据(即代码略部分)。B正确。
【例3】 (2024·浙江1月选考)使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图1所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图2所示。实现该功能的程序段如下,方框中应填入的代码是(　　)
t=h
p=d[h][1]
while p != －1 :
　　q=d[p][1]
　　　　　　　　
　　p=q
d[t][－1]=－1　
图1　 　图2
A. if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
B. if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C. if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
D. if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
C
(　　)
【解析】 本题考查单链表及分支语句和数据排序等知识。由于数据区域中数值的绝对值由小到大排列,由代码可知,原先的节点关系是:t→p→q,若数据区域d[p][0]的数值为正数,则原链表节点关系不变,只需将各节点关系往下迭代即可,即:t变为p,p变为q即可。若数据区域d[p][0]的数值为负数,则原先的链表各节点关系需要重新指向,由于原数据是按照绝对值大小排序的,因此越往后面绝对值数越大,因此其相反数(负数)就越小,这样每一个当前节点p的负数肯定是当前链表中最小的数,因此该数应该变为最小的头节点,采用头插法可以实现,即将当前节点p的指针域指向原先的头节点h,然后再将头节点h变为当前节点p,C正确。
自我检测
1. 关于单向链表的节点结构,下列说法中错. 误. 的是(　　)
A. 节点的数据区域用于存放实际需要处理的数据元素
B. 节点的指针区域用于存放该节点相邻节点的存储地址
C. 单向链表必须带有数据区域为空的头节点和尾节点
D. 单向链表中的各个节点在内存中可以非顺序存储
【解析】 单向链表的头尾节点一般情况下数据区域都不为空,是有效节点,C符合题意。
C
2. 有如下Python程序段:
d=[[7,1],[8,2],[9,－1],[6,0]]
head=3
head=d[head][1]
程序执行后,链表中共有几个节点(　　)
A. 1 B. 2
C. 3 D. 4
【解析】 本题考查链表的知识。原链表有4个节点,经过代码“head=d[head][1]”操作后,头节点变为0,故节点数减少为3,C正确。
C
3. 下列关于链表的说法,正确的是(　　)
A. 链表中的各元素在存储空间中的位置必须是连续的
B. 链表中的表头元素一定存储在其他元素的前面
C. 链表中的各元素在存储空间中的位置不一定连续,且各元素的存储顺序也是任意的
D. 链表一旦创建好后,它的占用空间就是固定的
【解析】 本题考查链表的基础知识。链表中的各元素在存储空间中的位置不一定连续,A错误。链表中的表头元素也可以在其他元素后面,B错误。链表一旦创建好后,其占用空间是可变的,比较灵活,D错误。
C
4. 有如下Python程序段:
d=[[7,2],[5,4],[4,1],[9,－1],[1,3]]
p=head=2
while d[p][1]!=－1:
　　print(d[p][0],end="－>")
　　p=d[p][1]
执行该代码后,输出的结果是(　　)
A. 4－>5－>1 B. 7－> 4－>5－>1－>
C. 4－>5－>1－> D. 4－>5－>1－>9
【解析】 本题考查链表的遍历。由于循环的条件是d[p][1]!=－1,也就是当前头指针p的下一个指针域不是最后一个(指针域为－1),则输出该数据域。因此这样输出,最后的9不能输出,C正确。
C
5. 有如下Python程序段:
d=[[6,2],[4,3],[8,1],[2,－1]]
p=head=0
while p!=－1:
　　print(d[p][0],end="－>")
　　p=d[p][1]
执行上述语句后,程序输出结果为(　　)
A.6－>8－>4－> B.6－>8－>4
C.2－>8－>6－>4 D.6－>8－>4－>2－>
【解析】 列表d存储了一个单向链表,d[p][0]和d[p][1]分别是节点p的数据域和指针域,程序功能为从头节点开始遍历链表输出各节点的数据域的值,且这种遍历可以输出最后一项节点的数据2。
D二、 链表及其基本操作
1. 链表的概念
(1)链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。
(2)每个节点一般包括两个区域:数据区域和指针区域。
(3)每个链表有一个表头——head(也称头指针),是链表的入口,也便于循环链表在数据处理时的边界判断和处理。
(4)链表的形式。
链表的形式主要有单向链表、双向链表和循环链表。
①单向链表:只有一个指针用来指向其后继节点。单向链表如图所示。
②双向链表:有两个指针分别用于指向其前驱节点和后继节点。双向链表如图所示。
③循环链表:第一个节点和最后一个节点使用指针链接。循环链表如图所示。
2. 链表的特性
(1)同一链表中每个节点的结构均相同,由数据区域和指针区域组成。
(2)每个链表必定有一个头指针,以实现对链表的引用和边界处理。
(3)链表占用的空间不固定。
可根据需求增删节点,提高存储空间的利用率。
3. 链表的基本操作
(1)链表的创建。
(2)链表节点的访问。
链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。
(3)链表节点的插入与删除。
插入操作:
插入datax节点
删除data2节点
(4)链表节点的访问与遍历。
访问链表中的节点时,只能通过头指针进入链表并通过指针链接依次访问,直到找到目标位置上的节点。
*4. 链表的类实现
在Python中,链表除了可以使用列表来实现,还可以使用“类”来实现。“类”是一种抽象的数据结构,它将数据及其操作封装在一起。构造单向链表类的具体实现过程如下:
(1)自定义单向链表的节点类:
class Node:　　　#定义单链表节点类
　　def_init_(self,data,next_=None):
#初始化节点包含两个域self.data、self.next
　　　self.data=data　#self.data域保存数据
　　　self.next=next　#self.next域保存指针,缺省值为None
(2)构造单向链表类:
class Link:　　　#定义单向链表类Link
　　def_init_(self):　#初始化空链表
　　　　self._head=None　#空链表头指针指向为空
【例1】 下列关于链表的说法,错误的是(　C　)
A. 插入、删除操作不需要移动数据元素
B. 增加或减少节点会改变链表占用的存储空间
C. 可随机快速访问任何一个数据元素
D. 同一链表中每个节点的结构均相同
【解析】 可随机快速访问数据元素的是数组结构,原因是数组结构不仅在逻辑上相邻,其物理存储位置也相邻。但链表的物理存储位置可能是随机的,C符合题意。
【例2】 (2024·浙江6月选考)使用列表d模拟链表结构(节点数n>0),如图1所示,每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,最终保持节点链接关系不变,结果如图2所示。实现上述功能的Python程序段如下,方框中应填入的代码是(　B　)
图1　 图2
　　p,i = h,0
　　while p!=－1:
　　　　tp = d[p][1]
　　　　if p == i:
　　　　　　i+= 1
　　　　elif p>i:
　　　　　　d[i][0],d[p][0] = d[p][0],d[i][0]
　　　　　　　　　　　　
　　　　　　i+= 1
　　　　p = tp
# 调整头指针h及指针区域,保持节点链接关系不变,代码略
A. d[i][1] = d[p][1]
d[p][1] = i
B. d[p][1] = d[i][1]
d[i][1] = p
C. d[i][1] = p
d[p][1] = d[i][1]
D. d[p][1] = i
d[i][1] = d[p][1]
【解析】 本题考查链表的节点操作。根据题意可知,当前节点为p节点,p从头结点开始进行遍历。而变量i是从0开始顺序增加的,当p和i相等时,意味着链表是按链表顺序依次存放到d[0][0]、d[1][0]…d[n－1][0]的,即已经符合题意,此时只需依次进行简单的迭代即可。若p和i不相等,即数据的存放不符合题意,由于i是从0开始的,因此若p和i不等则肯定是p>i,此时由代码可知将节点i和节点p的数据域进行交换,由于在链表中p的位置比节点i更加靠前,即p→i。而数据交换后两者的关系刚好逆转了,即i→p,因此可以先删除节点i,然后将节点i插入到p节点的前面,这样即可实现题意,故先执行代码 d[p][1]=d[i][1],删除节点i,然后再将节点i指向节点p,故代码为d[i][1]=p。以此类推直到循环结束。至此，链表已实现按照顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,但循环结束后,还需要修改头指针h的值,以及重新调整每个节点的指针域数据(即代码略部分)。B正确。
【例3】 (2024·浙江1月选考)使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图1所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图2所示。实现该功能的程序段如下,方框中应填入的代码是(　C　)
t=h
p=d[h][1]
while p != －1 :
　　q=d[p][1]
　　　　　　　　
　　p=q
d[t][－1]=－1　
图1　 　图2
A. if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
B. if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C. if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
D. if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
【解析】 本题考查单链表及分支语句和数据排序等知识。由于数据区域中数值的绝对值由小到大排列,由代码可知,原先的节点关系是:t→p→q,若数据区域d[p][0]的数值为正数,则原链表节点关系不变,只需将各节点关系往下迭代即可,即:t变为p,p变为q即可。若数据区域d[p][0]的数值为负数,则原先的链表各节点关系需要重新指向,由于原数据是按照绝对值大小排序的,因此越往后面绝对值数越大,因此其相反数(负数)就越小,这样每一个当前节点p的负数肯定是当前链表中最小的数,因此该数应该变为最小的头节点,采用头插法可以实现,即将当前节点p的指针域指向原先的头节点h,然后再将头节点h变为当前节点p,C正确。
1. 关于单向链表的节点结构,下列说法中错误的是(　C　)
A. 节点的数据区域用于存放实际需要处理的数据元素
B. 节点的指针区域用于存放该节点相邻节点的存储地址
C. 单向链表必须带有数据区域为空的头节点和尾节点
D. 单向链表中的各个节点在内存中可以非顺序存储
【解析】 单向链表的头尾节点一般情况下数据区域都不为空,是有效节点,C符合题意。
2. 有如下Python程序段:
d=[[7,1],[8,2],[9,－1],[6,0]]
head=3
head=d[head][1]
程序执行后,链表中共有几个节点(　C　)
A. 1 B. 2
C. 3 D. 4
【解析】 本题考查链表的知识。原链表有4个节点,经过代码“head=d[head][1]”操作后,头节点变为0,故节点数减少为3,C正确。
3. 下列关于链表的说法,正确的是(　C　)
A. 链表中的各元素在存储空间中的位置必须是连续的
B. 链表中的表头元素一定存储在其他元素的前面
C. 链表中的各元素在存储空间中的位置不一定连续,且各元素的存储顺序也是任意的
D. 链表一旦创建好后,它的占用空间就是固定的
【解析】 本题考查链表的基础知识。链表中的各元素在存储空间中的位置不一定连续,A错误。链表中的表头元素也可以在其他元素后面,B错误。链表一旦创建好后,其占用空间是可变的,比较灵活,D错误。
4. 有如下Python程序段:
d=[[7,2],[5,4],[4,1],[9,－1],[1,3]]
p=head=2
while d[p][1]!=－1:
　　print(d[p][0],end="－>")
　　p=d[p][1]
执行该代码后,输出的结果是(　C　)
A. 4－>5－>1 B. 7－> 4－>5－>1－>
C. 4－>5－>1－> D. 4－>5－>1－>9
【解析】 本题考查链表的遍历。由于循环的条件是d[p][1]!=－1,也就是当前头指针p的下一个指针域不是最后一个(指针域为－1),则输出该数据域。因此这样输出,最后的9不能输出,C正确。
5. 有如下Python程序段:
d=[[6,2],[4,3],[8,1],[2,－1]]
p=head=0
while p!=－1:
　　print(d[p][0],end="－>")
　　p=d[p][1]
执行上述语句后,程序输出结果为(　D　)
A.6－>8－>4－> B.6－>8－>4
C.2－>8－>6－>4 D.6－>8－>4－>2－>
【解析】 列表d存储了一个单向链表,d[p][0]和d[p][1]分别是节点p的数据域和指针域,程序功能为从头节点开始遍历链表输出各节点的数据域的值,且这种遍历可以输出最后一项节点的数据2。

展开更多......

收起↑