s A base=(Elem Type*)malloc(elemtotal *sizeof(ET); 结if(!A.base)exit(Oⅴ ERFLOW); A constants=(int )malloc(dim*sizeof(int)); x if(!A constants)exit(OVERFLOW); A constants]dim-1=l; or(i=dim-2; i>=0; i--) 组和广义表 A constants i=A constants i+1]A bounds i+1; 义 return OK 5.3特殊矩阵的压缩存储 据 >特殊矩阵:数值相同的元素或零元素 在矩阵中的分布有一定规律。 之例:对称矩阵的压缩存储:以行序为主 数 序存储下三角中的元素,包括对角线 组上的元素。 表
6 数 据 结 构 之 数 组 和 广 义 表 11 A.base=(ElemType*)malloc(elemtotal*sizeof(ET)); if( ! A.base) exit(OVERFLOW); A.constants=(int *)malloc(dim *sizeof(int)); if( !A.constants) exit(OVERFLOW); A.constants[dim-1]=1; for(i=dim-2 ; i >=0 ; i--) A.constants[i]=A.constants[i+1]*A.bounds[i+1]; return OK; } 数 据 结 构 之 数 组 和 广 义 表 12 5. 3 特殊矩阵的压缩存储 ¾ 特殊矩阵：数值相同的元素或零元素 在矩阵中的分布有一定规律。 例：对称矩阵的压缩存储：以行序为主 序存储下三角中的元素，包括对角线 上的元素。 aij = aji 1<= i, j <= n
(1)二维下标为(i,j),存储空间的一维下标 为k,给出k与i,j的关系 (1<=i,j<=n, 结 0<=k<n*(n+1)/2); k=(i-1)*i/2+j-1(讠>=j)(,j)在下三角区 k=-1)j2+1(i<j)()在上三角区 int into k(int i, int ]i 组 if(i<l j<1 )return(-1); f(i>=j return((i-1)*1/2+j-1) return((-1)*j/2+i-1);} 13 (2)输入并存储对称矩阵的算法(以行序为主序) void Input(ET All, int n)t 数据结构之 for(k=0;k<(n+1)n/2;k++) scanf(&AkD;) 数(3)读取对称矩阵中某个元素的算法 Status GetElem(ET All, int i, int j, ET &e)i if(k=ijTo k(i,j>=0)t e=alk; return O; else return error
7 数 据 结 构 之 数 组 和 广 义 表 13 (1) 二维下标为( i , j ),存储空间的一维下标 为k，给出k与 i , j 的关系（1<= i, j <= n , 0<= k < n*(n+1)/2); k=(i-1)*i/2+j-1 ( i>=j) (i, j)在下三角区 k=(j-1)*j/2+i-1 (i< j) (i, j)在上三角区 int ij_TO_k(int i , int j){ if( i<1 || j<1 )return(-1); if(i>=j) return((i-1)*i/2+j-1); return ((j-1)*j/2+i-1); } 数 据 结 构 之 数 组 和 广 义 表 14 (2)输入并存储对称矩阵的算法(以行序为主序) void Input(ET A[ ], int n){ for(k=0;k<(n+1)*n/2; k++) scanf(&A[k]); } (3)读取对称矩阵中某个元素的算法: Status GetElem(ET A[ ], int i, int j , ET &e) { if(k=ij_TO_k(i , j)>=0){ e=A[k];return OK; } else return ERROR; }