2.2链表 课件-2022—2023学年高中信息技术浙教版（2019）选修1

链 表 1 1、链表是为了解决什么问题而发明的 为了解决动态数量的数据存储 2、有没有更优方案 1 2 1、链表是为了解决什么问题而发明的 为了解决动态数量的数据存储 2、有没有更优方案 概念 节点 a 2 c -1 b 1 head=0 头指针 p=head 指针 p=a[p][1] 后继指针 链表概念 链表是指将需要处理的数据对象以节点的形式， 通过指针串联在一起的一种数据结构。 空间 时间 链表 数组 如何创建列表 a=[ ] #创建空列表 head=-1 a.append([“a”,1]) #添加元素 a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ] p = head while p != -1: print(a[p][0], end="->") p = a[p][1] 链表的访问（全部元素的遍历） 输出结果： a->b->c->d->e-> ？ head=2 a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ] p = head while a[p][1] != -1: print(a[p][0], end="->") p = a[p][1] （遍历） 输出结果： a->b->c->d->e ？ head=2 print(a[p][0]) a[p][1] ! = -1: a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ] 在头结点插入一个大写字母A b= ["A", 5] a.append(b) len（a） 5是怎么来的？ 代码实现 总结反思 链表的访问（全部元素的遍历） 链表 da = [["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0]] head = 2 p = head while da[p][1] != -1: print(da[p][0], end="->") p = da[p][1] print(da[p][0]) 输出结果： a->b->c->d->e 单向链表节点的插入 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改 新节点与其前驱节点的指针，将新节点插入到链表的正确位置。 ①从头部插入新节点 next data1 next data2 next data3 -1 head 单向链表从头部插入新节点 new data next data1 next data3 data2 next -1 head Miss 王 (M王) - 代码实现 a=[["data1",1],["data2",2],["data3",-1]] head=0 a.append(["new_data",head]) head=len(a)-1 从中间或者尾部插入新节点该怎么实现呢？ 0 data8 -1 1 data3 7 2 data1 6 3 data6 5 4 data5 3 5 data7 0 6 data2 1 7 data4 4 head 列表名data 列表索引 0 data8 -1 1 data3 7 2 data1 6 3 data6 5 4 data5 3 5 data7 0 6 data2 1 7 data4 4 0 data8 -1 1 data3 2 data1 6 3 data6 5 4 data5 3 5 data7 0 6 data2 1 7 data4 4 8 new head head 列表名data 列表索引 列表名data 列表索引 在第3个节点，即data3节点后插入新节点 7 8 ②从中间插入新节点 a=[["data1",1],["data2",2],["data3",-1]] head=0 p=0 a.append(["new_data",a[p][1]]) a[p][1]=len(a)-1 ③从尾部插入新节点 a=[["data1",1],["data2",2],["data3",-1]] head=0 p=head While a[p][1]!=-1: p=a[p][1] a.append(["new_data",-1) a[p][1]= ? len(a)-1 单向链表节点的删除 删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。 data1 next data2 next data3