2.1 数组（教学课件）信息技术浙教版2019选择性必修1

第1节 数组（1.5课时） 第2章 数组与链表 浙教版（2019） 选修一 数组的概念与特性 01 数组的基本操作 02 学习目录 理解数组概念和特性 01 能运用数组编程解决实际问题。 03 掌握数组的基本操作。 02 学习目标 PART 01 数组的概念与特性 新课导入 想 想 一 想要用程序实现比较不同人的身高，完成从高到矮的排序。 思考:随着人越来越多,需要的变量也增加,如何解决这个问题? 问题 这些变量有什么共同特点? 提问 新课导入 身高都是数值，即数据类型相同 数组在内存中的存储方式为顺序存储，适用于数据规模可预估且在处理过程中数据规模保持稳定的问题。 变量有什么共同特点 ？ 数组的概念与特性 一 顺序存储结构和非顺序存储结构 计算机中数据的存储结构主要分为顺序存储结构和非顺序存储结构。其中顺序存储 结构是将逻辑上相邻的数据节点存储在物理位置相邻的存储单元中，典型代表为数组;而 非顺序存储结构的形式就是链式存储结构，在链式存储结构中可以将逻辑上相邻的数据节点在内存中分开存储，节点之间的前后关系由每个节点中的指针确定，典型代表为链表。 数组作为常用数据结构，有特定的数据组织、存储结构及操作特性。 拓展链接 数组的概念与特性 一 数组 的概念 01 02 用一个数组名和下标来唯一确定数组元素 数组是一组具有相同数据类型的变量集合 a[i] 数组名 数组 元素 下标/索引 数组的概念与特性 一 数组 的概念 数组在内存中存储的结构简单，创建数组时系统会分配一块连续的存储空间，每个数组元素按照下标顺序依次存储。 数组的存储结构 如右图所示，数组中的数据在内存中按照下标顺序依次存储，使用数组名指向第一个数组元素存储的位置，由于每个数组元素的类型相同，所需的存储空间一致，因此在明确第一个数组元素的存储位置后，可以利用下标计算出其他数组元素的存储位置，从而达到快速访问的目的。 数组的概念与特性 一 二维数组（形象、方便） 二维空间内既有纵向联系又有横向联系的一批数据。 由于二维数组中的数据元素有行、列两个维度位置信息，因此需要两个下标。 数组下标表示方法 不同程序语言中的数组，特别是多维数组的下标表示各有不同。有的语言中使用多个方括号分别表示其中一个下标，如:a[1][3]，典型代表有C、C++、Python等;有的语言中则是使用一个方括号包含所有下标，每个下标之间用逗号隔开，如:a[1,3]，典型代表有Pascal;有的则使用一个圆括号包含所有下标，每个下标之间用逗号隔开，如:a(1,3)，典型代表有VB。 数组的概念与特性 一 二 维 数 组 描述的棋盘信息 平面棋盘 与棋子布局 数组的概念与特性 一 二维数组在内存中也采用顺序存储，有行优先存储和列优先存储两种方式。 数组名指向数组中第一行第一个元素存储的位置，其它数组元素可通过下标快速得到。 0 1 0 0 1 2 2 0 … [0] [0] [0] [1] [0] [2] [0] [3] [1] [0] [1] [1] [1] [2] [1] [3] … 0 1 0 0 1 2 2 2 … [0] [0] [1] [0] [2] [0] [3] [0] [0] [1] [1] [1] [2] [1] [3] [1] … 行优先存储 列优先存储 数组的概念与特性 一 一个数组的第一个元素的存储位置为1000(表示在第1000个字节处)，每个元素所占空间大小为8个字节，则第5个元素的位置是（ ）? A.1000 B.1040 C.1032 D.1256 C 数组的概念与特性 一 数组 的特性 （1） （3） （2） 特性 数组元素(下标变量)的数据类型相同 存储空间固定不变 通过下标变量对数组元素的值进行访问 数组的概念与特性 一 静态数组 动态数组 VS 遇到下面问题： 一是有些问题很难预估需要多少存储空间; 二是如果删除了很多数据元素，不能充分利用空余空间，导致系统内存的浪费。 我来解决： 数组定义时没有确定数据规模，可以在任何时候更改数据规模。 数组的基本操作 二 数组 列表 区别 数组 列表 元素类型 一致 可以不一致 存储结构 顺序（连续）存储 链式（不连续）存储 … … … 当列表中每个数据元素所含数据项的数量和数据类型均相同时，可以将该列表视为数组，列表索引可视为数组的下标。 ≠ 数组的基本操作 二 列表的存储 虽然可以使用列表来模拟数组，但是列表的存 储方式与数组是截然不同的，列表中索引是连续的， 但其数据元素在内存中存储时一般不是连续存储的，这是由Python中变量存储模式决定的，如定义1000 个初始化为0的列表，这1000个数值为0的列 表元素均指向同一个地址，可以使用id() 函数进行验证。 拓展链接 数组的基本操作 二 数组的创建 0 0 0 0 0 0 0 0 0 0 0 0 ※一维数组 ※二维数组 ①直接创建:a=[0,0,0] ②间接创建:a=[0]*3 ③列表生成式创建: ①直接创建:b=[[0,0,0],[0,0,0],[0,0,0]] ②间接创建: b=[[0]*3]*3 ③列表生成式创建: a=[0 for i in range(3)] 可以理解为: for i in range (3): a.append(0) a b 数组的基本操作 二 数组的创建 b=[[0]*3]*3 b[1][1]=1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 想象中的b数组 实际上的b数组 数组的基本操作 二 学校元旦文艺会演比赛时，现场有9 位评委给各班节目打分，统计系统需要 根据9位评委的原始分计算平均分，作为各班表演节目的最终得分。 分析:该问题中9位评委给出的分数属于 同一类型的数据，可以创建一个包含9个下标变量的数值型数组来存储评委的原始分。 例题：统计分数 数组的基本操作 二 程序 测试结果 一维数组S 的 程序 [0,0,0,0,0,0,0,0,0] s=[0]*9 print(s) 在Python中使用列表实现二维数组有两种方式: 一是直接定义，适合创建规模较小的二维数组; 二是间接定义，适合创建规模较大的二维数组。 数组的基本操作 二 下面两个程序分别使用直接定义和间接定义两种方式创建保存棋盘信息的二维数组qp，并将其信息按行输出。 常见的数据结构 二 只需知道数据之间相互链接的顺序 探讨与讨论 1 有如下Python程序段: a=[[0]*4]*3 b=[[0]*4 for i in range(3)] a[2][3]=8 b[2][3]=8 则程序执行后，下列说法正确的是( ) A.a[0][3]的值为0,b[0][3]的值为0 B.a[0][3]的值为0,b[0][3]的值为8 C.a[0][3]的值为8,b[0][3]的值为0 D.a[0][3]的值为8,b[0][3]的值为8 C 常见的数据结构 二 只需知道数据之间相互链接的顺序 探讨与讨论 2 有如下Python程序段: a[[0]*3 for i in range(4)] for i in range(len(a)): for i in range(len[a[0]]): a[i][j]=i*len(a[0])+j+1 则程序执行后，a[2][2]的值为( ) A.5 B.6 C.8 D.9 D 数组的基本操作 二 数组元素的访问 数组元素可通过数组名和下标快速定位其内存地址，因此可通过数组名和下标直接进行访问。 01 02 一维数组 数组名[下标访问] 想要取到数组中第三个元素: a[2] 想要访问数组中第2到第4个元素切片访问: a[1:4] 二维数组 数组名[行下标][列下标] 想要取到数组中第2行第3列的元素: a[1][2] 访问第i行第j列的元素表示为: a[i-1][j-1] 数组的基本操作 二 第一章1.2节将“数据合并”问题简化成合并两个有序数据序列的问题，对如何使用数组解决数据合并问题进行了分析并设计了算法。下面将对算法进行修改和优化，避免插入数据时其他数据元素的移动，并编程实现该功能。 实例 讲解 01 04 02 03 使用变量i指向数组a，变量j指向数组b，变量k指向数组c 重复以下操作，直至数组a或数组b中的数据元素全部合并入数组c中:比较a[i]和b[j]的大小 初始化3个数组a，b，c，元素个数分别为n，m和n+m。 如果数组a或数组b中尚有未处理的数据元素，那么将剩余数据元素按原有顺序依次存入数组c中，合并完成，输出数组c。 （1）设计算法 数组的基本操作 二 （2）编写程序 对于二维数组，也可以使用数组的数组名和下标来任意访问数组元素。 阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”’。相关代码如下: a=[["浙江省","杭州市"]，["吉林省","长春市"],["湖南省","长沙市"],["湖北省","武汉市"],["江苏省","南京市"],["广东省","广州市"]] for p in a: print(f"{ }的省会是{ }") 则划线①和②处分别应填写的代码为( ) A.①p[1];②p[0] B.①p[0];②p[1] C.①a[p][0];②a[p][1] D.①p[1];②p[2] 课堂 小练 ① ② B 数组的基本操作 二 数组元素的插入与删除 当需要在数组中某个位置插入一个新数据时，必须先将该位置及其后的所有数据依次向后移动一位，在保证顺序不变的前提下保存这些数据，最后再修改该位置上的数据为新数据。 数组中 插入新数据的过程 数组的基本操作 二 要删除数组中的某个元素，只需将其后的所有元素依次前移一位，并将数组长度减一即可。 注:若数组的实际长度为n，删除元素只是让n减1，并不改变数组所占用的存储空间。 for i in range(p,n-1): a[i] = a[i+1] n -= 1 已知数组a的实际长度为n，删除下标为p的数组元素? a = [1,2,3,4,5] a.pop(2) a.pop() print(a) a.pop(i):删除列表a中下标为i的元素，若是i省略，则默认为-1，即删除最后一个元素 [1,2,4] 使用数组组织、存储数据时应尽量避免数组元素的增加或删除操作。 数组的基本操作 二 问题与 讨论 解析 问题 1.在数组中插入新数据是否可以先插入数据，再移动其他数组元素?移动数组元素时，其顺序应该是怎样的?为什么一定要这样的顺序? 2.参考数组元素的插入过程，分组讨论并得出在数组中删除一个数组元素的步骤及其注意事项。 对于静态数组，在增加数组元素时，需要将某位置及其后的所有元素后移一个位置后再插入，一方面时间效率较低，另一方面可能会超出限定的数组元素数量而导致数据的丢失;而在删除数组元素时，需要将被删除元素位置后的所有元素前移一个位置，同样有时间效率低的问题，而且在删除比较多的元素后，数组中存储的有效数据减少，从而造成存储空间的浪费。因此，在使用数组组织、存储数据时应尽量避免数组元素的增删操作。 有了数组概念并知道数组的基本操作后，可以使用数组组织、存储数据解决问题。 数组的基本操作 二 车牌摇号系统 基于数组的车牌摇号系统功能实现 汽车数量的急剧增加，导致城市交通的压力越来越大，许多大城市采取通过摇号方式来发放汽车车牌。在申请人通过资格审核后，车牌摇号系统反馈回一个唯一的编号。每次摇号前，车牌摇号系统需要收集所有本次申请人的编号，再在所有编号中随机抽取不重复的若干个编号来发放车牌。 数组的基本操作 二 (1)抽象与建模 用n表示有资格参加摇号的申请人总数，用数组luck存储编号，luck[0]，luck[1]，…，luck[n-1]依次表示n个编号，其中的下标表示每个编号在数组中的位置，luck[i]的初值为第i+1位申请人的编号。使用变量m表示最终的车牌发放数量，计数器c表示已抽中人数，每当随机抽出一个有效的下标位置(如k)时，计数器c加1，输出申请人的编号后将该下标位置(如luck[k])的值设为空字符串(表示该编号已被抽取)，用来判断其后抽取的编号是否重复。重复该过程直至计数器c的值变为m，摇号结束。 数组的基本操作 二 01 03 02 第一步 第三步 第二步 根据申请人总数n，初始化数组luck，其数组下标代表位置，数组元素值为申请者编号(类型为字符串)，并使用计数器c表示已抽中人数，初始化值为0。 使用随机整数函数randint(start,end)随机产生一个位置k，若其作为数组下标对应的数组数据元素值为空串，则表示该编号已被抽取，该编号为重复号码，需要重新生成;否则，表示该编号为有效编号，计数器c加1，输出对应的数组元素并修改数组元素值为空串，表示该编号已被抽取。 重复执行步骤②，直至计数器c变为m，程序结束。 (2)设计算法 数组的基本操作 二 (3)编写程序 数组的基本操作 二 Python列表常用函数与方法 课堂小练 三 1.列关于数组的描述中，不正确的是（ ）A.数组元素的数据类型均相同B.仅通过数组名就能访问数组中的某个元素C.数组一旦创建好以后，其存储空间将固定不变D.在数组中进行删除元素操作后，其占用的空间不会发生改变 2.有二维数组a=[[1,2,3],[4,5,6],[7,8,9]]，则数组元素a[1][2]的值为( )A.1 B.2 C.6 D.73.有一维数组a=list[“computer”]，则数组元素a[-3]的值为( )A.“m” B.“p” C.“u” D.“t” B C D 课堂练习 三 只需知道数据之间相互链接的顺序 探讨与讨论 4.有如下Python程序段： a=[3,6,12,5,9,20,17,8] p=0 for i in range (1,len(a)): if a[i]>a[p]: p=i a.pop(p) 则执行程序段后，数组a中的元素为( ) A.3,6,12,5,9,20,17,8 B.3,6,12,5,9,17,8 C.3,6,12,5,9,20,17 D.6,12,5,9,20,17,8 B 小结 四 小 结 数组的概念和特性 数组的应用 数组的基本操作 数组 1.数组的创建 2.数组元素的访问 3.数组元素的插入与删除 1.数组的概念 2.数组的特性 ①数组元素(下标变量)的数据类型相同 ②通过下标变量对数组元素的值进行访问 ③存储空间固定不变 谢谢观看 第1节 数组 浙教版（2019） 选修一 $$