第五章数组5.1数组的定义5.2数组的表示和实现5.3数组的压缩中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩
5.1数组的定义ADT Array数据对象: D={ajiaji...ajnl ajiaj2...ain EElemset,j:=0，1，…b:-1bi是数组第i维的长度，n是位数数据关系：R={R,R,"-R,}R={aji...aj...ajin , aji...aji+...ajn ED, i=2, 3..n0<=jk<=bk-1, 1<=k<=n, k!=I0<=j;<=b;-1 }中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 5.1数组的定义 ADT Array{ 数据对象：D={aj1 aj2.ajn| aj1 aj2.ajn∈Elemset, ji=0,1,.bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1 ,R2.Rn} Ri={| aj1.aji.ajn , aj1.aji+1.ajn ∈D,i=2,3.n 0<=jk<=bk-1,1<=k<=n,k!=I 0<=ji<=bi-1 }
基本操作：initArray(&A,n,bound1,bound2...boundn)DestroyArray(&A)Value(A,&e,indexl,index2.....indexn)Assign(&A,e,indexl,index2.....indexn)ADT Array二维数组定义一其数据元素是一维数组的线形表N维数组定义其数据元素是N-1维数组的线形表3中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 基本操作 : initArray(&A,n,bound1,bound2.boundn) DestroyArray(&A) Value(A,&e,index1,index2.indexn) Assign(&A,e,index1,index2.indexn) }ADT Array • 二维数组定义 – 其数据元素是一维数组的线形表 • N维数组定义 – 其数据元素是N－1维数组的线形表
5.2数组的顺序表示和实现数组元素的两种存储方式一行主序存储一列主序存储数组中元素在内存映象中的关系- 二维数组A[m][n]LOC(i,j)-LOC(0,0)+(i*n+i)*L_三维数组B[p][m][n]LOC(i,j,k)=LOC(0,0,0)+(i*m*n+j*n+k)*L一多维：LOC(j1.j2..jn)-LOC(0,...0)+(b2*...*b.*ji+ b3*..*b*j2+... +bn*jn-1+jn )*L=LOC(0,0... 0)+Zcjicn=-L,Ci-1=b,*c,1<i<=n4中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 • 数组元素的两种存储方式 – 行主序存储 – 列主序存储 • 数组中元素在内存映象中的关系: – 二维数组A[m][n] LOC(i,j)=LOC(0,0)+(i*n+j)*L – 三维数组B[p][m][n] LOC(i,j,k)=LOC(0,0,0)+(i*m*n+j*n+k)*L – 多维： LOC(j1 ,j2.jn )=LOC(0,0.0)+(b2 *.*bn*j1+ b3 *.*bn*j2 +.+bn*jn-1+jn )*L=LOC(0,0.0)+∑ci j i cn=L,ci-1=bi*ci ,1<i<=n 5.2数组的顺序表示和实现
数组应用例寻找两个串最长的公共子串一通常的匹配算法复杂度O(m*n2)一利用二维数组构造串之间的关系来求解S1=sgabacbadfgbacst"S2=gabadfgab"最大公共子串"badfg"算法时间复杂度O(m*n)5中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 5 中国科学技术大学 • 例寻找两个串最长的公共子串 – 通常的匹配算法复杂度O(m*n2 ) – 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用
特征值特征值i-j-0fbba1Sacbaa60asgi-j=-(n-1)11oMat[0,0]111ainjb1为固定值1adf1g特征值111ai-j-m-1Mat(m-1,n-1]111n
s g a b a c b a d f g b a c s t g 1 1 a 1 1 1 1 b 1 1 1 a 1 1 1 1 d 1 f 1 g 1 1 a 1 1 1 1 b 1 1 1 Mat[0,0] Mat[m -1,n -1] i-j 为固定值 特征值 i-j= -(n -1) 特征值 i-j=m-1 特征值 i-j=0
5.3数组的压缩特殊形状矩阵的存储表示（下标从0开始）对称矩阵：A[n][n]存储到B[n(n+1)/2]A[i,j]->B[k]r k=(i+1)i/2+j i>=jk=(j+1)j/2+i iB[k]（k=(i+1)i/2+j i>=j10ikj带状矩阵A[n][n]存储到B[3n-2]A[i,j]->B[k]k=3i-1+(j-i+2)-1=2i+j [i-j<=1lo随机稀疏矩阵一非零元比零元少的多且分布无规律的矩阵中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 • 特殊形状矩阵的存储表示(下标从0开始) 对称矩阵：A[n][n]存储到B[n(n+1)/2] A[i,j]->B[k] k=(i+1)i/2+j i>=j k=(j+1)j/2+i iB[k] k=(i+1)i/2+j i>=j 0 iB[k] k=3i-1+(j-i+2)-1=2i+j |i-j|<=1 0 随机稀疏矩阵 – 非零元比零元少的多且分布无规律的矩阵。 5.3 数组的压缩
随机稀疏矩阵的存储表示三元组顺序表const MAXSIZE=1000129..0..0.0..0..0..0..0. :0..0..0..0..0.typedef struct?0. :-30.0.0.140.intij;0..0. :240.0.0.0.ElementTypee;0..180..0.0..0..0.}Triple;O.0s15.-7.0O.0typedef struct(Tripledata[MAXSIZE+11intmu,nu,tu,↓TSMatrix;8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 • 三元组顺序表 const MAXSIZE=1000 typedef struct{ int i,j; ElementType e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; int mu,nu,tu; }TSMatrix; 随机稀疏矩阵的存储表示
三元组顺序表示例(下标从1开始)--jee1231-3121111326915213132-3123(b) T.data365142184(a) M.data4543319524635242461866174-715783646148-7cpot[1]=1129..0..0..0..0..0.0..cpot[col]=cpot[col-1]+num[col-1]2<=col<=nu0..0..0..0..0..0.-30..0.0.0140.1423567col0..0..240.0.0.0.1022102num[col]0..180.0.0..0..0.7583891cpot[co]]O15.O.0.-7.0,O
三元组顺序表示例 i j e 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 (a) M.data i j e 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 (b) T.data col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 3 5 7 8 8 9 cpot[col]=cpot[col-1]+num[col-1] 2<=col<=nu cpot[1]=1 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 •(下标从1开始)
矩阵转置void transpose(ElemType M[Il,T[JD)时间复杂度O(n×m)“按需点菜”的思想复杂度O(M.nu×M.tu)“按位就座”的思想 建立辅助数组 num[n] cpot[n]void createpos(TSMatrix M)一快速转置status fastTransposeSMatrix(TSMatrix M, TSMatrix T)时间复杂度 O(M.nu+M.tu)10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 • 矩阵转置 void transpose(ElemType M[][],T[][]) 时间复杂度O(n×m) • “按需点菜”的思想 复杂度O(M.nu×M.tu) • “按位就座”的思想 – 建立辅助数组 num[n] cpot[n] void createpos(TSMatrix M) – 快速转置 status fastTransposeSMatrix(TSMatrix M, TSMatrix T) 时间复杂度 O(M.nu+M.tu)