北航数据结构Data03

数据结构2第三章数组3.1数组的概念3.1.1数组的定义3.1.2数组的形式化定义3.2数组的存储结构3.3矩阵的压缩存储3.3.1对称矩阵的压缩存储3.3.2对角矩阵的压缩存储3.4稀疏矩阵的三元组表示33.5稀疏矩阵的十字链表表示3.6数组应用举例3.6.1一元多项式的数组表示3.6.2n阶魔方上机作业43.1.1数组的定义1、数组数组(Array)是一组按一定格式排列的、具有相同属性的项目或者数据元素，如线性表、矩阵等。如果线性表的所有元素都是线性表(称为子表)，且这些子线性表具有相同的上限标号和下限标号，那么这类线性表也称为数组。数组可以看成是下标与值组成的数偶的有序集合，即对于每个下标，总有一个相应的元素与之对应。这种基于位置上的对应关系是一种线性关系，因此，数组的逻辑结构就是一种线性结构。52、数组的表示在数组中用下标来唯一标识数据元素。如果数组元素只需要一个下标就能唯一确定，则称为一维数组；至少需要n个下标才能唯一确定一个元素，则称为n维数组。一维数组表示成：A(n)

或者A(m:

n)；其中A是数组名称，m称为数组的下界，n称为上界；而A(n)的下界默认为1。二维数组表示成：A(m,n)

或者A(i:m,j:n)；n维数组表示成：A(i1,i2,i3,...,in)；其中i1,i2,i3,...,in表示数组各维的下标上界，下界均为1。63.1.2数组的形式化定义1、一维数组的形式化定义一维数组的逻辑结构可以形式化地定义为：ARRAY_1=(D,R)，其中，D={ai|c1<=i<=c2,aidataobject}，R={ROW}，ROW={<ai,ai+1>|c1<=i<=c2,ai,ai+1D}。c1、c2,分别表示下标的一对界偶，即下界和上界。数组中元素个数=c2-c1+172、二维数组的形式化定义二维数组，其逻辑结构的形式化定义可以表示成：ARRAY_2=(D,R)，其中，D={aij|c1<=i<=c2,d1<=j<=d2,aijdataobject}，R={ROW,COL}，ROW={<aij,ai,j+1>|c1<=i<=c2,d1<=j<=d2-1,aij,ai,j+1D}COL={<aij,ai+1,j>|c1<=i<=c2-1,d1<=j<=d2,aij,ai+1,jD}（c1、c2）与（d1、d2）分别是下标i和j的上下界。数组中元素个数=(c2-c1+1)*(d2-d1+1)8n维数组的逻辑结构的形式化定义ARRAY_n=(D,R)，其中，

D={aj1,j2,…,jn|ci<=ji<=di,aj1,j2,…,jndataobject}，R={R1,R2,……,Rn}Ri={<aj1，…,ji,…,jn,aj1,…，ji+1,…,jn>|ck<=jk<=dk且k<>i，ci<=ji<=di-1，

aj1,…，ji,…,jn,aj1,…，ji+1,…,jnD}3、n维数组的形式化定义94、数组的操作n维数组的每个元素受到n个关系的约束，再每个关系中，每个元素都存在一个直接后继。每个关系都是线性关系。因此，n维数组是线性表的一种推广。一般数组的规模是固定的，没有插入、删除运算。给出一组下标，检索对应的数据元素；或者存取相应元素的值；重新排列数组元素。103.2数组的存储结构1、数组的降维存储由于计算机内的存储空间是一维(线性)的，要将多维数组存储到计算机内，必须将多维数组映射到一维存储空间中，因此，需要降低数组的维数，即将n维数组看成是n个n-1维数组的有序集合。在计算机中，数组也与线性表一样，是保存在一块连续的内存空间中的，即数组采用的是顺序分配方式。112、行主序一个2×3的二维数组A(2,3)共有六个元素，需要用6个连续的单元存放。对这些元素，有两种组织方式。一种是以“行”为主次序进行分配，称为行主序。A(1,1)A(1,2)A(1,3)第一行A(2,1)A(2,2)A(2,3)第二行(a)以行为主序存放123456A(i,j)元素存放位置=B+[(i-1)*3+(j-1)]*Lena11a12a13a21a22a23123、列主序以“列”为主次序进行存储分配。A(1,1)A(2,1)A(1,2)第一列A(2,2)A(1,3)A(2,3)第二列(b)以列为主序存放第三列123456A(i,j)元素存放位置=B+[(i-1)+(j-1)*2]*Lena11a12a13a21a22a23134、数组A(m,n)的存储地址访问公式以“行”为主次序存放：

A(i,j)的起始地址=b+[(i-1)*n+(j-1)]*L以“列”为主次序存放：

A(i,j)的起始地址=b+[(i-1)+(j-1)*m]*L5、数组A(m:n,p:q)的存储地址访问公式以“行”为主次序存放：

