2.1数组课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第二章浙教版（2019）

一维数组的概念与基本操作 信息技术 选考课程 学习目标 1、了解数组的概念和特性。 2、掌握一维数组的基本操作（创建/访问/插入/删除）（重点）。 3、理解数组的合并过程及程序实现。 4、数组的应用 – 寻找最值及其下标、寻找相邻元素差值中的最大值。 一、数组概念 1、数组是一组具有相同数据类型的数据元素的集合，占用一段连续的存储空间， 常用来实现数据的顺序存储。 访问：用一个数组名和下标(索引)来唯一确定数组元素。 姓名 年龄 身高 体重 张三 30 178 150 李四 29 160 90 王五 33 167 140 …… …… …… …… xm[i] age[i] sg[i] tz[i] “张三” “李四” “王五” 内存 xm[0] xm[1] xm[2] python语言为例： xm = [“张三”,”李四”,”王五”] 一维数组 3 一、数组特性 数组元素的数据类型相同 系统会根据数组的数据类型和总元素个数，在内存中开辟一批连续且空间固定的存储空间 通过数组名和下标对数组元素的值进行访问 存储空间固定不变（静态数组） 可能造成空间浪费和空间不够导致数据丢失的现象。 静态数组：数组适用于数据规模可预估且在处理过程中保持稳定的问题。 二、一维数组的基本操作（创建/访问/插入/删除） ①Python没有数组这种结构，但当列表中每个数据元素所含数据项的数量和数据类型均相同时，可以将其视为数组，即Python中可使用列表来实现数组的基本操作。 ②数组创建的实质是在系统中划分一块连续区域，用来保存数组所含的所有数据元素。 一维数组的创建：a = [1,2,3,4] a = [0]*10 #创建一个长度为10的整型数组 a = [i for i in range(10) if i % 2 == 0] a = [random.randint(0,10) for i in range(10)] #用列表生成式创 建一个长度为10的随机整数数组 [0,2,4,6,8] 二、一维数组的基本操作（创建/访问/插入/删除） ①一维数组元素的访问: 数组名[下标/索引] a = [random.randint(0,10) for i in range(10)] print(a[0]) #注意：它是第一个元素 ②元素a[i]的存储位置计算方法： LOC(i)=LOC(0)+s*i #LOC(0)是第一个元素存放的位置 s是每个元素占用的空间大小 二、一维数组的基本操作（创建/访问/插入/删除） a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 6 3 1 2 8 10 5 在长度为n = 7的数组a中下标为 p= 3 （p<n）位置插入新数据newdata = 4 5 10 8 2 4 for i in range(n,p,-1): #移数据 腾位置 a[i]=a[i-1] #将p位置及其后所有数据依次后移 a[p]=newdata #插数据，占位置 n+=1 #更新数组长度n python列表在指定位置插入元素的方法 a.insert(k,newdata) python列表在末位添加元素a.append(newdata) for i in range(n-1,p-1,-1): a[i+1]=a[i] a[p]=newdata n+=1 a[i] a[i-1] a[i] a[i-1] a=[6,3,1,2,8,10,5] 二、一维数组的基本操作（创建/访问/插入/删除） a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 原数组 1 2 3 5 6 8 10 11 新数组 1 2 3 6 8 10 11 11 在长度为n = 8的数组a中删除下标为p = 3的数据 for i in range(p,n-1,1): a[i] = a[i+1] #p位置之后的所有元素依次前移 n -= 1 #数组实际长度减1 1. 将列表下标为k的元素删除，若k不指定，默认为-1，即最后一个元素。 a.pop(k) 2.移除列表中某个值的第一个匹配项 a.remove(a[k]) 3.del a[p]表示删除列表a中下标为p的元素 a[i] a[i+1] a[i] a[i+1] a=[1,2,3,5,6,8,10,11] 二、一维数组的基本操作（插入/删除程序对比小结） 在长度为n 的数组a中删除下标为p的数据 for i in range(p,n-1,1): a[i] = a[i+1] #p位置之后的所有元素依次前移 n -= 1 #数组实际长度减1 在长度为n的数组a中下标为 p(p<n)位置插入新数据 方法1： for i in range(n,p,-1): #移数据 腾位置 a[i]=a[i-1] #将p位置及其后所有数据依次后移 a[p]=newdata #插数据，占位置 n+=1 #更新数组长度n 方法2： for i in range(n-1,p-1,-1): a[i+1]=a[i] a[p]=newdata n+=1 三、数组的应用 – 数组合并 两个有序（降序）数组的合并，合并完后保证数组依然有序 a[0] a[1] a[2] a[3] 97 93 87 67 b[0] b[1] b[2] b[3] b[4] b[5] 100 95 92 88 86 85 c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] 100 97 95 93 92 88 87 86 85 67 from random import randint a=[0]*4 b=[0]*6 c=[0]*10 a[0]=randint(95,100) for i in range(1,4): # 随机产生降序数据序列一 a[i]=a[i-1]-randint(1,5) b[0]=randint(95,100) for i in range(1,6): # 随机产生降序数据序列二 b[i]=b[i-1]-randint(1,5) print(" 原始数据序列一为： ") print(a) print(" 原始数据序列二为： ") print(b) #首先生成两个原始降序序列 三、数组的应用 – 数组合并 P37 a[0] a[1] a[2] a[3] 97 93 87 67 三、数组的应用 – 数组合并 b[0] b[1] b[2] b[3] b[4] b[5] 100 95 92 88 86 85 c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] 0 0 0 0 0 0 0 0 0 0 c=[0]*10 i=0；j=0；k=0 while i<len(a) and j<len(b): if a[i]>b[j]: c[k]=a[i] i+=1 else: c[k]=b[j] j+=1 k+=1 while i<len(a): c[k]=a[i]；i+=1；k+=1 i j k a[0] a[1] a[2] a[3] 97 93 87 67 三、数组的应用 – 数组合并 b[0] b[1] b[2] b[3] b[4] b[5] 100 95 92 88 86 66 c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] 0 0 0 0 0 0 0 0 0 0 c=[0]*10 i=0；j=0；k=0 while i<len(a) and j<len(b): if a[i]>b[j]: c[k]=a[i] i+=1 else: c[k]=b[j] j+=1 k+=1 i j k while j<len(b): c[k]=b[j]；j+=1；k+=1 三、数组的应用 – 寻找最值及其下标 #寻找数组a中元素的最大值max，并定位最值的位置maxpos a=[2,3,6,3,1,5,6,2] maxpos=0 max=a[0] for i in range(1,len(a)): if a[i]>max: maxpos=i max=a[i] print("最大值是%d"%max,"最大值是第%d个数"%(maxpos+1)) 三、数组的应用 – 寻找相邻元素差值中的最大值 a = [5,2,4,8,9,6] max = abs(a[1]-a[0]) maxpos = 1 for i in range(2,len(a)): if abs(a[i]-a[i-1]) > max: max = abs(a[i]-a[i-1]) maxpos = i print("差值最大为%d"%max,"位置在第%d和第%d之间"%(maxpos,maxpos+1)) 三、数组的应用 – 去重 len(arr)-1,i,-1 三、数组的应用 – 去重 arr[j-c]=arr[j] 三、数组的应用 – 去重 arr[j]!=arr[i] 三、数组的应用 – 子序列问题 “子序列”的定义：选取原始序列中的若干项，维持它们的相对位置不变，组成的一个新的序列，该序列称为原始序列的一个子序列 “连续子序列”的定义：选取原始序列中连续的若干项（即区间内的所有项）组成一个新的序列，该序列称为原始序列的一个连续子序列 子序列 连续子序列 三、数组的应用 – 子序列问题 子序列和的最大值 a = [3,4,-8,5,7,-4,8] sum = 0 for i in range(len(a)): if a[i] > 0: sum = sum + a[i] print("子序列的最大和为：",sum) 样例数据： a[0] a[1] a[2] a[3] a[4] a[5] a[6] 3 4 -8 5 7 -4 8 连续子序列和的最大值 三、数组的应用 – 子序列问题 a = [3,4,-8,5,7,-4,8] sum,ans = 0,0 for i in range(len(a)): sum = sum + a[i] if sum > ans: ans = sum if ____________ : sum = 0 print(“连续子序列和的最大值：”,ans) 样例数据： a[0] a[1] a[2] a[3] a[4] a[5] a[6] 3 4 -8 5 7 -4 8 sum < 0 当前区间和sum 在此处取得最大和 思考：是否会有这样的特殊情况？ 三、数组的应用 – 子序列问题 取得最大和的连续子序列 a = [3,4,-8,5,7,-4,8] sum,ans,pos = 0,0,0 #pos表示连续子序列求和的起点 for i in range(len(a)): sum = sum + a[i] if sum > ans: ans = sum ____________ if sum < 0: sum = 0 _______ 程序结束后： 最大和为: . 取得最大和的起点为: . 取得最大和的终点为: . 取得最大和的长度为: . ans bg ed ed-bg+1 样例数据： a[0] a[1] a[2] a[3] a[4] a[5] a[6] 3 4 -8 5 7 -4 8 bg = pos ;ed = i pos = i + 1 22 三、数组的应用 – 子序列问题 连续上升子序列的最大长度 程序结束后： 连续升序列的最大长度为: . 取得最大长度的起点为: . 取得最大长度的终点为: . ans pos-ans+1 pos 样例数据： a[1] a[2] a[3] a[4] a[5] a[6] a[7] 3 4 5 4 7 8 9 a = [3,4,5,4,7,8,9] cnt,ans,pos = 1,1,1 #pos表示连续上升子序列的终点 for i in range(1,len(a)): if a[i] > a[i-1] : cnt = cnt + 1 else: cnt = 1 if cnt > ans : ans = cnt pos = i 四、总结 二维数组 信息技术 选考课程 二维数组本质上是以数组作为数组元素的数组，即“数组的数组”（列表的列表来模拟），二维数组又称为矩阵，行列数相等的矩阵称为方阵。 一、二维数组的概念与特性 P35 qp=[[0,1,0,0],[1,2,2,0],[0,2,0,1],[0,2,0,0]] 利用二维数组来组织和存储数据，通过数组名[行下标索引]来访问数据元素，通过数组名[行下标索引][列下标索引]来访问数据项。 一、二维数组的概念与特性 顺序存储：有行优先存储和列优先存储 0 1 0 0 1 2 2 0 ....... 内存 qp[0][0] qp[0][1] qp[0][2] qp[0][3] qp[0][4] qp[1][0] qp[1][1] …… qp[0][0] qp[0][1] qp[0][2] qp[0][3] qp[0][4] qp[1][0] qp[1][1] …… 0 1 0 0 1 2 2 2 ....... 没有特殊说明，按照行优先存储。 一、二维数组的概念与特性 行优先存储，计算qp[i][j]的存放位置： LOC(qp[i][j])=LOC(qp[0][0])+(i*C+j)*s #LOC(qp[0][0])是第一元素存放位置， C是最大列数，每个元素占用空间大小为s 列优先存储，计算qp[i][j]的存放位置： LOC(qp[i][j])=LOC(qp[0][0])+(j*R+i)*s #R是最大行数，每个元素占用空间大小为s 数组的存储方法是顺序存储，每个元素在存储器中占用的空间大小是相同的。 qp[2][3] 二、二维数组的基本操作 - 创建 5*5二维矩阵 直接定义qp = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] 间接定义qp = [[0 for i in range(5)] for j in range(5)] qp = [[0]*5 for i in range(5)] qp = [[0]*5]*5 qp[1][1] = 1 错误方式 书本P35 test = [[i for i in range(3)] for j in range(4)] 得到一个怎样的二维数组？ 4行3列的二维矩阵 二、二维数组的基本操作 - 访问 利用二维数组来组织和存储数据。通过数组名[下标索引]来访问数据元素，通过数组名[行下标索引][列下标索引]来访问数据项 输出棋盘： qp = [[0 for i in range(5)] for j in range(5)] for i in range(5): print(qp[i]) 在第2行第3列的位置落白子： qp[1][2] = 1 1 三、二维数组的遍历 逐行遍历： bz,hz = 0,0 for i in range(5): for j in range(5): if qp[i][j] == 1: bz = bz + 1 elif qp[i][j] == 2: hz = hz + 1 print(“白子数量为：”,bz,”黑子数量为：”,hz) 统计棋盘中黑子和白子的数量 三、二维数组的遍历 逐列遍历： bz,hz = 0,0 for i in range(5): for j in range(5): if qp[j][i] == 1: bz = bz + 1 elif qp[j][i] == 2: hz = hz + 1 print(“白子数量为：”,bz,”黑子数量为：”,hz) 杨辉三角 杨辉三角,是二项式系数在三角形中的一种几何排列,在我国南宋数学家杨辉1261年所编写的《详解九章算法》一书中出现。我们可以把杨辉三角看作这样的图形:最左侧一列数字和右边的斜边数字均为1,内部其他位置上的每个数字均为上一行同一列的数字与上一行前一列数字之和,前10行的杨辉三角如图2-1所示。 （1）为了在计算机中存储和处理如图2-1所示的数据，可用如图2-2所示的二维数组来表示。从图2-2中可知数字“6”存储在数组元素pas[4][2]中,其值由数组元素 和 相加得到。 （2）在程序设计时，先将数组pas中的数据元素均赋初值为1,然后从数组元素 开始进行计算（数字“1”无须再次计算）。 pas[3][1] pas[3][2] pas[2][1] 35 （3）实现输出该图形的代码如下,在程序划线处填入适当的语句或表达式,将程序补充完整。 n = int(input("请输人行数n= ")) #输出n行的杨辉三角 pas = [[1 for i in range(n)] for j in range(n)] for i in range(2,n): for j in range(1,i): pas[i][j] = pas[i - 1][j - 1] + ______①______ for i in range(n): s =[ ] #定义列表s用于输出每一行所需数据 for j in range(___②___): s.append(pas[i][j]) print(s) 程序中①划线处应填入________________ 程序中②划线处应填入________________ pas[i-1][j] i+1 $$