资源简介 (共24张PPT)第二章内容复习PART1数组一 数组的概念1.定义:数组是由相同类型的变量构成的一个序列。2.特性:数组的数据类型相同通过数组名和下标对数组元素的值进行访问存储空间固定不变3.数据结构逻辑结构:物理结构:一维数组/二维数组顺序存储一 判断题1.一维数组适合用来表示具有线性特征的数据序列2.二维数组表示的数据在内存中以二维的形式存储3.同一个数组中,每个数组元素的数据类型一定是相同的4.数组的逻辑结构是顺序存储5.数组适用于数据规模可预估且在处理过程中数据规模保持稳定的问题√×√×√二 数组的创建创建方式 一维数组 二维数组直接创建间接创建列表生成式a=[0,0,0]a=[0]*3a=[0 for i in range(3)]0 0 00 00 00 0abb=[[0,0],[0,0],[0,0]]b=[[0]*2 for i in range(3)]b=[[0]*2]*3或b=[[0,0]]*3b=[[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.9B.25C.49D.16B二 练习2.有如下程序段:a=[[0]*3]*4b=ab[1][2]=3print(a[0][2],b[3][2])程序执行完毕后输出的值为( )A.0 0 B.3 0 C.0 3 D.3 3D二 练习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.9D二 练习4.有如下Python程序段:n=4a=[[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和7A三 数组的访问1.一维数组物理地址计算:【例】某数组第一个元素的存储位置在第900字节处,每个元素所占空间大小为2字节,则第五个元素的位置为________908LOC(i)=LOC(0)+s*is代表每个元素存储空间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)*s0 1 … C-11 …… … 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]=xn+=1#n为列表长度#p为元素插入位置apn-1x=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 listdel list[p]del list[:]#n为列表长度#p为元素插入位置apn-1PART2链表一 链表的概念1.定义:链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。2.特性:同一链表中每个结点的结构均相同每个链表必定有一个头指针,以实现对链表的引用和边界处理链表占用的空间不固定3.数据结构逻辑结构:物理结构:线性表非顺序存储一 判断题1.链表的核心是使用指针链接节点,是一种非常灵活的数据组织方式2.链表的存储空间利用率比数组高3.链表的删除、插入操作效率比数组高4.链表在生成时可以没有头结点5.链表适合数据规模不确定,或初始时确定但处理过程中由于频繁增删数据导致数据规模不稳定的问题6.链表的数据类型可以相同,也可以不同7.链表节点占用的存储空间可以连续,也可以不连续√×√×√×√二 链表的创建linklist=[ [6,2],[3,-1],[4,1] ]head=01.单向链表的创建:2.双向链表的创建:dblinklist=[ [6,-1,1],[8,0,2],[9,1,-1] ]head=0data nextdata prev next三 链表的访问1.单向链表的访问:2.双向链表的访问:def display(a,head):p=headwhile a[p][1]!=-1:print(a[p][0])p=a[p][1]print(a[p][0])def display(a,head):p=headwhile 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=0while a[p][1]!=head:print(a[p][0],end="->")p=a[p][1]print(a[p][0])则执行,上述语句后,程序输出结果为( )A.3->7->2->1B.3->2->7->1C.1->7->3->2D.3->7->1->2A二 练习2.有如下代码段:a=[[2,2,5],[8,0,5],[0,- 1,0],[1,- 1,2],[5,5,- 1],[3,0,- 1]]head=2则该双向链表a的节点数量为( )A.3B.4C.5D.6A四 链表的插入&删除1.进制转化问题(以十进制转二进制为例):num=int(input(‘输入十进制数’))a=[]head=-1while num>0:node=[num%2,head]a.append(node)head=_______num=________p=headwhile p!=-1:print(a[p][0],end=‘’)p=________len(a)-1num//2a[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,nk=headi=1while length>1:i=i+1if i==m:t=list[k][1]____________if t==head:___________i=1length-=1k=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=0qa=pa=hapb=hbwhile 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=haelse: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)-1qa=a[qa][1]pb=b[pb][1]pa=hawhile a[pa][1]!=- 1: #遍历链表aprint(a[pa][0],end=" ->")pa=a[pa][1]print(a[pa][0])len(a)-1len(a)-1b[pb][1] 展开更多...... 收起↑ 资源预览