数据结构数组

第五章数组回忆前面几章学习的线性结构:线性表、栈、队列、串要求数据结构中的元素必须有相同的属性，即数据类型其中元素的数据类型只要相同即可，当然也可以就是一个数据结构。问题：数组与线性表的区别与联系

相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。

不同之处：

(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。本讲内容5.1数组的定义1.数组2.数组的逻辑定义5.2数组的顺序存储5.3矩阵的压缩存储1.特殊矩阵2.稀疏矩阵数组数组逻辑上是线性结构的推广；数组是以线性表为元素的线性结构，而且元素的结构相同；数组可以看作是下标和值的偶对的集合；数组是一种逻辑结构。高级语言中的数组inta[10];a[0]a[1]a[2]a[3]……a[10-1]charB[4][5];B[0][0]B[0][1]B[0][2]B[0][3]B[0][5-1]B[1][0]B[1][1]……B[1][5-1]B[2][0]B[2][1]……B[2][5-1]B[3][0]B[3][1]……B[3][5-1]二维数组inta[2][3];两个变量组成的一个数组，其中每一个变量都是数组。其中a[0]，a[1]都是数组的名字，也就是地址。

a[0][1]a[0][0]a[1][2]a[1][1]a[1][0]a[0][2]数组的逻辑定义

n（n＞1）维数组是一个向量，它的每个元素是n-1维数组，且具有相同的上限和下限。

()nAaaa,,,21=……()mjjjjaaaa,,,21=……()mAbbb,,,21=……()iniii,,,21=……bbbbúúúúûùêêêêëé=mnmmnnnmaaaaaaaaaA212222111211………………………………[][[[]]]×úúúúúûùêêêêêëéúúúúûùêêêêëéúúúúûùêêêêëéúúúúûùêêêêëé=mnnnmmnmaaaaaaaaaA212221212111…………………×数组的抽象数据类型ADTArray{

数据对象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…,jn|n(>0)称为数组的维数，bi是数组第i维的长度,ji是第i维的下标,aj1j2…,jn∈ElemSet}

数据关系：

R={R1,R2,R3,……,Rn}Ri={<aj1…ji……jn,aj1…ji+1……jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2

基本操作：

Value(A,&e,index1,…,indexn)

Assign(&A,e,index1,…,indexn)}ADTArray数组的操作对于数组的操作一般只有两类：(1)给定一组下标，存取相应的数据元素(2)给定一组下标，修改相应的数据元素的值。数组一般不做插入和删除操作数组的存储实现机制１、一维数组（n个元素）中任一元素ai的内存单元地址LOC(ai)=LOC(a０)+i*k(0≤i<n)２、一个m行n列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)注：C语言中数组元素采用行主序的存放方法，即行优先顺序。顺序存储时按行序和列序的约定数组顺序存储时，必须确定按行序或列序存储：（1）PASCAL、C以行序为主存储（2）FORTRAN以列序为主存储a11

a12

…

a1n

a21

a22

…

a2n

…

am1

am2

…

amn

a11

a21

…

am1

a12

a22

…

am2

…

a1n

a2n

…

amn

以行为主序以列为主序例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

设二维数组A[c1..d1][c2..d2]

其中c1、c2和d1、d2分别为二维数组A的下标的下界和上界，每个数组元素占L个存储单元，设第一个元素A[c1][c2]的存储位置为LOC(c1,c2)，则该二维数组中任一元素A[i][j]

(

c1≤i≤d1,c2≤j≤d2)的存储位置可由下式确定：

LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L在C语言中，下标从零开始,即:A[0..d1][0..d2]，则数组元素A[i][j]的存储位置是

LOC(i,j)=LOC(0,0)+(i*(d2+1)+j)*L

矩阵的压缩存储压缩存储思想当矩阵的阶数较高，而且矩阵中的一些元素有特殊的性质时，可以采用节省空间的存储办法（压缩存储）。两类矩阵1.特殊矩阵：值相同的元素或非零元素分布有一定的规律；2.稀疏矩阵：非零元素少且分布无规律；对称矩阵、上（下）三角矩阵、对角矩阵特殊矩阵——对称矩阵若n阶方阵A中的元素满足下述性质：

aij=aji

1≤i,j≤n则称A为n阶对称矩阵。a11

a21

a22

a31

…

an1

…

ann

k=0123

n2个元素可以压缩到n(n+1)/2个空间中；以行序为主序将其下三角（包括对角线）中的元素存储到一个向量B[n(n+1)/2]中:特殊矩阵——对称矩阵向量B[k]和矩阵中的元素aij之间存在着一一对应关系：

下面按下标从0开始讨论。

向量B[k]和矩阵中的元素aij之间的关系：由i和j推导k：特殊矩阵——对称矩阵下标变换公式三角矩阵:

下三角矩阵是指矩阵的上三角（不包括对角线）中的元素均为零或常数的n阶方阵。特殊矩阵——三角矩阵下三角矩阵存储公式和对称矩阵存储主对角线以下元素的公式基本相同，只需额外再增加一个存储常数或零的存储空间即可，即压缩存储空间为1+n(n+1)/2

。特殊矩阵——对角矩阵对角矩阵:

所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素均为零。b条对角线n行n列(a)a11

a12

a21

a22

a23

an-1,n

an,n

an,n-1

OO(b)a11

a12

a21

a22

a23

an-1,n

an,n

an,n-1

OO

三对角矩阵:共3n-2个非零元素，存入B[3n-2]中,元素在一维数组B中的下标k和元素在矩阵中的下标i和j的对应关系为：

k=3(i-1)-1(主对角线左下角，即i=j+1)

k=3(i-1)(主对角线上，即i=j)

k=3(i-1)+1(主对角线上，即i=j-1)由以上三式，得

k=2(i-1)+(j-1)(1≤

i,j≤

n;0≤

k≤

3n-1)特殊矩阵——对角矩阵稀疏矩阵的定义稀疏矩阵的定义非零元素较少，分布无规律。稀疏因子假设m行n列的矩阵含t个非零元素，则稀疏因子为δ=t/(m*n)<=0.05。稀疏矩阵的存储结构二维数组？压缩存储？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:(1)零值元素占了很大空间;(2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。(1)尽可能少存或不存零值元素；解决问题的原则:(2)尽可能减少没有实际意义的运算；(3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。压缩存储时，对零元素不分配存储空间，只存储稀疏矩阵中的非零元。稀疏矩阵的压缩存储顺序存储结构——三元组表链式存储结构——十字链表ije12616-2

34-8

42346751-12539三元组顺序表úúúúúúûùêêêêêêëé---=0009012700030008000000000200060A

#defineMAXSIZE12500

typedefstruct{

inti,j;

//该非零元的行下标和列下标

ElemTypee;

//该非零元的值

}

Triple;

//三元组类型typedefstruct{

Triple

data[MAXSIZE+1];

intmu,nu,tu;

}TSMatrix;//三元组顺序表表示稀疏矩阵三元组顺序表例：下面的三元组顺序表表示一个稀疏矩阵，试还原出它的稀疏矩阵。12221123134445366116ije0123450

0000

00000000

0000

0000

0000

20012

000

3

0000

0040

06016

000646datatumunu十字链表中非零元结点的结构:rowcoledownright元素结点十字链表同一列下一个非零元同一行下一个非零元十字链表的结构类型typedefstructOLNode{int