多维数组和广义表.pptVIP

第一页，共二十八页，2022年，8月28日 二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱和两个后继。也可看作是以线性表为数据元素的线性表。 n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。 因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。 5.1 多维数组 第二页，共二十八页，2022年，8月28日 多维数组用一维的存储单元存放，需约定次序。C语言是行优先顺序。 二维数组中任一元素aij的存储地址: n维数组 Loc(aij)=Loc(a00)+(n*i+j)*d 第三页，共二十八页，2022年，8月28日 5.2 矩阵的压缩存储 压缩存储 使用一维数组存储矩阵，并且在一维数组中为多个值相同的元素只分配一个存储空间，对零元不分配空间。 第四页，共二十八页，2022年，8月28日 5.2.1 特殊矩阵 对称矩阵： aij=aji 0≤i,j≤n-1 压缩存储方法：为每一对对称元分配一个存储空间 将下三角的元素，按行存储到一维数组sa中,共有n(n+1)/2个存储单元， aij在一维数组中的位置k为： i(i＋1)/2+j 当i=j； j(j＋1)/2+i 否则 第五页，共二十八页，2022年，8月28日 特殊矩阵 三角矩阵：上（下）三角中的元素均为常数c或0 压缩存储方法：只存储上（下）三角元素。 下三角：k=i*(i＋1)/2+j (i=j); k=n*(n+1)/2 (ij) 上三角：k=(i/2)*(2n-i+1)+j-i (i=j); k=n*(n+1)/2 (ij) 注意：k, i,j从零开始 第六页，共二十八页，2022年，8月28日 特殊矩阵 对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中 压缩方法：压缩存储到一维数组sa[ ]中，三对角矩阵有3n-2个元素。 第七页，共二十八页，2022年，8月28日 5.2.2 稀疏矩阵 已知矩阵Am×n，t为非零元个数，若t(m×n)，则称Am×n 为稀疏矩阵。 用三元组(i,j,v)存储行和列的位置及非零元值。 第八页，共二十八页，2022年，8月28日 1. 三元组表 顺序存储方式存储稀疏矩阵的三元组. 第九页，共二十八页，2022年，8月28日 三元组表结构定义 #define smax 16 //非零元个数最大值 Typedef int datatype typedef struct { int i，j; //行下标和列下标 datatype v; } node; typedef struct { node data[smax]; //非零元三元组表 int m,n,t; //行数、列数、非零元个数 }SpMatrix; SPMatrix *a,*b; 第十页，共二十八页，2022年，8月28日 三元组表稀疏矩阵的转置运算 第十一页，共二十八页，2022年，8月28日 稀疏矩阵的转置 Spmatrix *transmat(a) Spmatrix *a; { int ano,bno,col; Spmatrix *b; b=malloc(sizeof(Spmatrix)); b-m=a-n;b-n=a-m;b-t=a-t; if(b-t0) { bno=0; for(col=0;cola-n;col++) for(ano=0;anoa-t;ano++) if(a-data[ano].j==col) { b-data[bno].i= a-data[ano].j; b-data[bno].j= a-data[ano].i; b-data[bno].v= a-data[ano].v; bno++; } } return b; } 第十二页，共二十八页，2022年，8月28日 2.十字链表 当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。 行链表与列链表都是带表头结点的循环链表。 第十三页，共二十八页，2022年，8月28日 元素结点 rptr——指向同一行中下一个非零元素的