python数据结构之数组结构

一、线性表简介

线性表(Linear List)：线性表是n(n>=0)个数据元素a1, a2, …，an(通常具有相同类型)构成的有限序列。
例1：分析26 个英文字母组成的英文表
（ A, B, C, D, …… , Z）
数据元素都是字母; 元素间关系是线性
例2：分析学生情况登记表

学号	姓名	性别	年龄	班级
041810205	于春梅	女	18	04级计算机1班
041810260	何仕鹏	男	20	04级计算机2班
041810284	王爽	女	19	04级计算机3班
041810360	王亚武	男	18	04级计算机4班
：	：	：	：	：

数据元素都是记录; 元素间关系是线性
线性结构可表示为：(a₁ , a₂ , ……, a_n)
线性结构的特点：
① 表中元素属于同一种数据对象。a_i∈ElemSet
② 只有一个首结点和尾结点；
③ 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。序偶关系〈a_i , a_i+1〉
简言之，线性结构反映元素间的逻辑关系是一对一
数据结构常用二元组定义方式：
Linear List = ( D , R ) 其中：
D = { a_i | a_i∈ ElemSet, i=1,2,…,n, n≥0 }，称元素的集合
R = { <a_i, a_i+1 > | a_i , a_i+1∈D, i=1,2,…,n-1}，称关系的集合
常用基本操作：
（1）计算线性表的长度n；
（2）取线性表中第 i 个元素，1≤i≤n；
（3）插入一个元素到第 i 项（1≤ i ≤n+1），线性表长度加1；
（4）删除第 i 项元素（1≤ i ≤n），线性表长度减1；
（5）遍历线性表，即顺序读取表中个元素；
（6）修改第 i 项的值（1≤ i ≤n）；
（7）查找元素 x ；
（8）排序；
……

二、线性表的存储结构

