2.2.1单向链表 课件-2021-2022学年浙教版（2019）高中信息技术选修1

2.2 链表 单向链表 什么是链表？ 链表指的是将需要处理的数据对象以节点 的形式，通过指针串联在一起的一种数据 结构。 链表的表示？ Dui=[[“吴坚”，1],[“王林”，2], [“黄刚”，3],[“李丰”，-1]] 节点 （由数据区域和指针区域两部分构成） Dui=[[“吴坚”，1],[“王林”，2],[“黄刚”，3],[“李丰”，-1]] Dui[0][0]=“吴坚” Dui[0][1]=1 Dui[1][0]=“王林” Dui[1][1]=2 . . . Dui[3][1]=? -1 尾节点指针 想一想：如何访问链表？ head=0 头指针，指向第一个节点 链表的特性 （1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 单向链表的基本操作 1.单向链表的创建 （1）Python中可以使用二维列表来模拟单向链表，用包含两个元素 的列表来表示每一个节点，其中第一个元素存储数据，第二个元素存 储指针（即后继节点在二维列表中的索引）。 （2）创建一个空链表linklist的代码如下： linklist=[] head=-1 （3）创建一个拥有2个节点的链表linklist的代码如下： linklist=[[6,1],[8,-1]] head=0 2.单向链表节点的访问 链表节点只能通过头指针（head）进行访问，其他节点通过节点间的指针 依次访问。可以设计如下自定义函数输出链表的所有节点： Def display(a,head): p=head while a[p][1]!=-1: print(a[p][0],end=“—>”) p=a[p][1] print(a[p][0]) 3.单向链表节点的插入 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改 新节点与其前驱节点的指针，将新节点插入到链表的正确位置。 ①从头部插入新节点 next data1 next data2 ne