A(i,j)首址=b+[(i-m)*(q-p+1)+(j-p)]*L以“列”为主次序存放：

A(i,j)首址=b+[(i-m)+(j-p)*(n-m+1)]*L146、三维数组A(p,m,n)以行为主次序的访问公式如下：

A(i,j,k)首址=b+[(i-1)*m*n+(j-1)*n+(k-1)]*L以列为主次序的访问公式如下：

A(i,j,k)首址=b+[(i-1)+(j-1)*p+(k-1)*p*m]*L157、n维数组A(d1,d2,d3,......,dn)行主序：数组中任一元素A(j1,j2,j3,...,jn)的存储位置，可以通过访问公式计算，数组各元素的存取是随机的，在时间上大致相等，因此，数组是一种随机存取的数据结构。163.3.1对称矩阵的压缩存储1、对称矩阵一个m行n列的矩阵共有m*n个数据元素。当m=n时，则称该矩阵为n阶方阵。在程序设计中，通常将矩阵表示为一个二维数组。采用顺序存储方式。若一个n阶矩阵A的元素满足性质：aij=aji，1<=i,j<=n，则称该矩阵为n阶对称矩阵。n阶对称矩阵中几乎一半的元素相同，因此，对于每一对对称元素可以只分配一个存储单元。这样，n阶对称矩阵的n2个元素就可以压缩到（n*(n+1)/2）个存储单元中。172、对称矩阵的压缩存储a11，a12，a13，……，a1i，……，a1na21，a22，a23，……，a2i，……，a2n

……ai1，ai2，ai3，……，aii，……，ain……an1，an2，an3，……，ani，……，ann18按行主序存储对称矩阵下三角元素。数组LTA(1:(n*(n+1)/2))作为A的存储结构，A中的任意一个元素aij与LTA[k]之间存在的对应关系：对于每一组下标值(i,j)均可以在LTA中找到元素aij，反之，对于所有k=1，2，…，(n*(n+1)/2)，都能确定LTA[k]在矩阵A中的位置(i,j)。193.3.2对角矩阵的压缩存储矩阵的所有非零元素都集中在以对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方若干条对角线上的元素外，其余元素皆为零。1、对角矩阵对于三对角矩阵B，可以按行（或列）主序方式将对角矩阵B中的所有非零元素压缩存储到一个一维数组LTB[1：3n-2]中。202、对角矩阵的行主序方式存储按行主序方式存储，则B中任意一个非零元素bij，与LTB[k]之间存在一一对应关系，即k=2*i+j–2时，则有bij=LTB[k]。k=3*(i-1)-1+(j-(i-1))+1=3i-4+j-i+2=2i+j-2第i行的非0元素bij应当是：bij-1bijbij+1211、稀疏矩阵3.4稀疏矩阵的三元组表示当一个数组中的元素很多都是0时，该数组就称为稀疏数组。一个矩阵中有许多0元素时，则称该矩阵为稀疏矩阵。一个m×n的矩阵M，采用顺序方式存储时，需要分配m×n个单元；当有许多0元素时，会造成存储空间的浪费。因此，可以考虑进行压缩存储。一个m×n的矩阵M，每个元素可以用一个行标号和列标号来唯一确定它的位置，因此，可以用元素的行和列标号来指示非0元素的位置，同时保存下该非0元素值。即用(i,j,Vij)表示非0元素。222、稀疏矩阵的三元组表示(ijVij)123456781115142216651916328668下限为0和1，上限为t和3的二维数组A(0:t,1:3)来存储稀疏矩阵的非0元素。t是非0元素个数。233、稀疏矩阵的转置运算转置是一种最简单的矩阵运算。矩阵M转置成另一个矩阵N，应满足M(i,j)=N(j,i)，1im及1jn。244、三元组表示矩阵的转置6681115412261-15

22116681115412261-15

221136283236681115412261-15

221132343-643-66681115412261-15

2211323159143-66681115412261-15

2211323159143-66681115412261-15

22113231591362825按列顺序实现转置：43-6668

1115

4122

61-15

