2.1.1 数组的概念、特性、基本操作 课件（27张PPT）

(共27张PPT)
选择性必修1《数据与数据结构》
第二章 数组与链表
2.1.1 数组的概念、特性、基本操作
情境导入——杭州车牌阶梯摇号
情境导入——杭州车牌阶梯摇号
随机种子数
摇号基数序号
数组基本概念
数组是由相同类型的变量构成的一个序列。
由数组名和下标组成数组的各个变量称为数组的分量，也称为下标变量或数组元素。
b[0] b[2] b[3] b[4] b[5]
20 15 14 10 4
b [3]
数组分量/下标变量/数组元素
b
[3]
数组名
下标
每个数组元素的类型相同，所需的存储空间一致，因此在明确第一个数组元素的存储位置后，可以利用下标计算出其他数组元素的存储位置，从而达到快速访问的目的。
数组基本概念
一维数组：只有一个下标的数组称为一维数组，一维数组适合用来表示具有一维空间的线性特征的数据序列。
数组元素：d[0],d[1],d[2],d[3],d[4]….
数组基本概念
二维数组：二维数组中的数据元素有行、列两个维度的元素，需要两个下标。
平面棋盘与棋子布局
二维数组描述的棋盘信息
数组基本概念
二维数组描述的棋盘信息
二维数组行优先存储方式
请填写二维数组列优先存储方式。
数组的特性
（1）数组元素（下标变量）的数据类型相同
（2）通过下标变量对数组元素的值进行访问
（3）存储空间固定不变
除非特殊说明，数组指向的往往是静态数组
数组的基本操作——一维数组的创建
例1 统计分数
学校元旦文艺汇演比赛时，现场有9位评委给各班节目打分，统计系统需要根据9位评委的原始分计算平均分作为各班表演节目的最终得分。
分析：该问题中9位评委给出的分数属于同一类型的数据，可以创建一个包含9个下标变量的数值型数组来存储评委的原始分。
创建保存评委原始分的一维数组s的程序如下：
数组的基本操作——二维数组的创建
qp=[[0]*4]*4
数组元素的访问
由于数组元素可以通过数组名和下标快速确定数据元素的内存地址，因此可通过下标变量直接进行访问。例如，print(s[5])表示将一维数组s中第6个元素的值进行输出（第1个元素为s[0]）。
数组元素的访问
算法设计：
①初始化3个数组a，b，c，元素个数分别为n，m和n+m。数组a和数组b用来存储已有的两个有序数据（降序），数据使用随机函数randint(start,end)产生；数组c用于保存合并后的所有数据（降序），所有数组元素的值初始化为0。
②使用变量i指向数组a当前未处理数据中要处理的数据元素的位置，初始化为0；变量j指向数组b当前未处理数据中要处理的数据元素的位置，初始化为0；变量k指向数组c中可加入元素的位置，初始化为0。
数组元素的访问
算法设计：
③重复以下操作，直至数组a或数组b中的数据元素全部合并入数组c中：比较a[i]和b[j]的大小，若a[i]≥b[j]，则将a[i]放入数组c中，并将i和k的值增加1；否则，将b[j]放入数组c中，并将j和k的值增加1。
④如果数组a或数组b中尚有未处理的数据元素，那么将剩余数据元素按原有顺序依次存入数组c中，合并完成，输出数组c。
数组元素的访问
程序 测试结果
from random import randint a=[0]*20 #创建数组 b=[0]*15 c=[0]*35
a[0]=randint(95,100) for i in range(1,20): # 随机产生降序数据序列一 a[i]=a[i-1]-randint(1,5) 生成a数组序列：
[99, 97, 95, 94, 90, 87, 83,79, 78, 73, 71, 69, 67, 66, 61,60, 56, 55, 52, 51]
b[0]=randint(95,100) for i in range(1,15): # 随机产生降序数据序列二 b[i]=b[i-1]-randint(1,5) 生成b数组序列：
[99, 96, 94, 91, 90, 88, 87,
82, 80, 79, 75, 73, 70, 66, 62]
print(" 原始数据序列一为： ") print(a) print(" 原始数据序列二为： ") print(b)
数组元素的访问
程序 测试结果
i=0 j=0 k=0 while(i<20 and j>15): # 合并数据直至某个数组数据合并完成 if a[i] >=b[j]: c[k]=a[i] i=i+1 k=k+1 else: c[k]=b[j] j=j+1 k=k+1 C数组序列
[99, 99, 97, 96, 95, 94, 94,
91, 90, 90, 88, 87, 87, 83, 82,
80, 79, 79, 78, 75, 73, 73, 71,
70, 69, 67, 66, 66, 62,0,0,0,0,0,0]
j=15
i=14
数组元素的访问
程序 测试结果
while i < 20: # 当数据序列一中还有数据时的处理 c[k]=a[i] i=i+1 k=k+1 C数组序列
[99, 99, 97, 96, 95, 94, 94,
91, 90, 90, 88, 87, 87, 83, 82,
80, 79, 79, 78, 75, 73, 73, 71,
70, 69, 67, 66, 66, 62, 61, 60,
56, 55, 52, 51]
j=15
i=20
while j ＜ 15: # 当数据序列二中还有数据时的处理 c[k]=b[j] j=j+1 k=k+1
print(" 合并后的数据序列为： ") print(c) 输出合并后的C数组序列
数组元素的访问
二维数组访问：
二维数组，可以使用数组的下标变量来任意访问数组元素。
数组元素的插入与删除
数组元素的插入与删除
车牌摇号系统实例
（1）抽象与建模
用n表示有资格参加摇号的申请人总数，用序列luck存储编号，luck 0 ，luck 1 ，…，luck n–1 依次表示n个编号，其中的下标表示每个编号的位置，luck i 的初值为第i+1位申请人的编号。使用变量m表示最终的车牌发放数量，计数器c表示已抽中人数，每当随机抽出一个有效的下标位置（如k）时，计数器c加1，输出申请人的编号后将该下标位置（如luck k ）的值设为空串（表示该编号已被抽取），用来判断其后抽取的编号是否重复。重复该过程直至计数器c的值变为m，摇号结束。
车牌摇号系统实例
（2）设计算法
由于该问题中数据规模可以预估，在处理过程中其数据规模保持不变，并需要根据随机产生的编号读取和修改对应的值，所以用数组来存储所有申请人的编号，下标表示该编号的位置。算法分为两个步骤：
①根据申请人总数n，初始化数组luck，其数组下标代表位置，数组元素值为申请者编号（类型为字符串），并使用计数器c表示已抽中人数，初始化值为0。
②使用随机整数函数randint(a,b)随机产生一个位置k，若其作为数组下标对应的数组数据元素值为空串，则表示该编号已被抽取，该编号为重复号码，需要重新生成；否则，表示该编号为有效编号，计数器c加1，输出对应的数组元素并修改数组元素值为空串，表示该编号已被抽取。
③重复执行步骤②，直至计数器c变为m，程序结束。
车牌摇号系统实例
车牌摇号系统实例
Python列表常用函数与方法
车牌摇号系统列表函数版
from random import randint
luck=[] # 新建列表
csv_file=open("bh.csv", "r", encoding='utf-8') # 打开存有编号的文件 bh.csv
flines=csv_file.readlines() # 将文件中所有编号按行读入 flines 中
csv_file.close # 关闭文件
n=0
for one_line in flines:
tmp=one_line.strip("\n") # 将一个编号去除换行后赋给 tmp
luck.append(tmp) #填加列表元素
n+=1 #元素数组减少1个
m=int(input(" 请输入发放数： "))
for i in range(m):
k=randint(0,n-1)
print(luck[k])
luck.pop(k) #编号抽取后删除
n-=1
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能理解数组的概念、组织结构及其特性。 5 4 3 2 1 5 4 3 2 1
了解数组的基本操作 5 4 3 2 1 5 4 3 2 1
能合理利用数组解决相应的简单问题并编程实现 5 4 3 2 1 5 4 3 2 1
课堂作业