数据结构数组

数据结构数组第1页，共42页，2023年，2月20日，星期六定义：相同类型的数据元素的集合。一维数组的示例：352749186054778341020123456789一维数组2.4.1数组的定义第2页，共42页，2023年，2月20日，星期六数组的定义和初始化main(){inta1[3]={3,5,7},*elem;for(inti=0;i<3;i++)printf(“%d”,a1[i],“\n”);//静态数组elem=a1; for(inti=0;i<3;i++){printf(“%d”,*elem,“\n”);//动态数组elem++;}}2.4.1数组的定义第3页，共42页，2023年，2月20日，星期六一维数组存储方式352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la2.4.1数组的定义第4页，共42页，2023年，2月20日，星期六二维数组：类似于线性表，一个二维数组的逻辑结构可形式地表示为：2_Array=(D,R)D={aij(i=0,1,…,m-1,j=0,1,…,n-1)},aij是同类型数据元素的集合。R={ROW,COL}是数据元素上关系的集合。2.4.1数组的定义a11a12a13…a1na21a22a23…a2nam1am2am3…amn…ai,j-1

aij

ai,j+1

………

ai-1,j

ai+1,j

Am,n=第5页，共42页，2023年，2月20日，星期六aij受行列两个关系的约束：第i行的行向量，第j列的列向量。ROW={<aij,ai(j+1)>|0im-1,0jn-2}每一行上的列关系。

aij的行前趋ai,j-1，aij的行后继ai,j+1COL={<aij,a(i+1)j>|0im-2,0jn-1}每一列上的行关系。

aij的列前趋ai-1,j，aij的列后继ai+1,j2.4.1数组的定义第6页，共42页，2023年，2月20日，星期六行优先存放(例：pascal、C语言)：

设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元

LOC(i,j)=a+(in+j)l2.4.2数组的顺序存储结构约定存放次序：因为计算机的存储单元是一维的，数组可以是多维的，所以必须约定存放次序。第7页，共42页，2023年，2月20日，星期六

列优先存放(例：Fortran语言)

：

设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元

LOC(i,j)=a+(jm+i)l2.4.2数组的顺序存储结构第8页，共42页，2023年，2月20日，星期六三维数组：各维元素个数为

m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：(按页/行/列存放)LOC(i1,i2,i3)=a+(i1m2m3+i2m3+i3

)*l

前i1页总元素个数第i1页的前i2行总元素个数2.4.2数组的顺序存储结构第i1页的第i2行i3列前元素个数第9页，共42页，2023年，2月20日，星期六下标为i1,i2,i3的数组元素的存储地址：(按列/行/页存放)LOC(i1,i2,i3)=a+(i3m1m2+i2m1+i1

)*l

前i3列总元素个数第i3列的前i2行总元素个数2.4.2数组的顺序存储结构第i3列的第i2行i1页前元素个数第10页，共42页，2023年，2月20日，星期六

n维数组：各维元素个数为m1,m2,m3,…,mn

下标为

i1,i2,i3,…,in

的数组元素的存储地址：

LOC(i1,i2,…,in)=a+(i1m2m3…mn+i2m3m4…mn++……+in-1mn+in)l

2.4.2数组的顺序存储结构第11页，共42页，2023年，2月20日，星期六

二维数组

三维数组

行向量下标

i1

页向量下标

i1

列向量下标

i2

行向量下标

i2

列向量下标

i3第12页，共42页，2023年，2月20日，星期六特殊矩阵的压缩存储特殊矩阵：是指非零元素的分布有一定规律/大量零元素的矩阵。压缩存储：针对阶数很高的特殊矩阵。为节省存储空间，可以不存储零元素或对称元素。

对称矩阵

三对角矩阵2.4.2数组的顺序存储结构第13页，共42页，2023年，2月20日，星期六对称矩阵的压缩存储设有一个

nn

的对称矩阵

A。在矩阵中，aij=aji2.4.2数组的顺序存储结构第14页，共42页，2023年，2月20日，星期六

为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。

把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。

数组B共有

n+(n-1)++1=n(n+1)/2个元素。2.4.2数组的顺序存储结构第15页，共42页，2023年，2月20日，星期六上三角矩阵下三角矩阵第16页，共42页，2023年，2月20日，星期六下三角矩阵Ba00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1若

i

j,数组元素A[i][j]在数组B中的存放位置为

1+2++i+j=(i+1)i/2+j前i行元素总数

第i行第j个元素前元素个数第17页，共42页，2023年，2月20日，星期六

若i<j，数组元素A[i][j]在矩阵的上三角部分,在数组B中没有存放，可以找它的对称元素：A[j][i]：=j(j+1)/2+i

若已知某矩阵元素位于数组B的第k个位置，可寻找满足i(i+1)/2k<(i+1)(i+2)/2的i(行号),

j=k-i(i+1)/2(列号)

例:当k=8,34/2=6k

<4*5/2=10,取i=3。则j=8-34/2=2。

2.4.2数组的顺序存储结构第18页，共42页，2023年，2月20日，星期六上三角矩阵Ba00a01a02a03a11a12a13a22a23

a33

0123456789

若i

j，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i=(2n-i-1)i/2+j前i行元素总数

第i行第j个元素前元素个数n=4第19页，共42页，2023年，2月20日，星期六

若i>j，数组元素A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此，找它的对称元素A[j][i]。

A[j][i]在数组B的第(2n-j-1)

j/2+i的位置中找到。2.4.2数组的顺序存储结构第20页，共42页，2023年，2月20日，星期六三对角矩阵的压缩存储Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

0123456789102.4.2数组的顺序存储结构第21页，共42页，2023年，2月20日，星期六

三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]。在三条对角线上的元素aij

