数据结构与算法设计（第二版）课件 第5章数组

第五章数组数组—逻辑结构数组是我们很熟悉的一种数据结构，可以把数组看做是线性表的推广。数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一维数组二维数组三维数组数组—逻辑结构从小事做起，学会“积累”，学习也是一个积累的过程。使学生明白“积少成多”，能力才能螺旋式上升。数组—逻辑结构数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，一维数组可以看做是一个线性表；（a1a2…aj…an）二维数组可以看做是“数据元素是一维数组”的一维数组；三维数组可以看做是“数据元素是二维数组”的一维数组。a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………m行n列的二维数组看成n个列向量的线性表推广：

n维数组—每个数据元素受n个关系的约束，每一单个关系，仍是线性关系。也可看成m个行向量的线性表B=(βiβ2β1βm……a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………A=(α1

α

2…α

j

…α

n)每一个数组元素aij在第i行，第j列，受到两个线性关系的约束，就是行和列关系。数组—逻辑结构一般来说，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。从数组的特殊结构可看出，数组中的每个元素由一个值和一组下标来描述。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..数组—逻辑结构由于对数组一般不做插入、删除操作；一旦建立了数组，数据元素个数和元素之间的关系就不再发生变动；

采用顺序存储结构表示数组；由于存储单元是一维的结构，而数组是多维的结构，则采用一组连续存储单元存放数组元素就有个次序约定问题。一般有两种存储方式：一是以行为主序(即先行后列)的顺序存放，一行存储完了接着存储下一行。二是以列为主序(即先列后行)的顺序存放，一列存储完了接着存储下一列。数组—存储结构数组—存储结构第一行第二行第一列第二列第三列a11a12a13a21a22a232×3数组的逻辑状态a11a12a23a21a22a23

以行为主序a11a21a12a22a13a23

以列为主序采用以行为主序的方法存放，则存放顺序为：a111，a112，a121，a122，…，a331，a332，a341，…；采用以纵为主序的方法存放，则顺序为：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342。假设有一个3 × 4 × 2的三维数组，共有24个元素。三维数组元素的下标由三个数字表示，即行、列、纵三个方向。A231表示第2行、第3列、第1纵的元素。数组—存储结构

数组的顺序存储是一种随机存取的结构。如果已知多维数组的维数，以及每维的上、下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出数组中某个数组元素在存储器中的位置。设有m × n二维数组Amn，假设下标从1开始，以“以行为主序”的分配为例。设数组中的a11存储地址为Loc(a11)，每个数组元素占据L个地址单元，那么aij的物理地址可计算出来：Loc(aij) = Loc(a11) + ((i - 1)×n + j - 1) × L

这是因为数组元素aij的前面有i-1行，每一行的元素个数为n，在第i行中它的前面还有j-1个数组元素。数组—存储结构

同理，可得到三维数组Amnp中任意元素aijk的存储地址的计算公式：Loc(aijk) = Loc(a111) + ((i - 1) × n × p + (j - 1) × p + k - 1) × L

数组元素的存储位置是其下标的线性函数，一旦数组下标确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。数组—存储结构推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为:Loc(aijk)=Loc(ac1c2c3)+((i-c1)×(d2-c2+1)×(d3-c3+1)  +(j-c2)×(d3-c3+1)+(k-c3))×L对于n维数组A(c1..d1,c2..d2,…,cn..dn)，我们只要把上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储地址的计算公式：

容易看出，数组元素的存储位置是其下标的线性函数，一旦数组下标确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。数组—存储结构矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。而当数组元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干数组元素共用一个存储单元，即进行压缩存储。所谓压缩存储，是指为多个值相同的数组元素只分配一个存储空间，值为零的数组元素不分配空间。特殊矩阵—压缩存储矩阵的压缩存储是为了节约空间，虽然现在计算机硬件发展很快，其处理量以指数级增长，必须考虑存储空间的有效利用。“勤俭节约”，杜绝浪费。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..在一个n阶方阵中，有aij

=

aji，称之为对称矩阵；对称矩阵的特点是：在一个n阶方阵中，有aij

=

aji，其中1≤i,j≤n。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。特殊矩阵—压缩存储透过现象看本质！！！对于n*n矩阵A，只存储A中的下三角中的数组元素aij，上三角中的数组元素aij，和对应的aji相等，因此当访问的数组元素在上三角时，直接去访问和它对应的下三角数组元素即可，这样，原来需要n2个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..特殊矩阵—压缩存储透过现象看本质！！！第1行第2行第3行第n行对于下三角中的数组元素aij，其特点是：i≥j且1≤i≤n，存储到SA中后，根据存储原则，它前面有i-1行，共有1 + 2 + … + i - 1 = i × (i - 1) / 2个元素。而aij又是它所在的行中的第j个，所以在上面的排列顺序中，aij是第i × (i - 1) / 2 + j个元素。因此它在SA中的下标k与i、j的关系为Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..12345···n(n+1)/2a10a21a22a31a32a33···an1an2···ann特殊矩阵—压缩存储若i < j，则aij是上三角中的数组元素，因为aij = aji，这样，访问上三角中的数组元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的数组元素在SA中的对应关系：

综上所述，对于对称矩阵中的任意数组元素aij，若令I = max(i,j)，J = min(i,j)，则将上面两个式子综合起来得到：k = I × (I-1)/2 + J。特殊矩阵—压缩存储下三角矩阵上三角矩阵三角矩阵与对称矩阵类似，不同之处在于存完下三角中的数组元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可。这样一共存储了n × (n+1)/2+1个元素。下三角矩阵的压缩存储形式362481746082957c12345678910111213141516特殊矩阵—压缩存储若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。三对角带状矩阵特点：第一行、第n行只有两个非零元素，中间n-2行每行有三个非零元素。12345678910111213a11a12a21a22a23a32a33a34a43a44a45a54a32特殊矩阵—压缩存储(1)确定存储该矩阵所需的一维向量空间的大小。所需一维向量空间的大小为2 + 2 + 3(n - 2) = 3n - 2(2)确定非零元素在一维数组空间中的位置：Loc[i,j]。前i-1行元素个数 = 3 × (i-1) - 1(因为第1行只有两个非零元素)；第i行中aij前非零元素个数 = j-i+1，其中j-i的绝对值小于等于1。现在的任务是：将矩阵中的非零元素aij压缩存储。Loc[i,j] = Loc[1,1] + 3(i - 1) - 1 + j - i + 1 = Loc[1,1] + 2(i - 1) + j - 1特殊矩阵—压缩存储总而言之，对特殊矩阵的压缩存储方法时可以总结为两条：首先，确定压缩存储矩阵所需的空间的大小。第二：确定矩阵元素aij在压缩存储区域中的位置。特殊矩阵—压缩存储内容回顾数组—逻辑结构数组是我们很熟悉的一种数据结构，可以把数组看做是线性表的推广。数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一维数组二维数组三维数组数组—逻辑结构从小事做起，学会“积累”，学习也是一个积累的过程。使学生明白“积少成多”，能力才能螺旋式上升。对于n维数组A(c1..d1,c2..d2,…,cn..dn)，我们只要把上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储地址的计算公式：

容易看出，数组元素的存储位置是其下标的线性函数，一旦数组下标确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。数组—存储结构矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。而当数组元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干数组元素共用一个存储单元，即进行压缩存储。所谓压缩存储，是指为多个值相同的数组元素只分配一个存储空间，值为零的数组元素不分配空间。特殊矩阵—压缩存储矩阵的压缩存储是为了节约空间，虽然现在计算机硬件发展很快，其处理量以指数级增长，必须考虑存储空间的有效利用。“勤俭节约”，杜绝浪费。设m × n矩阵中有t个非零元素且t << m × n，稀疏矩阵—压缩存储δ=t/m × n，δ称为稀疏因子,

δ≤0.05时为稀疏矩阵。如果按顺序存储结构存储，会造成空间的浪费。通常零元素分布没有规律，存储非零元素的值是不够的，还要记下它所在的行和列。将非零元素所在的行、列以及它的值构成一个三元组(i,j,v)，然后再按某种规律存储这些三元组，这种方法可以节约存储空间。透过现象看本质！！！将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。

ijv123456711122351462341

1522

-15113691显然，要唯一地表示一个稀疏矩阵，可在存储三元组表的同时存储该矩阵的行、列，为了运算方便，矩阵的非零元素的个数也同时存储。稀疏矩阵—压缩存储1defineSMAX10242typedefstruct3{4inti,j; 5datatypev; 6}SPNode; 7typedefstruct8{9intmu,nu,tu;10SPNodedata[SMAX]; 11}SPMatrix; /*一个足够大的数*//*非零元素的行、列*//*非零元素值*//*三元组类型*//*矩阵的行、列及非零元素的个数*//*三元组表的存储类型*//*三元组表*/稀疏矩阵—压缩存储稀疏矩阵的三元组表表示法虽然节约了存储空间，但比起矩阵正常的存储方式来讲，其实现相同操作要耗费较多的时间，同时也增加了算法的难度，以耗费更多时间为代价来换取空间的节省。稀疏矩阵—压缩存储

所谓矩阵转置，是指变换元素的位置，把位于(row，col)位置上的元素换到(col，row)位置上，也就是说，把元素的行、列互换。采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：1voidTransMatrix(datatypesource[n][m],datatypedest[m][n])2{/*source和dest分别为被转置的矩阵和转置以后的矩阵*/3inti,j;4for(i=0;i<m;i++)5for(j=0;j<n;j++)6dest[i][j]=source[j][i];7}

显然，时间复杂度为O(m × n)。1稀疏矩阵的转置在A的三元组存储基础上得到B的三元组表存储算法思路：①由A的行数、列数、非零元数目转化成B的列数、行数、非零元数目。②按A的列(B的行)进行循环处理：对A的每一列扫描三元组，找出相应的元素，若找到，则交换其行号与列号，并存储到B的三元组中。-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元组表A(b)三元组表B

1稀疏矩阵的转置1SPMatrix*TransM1(SPMatrix*A)2{SPMatrix*B;3intp,q,col;//p为A中下标，q为B中下标4B=(SPMatrix*)malloc(sizeof(SPMatrix));/*申请存储空间*/5B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩阵的行、列、元素个数*/6if(B->tu>0)/*有非零元素则转换*/7{q=1;8for(col=1;col<=(A->nu);col++)/*按A的列序转换*/9for(p=1;p<=(A->tu);p++)/*扫描整个A的三元组表*/10if(A->data[p].j==col)//三元组中的元素在当前列。11{B->data[q].i=A->data[p].j;//逐个复制当前的A三元组元素到B三元组12B->data[q].j=A->data[p].i;13B->data[q].v=A->data[p].v;14q++;15}/*if*/16}/*if(B->tu>0)*/17returnB;/*返回的是转置矩阵的指针*/18}/*TransM1*/时间复杂度为O(A.n×A.len),最坏情况当A.len=A.m×A.n时，时间复杂度为O(A.m×A.n2)。1稀疏矩阵的转置依次按三元组表A的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。

为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：待转置矩阵每一列中非零元素的个数。(2)待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置。快速转置方法：为此，需要设两个数组num[col]——用来存放A中第col列非零元素个数cpot[col]——用来存放A中第col列中第一个非零元素在三元组表B中的正确位置。col90781687531Position[col]01222num[col]54321-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元组表A(b)三元组表B(1)num[col]的计算方法：将三元组表A扫描一遍，对于其中列号为k的元素，给相应的num[k]加1。(2)position[col]的计算方法：position[1]=1，position[col]=position[col-1]+num[col-1]，其中2≤col≤A.nu。

算法如下：SPMatrix*FastTM(TSMatrix*A){SPMatrix*B;intcol,t,p，q;//p为A下标，q为B下标

intnum[MAXSIZE],cpot[MAXSIZE];B->tu=A->tu;B->nu=A->mu;B->mu=A->nu;if(B->tu>0){for(col=1;col<=A->nu;col++)num[col]=0;//num初始化

for(t=1;t<=A->tu;t++)num[A->data[t].col]++;//计算num

cpot[1]=1;for(col=2;col<=A->nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<A.tu；p++){col=A.data[p].col;q=cpot[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].ecpot[col]++;//下一个col行非零元素位置加1}//for}//if}快速转置算法时间耗费在四个并列的单循环上，这四个并列的单循环分别执行了A.nu，A.tu，A.nu，A.tu次；因而总的时间复杂度为O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。当待转置矩阵M中非零元素个数接近于A.mu×A.nu时，其时间复杂度接近于经典算法的时间复杂度O(A.mu×A.nu)。空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num[1..A->nu]，cpot[1..A->nu]。可见，算法在时间上的节省，是以更多的存储空间为代价的。岁月静好，是因为有人在替我们负重前行三元组表存储的稀疏矩阵，在进行矩阵加法、减法和乘法等操作时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A = A + B，将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。为此引入了链式存储稀疏矩阵。矩阵中，每一个矩阵元素aij，受两个线性关系的约束，行关系、列关系；每一个关系都是线性的，我们可以用线性链表来存储行关系、列关系；这样，aij就处于第i行的单链表中，也处于第j列的单链表中，就像处于十字路口一样，所以我们将这种存储结构称之为“十字链表”。稀疏矩阵—压缩存储在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row，col，value)以外，还要有以下两个链域：

right：用于连接同一行中的下一个非零元素；

down：用于连接同一列中的下一个非零元素。同一行的非零元素通过right域连接成一个单链表，同一列中的非零元素通过down域连接成一个单链表。同时，再附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头指针的一维数组。rowcolvaluedownright稀疏矩阵—压缩存储稀疏矩阵十字链表十字链表的结构类型说明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下标*//*非零元素*//*非零元素所在行表、列表的后继链域*//*行、列链表的头指针向量*//*稀疏矩阵的行数、列数、非零元素的个数*/稀疏矩阵—压缩存储十字链表的结构类型说明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下标*//*非零元素所在行表、列表的后继链域*//*行、列链表的头指针向量*//*稀疏矩阵的行数、列数、非零元素的个数*/稀疏矩阵—压缩存储广义表是线性表的推广，也有人称其为列表。线性表是由n个数据元素组成的有限序列。(a1，a2，…，ai，…，an)其中每个组成元素被限定为单元素。广义表将这种限制突破了，表中的元素可以是单元素，也可以是一个表。广义表—逻辑结构中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：(俄罗斯，巴西，(国家，河北，四川)，古巴，美国，()，日本)韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这就是广义表。广义表是n(n≥0)个数据元素a1，a2，…，ai，…，an的有序序列，一般记作：ls = (a1，a2，…，ai，…，an)其中：ls是广义表的名称，n是它的长度。每个ai (1≤i≤n)是ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls的单元素和子表。当广义表ls非空时，称第一个元素a1为ls的表头(head)；称其余元素组成的表a2，…，ai，…，an)为ls的表尾(tail)。广义表—逻辑结构通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。广义表的例子：D = ( ) 空表，其长度为零A = (a，(b，c))表长度为2的广义表 B = (A，A，D) 长度为3的广义表C = (a，C)长度为2递归定义的广义表C相当于无穷表C = (a，(a，(a，(…))))

广义表—逻辑结构广义表的重要性质：(1)广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。A = (a，(b，c))