数据结构4数组

第4章数组

4.1数组定义及基本操作

4.2数组的存储结构

4.3特殊矩阵的压缩存储

4.4稀疏矩阵的压缩存储

4.5数组的运算

2/1/20231第4章数组

数组是我们最常用的一种数据结构，各种计算机语言均有此类型。例如：顺序表、顺序栈、循环队列等。１．数组的定义：数组：是ｎ（ｎ＞１）个相同数据类型的数据元素a0,a1…an-1,构成的占用一块连续的内存单元的有限序列。数组特点：

1.有限个元素的集合；

2.所有元素具有相同的特性；

3.元素名由数组名和下标组成；

4.下标值与元素对应（代表元素的位置）。4.1数组的定义及操作2/1/20232第4章数组

数组与线性表:相同之处:由若干个相同数据类型的数据元素组成.不同之处:1.存储单元连续与否

2.数据元素在逻辑意义上可分与否

3.操作不同。2/1/20233第4章数组２.数组的逻辑结构

一维数组（a0,a1,a2,a3,…an-1）满足线性关系；二维或二维以上数组：（以二维为例）Amxn=a

a

…..

aa00

a01…….a0n-110111n-1……...a

a

am-10m-11m-1n-1看元素a11有两个直接前趋a10和a01两个直接后继a21和a12三维数组:每个元素有三个直接前趋和三个直接后继.可见:数组(除一维数组外)是一种复杂的非线性数据结构.2/1/20234第4章数组但是:1)可将Amxn看成由m个行向量组成的向量,即

Amn={(a00,a01,……a0n-1),(a10,a11,……a1n-1),……(am-10,

am-11,……am-1n-1)}2)将Amxn看成由n个列向量组成的向量,即

Amn=((a00,a10,……am-10),(a01,a11,……am-11)……

(a0n-1,a1n-1,……am-1n-1))

列向量为线性.元素1元素2元素m看(ai0,ai1,…..ain-1),除ai0,ain-1

外只有一个直接前趋和一个直接后继.元素1元素2元素n2/1/20235第4章数组

据此数组可看成是线性表的扩展:即线性表中的数据元素本身也是一个数据结构.

数组可表示成两类线性表:1.以行向量做线性表的一个元素;2.以列向量做线性表的一个元素.2/1/20236第4章数组３．数组抽象数据类型：数据集合：数组的数据集合可表示为a0,a1…an-1,每个数据元素的类型为抽象数据类型:DataType．（限定顺序存储）数据关系:线性关系.操作集合：

各种高级程序设计语言的操作各不相同，必备的操作有：（1）求数组元素个数（2）随机取（3）随机存（4）矩阵运算2/1/20237第4章数组

一般数组:(以二维数组为例)多采用顺序存储:(1).按行优先顺序存储

假设：Am×n=a00a01a02…a0n-1a10…a00a01a02a03…a0n-1

a10a11a12a13…a1n-1…am-10am-11am-12am-13…am-1n-1即a00,a01,a02……a0n-1,a10,a11,…...a1n-1……aij的存储地址:am-1,04.2数组的存储结构:2/1/20238第4章数组

L:为每个元素所占存储单元.Pascal和C语言中数组存储为此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列优先顺序存储,即

a00,a10,a20……am-10,a01,a11,…...am-11……

aij存储地址:

Loc(aij)=Loc(a00)+(j*m+i)*LFortran语言采用此方法.a00a10a20…am-10a01…可见:数组是一种随机存储结构.存取任意元素的时间相等2/1/20239第4章数组推广:假设:A[c1--d1][c2--d2]例：二维数组floata[4][3].计算（1）数组元素数目？（2）若数组Loc(a00)=1000,且L=4,数组元素a[3][2]的地址?(按行优先存储)4*3=12Loc(a32)=Loc(a00)+(i*n+j)*L=1000+(3*3+2)*4=1044Loc(aij)=Loc(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L按行优先顺序存储：Loc(aij)=Loc(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*L按列优先顺序存储：2/1/202310第4章数组特殊矩阵：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的规律。采用压缩顺序存储方式:只存非零元素,节省空间.

1.下三角矩阵:

存放形式:{a00,a10,a11,a20,a21,…an-10,an-11,…an-1n-1}4.3特殊矩阵的压缩存储a0000……..0a10a110…….0……………….0an-10an-11…..an-1n-1Ann=可以是0和常数C第1行：1个第2行：2个第3行：3个……第n行：n个1+2+3+4+5+…+n=n(n+1)/22/1/202311第4章数组非零元素aij存储地址:Loc(aij)=Loc(a00)+[i*(i+1)/2+j]*L（0≤j≤i≤n-1）K0123…n(n-1)/2…n(n+1)/2-1sb[k]a00a10a11a20…an-11…an-1n-12/1/202312第4章数组假设：以一维数组sb[n(n+1)/2+1]作为n阶下三角矩阵A的存储结构，A中任意元素aij与sb[k]对应关系如下：

i(i+1)/2+j当i≥j时(非零元素)k=n(n+1)/2当i<j时(零或常数)其中：sb[k]:sb[0]~sb[n(n+1)/2-1]sb[n(n+1)/2]存放常数或零2/1/202313第4章数组2.对称矩阵对称矩阵：n阶方阵A中的元素满足：

aij

=aji

0≤i,j≤n-1存储：可只存储上三角矩阵或下三角矩阵将n*n个元素压缩存储到n(n+1)/2个元素空间中（sa数组）。以按行优先存储为例。A矩阵与sa[k]关系：上三角矩阵的存储类似下三角矩阵，上三角矩阵自推i(i+1)/2+ji≥jj(j+1)/2+ii<jk=2/1/202314第4章数组K0123…n(n-1)/2…n(n+1)/2-1sa[k]a00a10a11a20…an-11…an-1n-1隐含a01a02…a1n-13.对角矩阵：形状：Ann=非零元素带2/1/202315第4章数组例：三对角阵

An×n=其中非零元素按行优先顺序存放：{a00,a01,a10,a11,a12,a21,a22,a23,…,an-1,n-2,an-1,n-1}

非零元素aij的地址关系式：Loc(aij)=Loc(a00)+2*i+j(i=0,j=0,1或i=n-1,j=n-2,n-1或0<i<n-1,j=i-1,i,i+1)推广：n阶对角阵有（2h-1）条非零元素带。h2/1/202316第4章数组以上数组存储方式与顺序存储线性表类似数组元素的存储位置是其下标的线性函数。总之：特殊矩阵的压缩存储方法：找出特殊矩阵的非零元素的分布规律，将其存储到一个存储空间，只需在算法中按公式计算即可实现矩阵元素的随机存取。2/1/202317第4章数组稀疏因子：设在m*n的矩阵中，有t个非零元素，令称为矩阵的稀疏因子。通常认为<=0.05时为稀疏矩阵。我们在存储的时候，除了存储非零元的值之外，还得存储它所在的行号和列号。由此构成一个三元组(i,j,aij)，该三元组唯一确定了该矩阵元素。

4.4稀疏矩阵:2/1/202318第4章数组含有大量零元素的矩阵,且无规律。仅存非零元素,可省空间,避免大量无意义运算,提高运算效率.例:A=000700-100-1-20000000000020

1.顺序存储:按行优先顺序排列.(1).三元组顺序表:每个结点由三个域组成

a.非零元素行下标;b.非零元素列下标;c.非零元素值.2/1/202319第4章数组

A的三元组顺序表表示:(0,0,3)(0,4,7)(1,2,-1)(2,0,-1)(2,1,-2)(4,3,2)若有N个非零元素则需要3N个存储单元

00304712-120-121-2432行列值6552/1/202320第4章数组2.链接存储结构:(1)三元组(单)链表.

三元组线性表采用链接存储结构。(0,0,3)(0,4,7)(1,2,-1)(2,0,-1)(2,1,-2)(4,3,2)A=3000700-100-1-20000000000020

缺点：算法事件复杂度高300740-121-102-2122∧34h552/1/202321第4章数组01234/\

(2)行指针数组结构的三元组链表.

设置一个行指针数组,数组中每个元素为指针类型,它指向本行矩阵的第一个非零元素,若该行无非零元素,则指针为空.

以A为例:行指针数组

0347/\2-1/\32/\1-2/\0-1A=3000700-100-1-20000000000020

2/1/202322第4章数组(3).三元组十字链表:上面介绍的行指针数组结构的三元组链表形式容易实现按行找某列元素,不容易实现按列找某行元素.改进:按照行指针数组结构的三元组链表形式构造出相同结构的列指针数组.例:A=000700-100-1-20000000000020

003/\-1/\/\12341234/\-1/\7/\/\-2/\/\2/\2/1/202323第4章数组为了方便算法中对矩阵的行方向和列方向的搜索。

采用动态存储结构:每个非零元素用一个结点由五个数据域组成:三个数值,两个指针.三个数值：i，j，value.表示非零元素的行号、列号和元素值。两个指针：Down：向下指针

Right：向右指针行链表的头结点与列链表的头结点共用一个结点.ijValueDownRight十字链表设置：行头结点、列头结点和链表头结点.linkDownRight行头结点列头结点(4).十字链表:2/1/202324第4章数组链表头结点mnlink300700-10-1-2000000例:

A5×5=2/1/202325第4章数组4400303721-212-120-1headh1h1h2h2h3h3h4h4300700-10-1-20000002/1/202326第4章数组转置运算：设稀疏矩阵A以三元组表顺序存储结构存放。三元组顺序表结构定义如下：#defineMAX100typedef

struct{inti;/*行*/

intj;/*列*/

DataTyped;/*元素值*/}tupletype;/*三元组*/typedef

struct{int

md;/*总行数*/

int

nd;/*总列数*/

inttd;/*总非零元素数*/

tupletypedata[MAX];}tabletype;/*三元组表*/4.5数组运算：2/1/202327第4章数组mdndtdijdijdijdijdsa.md#defineMAX10typedef

struct{inti;/*行*/

intj;/*列*/

DataTyped;/*元素值*/}tupletype;/*三元组*/typedef

struct{int

md;/*总行数*/

int

nd;/*总列数*/

inttd;/*总非零元素数*/

tupletypedata[MAX];}tabletype;/*三元组表*/tabletype

sa;sa.ndsa.tdsa.data[].isa.data[].j2/1/202328第4章数组例：将稀疏矩阵A进行转置A=0011017000250000000000000000000037000000000025676021104171125301943375650sa:p=0766031911252011343740176550sb:q=0转置v=02/1/202329第4章数组转置算法：Voidtrantup(tabletype

sa,tabletype*sb){intp,q,v;

sb->md=sa.nd;

sb->nd=sa.md;

sb->td=sa.td;

if(sb->td!=0){q=0;for(v=0;v<sa.nd;v++){for(p=0;p<sa.td;p++){if(sa.data[p].j==v){sb->data[q].i=sa.data[p].j;

sb->data[q].j=sa.data[p].i;

sb->data[q].d=sa.data[p].d;