满足

0i

n-1,i-1

j

i+1在一维数组B中A[i][j]在第i行，它前面有3i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为k=2i+j。2.4.2数组的顺序存储结构第22页，共42页，2023年，2月20日，星期六2.4.3稀疏矩阵(SparseMatrix)

非零元素个数远远少于矩阵元素个数且分布无规律可循。

在上图中,矩阵A是6*7的矩阵,它有42个元素,但只有8个非零元素。

简单的压缩存储会失去随机存取功能，还要存储辅助信息

存储非零元素时，存储元素的行列号

存储方式：

顺序存储：不改变矩阵的稀疏程度(存取、修改、转置)

链式存储：改变矩阵的稀疏程度(相加、相乘)第23页，共42页，2023年，2月20日，星期六稀疏矩阵的抽象数据类型(三元组顺序表）#defineMAXSIZE12500typedefstruct{ inti,j; //非零元素行号/列号 ElemTypee;//非零元素的值}Triple;//三元组typedefstruct{ Tripledata[MAXSIZE]; intmu,nu,tu;//矩阵行数、列数、非零元个数}TSMatrix;//稀疏矩阵类定义

2.4.3稀疏矩阵(SparseMatrix)第24页，共42页，2023年，2月20日，星期六2.4.3稀疏矩阵(SparseMatrix)稀疏矩阵A76第25页，共42页，2023年，2月20日，星期六转置矩阵B67=AT762.4.3稀疏矩阵(SparseMatrix)第26页，共42页，2023年，2月20日，星期六用三元组表表示的稀疏矩阵及其转置2.4.3稀疏矩阵(SparseMatrix)如果只简单交换行列下标，所得B是按列优先存储第27页，共42页，2023年，2月20日，星期六稀疏矩阵转置算法思想

显然，一个稀疏矩阵的转置仍然是一个稀疏矩阵。(1)将矩阵的行列值交换(2)将每一个三元组的i和j相互调换(3)重排三元组之间的次序

可以有两种处理方法：2.4.3稀疏矩阵(SparseMatrix)第28页，共42页，2023年，2月20日，星期六方法一：按照A(mn)的列序来进行转置,设矩阵列数为nu，对矩阵三元组表扫描nu次。第k次检测列号为k的项。第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。2.4.3稀疏矩阵(SparseMatrix)按A的列下标转置，所得B是按行优先存放第29页，共42页，2023年，2月20日，星期六稀疏矩阵的转置StatusTransposeSMatrix(TSMatrix&A,TSMatrix&B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;

//转置矩阵的列数,行数和非零元素个数

if(B.tu){ q=0;//矩阵B的指针 for(col=0;col<=A.nu-1;++col) for(p=0;p<=A.tu-1;++p)//矩阵A的指针 if(A.data[p].j==col){ B.data[q].i=A.data[p].j; B.data[q].j=A.data[p].i; B.data[q].e=A.data[p].e; ++q; } } return1;}//TransposeSMatrix2.4.3稀疏矩阵(SparseMatrix)特点：以B矩阵的三元组为中心，在A矩阵的三元组中通盘查找合适的结点置入B中。第30页，共42页，2023年，2月20日，星期六

该算法主要工作是在pcol的两重循环中做的，所以时间复杂度是O(nutu)。一般矩阵的转置算法是在numu的两重循环中做的，时间复杂度是O(numu)。当稀疏矩阵的非零元个数tu=numu时，其时间复杂度:O(nutu)=O(nunumu)=O(nu2mu)大大高于一般矩阵的时间复杂度，所以该算法仅适用于tu<<numu的稀疏矩阵。2.4.3稀疏矩阵(SparseMatrix)用三元组节省了存储空间，但增加了执行时间第31页，共42页，2023年，2月20日，星期六方法二：快速转置运算(带辅助向量的三元组)预先确定A的每一列第一个非零元在B中应有的位置，则在转置时就可直接放到B中去，所以在转置前，应先求得A的每一列中非零元的个数和每一列的第一个非零元在B中的位置。

只需对A扫描一遍。需要两个辅助数组num和pos。num表示A中第col列非零元素的个数。pos表示A中第col列第一个非零元素在B中的位置。显然有：pos[0]=0pos[col]=pos[col-1]+num[col-1]2.4.3稀疏矩阵(SparseMatrix)第32页，共42页，2023年，2月20日，星期六矩阵A的辅助数组的值Col012356num[col]111221pos[col]012357转置矩阵第33页，共42页，2023年，2月20日，星期六StatusFastTransposeSMatrix(TSMatrix&A,TSMatrix&B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu; if(B.tu){ for(col=0;col<=A.nu-1;++col)num[col]=0;//初始化num for(t=0;t<=A.tu-1;++t)++num[A.data[t].j];//求A中每列非零元个数 pos[0]=0; for(col=1;col<=A.nu-1;++col)pos[col]=pos[col-1]+num[col-1];

//求第col列中第一个非零元在B中的序号 for(p=0;p<=A.tu-1;++p){ col=A.data[p].j;q=pos[col]; B.data[q].i=A.data[p].j; B.data[q].j=A.data[p].i; B.data[q].e=A.data[p].e;++pos[col];//该列下一元素位置 } } return1;}//FastTransposeSMatrix2.4.3稀疏矩阵(SparseMatrix)第34页，共42页，2023年，2月20日，星期六

该算法有四个并列的单循环，所以算法复杂度是O(2nu+2tu)=O(nu+tu)。当稀疏矩阵的非零元个数tu=numu时，其时间复杂度:O(nu+tu)=O(nu+numu)=O(numu)增加列辅助向量提高了转置的运算速度，但有空间代价。2.4.3稀疏矩阵(SparseMatrix)第35页，共42页，2023年，2月20日，星期六

2.4.4数组的链式存储结构带行指针的链表

把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。

例如，稀疏矩阵A的带行指针的链表：存储量：3tu+mu第36页，共42页，2023年，2月20日，星期六十字链表非零元结点：既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。行、列循环链表的表头结点：行、列、值为0，并且将所有的行、列链表和头结点一起链成一个循环链表。在行(列)表头结点中，行、列域的值都为0，故两组表头结点可以共用：即第i行链表和第j列链表共用一个表头结点，这些表头结点本身又可以通过val域(非零元值域，但在表头结点中为next，指向下一个表头结点)相链接。总的头结点(由指针hm指示，行、列域分别为稀疏矩阵的行、列数)，指向第一个表头结点。整个十字链表可由hm指针唯一确定。2.4.4数组的链式存储结构第37页，共42页，2023年，2月20日，星期六2.4.4数组的链式存储结构00nextdownright十字链表表头结点rowcolvaldownright十字链表非零元结点行指针域列指针域行、列和值的三元组mununext十字链表总的表头结点hm第38页，共42页，2023年，2月20日，星期六十字链表2.4.4数组的链式存储结构第39页，共42页，2023年，2月20日，星期六第一步，建立表头的循环链表

输入矩阵的行、列数和非零元素个数：m,n和t。表头结点的个数s=max(m,n)。建立总表头结点(由hm指针指向)和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表。总表头结点的行、列域分别为m和n；s个表头结点的行列域分别为0。s个行、列表头结点中的行、列指针域right和down均指向头结点本身。第二步，生成