(一）静态数据结构（顺序存储）

用一整片地址连续的存储单元依次存储线性表的各个数据元素。又称为顺序存储结构或顺序映像。
线性表中逻辑上相邻的元素 a_i和 a_i+1 的存储位置LOC(a_i)和LOC(a_i+1)也是相邻(连)的。即：
LOC( a_i+1 ) = LOC( a_i ) + m
LOC( a_i) = LOC( a₁ )+( i-1 ) * m
整个线性表的所占空间为：n * m
★python可以使用列表（list）实现。

Python代码：

python

>>> a=[0]*10
>>> a[0]=87
>>> a[1]=76
>>> a[2]=91
>>> n=3
>>> print(a)

列表a示意图如下：

运行结果：

python

1	>>> [87, 76, 91, 0, 0, 0, 0, 0, 0, 0]

几个要点：
（1）存储空间大小需事先确定。
（2）元素间逻辑关系通过下标表示，逻辑上相邻两个元素，存储位置也相邻。
（3）存取或修改表中元素方便，只要明确下标即可，这种特性为顺序表最大优势，称为随机存取。
（4）插入或删除一个元素时，需要移动大量后续元素。

(二）动态数据结构（链式存储，Linked List）

采用不连续的存储单元存储线性表的各个数据元素。元素之间的关系通过地址链联系。
又称为非顺序映像或链式映像。
特点：
（1）不要求逻辑上相邻的元素在物理位置上也相邻。可以用任意的存储单元存储数据元素。
（2）线性表元素之间的逻辑关系由指针指示。除了保存元素值外还需保存逻辑信息（后续元素的地址）。
（3）访问元素必须按指针关系顺序访问。称为顺序存取机制。
（4）数据插入和删除不需要移到大量的后续元素，只要修改连接关系。
单链表：构成链表的结点只有一个指针域

存储地址	数据域	指针域
1	ZHANG	13
7	WANG	1
13	LI	null
19	ZHAO	37
25	WU	7
31	ZHOU	19
37	SUN	25

三、数组

用一整块内存空间逐个存放各个元素，数组名表示该空间的起始地址，索引（下标）用来表示第几个元素。

特征：

起始地址：数组名（即第一个元素的地址）
维度：包括一维数组、二维数组、三维数组…
索引值范围： 0 ~ n-1
数组类型：元素的类型决定了整个数组的内存空间，m*n
不同程序语言中，数组使用不同：

C语言：

1 2	int a[10]; /定义长度为10类型为整型的一维数组/ char b[5][10]; /#定义类型为字符的二维数组b，5行10列/

Python语言：用列表（list）来实现数组

python

a[0]*10   #声明长度为10，初始为0的一维列表a
m=4
n=6
b=[[0]*n for row in range(m)]  #声明初始值为0，m*n的二维列表

例1：
假设A为一个具有2000个元素的一维数组，每个元素为4个字节，若A[500]的地址为100016，则a[1000]的地址是多少？
解：Loc(A[1000])=Loc(A[500])+(1000-500)*4=4096(100016)+2000=6096(17D016)
例2：
使用python一维列表来记录5个学生的分数，打印输出每位学生的成绩并计算分数的总和。

python

Score=[87,66,90,65,70]
Total_Score=0
for count in range(5):
     print('第 %d 位学生的分数:%d' %(count+1,Score[count]))
     Total_Score+=Score[count]
print('-------------------------')
print('5位学生的总分:%d' %Total_Score)

输出结果：

python

第 1 位学生的分数:87
第 2 位学生的分数:66
第 3 位学生的分数:90
第 4 位学生的分数:65
第 5 位学生的分数:70
-------------------------
5位学生的总分:378

（一）二维数组

如果说一维数组是一个线性序列的话，则二维数组就是一个平面。
如一个m*n（m行n列）的二维数组，需要两个下标（行下标、列下表）来确定其中一个元素。

python

1	A=[[None]n for row in range(m)] #mn的空二维数组（列表）

那么二维数组平面的排列方式如何在内存中存储？
(1)以行为主(Row-Major)
一行一行按序存储，先存储第一行a[0][0]、a[0][1]、…、a[0][n-1]，然后存储第二行a[1][0]、a[1][1]，…
下标对应关系：[i][j] —–> i*n+j
(2)以列为主(Column-Major)
一列一列按序存储，先存储第一列a[0][0]、a[1][0]、…、a[m-1][0]\，然后存储第二列a[0][1]、a[1][1]，…
下标对应关系：[i][j] —–> i*m+j
多数程序设计语言按照以行为主的方式，即可以把一个二维数组按行（或列）为主采用一维数组存放
例:
使用python二维列表来编写一个求二阶行列式的值。二阶行列式的值计算公式为：a₁*b₂-a₂*b1。

python

N=2
#声明2x2的数组arr并将所有元素赋值为 None
arr=[[None] * N for row in range(N)] 
print('|a1 b1|')
print('|a2 b2|')
arr[0][0]=input('请输入a1:')
arr[0][1]=input('请输入b1:')
arr[1][0]=input('请输入a2:')
arr[1][1]=input('请输入b2:')
#求二阶行列式的值
result = int(arr[0][0])*int(arr[1][1])-int(arr[0][1])*int(arr[1][0]) 
print('|%d %d|' %(int(arr[0][0]),int(arr[0][1])))
print('|%d %d|' %(int(arr[1][0]),int(arr[1][1])))
print('行列式值=%d' %result)

输出结果：

python

|a1 b1|
|a2 b2|
请输入a1:5
请输入b1:9
请输入a2:3
请输入b2:4
|5 9|
|3 4|
行列式值=-7

四、矩阵

对于数学上一个m*n的矩阵（Matrix），可以用一个m*n的二维数组来描述。
矩阵的常用运算包括：加、乘、转置
如一个m*n（m行n列）的矩阵A：

1. 矩阵相加：A+B

前提：A、B两个矩阵都是m*n
方法：C[i][j]=A[i][j]+B[i][j]
结果：生成一个新的m*n的矩阵C

python

A= [[1,3,5],[7,9,11],[13,15,17]]   #二维数组的声明
B= [[9,8,7],[6,5,4],[3,2,1]]          #二维数组的声明
N=3
C=[[None] * N for row in range(N)]  #声明一个3*3的二维数组
	
for i in range(3):
    for j in range(3):
        C[i][j]=A[i][j]+B[i][j]     #矩阵C = 矩阵A + 矩阵B
print('[矩阵A和矩阵B相加的结果]’)   #打印出A+B的内容
for i in range(3):
    for j in range(3):
        print('%d' %C[i][j], end='\t')
    print()

输出结果：

python

[矩阵A和矩阵B相加的结果]
10	11	12	
13	14	15	
16	17	18

2. 矩阵相乘：A*B

前提：Cmp = Amn Bnp ，注意维度
方法：

结果：生成一个新的m*p的矩阵C

python

print("【请输入A维数(M,N)】")
M = int(input("M="))
N = int(input("N="))
if M<=0 or N<=0:
    print("错误：维数M,N必须大于0")
    return
A = [None]*M*N
print("【请输入A中各个元素】")
for i in range(M):
    for j in range(N):
        A[i*N+j] = input("a{}{}=".format(i+1,j+1))
print("【请输入B维数(N,P)】")
N = int(input("N="))
P = int(input("P="))
if N<=0 or P<=0:
    print("错误：维数M,N必须大于0")
    return
B = [None]*N*P
print("【请输入B中各个元素】")
for i in range(N):
    for j in range(P):
        B[i*P+j] = input("a{}{}=".format(i+1,j+1))
C = [None]*M*P
#开始相乘
for i in range(M):
    for j in range(P):
        Temp = 0
        for k in range(N):
            Temp = Temp + int(A[i*N+k])*int(B[k*P+j])
        C[i*P+j] = Temp
print("[A*B的结果是]")
for i in range(M):
    for j in range(P):
        print("{}".format(C[i*P+j]),end='\t')
    print()

运行结果：

python

【请输入A维数(M,N)】
M=3
N=2
【请输入A中各个元素】
a11=1
a12=2
a21=3
a22=4
a31=5
a32=6
【请输入B维数(N,P)】
N=2
P=3
【请输入B中各个元素】
a11=1
a12=2
a13=3
a21=4
a22=5
a23=6
[A*B的结果是]
9	12	15	
19	26	33	
29	40	51

3. 矩阵转置：B = A^t

方法：B[i][j] = A[j][i]
结果：生成一个新的n*m的矩阵，即行列互换

python

N = int(input("请输入方阵阶数(N)："))
if N<=0:
    print("错误：阶数N必须大于0")
    return
A = [[None]*N for row in range(N)]
B = [[None]*N for row in range(N)]
print("【请输入A中的各个元素】")
for i in range(N):
    for j in range(N):
        A[i][j] = eval(input("a{}{}=".format(i+1,j+1)))
print("【原设置的矩阵内容】")
for i in range(N):
    for j in range(N):
        print("{}".format(A[i][j]),end='\t')
    print()
#进行转置
for i in range(N):
    for j in range(N):
        B[i][j] = A[j][i]
print("【转置矩阵内容为】")
for i in range(N):
    for j in range(N):
        print("{}".format(B[i][j]),end='\t')
    print()

运行结果：

python

请输入方阵阶数(N)：2
【请输入A中的各个元素】
a11=1
a12=2
a21=3
a22=4
【原设置的矩阵内容】
1	2	
3	4	
【转置矩阵内容为】
1	3	
2	4

4. 特殊矩阵的存储

①右上三角矩阵
定义：N*N的方阵，主对角线下元素都为0(或常数)。
右上三角矩阵的压缩存储：
把上三角非0元素按下标对应关系存储到一维数组中，此一维数组的大小为非0元素的个数，即 n*(n+1)/2。
采用以行为主方式，非0元素下标(i , j) 对应到一维数组下标 index: (注，下标从0开始)
index = i*(2*N-i+1)/2+j-i ( i≤j )

python

A = [[7,8,12,21,9],
     [0,5,14,17,6],
     [0,0,7,23,24],
     [0,0,0,32,19],
     [0,0,0,0,8]]
N = 5

num = int(N*(1+N)/2)    
B = [None]*(num)

def getMValue(i,j):
    index = int(i*(2*N-i+1)/2+j-i)
    return B[index]
     
print('='*40)
print("右上三角矩阵")
for i in range(N):
    for j in range(N):
        print('%d'%A[i][j],end='\t')
    print()

index = 0
for i in range(N):
    for j in range(N):
        if(A[i][j]!=0):
            B[index]=A[i][j]
            index += 1
print("="*40)
print("以一维数组的方式显示")
print("[",end='')
for i in range(N):
    for j in range(i,N):
        print(' %d'%getMValue(i,j),end='')
print(" ]")

运行结果：

python

========================================
右上三角矩阵
7	8	12	21	9	
0	5	14	17	6	
0	0	7	23	24	
0	0	0	32	19	
0	0	0	0	8	
========================================
以一维数组的方式显示
[ 7 8 12 21 9 5 14 17 6 7 23 24 32 19 8 ]

②左下三角矩阵
定义：N*N的方阵，主对角线下元素都为0(或常数)。
左下三角矩阵的压缩存储：
把下三角非0元素按下标对应关系存储到一维数组中，此一维数组的大小为非0元素的个数，即 n*(n+1)/2。
采用以行为主方式，非0元素下标(i , j) 对应到一维数组下标 index: (注，下标从0开始)
index = i*(i+1)/2+j ( i≥j )

python

A = [[76,0,0,0,0],
     [54,51,0,0,0],
     [23,8,26,0,0],
     [43,35,28,18,0],
     [12,9,14,35,46]]
N = 5
num = int(N*(1+N)/2)    
B = [None]*(num)

def getMValue(i,j):
    index = int(i*(i+1)/2+j)
    return B[index]

print('='*40)
print("左下三角矩阵")
for i in range(N):
    for j in range(N):
        print('%d'%A[i][j],end='\t')
    print()

index = 0
for i in range(N):
    for j in range(N):
        if(A[i][j]!=0):
            B[index]=A[i][j]
            index += 1
print("="*40)
print("以一维数组的方式显示")
print("[",end='')
for i in range(N):
    for j in range(0,i+1):
        print(' %d'%getMValue(i,j),end='')
print(" ]")

运行结果：

python

========================================
左下三角矩阵
76	0	0	0	0	
54	51	0	0	0	
23	8	26	0	0	
43	35	28	18	0	
12	9	14	35	46	
========================================
以一维数组的方式显示
[ 76 54 51 23 8 26 43 35 28 18 12 9 14 35 46 ]

③左上三角矩阵、右下三角矩阵
右上三角矩阵与左下三角矩阵是以方阵的主对角线区分，同样，也可以副对角线区分，为左上三角矩阵和右下三角矩阵。
压缩存储：
类似前两种，把三角矩阵非0元素按下标对应关系存储到一维数组中，前两种均按照以行为主模式，同样也可以按照以列为主模式，只是特别注意在python中，二维数组（列表）和一维数组（列表）都从下标0开始。
此两种三角矩阵，按照前两个以行为主方法自行研究实现。
右下三角矩阵：

python

A = [[0,0,0,0,8],
     [0,0,0,32,19],
     [0,0,7,23,24],
     [0,5,14,17,6],
     [7,8,12,21,9]]
N = 5

num = int(N*(1+N)/2)    
B = [None]*(num)

def getMValue(i,j):
    index = int((i+2)*(i+1)/2+j-N)
    return B[index]
     
print('='*40)
print("右下三角矩阵")
for i in range(N):
    for j in range(N):
        print('%d'%A[i][j],end='\t')
    print()

index = 0
for i in range(N):
    for j in range(N):
        if(A[i][j]!=0):
            B[index]=A[i][j]
            index += 1
print("="*40)
print("以一维数组的方式显示")
print("[",end='')
for i in range(N):
    for j in range(N-i-1,N):
        print(' %d'%getMValue(i,j),end='')
print(" ]")

运行结果：

python

========================================
右下三角矩阵
0	0	0	0	8	
0	0	0	32	19	
0	0	7	23	24	
0	5	14	17	6	
7	8	12	21	9	
========================================
以一维数组的方式显示
[ 8 32 19 7 23 24 5 14 17 6 7 8 12 21 9 ]

一、线性表简介

二、线性表的存储结构

(一）静态数据结构（顺序存储）

(二）动态数据结构（链式存储，Linked List）

三、数组

（一）二维数组

四、矩阵

1. 矩阵相加：A+B

2. 矩阵相乘：A*B

3. 矩阵转置：B = At

4. 特殊矩阵的存储

3. 矩阵转置：B = A^t