选择性必修1 专题二 数组、链表及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教学课件PPT（浙江专用）

专题二　数组、链表及应用 思维导图 一、数组及其操作 1.数组的概念 数组是由相同类型的变量构成的一个序列。 (1)数组名和下标组成数组的各个变量称为数组的分量,也称为数组元素。 (2)创建数组时,系统会在内存中分配一块连续的存储空间,每个数组元素按照下标顺序存储,数组在内存中的存储方式为顺序存储。 (3)一维数组:只有一个下标,下标用来表示数据元素在该序列中的位置。 二维数组:有两个下标,表示数据元素在该序列中的行、列位置,二维数组有行优先存储和列优先存储两种方式。 归纳提炼 2.数组的特性 (1)数组元素的数据类型相同。 (2)通过数组名和下标对数组元素的值进行访问。 (3)存储空间固定不变。 3.数组的基本操作 (1)数组的创建 数组的创建实质是在系统内存中划分一块连续区域,用来保存数组所含的所有数据元素。 (2)数组元素的访问 通过数组名和下标直接进行访问数组元素。 (3)数组元素的插入与删除 ①当数组中某个位置要插入一个新元素时,必须先将该位置及后面的所有数据向后移动一个位置,以空出该位置,用于存放新元素。 例如,在数组a的1位置插入一个新数据datax,操作后的数组a如下图所示。 ②删除数组元素时,需要将被删除元素位置后的所有元素依次前移一个位置。 例如,删除数组元素a[1]后的数组如下图所示。 4.Python列表常用函数和方法 在Python中,常用列表来模拟实现数组的操作。 Python列表常用函数和方法 函数和方法 功能 实例 len(list1) 统计列表list1中元素的个数 list1=[1,2,3,4] print(len(list1)),输出为4 list1.append(x) 在列表list1末尾添加元素x list1=[1,2,3,4] list1.append(5) 列表中的内容为:[1,2,3,4,5] list1.insert(i,x) 在列表list1中下标为i位置处插入元素x list1=[1,2,3,4] list1.insert(2,5) 列表中的内容为:[1,2,5 3,4] list1.pop(i) 将列表list1中下标为i的元素删除;若i不指定,默认为 -1,即删除最后一个元素 list1=[1,2,3,4] list1.pop() 列表中的内容为:[1,2,3] 二、链表及其操作 1.链表的概念 链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。 (1)链表中每个节点一般由“数据区域”和“指针区域”两部分构成。 (2)每个链表有一个表头——head(也称头指针),是链表的入口,也便于循环链表在数据处理时的边界判断和处理。 2.链表的形式 链表的形式主要有:单向链表、双向链表、循环链表。 单向链表:只有一个指针用来指向其后继节点。单向链表如下图所示。 双向链表:有两个指针分别用于指向其前驱节点和后继节点。双向链表如下图所示。 循环链表:第一个节点和最后一个节点使用指针链接。循环链表如下图所示。 3.链表的特性 (1)同一链表中每个节点的结构均相同,有数据区域和指针区域组成。 (2)每个链表必定有一个头指针,以实现对链表的引用和边界处理。 (3)链表占用的空间不固定。 可根据需求增删节点,提高了存储空间的利用率。 4.链表的基本操作 (1)链表的创建 (2)链表节点的访问 链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。 (3)链表节点的插入与删除 插入datax结点 删除data2结点。 (4)链表节点的访问与遍历 访问链表中的节点时,只能通过头指针进入链表并通过节点间的链接关系依次访问,直到找到目标位置的节点。 5.数组与链表的优缺点比较 数据结构 访问数据元素 插入、删除数据元素 数组 直接访问数组元素,效率高 需要大量移动数组元素,效率低 链表 通过头指针,通过节点的链接关系依次访问节点,效率低 不需要移动链表中的节点,效率高 [例1] 下列有关数组的说法,正确的是(　　) A.一维数组适合用来表示具有线性特征的数据序列 B.二维数组表示的数据元素在内存中的存储方式为非顺序存储 C.仅通过数组名就能访问数组中的某个元素 D.非顺序存储结构的典型代表为数组 典型例题 解析:二维数组表示的数据元素在内存中的存储方式也是顺序存储,有行优先存储和列优先存储两种方式,因此B选项错误;通过数组名和下标就能访问数组中的某个元素,因此C选项错误;数组是顺序存储结构的典型代表,因此D选项错误;一维数组适合用来表示具有线性特征的数据序列,因此答案为A。 A [例2] 在Python语言中,一维数组d中第一个元素可表示为(　　) A.d(0) B.d(1) C.d[0] D.d{0} C 解析:一维数组元素表示为数组名[下标],