第11章数组与链表（含代码）知识点梳理高考信息技术二轮复习知识点梳理

第十一章数组与链表（含代码）

1.数组在内存中的存储方式为顺序存储，数组作为常用的数据结构，有特定的数据组织、存储

结构及操作特性。

2.计算机中数据的存储结构主要分为顺序存储结构和非顺序存储结构。常见的顺序存储结构是

数组，常见的非顺序存储结构是链表

3.数字是由相同类型的变量构成的一个序列。数组使用一个标识符命名，并用编号区分数组内

的各个变量，这个特殊的标识符号称为数组名，编号称为下表或索引。由数组名和下标组成数

组的各个变量称为数组的分量，也称为数组元素。（数组的下标一般从0开始）

4.数组在内存中的存储结构简单，创建数组时系统会分配一块连续的存储空间，每个数组元素

按照下标顺序依次存储。如下图

下标

数组名d

5.一维数组适合川来表示具有线性特征的数据序列，因此只需要一个下标来表示数据元素在该

序列中的位置。如果要表示二维空间内既有纵向联系和又有横向联系的一批数据，那么采用二

维数组会变得更形象、方便由于二维数组中的数组有行有列两个维度的位置信息，因此需要两

个下标。二维数组下标详见下图:

6.用二维数组表示的数据在内存中的存储方式也才用顺序存储，有行优先存储和列优先存储。

一般默认采用行优先。

7.数组的特性：1.数组元素的数据类型相同，2.通过数组名的下标对数组元素的值进行访问，

3.数据存储空间不变

8.动态数组就是在声明时没有确定数据规模的数组，可以在任何时候改变数据规模。

9.对数组的常见操作有：数组的创建、数组元素的访问、数组元素的插入和删除等。

10.Python没有数组这种数据结构，所以采用列表来实现。

11.数组的和创建实质是在系统内存中划分一块连续区域，同来保存数组所含的所有数据元素

12.数组元素的访问指的是寻址到特定的数组元素，并根据存储地址对该数据元素进行读取、

修改等操作。因为数组元素从0开始数，所以：例如s[5]访问的是s数组的第六个元素

13.Python列表常用函数与方法：

函数和方法功能实例

len(list)统计列表list中元素个数print(len(list))

依出为：0

list=(22,33,44]

list.appcnd(55)

list.append(x)在列表list末尾添加元米x

print(list)

榆出为：[2233,44,55)

list=(-AMB"JD"]

list.insert(2,"C")

list.inscrt(i.x)在列表list中下标为i位置处插入元素x

print(list)

输出为：「A”JB"C"D"]

list=C*A".■B"JC"JD-]

将列表list中下标为i的元素朗除；若ilist.pop(2)

list.pop(i)

不指定，戏认为T.即最后一个print(list)

输出为：「A-JB"JO'']

图1.3

14.链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。

链表中的每一个节点一般由“数据区域”和“指针区域”两部分构成（如下图）。数据区域用

于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址，通过该地址

指向（指针）来实现从当前节点按顺序走到相邻的节点。某个节点前面的相邻节点称为该节点

的前驱节点，后面的相邻节点称为该节点的后继节点。

15.每个链表都拥有一个表头head（也称为头指针），头指针的作用之一是链表的入口，只有通

过头指针才能进入链表；作用之二是为循环链表设立一个边界，便于数据处理时的边界判断和

处理。

16.链表可以根据每个节点中指针的数量分为两类：只有一个指针的单向链表和有两个指针的

双向链表（即每个节点有两个指针区域，一个指向前驱节点，一个指向后继节点）。将第一个

节点和最后一个节点使用指针链接，就会形成循环链表

17.单向链表中各个节点在内存中可以非顺序存储，每个节点使用指针指向后继节点的存储地

址。进入链表只能通过头指针head,其他节点则需要经过所有在它之前的节点才可以访问，

尾早点的指针指向null,表示指向为空（一般情况下，尾指针为1。当尾指针指向head时，即

为循环链表）

18.链表的特性：1.同一链表中每个节点的结构均相同，2.每个链表必定有一个头指针，以实

现对链表的引用和边界处理，3.链表占用的空间不固定。

19.链表的操作有：链表的创建、链表节点的访问、链表节点的插入与删除

单向链表代码实现

给定一个链表a口，其第一个元素代表的下标为head。a[i]代表的元素是一个长度为2的

数组，其中a[i][O]表示它的数据data（数据都是整数）,表示它的下一个元素next,

如果next为T代表其是链表的最后一个元素。

假设有如下代码：

head-0

#删除第一个元素#遍历链表

head=a[head][1]h=head

whileh!=1:

print(a[h][0])

h=a[h][1]

#删除中间元素,根据内容B#在头部插入元素

h=headhead=0

pre=heada.append(['E',head])

whileh!=1:head=len(a)1

ifa[h][0]=,B>:

break

else:

pre=h

h=a[h][1]

a[pre][1]=a[h][1]

#插入中间元素根据值链表相对于数组而言，更便于删除和添加，

#首先找到B数组相对于链表而言，更便于查找和修改

h=head

whileh!=1:

ifa[h][0]=='B':

break

else:

h=a[h][l]

#然后插入E

a.append([*E*,a[h][1]])

a[h：[1]=len(a)1

表1.1

双向链表代码实现

给定一个链表a[],其第一个元冢代表的下标为headoa[i]代表的元素是一个长度为3的数

组，其中a[i][0]表示当前节点的前一个节点pre,a[i][1]表示它的数据data（数据都是

整数）,a[i][2]表示它的下一个节点next,如果next为T代表其是链表的最后一个元素。

假设有如下代码：

a=[[l,，A\2],[3/D\l],[0/B,,3],[2/C\l]]

head=0

pre=nextl=head

#遍历链表(从前往后)#遍历链表(从后往前)

whilenextl!=1:whilea[nextl][2]!=1:

print(a[nextl][1])#先找到最后一个节点

nextl-a[nextl][2]next1-a[nextl][2]

pre=nextl

whilepre!=l:

#从最后一个节点向前遍历

print(a[pre][1])

pre=a[pre][0]

#删除中间元素，根据内容B#在头部插入元素

whilenextl!=1:a.append([1,'E',head])

ifa[nextl]head=len(a)1

breakpre=next1=head

else:

pre=nextl

nextl=a[nextl][2]

a[a[nextl][2]][0]=a[nextl][0]

a[pre][2]=a[nextl][2]

表1.2

#插入中间元素根据值#删除第一个元素

whilenextl!=1: