资源简介

(共43张PPT)
信息技术
2
第二章
数组与链表
计算机中数据的存储模式分为顺序存储和非顺序存储，所有数据结构的存储也可以分为这两类，而作为常用数据结构中的数组与链表，就是这两种存储模式的典型代表,其他的数据结构都是在这两种数据结构的基础上构建的。
顺序存储结构和非顺序存储结构
计算机中数据的存储结构主要分为顺序存储结构和非顺序存储结构。其中顺序存储结构是将逻辑上相邻的数据节点存储在物理位置相邻的存储单元中，典型代表为数组;而非顺序存储结构的形式就是链式存储结构，在链式存储结构中可以将逻辑上相邻的数据节点在内存中分开存储，节点之间的前后关系由每个节点中的指针确定,典型代表为链表。
第二章 数组与链表
数组与链表
数组
链表
链表的概念
链表的特性
链表的基本操作
数组的概念
数组的特性
数组的基本操作
内容总览
数组是由相同类型的变量构成的一个序列。
由数组名和下标组成数组的各个变量称为数组的分量，也称为下标变量或数组元素。
b[0] b[1] b[2] b[3] b[4]
20 15 14 10 4
b [3]
数组分量/下标变量/数组元素
b
[3]
数组名
下标
每个数组元素的类型相同，所需的存储空间一致，因此在明确第一个数组元素的存储位置后，可以利用下标计算出其他数组元素的存储位置，从而达到快速访问的目的。
2.1 数组
一维数组：只有一个下标的数组称为一维数组，一维数组适合用来表示具有一维空间的线性特征的数据序列。
数组元素：d[0],d[1],d[2],d[3],d[4]….
二维数组（形象、方便）：
二维空间内既有纵向联系又有横向联系的一批数据。
由于二维数组中的数据元素有行、列两个维度位置信息，因此需要两个下标。
数组下标表示方法
不同程序语言中的数组，特别是多维数组的下标表示各有不同。有的语言中使用多个方括号分别表示其中一个下标，如: a[1][3]，典型代表有C、C++、Python等;有的语言中则是使用一个方括号包含所有下标，每个下标之间用逗号隔开，如: a[1,3]，典型代表有Pascal;有的则使用一个圆括号包含所有下标，每个下标之间用逗号隔开，如: a(1,3)，典型代表有VB。
0 1 0 0
1 2 2 0
0 2 0 1
0 2 0 0
数组名：qp 列位置下标：
0 1 2 3
行位置下标：0
1
2
3
数组元素：qp[0][0], qp[0][1],……, qp[3][3],
行、列下标均从0开始
0：无子
1：黑子
2：白子
qp[0][0]=0
qp[0][1]=1
qp[0][2]=0
qp[0][3]=0
存储方式可分为：行优先和列优先两种。
二维数组：顺序存储
数组名qp
下标
[0][0]
[0][1]
[0][2]
[0][3]
[1][0]
[1][1]
[1][2]
……
0
1
0
0
1
2
2
…
数组名：qp 列位置下标：
0 1 2 3
行位置下标：0
1
2
3
数组元素：qp[0][0], qp[0][1],……, qp[3][3],
0 1 0 0
1 2 2 0
0 2 0 1
0 2 0 0
数组快速访问：先指向第一个第一行数组元素存储的位置，其他元素根据下标快速得到存储位置。
2.数组的特性
（1）数组元素（下标变量）的数据类型相同
（2）通过下标变量对数组元素的值进行访问
（3）存储空间固定不变
除非特殊说明，数组指向的往往是静态数组
开辟一批地址连续，且空间固定的存储空间。
快速访问一维数组a[9]:第10个元素的位置
静态数组特点：
规模可预估，处理过程稳定
动态数组
没有确定数据规模的数组，可以在任何时候改变数据规模。可在运行时具体改变数组大小的，从而引入动态数组。
2.1.2 数组基本操作
列表包含类型可不同。《必修1 》P72
列表=数组（列表中每个数据元素所含数据项的数量和数据类型都相同）
列表的存储
列表的存储虽然可以使用列表来模拟数组,但是列表的存储方式与数组是截然不同的,列表中索引是连续的,但其数据元素在内存中存储时一般不是连续存储的,这是由Python中变量存储模式决定的，如定义1000个初始化为0的列表,这1000个数值为0的列表元素均指向同一个地址,可以使用id()函数进行验证。
1.数组的创建
例1 统计分数
学校元旦文艺汇演比赛时，现场有9位评委给各班节目打分，统计系统需要根据9位评委的原始分计算平均分作为各班表演节目的最终得分。
分析：该问题中9位评委给出的分数属于同一类型的数据，可以创建一个包含9个下标变量的数值型数组来存储评委的原始分。
创建保存评委原始分的一维数组s的程序如下：
qp=[[0]*4]*4
规模较小
规模较大
二维数组的创建
Python中二维数组的创建
Python中创建二维数组的方式比较特殊,不能使用如同一维数组的方式创建,若使用语句qp=[[0]*4]*4来创建,则在修改某行元素时,4行中同一列的数据会同时被修改。这是因为其实质是创建了一行数据的4个引用,因此修改某一行中的数据相当于修改了所有行中的数据。这种情况在Python中称为浅拷贝。
0 0 0 0
qp=[[0]*4]*4
二维数组：3行4列？
1.8作业：
创新设计-《教学案》 p8-p9
2.数组的访问
由于数组元素可以通过数组名和下标快速确定数据元素的内存地址，因此可通过下标变量直接进行访问。例如，print(s[5])表示将一维数组s中第6个元素的值进行输出（第1个元素为s[0]）。
第一章1.2节将“数据合并”问题简化成合并两个有序数据序列的问题，对如何使用数组解决数据合并问题进行了分析并设计了算法。下面将对算法进行修改和优化，避免插入数据时其他数据元素的移动，并编程实现该功能。
例2 基于数组实现数据合并的功能
①初始化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。
1.如何保证降序？
2.如何合并数据？
3.如何做到空间适时灵活分配？
4.若数组a、b元素相等，哪个放前？
5.若数组a、b元素个数不等，其中一个数组元素排完后，另一个数组剩下元素怎么办？
程序 测试结果
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数组序列
3.数组的插入与删除
当需要在数组中某个位置插入一个新的数据时，必须先将该位置及其后的所有数据向后移动一个位置，在保证顺序不变的前提下保存这些数据，最后再修改该位置上的数据为新数据。
在数组d中第3个位置( d[2])插入新数据：
将该位置及其后所有数据依次向后移动一个位置;
第二步，修改d[2]的值为新的数据。
静态数组插入元素，移动位置：a[i+1]=a[i]；
效率较低，可能会超出数组元素数量而导致数据丢失；
思考
？
静态数组删除元素：将被删除元素位置后的所有元素前移一个位置：a[i]=a[i+1]；
效率较低，且删除元素后，会留有空位，造成存储空间浪费；
在使用数组组织、存储数据时应避免数组元素的增删操作！
例3 基于数组的车牌摇号系统功能实现
汽车数量的急剧增加，导致城市交通的压力越来越大，许多大城市采取通过摇号方式来发放汽车车牌。在申请人通过资格审核后，车牌摇号系统反馈回一个唯一的编号。每次摇号前，车牌摇号系统需要收集所有本次申请人的编号，再在所有编号中随机抽取不重复的若干个编号来发放车牌。
（1）抽象与建模
用n表示有资格参加摇号的申请人总数，用序列luck存储编号，luck 0 ，luck 1 ，…，luck n–1 依次表示n个编号，其中的下标表示每个编号的位置，luck i 的初值为第i+1位申请人的编号。使用变量m表示最终的车牌发放数量，计数器c表示已抽中人数，每当随机抽出一个有效的下标位置（如k）时，计数器c加1，输出申请人的编号后将该下标位置（如luck k ）的值设为空串（表示该编号已被抽取），用来判断其后抽取的编号是否重复。重复该过程直至计数器c的值变为m，摇号结束。
例3 基于数组的车牌摇号系统功能实现
（2）设计算法
由于该问题中数据规模可以预估，在处理过程中其数据规模保持不变，并需要根据随机产生的编号读取和修改对应的值，所以用数组来存储所有申请人的编号，下标表示该编号的位置。算法分为两个步骤：
①根据申请人总数n，初始化数组luck，其数组下标代表位置，数组元素值为申请者编号（类型为字符串），并使用计数器c表示已抽中人数，初始化值为0。
②使用随机整数函数randint(a,b)随机产生一个位置k，若其作为数组下标对应的数组数据元素值为空串，则表示该编号已被抽取，该编号为重复号码，需要重新生成；否则，表示该编号为有效编号，计数器c加1，输出对应的数组元素并修改数组元素值为空串，表示该编号已被抽取。
③重复执行步骤②，直至计数器c变为m，程序结束。
函数和方法 功能 实例
len(list) 统计列表list中元素个数 list=[]
print(len(list))
输出为：0
list.append(x) 在列表中list末尾添加元素x list=[22,33,44]
list.append(55)
print(list)
输出为：[22,33,44,55]
list.insert(i,x) 在列表list中下标为i处插入元素x list=[“A”, ”B”, ”D”]
list.insert(2,”C”)
print(list)
输出为：[“A”, ”B”, ”C”，”D”]
list.pop(i） 将列表list中下标为i的元素删除，若i不指定，默认为-1，即最后一个 list=[“A”, ”B”, ”C”，”D”]
list.pop(2)
print(list)
输出为：[“A”, ”B”, ”D”]
函数和方法 功能 实例
len(list) 统计列表list中元素个数 list=[]
print(len(list))
输出为：0
list.append(x) 在列表中list末尾添加元素x list=[22,33,44]
list.append(55)
print(list)
输出为：[22,33,44,55]
list.insert(i,x) 在列表list中下标为i处插入元素x list=[“A”, ”B”, ”D”]
list.insert(2,”C”)
print(list)
输出为：[“A”, ”B”, ”C”，”D”]
list.pop(i） 将列表list中下标为i的元素删除，若i不指定，默认为-1，即最后一个 list=[“A”, ”B”, ”C”，”D”]
list.pop(2)
print(list)
输出为：[“A”, ”B”, ”D”]
使用以上列表的函数和方法后，可以将由列表模拟实现的数组视为动态数组，其中的增加、删除数组元素的操作由相应的函数实现。
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
m=int(input(" 请输入发放数： "))
for i in range(m):
k=randint(0,n-1)
print(luck[k])
luck.pop(k) #编号抽取后删除
n-=1 #元素数组减少1个
思考与练习
？
1.参考二维数组的行优先存储方式，画图模拟二维数组的列优先存储方式。观察并比较行优先存储与列优先存储中相同元素的存储位置的改变，如qp[1][2]在行优先存储方式下在序列的第7个位置，则其在列优先存储方式下在序列的第几个位置
2.参考摇号系统的功能实现，将自己班级所有同学的名字以一个名字一行的形式存入文件name.csv，并使用文件读入的方式，使用数组实现随机抽奖程序。
课堂小结：
2.1.2 数组基本操作
列表包含类型可不同。《必修1 》P72
列表=数组（列表中每个数据元素所含数据项的数量和数据类型都相同）
列表的存储
列表的存储虽然可以使用列表来模拟数组,但是列表的存储方式与数组是截然不同的,列表中索引是连续的,但其数据元素在内存中存储时一般不是连续存储的,这是由Python中变量存储模式决定的，如定义1000个初始化为0的列表,这1000个数值为0的列表元素均指向同一个地址,可以使用id()函数进行验证。
下列python语句的输出结果是：
s1=[4,5,6]
s2=s1
s[1]=0
print(s2)
A.[4,5,6] B.[0,5,6]
C.[4,0,6] D.[1,0,0]
答案：C
s1和s2指向同一对象（同一个列表）
浅拷贝vs深拷贝
在浅拷贝时，拷贝出来的新对象的地址和原对象的地址是不一样的，但是新对象的可变元素和原对象的可变元素的地址是一样的。也就是说，浅拷贝它拷贝的是浅层次的数据结构元素（不可变元素），对象的可变元素作为深层次的数据结构并没有被拷贝到新地址里面去，而是和原对象的可变地址指向同一个地址，所以在新对象和原对象里对这个可变元素做修改时，两者对象同时改变。
不可变元素
可变元素
浅拷贝
拷贝前后对象地址应当不同
可变元素
不可变元素
python格式化输出（使用占位符）：【选修1作业本】P13
%s表示字符串输出，%d表示整数输出，%f表示浮点数输出
示例：
>>> name="Lucy"
>>> age=19
>>> print('%s的年龄是%d'%(name,age))
Lucy的年龄是19
示例：
>>> money=12345.123456789
>>> name="174"
>>> print('%s的工资是%f'%(name,money))
174的工资是12345.123457 默认保留6位小数
示例：
>>> scale=0.13526
>>> print('数据的比例是%.2f%%'%scale)
数据的比例是0.14%
python格式化输出：
情况一：
>>> rate=0.91826
>>> print("rate的终值为:%0.2f分"%rate)
rate的终值为:0.92分
情况二：
>>> rate=0.91826
>>> print("rate的终值为:%.2f分"%rate)
rate的终值为:0.92分
情况三：
>>> rate=0.91826
>>> print("rate的终值为:%0.3f分"%rate)
rate的终值为:0.918分
作业本 （双色版）
11.9作业：
《2.1 数据的概念及其操作》1-7题
错题本：整理《上机实验练习纸》，例如：升序段个数+其他任意两题
格式：选择题（可以剪程序，自己写解析思路）
编程题：重在一题多解（例如：list.append()或者list=list+[]）
杨辉三角：
1
1 1
1 2 1
1 3 3 1
1 2 6 4 1
1 5 8 10 5 1
………………
数组名：pas 列下标元素
0 1 2 3 4
0 1
行 下 标 位 值 1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
（1）为了在计算机中存储和处理所指元素，已知数字“6”存储在数组元素pas[4][2]中,其值由数组元素________和数组元素_________相加得到。
（2）在程序设计时，先将数组pas中的数据元素均赋初值为1，然后从数组元素_____开始进行计算（数字“1”无须再次计算）。
（3）实现输出该图形的代码如下，在程序划线处填入适当的语句表达式，将程序补充完整。
n=int（input(“请输入行数n=”)） #输出n行的杨辉三角
pas=[[1 for 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
数组名：pas 列下标元素
0 1 2 3 4
0 1
行 下 标 位 值 1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
作业本 （双色版）
11.9作业：
《2.1 数据的概念及其操作》1-7题
下节课复习带知识清单2张（学考+选考）、《必修1 数据与数据计算》教材

展开更多......

收起↑