python数据结构与算法---数组(线性数组) 笔记

线性表:(a1,a2,…an)

1线性表是有序对的集合,表示线性表中任意两相邻元素之间的关系,也可以是空集合 2存在唯一的第一个元素a1和最后一个元素an 3除了a1，每个元素都有唯一的先行者，例如ai的先行者是ai-1 4除了an，每个元素都有唯一的后继者，例如ai的后继者是ai+1

线性表相邻元素存在的关系:

1计算线性表的长度n 2线性表的第i项满足，1<=i<=n 3插入一项i,1<=i<=n，使原来的第i,i+1...n,后移变成i+1,i+2.....n+1 4删除第i项，位数前移一位 5从左至右或从右至左读取每个数据 6第i项存入新值是取代旧值 7复制 8合并

线性表数据结构：内存存储的方式

1静态数据结构：使用连续分配的内存空间，设计简单，编译时给相关变量分配好相应空间设置好最大占用空间，优点读取修改时间固定，查找随机查，缺点删除加入需移动大量数据2动态数据结构：链表，使用不连续的内存空间具存储具有线性特性数据优点：插入删除方便，内存空间不需要事先声明节省空间。缺点：设计麻烦，查找只能按顺序查找如有n项数据任意插入平均要移动数据(n+1)/2项。，任何可能插入概率为1/n: E=1*(1/n)+2*(1/n)+...+n*(1/n)=(1/n)*n(n+1)/2=(n+1)/2

数组:紧密相连的可读内存，并提供能直接访问单一数据内容的方法

属性1:起始地址，数据第一个元素在内存中的起始地址属性2:维度,代表数组是几维数组属性3:索引上下限:元素在次数组中，内存所存储位置的上标和下标属性4:数组元素个数:索引上限与下线差加1 属性5:声明次数组的类型决定了数组元素在内存当中所占容量大小

多维数组必须以一维数组的物理内存来表示，内存地址是按线性递增的
【python数据结构与算法---数组(线性数组)】按不同语言又分为两种:

以行为主:一行一行按序存储c/c++.java,PASCAL 一列为主：列式，Fortan的数组

python当中是以列表list来实现的:列表名称[列表元素设置值]*列表长度。如没有指定常数值则表示不定长列表

文章图片

二维数组:一维数组的扩展，内存当中不能以矩阵的方式存储，两种存储方式

文章图片

以行为主:Loc(aij)=a+n(i-1)*d+(j-1)*da是起始内存地址,i为aij所在行,j是所在列，n是总列数,d是。存储顺序为a11,a12,..a1n,a21,..a2n,..,amn以列为主:Loc(aij)=a+(i-1)*d+m*(j-1)*dm是总行数，顺序为:a11,a21,..am1,a12,a22,..a(m+1)2,..amn

数组两种表示法:

1简单表示法:A(m,n)或A(1:m,1:n)2注释表示法:A(l1:u1,l2,u2)l1<=i<=u1,l2<=j<=u2,则有m=(u1-l1+1),n=(u2-l2+1) 则以行为主:Loc(aij)=a+n((i-l1+1)-1)*d+((j-l2+1)-1)*d=a+(i-l1)*n*d+(j-l2)*d 同样以列为主:Loc(aij)=a+(i-l1)*d+(j-l2)*m*d

二维数组取值:列表名[行索引][列索引]
声明一个N*N的二维数组:arr=[[None]*N for row in range(N)]
三维数组:

线性方式:A(1:u1,1:u2,1:u3),含有u1*u2*u3三维数组 1,以行为主:Loc(A(i,j,k))=a+(i-1)u2*u3*d+(j-1)*u3*d+(k-1)*d 若A(l1:u1,l2:u2,l3:u3)则a=u1-l1+1,b=u2-l2+1,c=u3-l3+1 Loc(A(i.j,k))=a.+(i-l1)bcd+(j-l2)cd+(k-l3)*d 2,以列为主:Loc(A(i,j,k))=a+(k-1)u2*u1*d+(j-1)*u1*d+(i-1)d a=u1-l1+1,b=u2-l2+1,c=u3-l3+1 Loc(A(i,j,k))=a.+(k-l3)*abd+(j-l2)ad+(i-1)d

n维数组:

1以行为主: Loc(A(i1,i2,..in))=a.+(i1-1)u2*u3*...un*d +(i2-1)u3*u4*...un*d +(i3-1)u4*u5....un*d.... +((i(n-1))-1)*un*d +(in-1)*d 2以列为主: Loc(A(i1,i2,..in))=a.+(in-1)u(n-1)*u(n-2)...*u1*d +(i(n-1)-1)*u(n-2)*...*u1d... +(i2-1)*u1*d +(i1-1)*d