资源简介

(共45张PPT)
专题二　数组、链表及应用
思维导图
归纳提炼
一、数组及其操作
1.数组的概念
数组是由相同类型的变量构成的一个序列。
(1)由数组名和下标组成数组的各个变量称为数组的分量,也称为数组元素。
(2)创建数组时系统会分配一块连续的存储空间,每个数组元素按照下标顺序依次存储,数组在内存中的存储方式为顺序存储。
(3)一维数组:只有一个下标,下标用来表示数据元素在该序列中的位置。
二维数组:有两个下标,表示数据元素在该序列中的行、列位置,二维数组有行优先存储和列优先存储两种方式。
2.数组的特性
(1)数组元素的数据类型相同。
(2)通过数组名和下标对数组元素的值进行访问。
(3)存储空间固定不变。
3.数组的基本操作
(1)数组的创建
数组的创建实质是在系统内存中划分一块连续区域,用来保存数组所含的所有数据元素。
(2)数组元素的访问
通过数组名和下标直接进行访问数组元素。
(3)数组元素的插入与删除
①当数组中某个位置要插入一个新元素时,必须先将该位置及后面的所有数据向后移动一个位置,以空出该位置,用于存放新元素。
例如,在数组a的1位置插入一个新数据datax,操作后的数组a如下图所示。
②删除数组元素时,需要将被删除元素位置后的所有元素依次前移一个位置。
例如,删除数组元素a[1]后的数组如下图所示。
4.Python列表常用函数和方法
在Python中,常用列表来模拟实现数组的操作。
Python列表常用函数和方法
函数和方法 功能 实例
len(list1) 统计列表list1中元素的个数 list1=[1,2,3,4]
print(len(list1)),输出为4
list1.append(x) 在列表list1末尾添加元素x list1=[1,2,3,4]
list1.append(5)
列表中的内容为:[1,2,3,4,5]
list1.insert(i,x) 在列表list1中下标为i位置处插入元素x list1=[1,2,3,4]
list1.insert(2,5)
列表中的内容为:[1,2,5 3,4]
list1.pop(i) 将列表list1中下标为i的元素删除;若i不指定,默认为-1,即删除最后一个元素 list1=[1,2,3,4]
list1.pop()
列表中的内容为:[1,2,3]
二、链表及其操作
1.链表的概念
链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。
(1)链表中每个节点一般由“数据区域”和“指针区域”两部分构成。
(2)每个链表有一个表头——head(也称头指针),是链表的入口,也便于循环链表在数据处理时的边界判断和处理。
2.链表的形式
链表的形式主要有:单向链表、双向链表、循环链表。
单向链表:只有一个指针用来指向其后继节点。单向链表如下图所示。
双向链表:有两个指针分别用于指向其前驱节点和后继节点。双向链表如下图所示。
循环链表:第一个节点和最后一个节点使用指针链接。循环链表如下图所示。
3.链表的特性
(1)同一链表中每个节点的结构均相同。链表节点中包含数据区域和指针区域。
(2)每个链表必定有一个头指针,以实现对链表的引用和边界处理。
(3)链表占用的空间不固定。
可根据需求增删节点,提高了存储空间的利用率。
4.链表的基本操作
(1)链表的创建
(2)链表节点的访问
链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。
(3)链表节点的插入与删除
插入datax节点
删除data2节点
(4)链表节点的访问与遍历
当需要访问链表中某个位置的节点元素时,只能通过头指针进入链表并通过节点间的链接关系依次访问,直到找到指定位置的节点。
5.数组与链表的优缺点比较
数据结构 访问数据元素 插入、删除数据元素
数组 直接访问数组元素,效率高 需要大量移动数组元素,效率低
链表 通过头指针,通过节点的链接关系依次访问节点,效率低 不需要移动链表中的节点,效率高
典型例题
[例1] 下列有关数组的说法,正确的是(　 　)
A.一维数组适合用来表示具有线性特征的数据序列
B.二维数组表示的数据元素在内存中的存储方式为非顺序存储
C.仅通过数组名就能访问数组中的某个元素
D.非顺序存储结构的典型代表为数组
A
解析:二维数组表示的数据元素在内存中的存储方式也是顺序存储,有行优先存储和列优先存储两种方式,因此B选项错误;通过数组名和下标就能访问数组中的某个元素,因此C选项错误;数组是顺序存储结构的典型代表,因此D选项错误;一维数组适合用来表示具有线性特征的数据序列,因此答案为A。
[例2] 在Python语言中,一维数组d中第一个元素可表示为(　 　)
A.d(0) B.d(1)
C.d[0] D.d{0}
C
解析:一维数组元素表示为数组名[下标],一维数组d中第一个元素可表示为d[0],因此答案为C。
[例3] 某数组定义如下:b=[9,15,20,6,5,7,18,13],则运算表达式“b[1]+b[5]-b[7]”的值为(　 　)
A.-4 B.4
C.9 D.35
C
解析:一维数组d中第一个元素可表示为d[0],数组元素b[1]+b[5]-b[7]的值为15+7-13=9,因此答案为C。
[例4] 有如下Python程序段:
a=[8,7,6,5,15,12,11,20,19,18,0]
n=len(a)
cnt=0
for i in range(2,n):
　 if a[i]-a[i-1]==a[i-1]-a[i-2]:
　　　cnt+=1
print(cnt)
运行程序后,输出的结果为(　 　)
A.1 B.2
C.3 D.4
C
解析:当i分别为2、3、9时,满足条件“a[i]-a[i-1]==a[i-1]-a[i-2]”,即运行程序后,变量cnt的值为3,因此答案为C。
[例5] 下列有关链表的特性的描述,正确的是(　 　)
A.同一链表中每个节点的结构可以不同
B.一旦创建好链表后,链表的占用空间将固定不变
C.链表中相邻节点存储时需要连续的存储空间
D.每个链表必定有一个头指针,只有通过头指针才能进入链表
D
解析:同一链表中每个节点的结构必须相同,因此A选项错误;链表的占用空间是动态的,可以在建好的链表中增加或删除节点,因此B选项错误;链表中相邻节点存储时不需要连续的存储空间,可充分利用空闲的空间,因此C选项错误;每个链表必定有一个头指针,只有通过头指针才能进入链表,因此答案为D。
[例6] 一个单向链表如下图所示,在p所指节点之后插入新的节点(r所指节点),则执行的操作是(　 　)
D
A.先将r所指节点的next值赋为p所指节点的next值,然后将r所指节点的next值赋为p
B.先将r所指节点的next值赋为p所指节点的next值,然后将p所指节点的next值赋为-1
C.先将p所指节点的next值赋为r,然后将r所指节点的next值赋为p所指节点的next值
D.先将r所指节点的next值赋为p所指节点的next值,然后将p所指节点的next值赋为r
解析:在p所指节点之后插入新的节点(r所指节点)时,应先将r所指节点的next值赋为p所指节点的next值,然后将p所指节点的next值赋为r,两个操作顺序不能颠倒,若先将p所指节点的next值赋为r,则将找不到原表中p所指节点的后一个节点的位置,因此答案为D。
[例7] 某智能货架有一排货位,货位号从0开始编号,每个货位等宽。货架上可放置不同宽度(占 1~3 个货位)的箱子,箱子从左往右连续相邻摆放。每次放置箱子时,只能在货架上最后一个箱子的右侧放置新箱子,搬离某个箱子时,该箱右侧所有箱子被自动左移。编写程序,模拟搬离或放置操作,操作结束后,输出当前货架上所有箱子的起始位置。
实现上述功能的部分Python 程序如下,请在划线处填入合适的代码。
#共有n个箱子供操作,代码略
lst=[-1]*n
st=m=0
while True:
　　 操作序列如["P1","M0"……],依次读取序列元素,存入变量op,"P1"表示放置宽度为1的箱子,"M0"表示搬离第1个箱子,代码略
　　if op[0]=="P":
w=int(op[1:]) #表示箱子的宽度为w
lst[m]=st
st=st+w
　　　①　　
　　elif op[0]=="M":
i=int(op[1:]) #表示第i+1个箱子将被搬离
if lst[i+1]!=-1:
dis=　　　②　　
else:
dis=st-lst[i]
while lst[i+1]!=-1:
lst[i]=lst[i+1]-dis
i=i+1
　　 lst[i]=-1
st=　　　③　　
m=m-1
else:
break
#输出当前货架上所有箱子的起始位置,代码略
程序划线①处应填入的代码为:　　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　。
m=m+1　
lst[i +1]-lst[i]　
st-dis
解析:本题主要考查数组的基本操作。划线①处表示放置箱子的情况,lst数组存放所有箱子的起点,st存放每个箱子的起点,划线处代码表示每个箱子,即lst的索引值,因此①处代码为m=m+1;划线②处表示搬离箱子的情况,若当前搬离箱子的右侧还有箱子时,求该箱子右侧所有箱子自动左移的距离,因此②处代码为lst[i+1]-lst[i];划线③处,表示重新求一下箱子放置的起点,因此③处代码为st-dis。
[例8] 为支持公益事业,彩票中心设立了一个彩票项目。每张彩票上印有7个各不相同的号码(号码范围从1到33)。每次开奖时,会随机生成一个由7个各不相同的号码构成的中奖号码。彩票的兑奖规则如下:“特等奖”彩票上的7个号码与中奖号码全部相同;“一等奖”有6个号码相同;“二等奖”有5个号码相同;“三等奖”有4个号码相同;“四等奖”有3个号码相同;“五等奖”有2个号码相同;“六等奖”有1个号码相同。兑奖时不考虑号码在彩票和中奖号码中出现的具体位置。例如,若中奖号码为23,31,1,14,19,17,18,而某张彩票的号码为12,8,9,23,1,16,7,则该彩票中得五等奖,因为其中有两个号码(23和1)与中奖号码相同。现编写一个Python程序,功能为:随机生成7个不重复的中奖号码,并读取文件“彩票记录.txt”(该文件存储所有已售出的彩票号码),最后根据兑奖规则输出开奖结果,运行界面示例如下:
中奖号码:[7,20,10,8,21,17,2]
出售的彩票号码:[[33,16,4,25,12,18,5],[26,20,32,23,27,20,25],[10,18,28,20,12,22,29],[16,14,
7,33,8,11,13],[11,13,21,4,23,8,17],[17,20,2,26,30,9,19],[17,3,27,33,9,10,23],[6,7,4,7,9,21,33]]
彩票开奖结果:
特等奖　产生:0个
一等奖　产生:0个
二等奖　产生:0个
三等奖　产生:0个
四等奖　产生:0个
五等奖　产生:5个
六等奖　产生:2个
(1)若中奖号码为“23,31,1,14,19,17,18”,彩票号码为“11,8,9,32,1,16,7”,则中奖结果为　　　　　 　　　。
六等奖或“六等奖”
解析:本题考查数组。程序通过生成中奖号码,然后与已售出的彩票号码进行比对,统计各奖项的数量。
(1)中奖号码为“23,31,1,14,19,17,18”,彩票号码为“11,8,9,32,1,16,7”,因为彩票号码与中奖号码只有1个相同(数字1),根据规则对应六等奖。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
import random　#随机生成7个[1,33]范围内不重复的中奖号码
flag=[0]*34;data=[0]*7
i=0
while i<7:
t=random.randint(1,33)
if not flag[t]:
　　①　
i=i+1
flag[t]=1
print("中奖号码:",data)
#读取"彩票记录.txt"文件,存储到sale=[[12,8,9,23,1,16,7],[11,7,10,21,2,9,31],…],代码略
num=[0]*8　　# num[0]表示特等奖个数,num[i]表示i等奖个数
for i in range(len(sale)):
cnt=0
for j in range(7):
if sale[i][j] in data:
cnt+=1
　 num[　　②　　]+=1
print("彩票开奖结果:")
for i in range(7):
s="特等奖一等奖二等奖三等奖四等奖五等奖六等奖"
print(s[　　③　　],"产生:",num[i],"个")
程序划线①处应填入的代码为:　　　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　　。
data[i]=t　
7-cnt　
i*3:i*3+3
解析:(2)①处需要将随机生成的不重复号码存入data数组,因此该空答案为data[i]=t。②处根据相同号码个数cnt确定奖项等级,cnt=7对应特等奖(索引0),cnt=6对应一等奖(索引1),以此类推,因此该空答案为7-cnt。③处需要从字符串s中截取对应的奖项名称,每个奖项名称占3个字符,因此该空答案为i*3··i*3+3。
(3)上述加框处代码,能否修改为“num=[0]*7” 　　　　(选填:能/不能)。
不能
解析:(3)上述加框处代码,不能修改为"num=[0]*7"。 因为奖项从特等奖到六等奖共7个等级,但num数组索引0-6分别对应这7个奖项,当cnt=0时对应num[7],如果数组长度只有7会导致索引越界。
感谢观看

展开更多......

收起↑