2.2 链表（教学课件）⾼中信息技术选修1数据与数据结构（浙教版 2019）.pptxVIP

第2节链表（3课时）第2章数组与链表浙教版（2019）选修一

链表的概念与特性01链表的基本操作02

初步理解数据结构的概念及其作用。01能运用链表编程解决实际问题。03掌握链表的基本操作。02

PART01链表的概念与特性

新课导入排队与插队

新课导入排在这里数组的缺点:※插入和删除元素操作需要移动大量的元素※频繁增、删数据导致数据规模不稳，形成存储空间“碎片”※需要限定最大空间，造成资源浪费

新课导入链表是一种存储空间利用率高的数据结构，适用于数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。链表

链表的概念与特性一12指针区域数据区域概念：将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。一个链表的节点保存数据元素保存相邻结点的存储地址两部分组成

链表的概念与特性一01STEP02STEP03STEP每个结点使用指针指向其后继结点的存储地址单向链表中各个结点在内存中可以非顺序存储进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。链表的组成※头节点:用于进入链表和边界判断※前驱节点:某个节点前面的相邻节点※后继节点:某个节点后面的相邻节点※尾节点:最后一个节点，指针指向空前驱节点某节点后继节点

链表的概念与特性一单向链表在内存中的存储模式单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。

链表的概念与特性一吴坚王林黄刚李丰∧head链表内存存放方式：head头节点数据域指针域tailNone头指针的作用0102链表的入口，只有通过头指针才能进入链表。为循环链表设立一个边界，便于数据处理时的边界判断和处理。

链表的概念与特性一链表的特性同一链表中每个节点的结构均相同①链表节点中包含数据区域和指针区域。不管是单向链表还是双向链表，每个节点的数据区域中的数据类型是相同的，指针区域中的指针数量和功能是相同的。数据区域指针区域数据类型相同指针数量和功能相同

链表的概念与特性一链表的特性每个链表必定有一个头指针，以实现对链表的引用和边界处理②链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。一个头指针对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。head

链表的概念与特性一链表的特性链表占用的空间不固定③链表的节点间通过指针相连，相邻节点存储时不需要连续空间，充分利用了内存的零散空间，提高了存储空间利用率。由于链表的存储空间由节点数决定，增加或减少节点都会改变链表占用的存储空间，因此链表占用的空间不固定。

链表的概念与特性一只需知道数据之间相互链接的顺序探讨与讨论1.以下有关链表的描述,不正确的是(）A.插入、删除操作无须移动数据元素B.增加或减少节点会改变链表占用的存储空间C.可随机快速访问任何一个数据元素D.同一链表中每个节点的结构均相同C

链表的基本操作PART02

链表的基本操作二节点访问节点插入删除基本操作空链表的创建链表的基本操作

链表的基本操作二Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。实现单向链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。165216211720160-1head头节点尾节点b=[[165,2],[160,-1],[162,1],[172,0]]

链表的基本操作二链表的创建创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。item=[]head=-1其中head值为-1，表示头指针指向为空，该链表为空链表。使用列表模拟链表例如:a=[[99,1],[95,2],[88,-1]]列表a中有3个元素:[99,1]、[95,2]、[88,-1]数据元素(a[0])的第一个元素(99)为数据域。数据元素(a[0])的第二个元素(1)为指针域，是列表a的第二元素的索引。头指针=0为开始节点尾指针=-1为尾节点，表示指向为空。

链表的基本操作二只需知道数据之间相互链接的顺序