资源简介

(共24张PPT)
第二章内容复习
PART
1
数组
一 数组的概念
1.定义：数组是由相同类型的变量构成的一个序列。
2.特性：
数组的数据类型相同
通过数组名和下标对数组元素的值进行访问
存储空间固定不变
3.数据结构
逻辑结构：
物理结构：
一维数组/二维数组
顺序存储
一 判断题
1.一维数组适合用来表示具有线性特征的数据序列
2.二维数组表示的数据在内存中以二维的形式存储
3.同一个数组中，每个数组元素的数据类型一定是相同的
4.数组的逻辑结构是顺序存储
5.数组适用于数据规模可预估且在处理过程中数据规模保持稳定的问题
√
×
√
×
√
二 数组的创建
创建方式 一维数组 二维数组
直接创建
间接创建
列表生成式
a=[0,0,0]
a=[0]*3
a=[0 for i in range(3)]
0 0 0
0 0
0 0
0 0
a
b
b=[[0,0],[0,0],[0,0]]
b=[[0]*2 for i in range(3)]
b=[[0]*2]*3或b=[[0,0]]*3
b=[[0 for i in range(2)]for j in range(3)]
二 练习
1.对于数组：a=[ i*i for i in range(10) if i%2!=0 ]
则数组元素a[2]的值为 （ ）
A.9
B.25
C.49
D.16
B
二 练习
2.有如下程序段：
a=[[0]*3]*4
b=a
b[1][2]=3
print(a[0][2],b[3][2])
程序执行完毕后输出的值为（ ）
A.0 0 B.3 0 C.0 3 D.3 3
D
二 练习
3.有如下Python程序段：
a=[[0]*3 for i in range(4)]
for i in range(len(a)):
for j 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
二 练习
4.有如下Python程序段:
n=4
a=[[j*n+i+1 for i in range(n)] for j in range(n)]
for i in range(1,n,2):
for j in range(n//2):
a[i][j]//=2
则程序执行后,a[1][1]和a[3][1]的值分别为( ）
A.3和7 B.3和6 C.2和6 D.2和7
A
三 数组的访问
1.一维数组
物理地址计算：
【例】某数组第一个元素的存储位置在第900字节处，每个元素所占空间大小为2字节，则第五个元素的位置为________
908
LOC(i)=LOC(0)+s*i
s代表每个元素存储空间
LOC（0）代表第一个元素存储的位置
三 数组的访问
2.二维数组
物理地址计算：
【例】二维数组a中，每个元素所占空间大小为2个字节，行下标i从0到4，列下标j从0到6，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素a[2][4]的起始地址为_____
SA+36
如果用列优先存储呢？
SA+44
行优先：
LOC(a[i][j])=LOC(a[0][0])+(i*C+j)*s
列优先：
LOC(a[i][j])=LOC(a[0][0])+(j*R+i)*s
0 1 … C-1
1 …
… … a[i][j] …
R-1 …
R为最大行数
s代表每个元素存储空间
C为最大列数
四 数组元素的插入
1.定义：将该位置及其后的所有数据向后移动一个位置，最后在修改该位置上的数据为新数据。
2.代码表示：
for i in range（n-1,p,-1）:
a[i]=a[i-1]
a[p]=x
n+=1
#n为列表长度
#p为元素插入位置
a
p
n-1
x=6
相关函数：list.insert(p,x)
五 数组元素的删除
1.定义：当需要在数组中某个位置中删除一个元素时，只需将所有元素依次前移一位，然后将所有数组长度减一即可。
。
2.代码表示：
for i in range（p,n-1）:
a[i]=a[i+1]
n-=1
相关函数： list.pop([p=-1])
list.remove()
del list
del list[p]
del list[:]
#n为列表长度
#p为元素插入位置
a
p
n-1
PART
2
链表
一 链表的概念
1.定义：链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
2.特性：
同一链表中每个结点的结构均相同
每个链表必定有一个头指针，以实现对链表的引用和边界处理
链表占用的空间不固定
3.数据结构
逻辑结构：
物理结构：
线性表
非顺序存储
一 判断题
1.链表的核心是使用指针链接节点，是一种非常灵活的数据组织方式
2.链表的存储空间利用率比数组高
3.链表的删除、插入操作效率比数组高
4.链表在生成时可以没有头结点
5.链表适合数据规模不确定，或初始时确定但处理过程中由于频繁增删数据导致数据规模不稳定的问题
6.链表的数据类型可以相同，也可以不同
7.链表节点占用的存储空间可以连续，也可以不连续
√
×
√
×
√
×
√
二 链表的创建
linklist=[ [6,2],[3,-1],[4,1] ]
head=0
1.单向链表的创建：
2.双向链表的创建：
dblinklist=[ [6,-1,1],[8,0,2],[9,1,-1] ]
head=0
data next
data prev next
三 链表的访问
1.单向链表的访问：
2.双向链表的访问：
def display(a,head):
p=head
while a[p][1]!=-1:
print(a[p][0])
p=a[p][1]
print(a[p][0])
def display(a,head):
p=head
while a[p][2]!=-1:
print(a[p][0])
p=a[p][2]
print(a[p][0])
二 练习
1.有如下Python程序段:
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end="->")
p=a[p][1]
print(a[p][0])
则执行，上述语句后，程序输出结果为（ ）
A.3->7->2->1
B.3->2->7->1
C.1->7->3->2
D.3->7->1->2
A
二 练习
2.有如下代码段：
a=[[2,2,5],[8,0,5],[0,- 1,0],[1,- 1,2],[5,5,- 1],[3,0,- 1]]
head=2
则该双向链表a的节点数量为( )
A.3
B.4
C.5
D.6
A
四 链表的插入&删除
1.进制转化问题（以十进制转二进制为例）：
num=int(input(‘输入十进制数’))
a=[]
head=-1
while num>0:
node=[num%2,head]
a.append(node)
head=_______
num=________
p=head
while p!=-1:
print(a[p][0],end=‘’)
p=________
len(a)-1
num//2
a[p][1]
四 链表的插入&删除
2.约瑟夫环问题（循环链表）：
list=[]
n=int(input(‘总人数’))
m=int(input(‘淘汰号码’))
for I in range(n-1):
list.append([i+1,i+1])
list.append(________)
#添加尾节点，使其成为循环链表
head,length=0,n
k=head
i=1
while length>1:
i=i+1
if i==m:
t=list[k][1]
____________
if t==head:
___________
i=1
length-=1
k=list[k][1]
print(list[head][0])
[n,0]
list[k][1]=list[t][1]
head=list[k][1]
四 链表的插入&删除
3.列表合并问题：
已知两个整数集合A和B。它们的元素分别依元素值递增有序存放在两个单向链表a和b中,请将这两个链表合并成一个单向链表，并保持元素值按递增序列排列。可以使用Python中的二维列表来模拟单向链表,为节省空间,可通过把链表b的节点插入到链表a中的方式来实现合并链表功能。
四 链表的插入&删除
ha=hb=0
qa=pa=ha
pb=hb
while pa!=-1 and pb!=-1;
if a[pa][0]<=b[pb][0]:
qa,pa=pa.a[pa][1]
else:
if pa==ha:
a.append(b[pb][0],ha)
ha=___________
qa=ha
else:
a.append([b[pb][0],a[qa][1]])
a[qa][1]=__________
qa=a[qa][1]
pb=___________
while pb!=-1:
a. append([b[pb][0],- 1])
a[qa][1]=len(a)-1
qa=a[qa][1]
pb=b[pb][1]
pa=ha
while a[pa][1]!=- 1: #遍历链表a
print(a[pa][0],end=" ->")
pa=a[pa][1]
print(a[pa][0])
len(a)-1
len(a)-1
b[pb][1]

展开更多......

收起↑