专题17 链 表 学习目标 1.掌握链表的概念和链表的遍历方法； 2.掌握链表头节点的插入和删除操作； 3.掌握链表除头节点外的其他节点的插入和删除操作. 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的，由数据区域和指针区域组成，其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始，因此头指针是链表必不可少的元素。 (2024年1月浙江省选考)使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为( ) t＝h p＝d[h][1] while p ！＝ －1 ： q＝d[p][1] p＝q d[t][1]＝－1 重难点1 链表的遍历 链表的遍历必须从头节点开始，每个节点包含数据区域和指针区域，数据区域可能有多个值，指针区域值往往在节点最后一个位置。若当前q指向头指针head，那么a[q]是整个节点的值，a[q][0]是数据区域的值，a[q][1]是下一节点的索引，通过语句q＝a[q][1]，实现指针向后移动。 例题 某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组 a 中，现计算相邻两个站点距离的总和。 import math a＝[[″廊桥″，3，2，3]，[″徐岙″，6，11，2]，[″北门″，13，8，－1]，[″上通″，3，7，1]] head＝0 ; s＝0 p＝a[head][3] while(1)_____： s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2) (2)_____ (3)_____ print(s) 上述程序段划线处可选的代码为( ) ①a[head][3]！＝－1 ②head＝p ③p＝a[head][3] ④head！＝－1，则(1)、(2)、(3)处的代码依次为( ) A.①②③ B.④②③ C.④③② D.①③② 变式 使用链表结构模拟某景区游玩路线，链表a中每一个节点包含3个数据，第1个为景点名称，第2个为预计游玩时间(单位：分钟)，第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从″天梯″离开，输出显示各大门进入路线及预计总时间的代码如下。 a＝[[″迎客松″，21，2]，[″激流勇进″，40，2]，[″天空栈道″，50，5]，[″一线天″，30，4]，[″飞来峰″，60，5]，[″天梯″，20，－1]] head＝[0，1，3] for i in range(len(head))： (1)_____ s＝a[p][1] while a[p][2]！＝－1： print(a[p][0], end＝″→″) (2)_____ (3)_____ print(a[p][0]) print(″预计时间：″，s，″分钟″) 上述程序划线处的可选代码有： ①p＝head ②p＝head[i] ③s＋＝a[p][1] ④p＝a[p][2]，则(1)(2)(3)处代码依次为( ) A.①③④ B.①④③ C.②③④ D.②④③ 重难点2 链表节点的删除 在数组中删除某个节点，往往需把该节点后面的值往前移，时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除，头节点的删除只要移动头指针到下一节点，即head＝a[head][1]即可，其他节点的删除，只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可，时间复杂度为常量阶O(1)。 例题 使用列表a模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针，链表中各节点已按数据区域中数值的由小到大排列。现要修改该链表各节点的链接关系，删除链表中数据区域数值相同的节点，使得链表各节点的数据区域值不重复。 实现该功能的程序段如下，方框中应填入的代码段可行的是( ) p ＝ head q ＝ a[p][1] while q！＝－1： a[p] ... ...
