第6课 链表2——链表综合-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第6课　链表2——链表综合(见学生用书P40) ——2.2　链表，教材P46～56 1.掌握循环链表的概念，了解循环链表组织、存储结构的原理与特征。　2.掌握双向链表的概念，了解双向链表组织、存储结构的原理与特征。　3.能利用链表结构解决实际问题。 1．循环链表 最后一个节点的指针指向第一个节点 (1)循环链表的创建 ①直接创建循环链表list list＝[[5，1]，[6，2]，[7，3]，[8，0]] head＝0 ②利用已有列表a，创建循环链表list a＝[i＋1 for i in range(6)] list＝[] for i in range(len(a))： list.append([a[i]，i＋1]) list[len(a)－1][1]＝0 head＝0 (2)循环链表的遍历 list＝[[5，1]，[6，2]，[7，3]，[8，0]] p＝head＝0 while list[p][1]！＝head： print(list[p][0]，end＝”－>”) p＝list[p][1] print(list[p][0]) 2．双向链表 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继节点和直接前驱节点。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。 (1)双向链表的创建 利用二维列表模拟双向链表，用包含3个元素的列表来表示每一个节点，其中第1个元素存储数据，第2、3个元素分别存储前驱指针prev和后继指针next。 ①创建空双向链表list list＝[] head＝－1 　　②直接创建多节点链表list list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] head＝0 ③利用已有的列表a创建链表list a＝[i＋1 for i in range(6)] list＝[] for i in range(len(a))： list.append([a[i]，i－1，i＋1]) list[len(a)－1][2]＝－1 head＝0 (2)双向链表的遍历 list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] p＝head＝0 while list[p][2]！＝－1： print(list[p][0]，end＝”－>”) p＝list[p][2] print(list[p][0]) (3)链表节点的插入和删除 ①在头节点之前插入节点 程序实现：新节点数值域为4。 list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] head＝0 list.append([4，－1，head]) list[head][1]＝len(list)－1 head＝len(list)－1 ②在链表中间插入新节点 程序实现：在p节点之后插入新节点，新节点数值域为4。 list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] head＝0 p＝2 list.append([4，p，list[p][2]]) list[list[p][2]][1]＝len(list)－1 list[p][2]＝len(list)－1 ③删除头节点 程序实现： list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] head＝0 head＝list[head][2] list[head][1]＝－1 　　④删除中间节点 程序实现：删除p节点之后的节点 list＝[[5，－1，1]，[6，0，2]，[7，1，3]，[8，2，－1]] head＝0 p＝1 list[p][2]＝list[list[p][2]][2] list[list[p][2]][1]＝p 3．基于链表实现数据合并 程序实现：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 from random import randint a＝[] heada＝－1 b＝[] headb＝－1 temp＝randint(95，100) a．append([temp，heada]) heada＝0 for i in range(1，randint(15，25))： temp＝a[i－1][0]－randint(0，5) a．append([temp，a[i－1][1]]) a[i－1][1]＝i print(”链表结构原始数据1”) print(a) temp＝randint(95，100) b．append([temp，headb]) headb＝0 for i in range(1，randint(15，25))： temp＝b[i－1][0]－randint(0，5) b．append([temp，b[i－1][1]]) b[i－1][1]＝i print(”链表结构原始数据2”) print(b) ka＝heada qa＝heada kb＝headb while ka！＝－1 and kb！＝－1： if a[ka][0]>b[kb][0]： qa＝ka ka＝a[ka][1] 　　　　else： 　　if ka＝＝heada： a．append([b[kb][0]，heada]) heada＝len(a)－1 qa＝heada 　　　　　else： 　　a．append([b[kb][0]，ka]) 　　a[qa][1]＝len(a)－1 　　qa＝a[qa][1] 　　　　　kb＝b[kb][1] while kb！＝－1： a．append([b[kb][0]，－1]) a[qa][1]＝len(a)－1 qa＝a[qa][1] kb＝b[kb][1] print(”排序后的链表序列”) temp＝heada while a[temp][1]！＝－1： print(a[temp][0]，end＝” ”) temp＝a[temp][1] print(a[temp][0]) 运行结果： 链表结构原始数据1 [[97，1]，[96，2]，[93，3]，[90，4]，[89，5]，[89，6]，[88，7]，[85，8]，[85，9]，[81，10]，[79，11]，[74，12]，[69，13]，[64，14]，[61，15]，[59，16]，[56，17]，[54，18]，[53，19]，[50，20]，[49，－1]] 链表结构原始数据2 [[96，1]，[91，2]，[86，3]，[81，4]，[81，5]，[79，6]，[74，7]，[74，8]，[71，9]，[71，10]，[68，11]，[63，12]，[62，13]，[60，14]，[60，15]，[57，16]，[57，17]，[54，18]，[53，19]，[51，20]，[50，21]，[47，22]，[42，23]，[39，24]，[38，－1]] 排序后的链表序列 97 96 96 93 91 90 89 89 88 86 85 85 81 81 81 79 79 74 74 74 71 71 69 68 64 63 62 61 60 60 59 57 57 56 54 54 53 53 51 50 50 49 47 42 39 38 4．链表类的实现 链表除了可以用列表来实现，还可以使用类实现。类是一种抽象的数据结构，它将数据及其操作封装在一起。构造单向链表的具体实现过程如下： ①自定义单向链表的节点类： class Node： #定义节点类Node def__init__(self，data，next_＝None)： #初始化包括两个区域 self.data＝data　　　　　　　　　　　#self.data区域保存数据 self.next＝next_ #self.next区域保存指针 　　②构造单向链表类： class Link：　　　　　　　　　　　#定义单向链表类Link def__init__(self)： #初始化空链表 self.head＝None #空链表头指针指向空 　　有如下Python程序段： a＝[[3，2]，[2，3]，[7，1]，[1，0]] p＝head＝0 while a[p][1]！＝head： print(a[p][0]，end＝＂－>＂) p＝a[p][1] print(a[p][0]) 执行该程序段后，输出的结果是(　A　) A．3－>7－>2－>1 B．3－>2－>7－>1 C．1－>7－>3－>2 D．3－>7－>1－>2 【解析】 循环链表的遍历，从头节点开始输出，当a[p][1]＝＝head时，循环结束，则节点[1，0]没有输出，通过语句print(a[p][0])，输出最后节点。 变式1山顶上有10个圆形排列的洞，一只狐狸和一只兔子各住一个洞，狐狸总想吃掉兔子。一天，兔子对狐狸说：“你把洞从1～10编上号，先到1号洞找我；第二次隔1个洞(即3号洞)找我，第三次隔2个洞(即6号洞)找我，依此类推，次数不限。找到我就可以吃掉我。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。请问兔子可能躲在哪个洞里？ 实现上述功能的Python程序段如下，请在横线处填入合适的代码。 hone＝[] n＝10 m＝1000 #构造一个循环链表，并给n个洞编号，设置洞的初始标志为0 #链表的节点样式为：[洞的标志，洞的编号] for i in range(n－1)： hone.append([0，i＋1]) ①　hone.append([0，0])　 #狐狸开始找兔子，将进入过的洞标志改为1，寻找m次结束 head＝0 k＝head hone[0][0]＝1 for i in range(1，m)： for j in range(1，i＋2)： ②　k＝hone[k][1]　 hone[k][0]＝1 #输出标志仍为0的洞，即兔子可能藏身的地点 for i in range(len(hone))： if hone[i][0]＝＝0： print(”兔子可能躲在第”＋③　str(i＋1)　＋”号洞”) 【解析】 ①构建循环链表，使最后的节点指向头节点，答案为hone.append([0，0])。 ②由条件“先到1号洞找我；第二次隔1个洞(即3号洞)找我，第三次隔2个洞(即6号洞)”可知，可利用循环j实现，例如，当i＝1，k往后走2步，即访问3号洞。遍历循环链表，依次遍历，答案为k＝hone[k][1]。 ③输出最后剩余的洞，答案为str(i＋1)。 　　有如下Python程序段： a＝[[2，2，3]，[8，3，－1]，[0，－1，0]，[4，0，1]] head＝2 if a[head][2]！＝－1： a[a[head][2]][1]＝－1 head＝a[head][2] p＝head while a[p][2]！＝－1： print(a[p][0]，end＝”－>”) p＝a[p][2] print(a[p][0]) 执行该程序段后，输出的结果是(　D　) A．0－>2－>4－>8 B．0－>2－>4 C．0－>2－>8 D．2－>4－>8 【解析】 双向链表的遍历输出，if语句将头节点后继节点的前驱设为－1，并将head指向后继节点，结果为[[2，－1，3]， [8，3，－1]， [0，－1，0]， [4，0，1]]； head＝0， while循环从head遍历输出，选项D正确。 变式1双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接前驱和直接后继。在Python中可以使用二维列表来模拟双向链表，用包含3个元素的列表来表示每一个节点，其中第一个元素存储数据，后两个元素分别存储指向前驱和后继的指针。若没有前驱或后继节点，则对应的指针值为－1。下列程序生成了一些随机正整数，并依次存储到一个双向链表a中。现要求删除其中值为偶数的节点，请在横线处填入合适的代码。 import random a＝[] head＝－1 for i in range(8)： node＝[random.randint(1，9)，－1，head] a．append(node) if head！＝－1：　　　#非空链表 a[head][1]＝len(a)－1 head＝①　len(a)－1　 p＝head while p！＝－1： if a[p][0]%2＝＝0： if a[p][1]！＝－1：　　#有前驱节点 a[a[p][1]][2]＝②　a[p][2]　 if a[p][2]！＝－1：　　#有后继节点 a[a[p][2]][1]＝a[p][1] if head＝＝p：　　#删除头节点 head＝③　a[p][2]　 　　p＝a[p][2] 【解析】 ①处在生成链表节点后，把头节点的指针指向最后节点的元素位置；②处删除值为偶数的节点，当有前驱节点，需要修改新节点指针指向与前一节点的指针指向一致，故答案为a[p][2]；删除的节点如果是头节点时，需修改头指针指向新节点，故③处答案为a[p][2]。 　　2023·诸暨中学检测为了增强学生的体质，学校要求学生在课间活动时进行慢跑活动。要求每班一路纵队，女生在前，男生在后，从矮到高进行排队。现在某班来了一个新生， 该生也要按照学校要求排入班级队伍中。小张编写了一个Python程序段，可以实现将一个学生排入队伍后，仍保留女生在前、男生在后且从矮到高排队的功能。程序代码如下，运行结果如图所示： (1)请在横线处填入合适的代码。 (2)程序中加框处代码有误，请改正：　link[p][2]！＝－1　。 def inserlink(xb，sg，link，head)： link.append([xb，sg，－1]) n＝len(link) p＝head while p！＝－1： if link[－1][0]＝＝”男” and link[p][0]＝＝”女”： q＝p p＝link[p][2] elif ①　link[n－1][0]＝＝link[p][0]　 and link[p][1]<link[n－1][1]： q＝p p＝link[p][2] else： 　　break if p＝＝head： link[n－2][2]＝head head＝n－1 else： 　　link[n－1][2]＝p 　　②　link[q][2]＝n－1或link[q][2]＝len(link)－1　 return link，head def printlin(link，head)　#输出学生信息 p＝head；cnt＝1 while： if cnt%5＝＝0： print(link[p][0]＋””＋str(link[p][1])) else： 　　print(link[p][0]＋””str(link[p][1])＋”－>”，end＝””) cnt＋＝1 p＝link[p][2] print(link[p][0]＋””＋str(link[p][1])) #列表xsxx 存储学生信息，xsxx[p][0]，xsxx[p][1]，xsxx[p][2]，分别存储索引位置p的学生的性别、身高与存储指向下一个学生信息的索引位置。现已按照女生在前、男生在后且从矮到高完成排队，代码略。 head＝0　　　 #head为链表的头指针 print(”该生入队前的顺序：　”) printlin(xsxx，head) xb＝input(”输入入队学生性别：　”) sg＝float(input(”输入入队学生身高(米)：　”)) xsxx，head＝inserlink(xb，sg，xsxx，head) print(”该生入队后的顺序”) printlin(xsxx，head) 【解析】 (1)①单向链表link，因排序按前女后男安排序列，若当前(n－1位置，即刚加入列表的新同学)为男，p节点位置性别为女，则继续遍历；若当前节点性别一致，即： link[n－1][0]＝link[p][0]， 则按身高比较，若p节点同学的身高大于或等于n－1节点同学身高， 则跳出循环， 准备将n－1 节点插入q 、p节点之间。②将n－1节点插入q 、p节点之间， 故将n－1节点连接到p节点， 接着将q节点连接到n－1节点。 (2)因为链表输出的最后一位同学输出后不带－＞符号， 故循环内部遍历到最后一个节点， 但最后一个节点不输出， 退出循环后输出最后一个节点。 变式1某餐厅辅助配餐程序提供给用户基于预算的点菜功能，该程序主要由“菜单显示”及“订单管理”两大基本模块组成，具体如下： ◆菜单显示功能：输出菜价小于等于预算经费余额且在售的菜品。 ◆订单管理功能：包括输出订单中的菜品信息，订单菜品的删除和添加等。 (1)菜品数据相对稳定，为了便于查找菜品，采用　①　结构较为合理，订单数据涉及频繁的增加或删除，采用　②　 结构较为合理。上述①、②处可填的内容为　A　(单选，填字母：A.数组、链表/B.链表、数组)。 (2)餐厅菜品数据表如下所示，每道菜由4个数据项组成，第一项为菜品编号，第二项为菜品名称，第三项的菜品单价(以“分”为单位，该数据项为0时表示菜品已下架)，第四项为当月销量。实现菜单显示和输出订单菜品信息的程序如下，餐厅菜单保存在menu中，格式为：menu＝[[0，”太湖三宝”，18800，535]， [1，”湖羊肉”，11800，446]，…]。 编号 菜品名称 菜品价格(单位：分) 当月销量 0 太湖三宝 18800 535 1 湖羊肉 11800 446 … … … … n－1 白果芦笋 0 2 　　程序运行结果如图所示，请在横线处填入合适的代码。 ★请输入你的消费预算　(单位：　分) ：　4000 ★可供选择的菜品： [4，”家常鳝丝”，2900，263] [18，”麻婆豆腐”，900，36] [21，”桂花糕”，800，32] [38，”卤水素鸡”，3200，2] [39，”豆豉鲮鱼油麦菜”，3800，2] [54，”煲仔饭”，3800，1] [57，”西兰花嫩菱”，2200，1] [58，”清蒸多宝鱼”，2800，1] ★请输入预选择的菜品编号，以逗号分隔：18，21，58，57，4 ★点单成功的菜品：麻婆豆腐 桂花糕 西兰花嫩菱 ★剩余金额：100 #读取餐馆全部菜品数据保存到menu中，数据类型及格式见题干描述，代码略 sal＝int(input(”★ 请输入你的消费预算　(单位：　分)：　”)) print(”★ 可供选择的菜品：　”) for i in range(len(menu))： if ①　menu[i][2]！＝0　 and menu[i][2]<＝sal： 　 print(' '，menu[i]) n＝input(”★ 请输入预选择的菜品编号，　以逗号分隔：　”).split('，') x＝len(n) lis＝[[int(n[i])，i＋1] for i in range(x)] lis[x－1][1]＝－1 p＝0 while p！＝－1： bh＝lis[p][0] if menu[bh][2]<＝sal： ②　sal－＝menu[bh][2]　 y＝p else： 　　lis[y][1]＝lis[p][1] p＝lis[p][1] p＝0；s＝'' while p！＝－1： 　　s＋＝menu[lis[p][0]][1]＋' ' 　　③　p＝lis[p][1]　 print(”★ 点单成功的菜品：　”＋s) print(”★ 剩余金额：　”＋str(sal)) 【解析】 (1)链表适合涉及频繁地增加或删除数据存储；数组适合快速查找数据，选项A正确。 (2)①sal为消费预算，首先将菜单中在售的且单价小于等于消费预算的菜品预选出来；②再将预选菜品构建单向链表lis，根据预选菜品的标号，在menu列表中找到菜品价格。如果小于等于消费预算，则可购买，并减去该菜品的价格，并更新剩余消费预算，答案为sal－＝menu[bh][2]；如果消费预算不够，则从链表中删除该预选菜品；③遍历剩余的预算链表，输出相应菜品名称，答案为p＝lis[p][1]。 　　已知单向链表的节点类的定义如下： class Link： def _init_(self，data_，next_＝Node)： self.data＝data_ self.next＝next_ 链表结构如下图所示： 若要修改节点p的后继节点的数据值，则应执行的语句为(　B　) A．p.data＝”电” B．p.next.data＝”电” C．p.next.next.data＝”电” D．self.next.data＝”电” 【解析】 p的后继节点表示为p.next，再找到该节点的数据域p.next.data，选项B正确。 |随|堂|检|测| 1． 使用链表结构模拟某景区游玩路线，链表a中每一个节点包含三个数据，第1个为景点名称，第2个为预计游玩时间(单位：分钟)，第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从“天梯”离开，输出显示各大门进入路线及预计总时间的Python代码如下： a＝[[”迎客松”，21，2]，[”激流勇进”，40，2]，[”天空栈道”，50，5]，[”一线天”，30，4]，[”飞来峰”，60，5]，[”天梯”，20，－1]] for i in range(len(head))： s＝a[p][1] while a[p][1]！＝－1： print(a[p][0]，end＝”－－>”) print(a[p][0]) print(”预计时间”，s，”分钟”) 上述程序段中加框处可选的代码有： ①p＝head　②p＝head[i]　③s＝s＋a[p][1]　④p＝a[p][2] 下列选项中，代码顺序正确的是(　D　) A．①③④ B．①④③ C．②③④ D．②④③ 【解析】 (1)处head是一个列表，应为head[i]，表示第1个大门开始路线，(2)(3)处注意s的初值为a[p][1]，同时最后一个节点取不到，所以应先跳入下一节点再统计当前时间的和，所以答案为②④③。选项D正确。 2．某校军训，需要按照身高由低到高排成n 行5 列的方阵。某班学生按照身高(100 cm≤身高(cm)≤199 cm)由低到高编写编号并将相关信息存在如图1所示的“stu.txt”文件中。根据教官提出的排方阵要求，排成如图2所示的方阵，方阵各点显示学生编号。 现有延迟报道学生归队，归队学生编号延续该班现有编号依次往后，编写程序完成下列任务：输入学生身高，输出新的方阵布局图。例如，输入学生身高为168，新的方阵布局图如图3所示，学生在方阵中的位置是(3，4)。 (1)若插入学生身高为160 cm，根据图1及范例，该学生在图2方阵中的位置是　(1，5)　。 (2)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 f＝open(”stu.txt”，”r”) a＝[ ] line＝f.readline().split i＝1 while line！＝[ ]： a．append([line[0]，line[1]，i ]) i＋＝1 line＝f.readline().split n＝len(a)－1 a[n][2]＝－1 sg＝input(”请输入插入的学生身高(cm)：　”) xh＝str(len(a)) head＝1 p＝head；q＝head while①　a[q][1]<sg and q！＝－1 或int(a[q][1])<int(sg) and q！＝－1　： p＝q q＝a[q][2] if q＝＝head： ②　a.append([xh，sg，head]) 或a.append([xh，sg，p])或a.append([xh，sg，q]) 或a＋＝[[xh，sg，head]] 或其他等价答案　 head＝len(a)－1 else： 　　a．append([xh，sg，a[p][2]]) 　　a[p][2]＝len(a)－1 p＝head m＝1 while p！＝－1： if m！＝5： print(a[p][0]，end＝” ”) m＋＝1 else： 　　print(a[p][0]) 　　m＝1 ③　p＝a[p][2]　 【解析】 (1)根据题意，方阵按照身高由低到高排序，插入学生身高为160 cm，观察题图1，编号01～04的学生均低于该学生，所以该学生插入到编号为04 的学生后，插入位置为第一行第五列。 (2)①空所在while 循环的功能为遍历链表寻找待插入学生的插入位置，若待插入学生身高sg大于当前节点学生身高a[q][1]，则继续遍历，应有一个条件为a[q][1]<sg，若该条件不成立，此时的q 即为插入位置。但存在始终找不到的情况，遍历结束后循环也应当结束，此时插入位置为尾节点之后，由此得到另一个循环条件q！＝－1。①空填写a[q][1]<sg and q！＝－1。②空所在分支结构实现的功能为节点的插入，插入位置为p，可使用append()在链表的尾部添加一个元素或用“＋”连接元素。插入分为两种情况，即插入在头节点之前或插入在链表中间。若是在头节点之前插入，插入节点的指针区域应为头节点head，数据区域为学生编号xh和身高sg。②空填入a.append([xh，sg，head]) 或a.append([xh，sg，p])或a.append([xh，sg，q]) 或a＋＝[[xh，sg，head]]等。 ③空所在循环实现链表的遍历输出，每次循环结束后，应通过当前遍历到的节点的指针区域找到下一次遍历到的节点位置，即p＝a[p][2]。 学科网（北京）股份有限公司 $$