第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩

5.1数组的定义 ADT Array{ 数据对象：D={aj1aj2…ajn| aj1aj2…ajn∈Elemset, ji=0,1,…bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1,R2…Rn} Ri={< aj1…aji…ajn , aj1…aji+1…ajn >| 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 }

基本操作 : 二维数组定义 N维数组定义 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][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)+∑ciji cn=L,ci-1=bi*ci,1<i<=n

数组应用 例寻找两个串最长的公共子串 通常的匹配算法复杂度O(m*n2) 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg”。 算法时间复杂度 O(m*n)

s g a b c d f t 特征值 i-j=0 特征值 i-j=-(n-1) i-j 为固定值 特征值 i-j=m-1 Mat[0,0] Mat[m-1,n-1]

5.3 数组的压缩 特殊形状矩阵的存储表示(下标从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 i<j 三角矩阵：A[n][n]存储到B[n(n+1)/2] A[i,j]->B[k] k=(i+1)i/2+j i>=j 0 i<j 带状矩阵A[n][n]存储到B[3n-2] A[i,j]->B[k] k=3i-1+(j-i+2)-1=2i+j |i-j|<=1 随机稀疏矩阵 非零元比零元少的多且分布无规律的矩阵。

随机稀疏矩阵的存储表示 三元组顺序表 const MAXSIZE=1000 typedef struct{ int i,j; ElementType e; }Triple; Triple data[MAXSIZE+1]; int mu,nu,tu; }TSMatrix;

三元组顺序表示例 (下标从1开始) (b) T.data (a) M.data i j e 1 2 12 3 9 -3 6 14 4 24 5 18 15 -7 i j e 1 3 -3 6 15 2 12 5 18 9 4 24 -7 14 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 (b) T.data (a) M.data cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=col<=nu col 1 2 3 4 5 6 7 num[col] cpot[col] 8 9

矩阵转置 “按需点菜”的思想 “按位就座”的思想 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)

逻辑链接的顺序表 为了能随机存取三元组表示数组的任意一行非零元素，在建立三元组顺序表存储结构同时建立rpos[n]辅助数组,这种带行链接信息的三元组表称为“逻辑连接的顺序表” typedef struct{ Triple data[MAXSIZE+1]; int rpos[MAXMN+1]; int mu,nu,tu; }RLSMatrix;

十字链表 矩阵运算增加或减少非零元时，使用链表结构来表示三元组序列。 typedef struct OLNode{ int i,j; ElementType e; struct OLNode *rnext,*cnext; }OLNode,*Olink; typedef struct { Olink *rhead,*chead; int mu,nu,tu; }CrossList;

谢 谢

对称阵

条带阵

三元组存储数组的快速转置 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 算法5.2 // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (! T.tu) return FAIL; for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) // 求 M 中每一列所含非零元的个数 ++num[M.data[t].j]; cpot[1] = 1; // 求 M 中每一列的第一个非零元在 b.data 中的序号 for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1]+num[col-1]; for (p=1; p<=M.tu; ++p) { col = M.data[p].j; q = cpot[col]; T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i; T.data[q].e =M.data[p].e; ++cpot[col]; } // for } // FastTransposeSMatrix