第五章数组 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-{a1a2anla1a2.an∈EI emset,. j0,1,b:-1bi是数组第i维的长度，n是位数} 数据关系：R={R,R2R} Rifaj1...ajan aj1...ajitan aj1.aji.ajn,ajl.ait1.an∈D,i=2,3…n 0<=jk=bk-1,1<=k<=n,k!=l 0<=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 }
S 基本操作 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维数组的线形表 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+j)*L - 三维数组B[p][ml[n] LOC(i,j,k)=LOC(0,0,0)+(i*m*n+j*n+k)*L -多维： L0CGj1j2jn)=L0C(0,00)t(b2*..*bn*j1+b3*..*bn*j2 +...+bn*jn-1+jn)*L=LOC(0,0...0)+ciji Cn=L,Ci-1=b*ci,1<i<=n ypb@ustc.edu.cn 4 中国科学技术大学
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数组的顺序表示和实现
数组应用 例寻找两个串最长的公共子串 -通常的匹配算法复杂度0(m*n) 一利用二维数组构造串之间的关系来求解 S1=sgabacbadfgbacst" S2-“gabadfgab' 最大公共子串"badfg”。 算法时间复杂度Om*n) ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 • 例寻找两个串最长的公共子串 – 通常的匹配算法复杂度O(m*n2 ) – 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用
特征值 i-j=0 g a b a b a d f g b a 特征值 j泸-(n-1) Mat[0,0] a 1 1 1 1 b 1 j 为固定值 1 1 d f g 1 特征值 a 1 1 1 i-j=m-1 Mat|m-1,n-1]
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,jl->B[k]k=(i+1)i/2+j i>= k=(j+1)j/2+i iB[k] k=(i+1)i/2+ji>=j 0 K 带状矩阵A[n][n]存储到B[3n-2] A[i,jl->B[k] (k=3i-1+(j-i+2)-1=2i+j i-j=1 0 随机稀疏矩阵 一非零元比零元少的多且分布无规律的矩阵。 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=1000 0.·12 9.0.…0.0.0 typedef struct{ 0.0. 0.,0.0.,0.,0 -3 0. 0.0.0.140. int ij 0.· 0.,240.0.0.0 ElementType e; 0.180., 0.…0.00 }Triple; 15.0. 0. -7.0.0.0. typedef struct{ Triple data[MAXSIZE+1]; int mu,nu,tu; TSMatrix; ypb@ustc.edu.cn 8 中国科学技术大学
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开始 e e 1 1 2 12 3 3 2 7 3 9 2 6 15 3 3 1 3 3 2 1 12 (a)M.data 4 3 6 14 4 2 5 18 (b)T.data 5 4 3 24 5 3 N 9 6 5 2 18 6 3 4 24 7 6 1 15 7 4 6 7 8 6 4 1 8 6 3 14 0..12 9. 0.00.0. cpot[1]=1 0·0·0 0…0…0…0 cpot[col]=cpot[col-1]+num[col-1] 2<=col<=nu -30.,0. 0.0.…140. col 1 2 3 7 0.·0.24 0.0.0.0 num[col] 2 2 0..180., 000.0 0 -7.0.0.0 cpot[col] 15.0
三元组顺序表示例 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[][],T[][]) 时间复杂度0n×m) “按需点莱”的思想 复杂度O(M.nu×M.tu) “按位就座”的思想 - 建立辅助数组num[n]cpot[n] void createpos(TSMatrix M) 快速转置 status fastTransposeSMatrix(TSMatrix M,TSMatrix T) 时间复杂度OM.u+M.tu) ypb@ustc.edu.cn 10 中国科学技术大学
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)