专题17　链　表 课件 2025届高中信息技术.pptxVIP

专题17链表;1.掌握链表的概念和链表的遍历方法；

2.掌握链表头节点的插入和删除操作；

3.掌握链表除头节点外的其他节点的插入和删除操作.;;;链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的，由数据区域和指针区域组成，其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始，因此头指针是链表必不可少的元素。;;(2024年1月浙江省选考)使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(); ;;重难点1链表的遍历;上述程序段划线处可选的代码为()

①a[head][3]！＝－1②head＝p③p＝a[head][3]④head！＝－1，则(1)、(2)、(3)处的代码依次为()

A.①②③ B.④②③C.④③② D.①③②;D;重难点2链表节点的删除;答案B; ;B; ;重难点3链表节点的插入;答案A; ;变式列表a存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为ha、hb，且a[ha][0]a[hb][0]，如图a所示。现要将其合并为一个升序链表，头指针为h，结果如图b所示，实现功能的程序段如下：;方框中应填入的正确代码为(); ;重难点4循环链表及链表的简单应用;例1报数游戏。已知班上有n名学生(用编号1，2，3，……，n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。

(1)当n＝6，m＝3时，最后留下的同学的编号是________。

(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。; ;A; ;例2某编程兴趣小组设计了一个点歌模拟程序，功能如下：

运??程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D”则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如图所示。;请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A

七里香GodIsaGirl十年年少有为淡季动物园兰亭序想自由

请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C

请输入歌曲；想自由

请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A

想自由七里香GodIsaGirl十年年少有为淡季动物园兰亭序

请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D

请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A

七里香GodIsaGirl十年年少有为淡季动物园兰亭序

请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E; ;答案①data[tail][1]＝len(data)－1

②data[pre][1]＝data[cur][1]③tail＝pre

④head＝data[head][1];A.删除该链表中的最后一个节点

B.删除该链表中的第一个节点

C.在该链表第一个节点前插入一个新节点

D.在该链表最后一个节点后插入一个新节点;;;;;;;;;D;C;;D;;1.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：;①“上海”所在节点的next值赋为“杭州”节点的next值

②“上海”所在节点的next值赋为5

③“杭州”所在节点的next值赋为“上海”所在节点的next值

④“杭州”所在节点的next值赋为－1

链表更新顺序正确的是()

A.③① B.③② C.①④ D.②④;B;;A;;已知链表b的长度不超过链表a，则下列选项中，代码顺序正确的是()

A.①④⑤ B.②③⑥C.①④⑥ D.②③⑤;5.用链表模拟队列操作(队列长度大于1)，链表的每个节点包含数据区域和指针区域。指针head指向队列的第一个元素，