数据结构基础知识01--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（一） 【知识要点】 1.数组的概念与特性 （1）数组的概念 数组是由相同类型的变量构成的一个序列。数组使用一个标识符（数组名）命名，并用编号（下标或索引）区分数组内的各个变量。由数组名和下标组成数组的各个变量称为数组的分量，也称为数组元素。 （2）数组的特性 ①数组元素的数据类型相同。②通过数组名和下标对数组元素的值进行访问。③存储空间固定不变。 （3）array 模块 array 模块是 Python 中一种高效的数组存储类型。它和 list 相似，但是所有的数组成员必须是同一种类型，在创建数组的时候，就确定了数组的类型。 2.数组的基本操作 （1）数组的创建 ①数组的创建实质是在系统内存中划分一块连续区域，用来保存数组所含的所有数据元素。 ②在Python中使用列表来模拟数组，其所占空间大小可以用内置函数len（）来获取。例如，创建一个长度为 10 的整型数组，其初始化元素值均为 0，代码：a=[0]*10 ③在Python中使用列表生成式来创建数组。例 如，创建一个长度为10的随机整数数组，元素值为0或1，代码：b=[random.randint(0,1) for i in range(10)] （2）数组元素的访问 ①数组元素的访问指的是寻址到特定的数据元素，并根据存储地址对该数据元素进行读取、修改等操作。由于数组元素可以通过数组名和下标快速确定数据元素的内存地址，因此可以通过数组名和下标直接进行访问。例如print(a[2])表示将一维数组a中第3个元素的值进行输出（第1个元素为a[0]。 ②数组的存储方法是顺序存储，每个元素在存储器中占用的空间大小相同。若第一个元素存放的位置是LOC(0)，每个元素占用的空间大小为s，则元素a[i]的存放位置为：LOC(i)=LOC(0)+s*i，任给一个i，可以很快计算出LOC(i)。 （3）数组元素的插入 ①当需要在数组中某个位置插入一个新的数据时，必须先将该位置及其后的所有数据向后移动一个位置，在保证顺序不变的前提下保存这些数据，最后再修改该位置上的数据为新数据。 ②举例：已知数组a所占空间为len(a)，其元素个数（实际长度）为n，当n<len(a)时，在数组a的下标p处插入一个新元素x的代码如下： for i in range(n,p,-1): #将p的位置及其后元素整体后移，腾出空位 a[i]=a[i-1] a[p]=x #将新的元素x插入到p的位置 n+=1 #数组实际长度增加1 ③Python列表提供了insert()方法将指定对象插入到列表的指定位置。其语法格式为list.insert(p,x)，其中参数p表示对象x需要插入的索引位置。该方法没有返回值。 （4）数组元素的删除 ①要删除数组中的某个元素，只需将其后的所有元素依次前移一位，然后将数组长度减一即可。通常记录数组的实际长度为n，删除元素后，只让n减1，而不改变数组所占空间。 ②举例：已知数组a的实际长度为n，将其下标为p的元素删除，代码如下： for i in range(p,n-1): #将p的位置及其后元素依次前移一位 a[i]=a[i+1] n-=1 #数组实际长度减少1 ③Python 列表提供了 pop()方法来移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。其语法格式为 list.pop([p=-1])，其中参数 p 表示要移除列表元素的索引值，不能超过列表总长度，默认p=-1，删除列表的最后一个元素。该方法返回从列表中移除的元素对象。 ④使用 del 语句来删除列表中的元素，例如 del a[p]表示删除列表 a 中下标为 p 的元素；del a[:]表示删除列表 a 中的所有元素，结果使得 a=[]；del a 表示删除列表 a，使之从内存中消失。 3.二维数组的概念与特性 （1）二维数组本质上是以数组作为数组元素的数组，即“数组的数组”。二维数组又称为矩阵，行列数相等的矩阵称为方阵。 （2）数组的存储方法是顺序存储，每个元素在存储器中占用的空间大小相同。 （3）按“行优先顺序”存储二维数组时，需要知道它的最大列数。若二维数组第一个元素存放的位置是LOC(a[0][0])，最大列数为C，每个元素占用的空间大小为s，则元素a[i][j]的存放位置为：LOC(a[i][j])=LOC(a[0][0])+s*（i*C+j），按“列优先顺序”存储二维数组时，需要知道它的最大行数R。元素a[i][j]的存放位置为：LOC(a[i][j])=LOC(a[0][0])