第5课 链表1——单向链表-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)
第5课 链表1——单向链表(见学生用书P32)
——2.2 链表,教材P46~56
1. 掌握链表的概念,了解链表组织、存储结构的原理与特性。 2.能根据问题特点规划节点的数据域和指针域。 3.完成创建链表以及访问、删除、插入链表节点的操作。
1.链表的概念与特性
(1)链表的概念
①链表指的是将需要处理的数据对象以 节点 的形式,通过 指针 串联在一起的一种数据结构。指针就是下一个节点的存储地址(索引)。
②链表中的每个节点一般由“ 数据区域 ”和“ 指针区域 ”两部分构成。数据区域用于保存实际需要处理的数据元素,指针区域用来保存该节点相邻节点的存储地址。
③某个节点前面的相邻节点称为该节点的 前驱节点 ;后面的相邻节点称为该节点的 后继节点 。
(2)链表的特性
①同一链表中每个节点的结构均 相同 。
②每个链表必定有一个 头指针 ,以实现对链表的引用和边界处理。
③链表占用的空间 不固定 。
2.链表的基本操作
(1)链表的创建
首先要根据问题特点规划节点的数据域和指针域,然后根据规划创建一个空链表。
学科网(北京)股份有限公司
(2)链表节点的访问
链表中的节点通过节点间的指针依次访问,当需要访问某个位置的节点元素时,只能通过头指针进入链表并通过节点间的链接关系一个一个往下访问,直到找到指定位置的节点。与数组相比,其节点的访问效率较低。
(3)链表节点的插入与删除
①链表节点的插入:根据新输入的实际数据形成节点,然后修改新节点与其前驱节点的指针,将新节点插入到链表的正确位置。
②链表节点的删除:将需删除的节点的前驱节点和其后继节点直接相连。
单向链表:只有一个指针用来指向其后继节点,单向链表如图所示:
1.链表的创建:
①创建空链表list
学科网(北京)股份有限公司
list=[]
head=-1
②直接创建多节点链表list
list=[[5,1],[6,2],[7,3],[8,-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])
list[len(a)-1][1]=-1
head=0
学科网(北京)股份有限公司