2.2 链表课件-2025-2026学年浙教版高中信息技术选修一

该高中信息技术课件围绕链表展开，涵盖概念特性、节点结构（数据与指针区域）、分类（单向、双向、循环）及Python实现的基本操作（创建、访问、插入、删除等），通过从理论到代码实践的逐步引导，构建支架式学习脉络。 其亮点在于结合计算思维（算法设计、节点指针修改逻辑）与数字化学习（Python列表模拟链表），通过插入删除步骤分解、约瑟夫环问题等实例，培养学生抽象建模能力。教师可利用代码示例互动教学，学生能提升问题解决效率，深化信息意识与创新思维。

链表 1 01 链表的概念及特性 不关心数据实际所处的具体位置，而只需知道数据之间的相互链接顺序的数据结构 链表是一种存储空间利用率高的数据结构，适用于插入和删除 2 01 链表的概念及特性 前驱节点：某个节点前边的节点 后继节点：某个节点后面的节点 3 01 链表的概念及特性 头指针作用之一是链表的入口，只有通过头指针才能进入链表； 作用之二是循环链表的边界，便于数据处理时的边界判断和处理。 4 02 链表的基本操作 Python中没有直接定义链表结构，可以使用列表实现 Test=[[“data2”,1],[“data3”,-1],[“data1”,0]] 正向索引： 0 1 2 当前节点的值 后继节点在列表中的索引 -1表示尾节点 如：Test[0][0]为第一个节点的数据，Test[0][1]为后继节点在列表中的索引 head=2 5 02 链表的基本操作 链表的创建 6 02 链表的基本操作 链表的访问 思考：退出循环a[p][1]= = -1时表示什么意思？ 思考：退出循环p = = -1时表示什么意思？ 7 02 链表的基本操作 链表的访问 #链表（单层列表）节点遍历 data=['data1','data3','data2'] next=[2,-1,1] p,head=0,0 while p!=-1: print("节点数据为：",data[p]) p=next[p] 8 02 链表的基本操作 链表节点的插入 修改新节点的指针值为当前节点的指针值 修改当前节点的指针值为新节点的所在“位置” 9 02 链表的基本操作 链表节点的插入 注意：先修改新插入节点指向当前节点的后继节点，再修改当前节点指向新节点 10 02 链表的基本操作 链表节点的插入 11 02 链表的基本操作 链表节点的插入 12 02 链表的基本操作 链表节点的删除（如删除data5） 修改待删除节点的前驱节点的指针值为待删除节点的指针值 13 02 链表的基本操作 链表节点的删除（如删除data3） 14 02 链表的基本操作 链表节点的删除 15 02 链表的基本操作 链表节点的删除 16 02 链表的基本操作核心 链表节点的访问与遍历 head指针进入链表 需要一个变量p遍历每个节点 链表节点插入 head指针进入链表 需要一个变量p遍历每个节点 将新添加的节点的指针值改为当前节点的指针值 将当前节点的指针值改为新添加节点的索引 17 02 链表的基本操作核心 链表节点的删除 head指针进入链表 需要一个变量p遍历每个节点 需要一个变量q指向待删除节点的前驱节点 将前驱节点的指针值改为要删除节点的指针值 18 02 链表的基本操作 基于链表实现数据合并 head_a,head_b：作为两个链表的头指针 k_a,k_b:指向两个链表中待比较的节点 q_a:记录插入位置的前驱节点 a=[[99,1],[96,-1]] b=[[98,1],[97,-1]] 19 02 链表的基本操作 链表节点的访问与遍历（约瑟夫环） N个人排成一圈，从某个人开始按顺时针从1开始依次编号。从编号为1的人开始顺时针报数，报到m的人退出圈子。这样不断循环下去，圈子里的人数不断减少，最终会只剩下一个人。 20 02 链表的基本操作 llist=[[1,1],[2,2],[3,3],[4,0]] 21 data[8][0]=“new data” data[8][1]=data[1][1] data[1][1]=8 #修改新节点的next值为data3节点的next值 #修改data3节点的next值为新节点的索引 #新节点数据区域赋值 data=[[8,-1],[3,7],[1,6],[6,5],[5,3],[7,0],[2,1],[4,4]] 22 02 链表的基本操作 链表的访问 非常重要！！！ 23 $