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

2.2 链表 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。 杭州 苏州 南京 济南 石家庄 北京 青岛 数组a 0 1 2 3 4 5 6 7 a=["杭州","上海","苏州","南京","济南","石家庄","北京",""] n=len(a) p=4 for i in range（n-2,p-1,-1）: _________________ ____________ n+=1 print(a) a[i+1]=a[i] a[p]=”青岛” 第一次： 上海 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。 杭州 上海 苏州 南京 济南 石家庄 北京 青岛 第二次： a=["杭州","上海","苏州","南京","青岛","济南","石家庄","北京"] n=len(a) q=3 for i in range(__________): a[i]=a[i+1] a.pop() n-=1 print(a) q,n-1 数组a 0 1 2 3 4 5 6 7 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。 杭州 苏州 济南 石家庄 北京 青岛 数组的缺点： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。 数组a 0 1 2 3 4 5 6 7 上海 链表基本概念 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 链表基本概念： 链表节点结构 保存数据元素 保存相邻节点的存储地址 头指针（head）作用： 一是链表的入口，只有通过头指针才能进入链表 二是为循环链表设立一个边界，便于数据处理时的边界判断和处理 吴坚 黄刚 王林 李丰 head next next next 链表基本概念 根据每个节点中指针的数量分为： 单向链表： 循环链表： 第一个节点和最后一个节点使用指针链接，这样就形成了循环链表。 next prev data next 双向链表： prev data next prev prev next：指向其后继节点 prev：指向其前驱节点 链表基本概念 单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。 链表的特性 （1）同一链表中每个节点的结构均相同 数据类型相同 指针数量和功能相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点， 只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。 对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断， 即边界处理。 head （3）链表占用的空间不固定 链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。 所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。 链表的基本操作 Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。 实现单向链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。 用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。 b=[[165,2],[160,-1],[162,1],[172,0]] head=3 165 2 160 -1 162 1 172 0 0 1 2 3 head→ 172 165 162 160 0 1 2 3 数组存储