22113231591362826算法步骤（1）从A中读取矩阵的行数m、列数n和非零元素个数t，并设置B的行数为n、列数为m、非零元素个数为t；（2）设置计数器col=1，表示当前正在转置A的第col列元素（B的第col行）；（3）从A中选择列号为col的元素，转置后顺序存入B；（4）当A中列号为col的元素转置完后，给col加1；（5）如果col不大于n，重复步骤（2）（3）（4），否则结束，完成转置。27voidTranspose(intA(ROW,COL),B(ROW,COL))；{intm,n,t,p,q,Col;m=A[0,1];n=A[0,2];t=A[0,3];B[0,1]=n;B[0,2]=m;B[0,3]=t;if(t>0){q=1;for(col=

1;Col<=n;col++)//当前转置的列号为col//for(p=1;p<=t;p++)if(A[p,2]==col){//本次需要转置的元素//B[q,1]=A[p,2];B[q,2]=A[p,1];B[q,3]=A[p,3];q=q+1;

}；//

一个元素转置//

}；//所有元素转置结束//}；//算法结束//285、快速转置快速转置的思路是：每行中的非0元素个数是可以统计出来的；每个非0元素都有自己最终的存储位置；按行进行转置时，直接将元素存入对应位置。设置一个数组Num(n)统计每列（转置后每行）的非0元素个数；设置一个数组Pot(n)存储转置后每行第一个非0元素的存储位置。29计算每列的非0元素个数快速转置过程for(Col=1,Col<=nCol++)Num[Col]=0;for(p=1,p<=t,p++)Num[A[p,2]]=Num[A[p,2]]+1;计算转置后每行第一个非0元素的存储位置：Pot[1]=1;for(Col=2,Col<=n,Col++)Pot[Col]=Pot[Col-1]+Num[Col-1];30Pot[Col]134688Col123456668111524122761-15922114532343-68159133628631快速转置算法voidFast-Transpose(intA(ROW,COL),B(ROW,COL)){intm,n,t,p,q,Col;m=A[0,1];n=A[0,2];t=A[0,3];B[0,1]=n;B[0,2]=m;B[0,3]=t;if(t<=0)return;for(Col=1;Col<=n;Col++)Num[Col]=0;for(p=1;p<=t;p++)Num[A[p,2]]=Num[A[p,2]]+1;Pot[1]=1;//计算转置后每行第一个非0元素存储位置//for(Col=2;Col<=n;Col++)Pot[Col]=Pot[Col-1]+Num[Col-1];for(p=1;p<=t;p++){//开始转置//Col=A[p,2];B[Pot[Col],1]=A[p,2];B[Pot[Col],2]=A[p,1];B[Pot[Col],3]=A[p,3];Pot[Col]=Pot[Col]+1;}//元素转置结束//}//算法结束//323.5稀疏矩阵的十字链表表示1、稀疏矩阵的循环链表表示用链表表示稀疏矩阵中的非0元素，需要存储：行号、列号、元素值；将非零元素以行主序方式用循环链表链接起来。ijVLinkmntLink表头结点34511414222331533-1H332、稀疏矩阵的十字链表表示每个元素按行有一个后继，按列有一个后继，因此，需要设置两个指针，分别指向行后继和列后继元素；用链表表示稀疏矩阵中的非0元素，需要存储：行号、列号、元素值；RowColRightDownValue结点结构mnRightDownt表头结点Row、Col、Value分别表示非0元素的行、列和值，Down和Right表示向下（列）和向右（行）指针，分别链接同一列和同一行中的非0元素。3434501002003004010020030011431514222333-1353.6.1一元多项式的数组表示方法1：定义一个一维数组A[1：n+2]。其中，A[1]用来存储多项式的阶数，从A[2]开始到A[n+2]，分别存储n+1个系数an，an-1，…，a0。1、一元n阶多项式的数组表示例如，多项式A（x）=10x6–8x5+3x2–1，表示成：36例如，B（x）=x200+4方法2：定义一个一维数组A[1：2m+1]来表示多项式。其中，第1个元素A[1]存放多项式中系数非0项的总项数m；从第2个元素到第2m+1个元素（共2m个）依次存放系数非0项的指数与系数偶对（共m个偶对）。373.6.2n阶魔方所谓n阶魔方是一个填数游戏。要求将数字1~n2个数字不重复地填入到一个由n行n列组成的方阵中，使得方阵中每行、每列、两个对角线上的数字之和分别等于同一个数值。这个方阵就称为“魔方”。最早的魔方据说是大禹治水(公元前2200)在神龟背上看到的3阶魔方：492357816洛书上的3阶魔方38公元80年出版的古书《大戴礼记》：“二九四、七五三、六一八”1977年出土的第二代汝阴侯夏侯灶(公元前165年)墓文物“太乙九宫占盘”八个方位所刻数字及中心位置的九宫数字恰为“四九二、三五七、八一六”南宋杨辉：研究魔方第一人，给出了3、4-10阶魔方39杨辉4阶魔方称为“花十六图”或“四四图”，分阳图和阴图杨辉4阶魔方216133115810791261441151395114106215117316128449516147112156103112813阴图生成法：十六子依次四行排列；外角四子互换：1-16、4-13；内角四子互换：6-11；7-104951614711215610311281340如何构造魔方适合于奇数阶魔方

将1设置在最上行中间，然后按对角线的方向（自右下向左上、或者自左下向右上方向）依次填入数字；如果到达顶部则转向底部；左（右）边界则转向右（左边），如果其上已有数字则转向下方。例如n=3“魔方”为：12345678

91、连续摆数法81635749241n=5“魔方”为：1234567891011121314151617181920212223242542voidMAGIC(intM(ROW,COL)，