【图解数据结构】数组和广义表全面总结 | 您所在的位置:网站首页 › 数据结构内容多吗 › 【图解数据结构】数组和广义表全面总结 |
目录 一、数组的定义 1.基本概念 2.抽象数据类型 二、数组的顺序存储和实现 1.行优先存储 2.列优先存储 3.多维数组存储地址 三、特殊矩阵的压缩存储 1.基本概念 2.三角矩阵 3.带状矩阵 4.三元组表示法 四、广义表 1.概念 2.运算 2.存储结构 一、数组的定义 1.基本概念 数组:按照一定格式排列同属性的值,为相同数据类型元素的集合。常用的有一维数组A[5]、二维数组A[5][5]、多维数组等。二维数组:通常把二维数组作为多维数组的代表,可以看出m个n维的线性表组成,如: 2.抽象数据类型ADT Array {数据对象:D={aj1j2…jn | ji =0,...,bi-1, i=1,2,..,n, n(>0)称为数组的维数,bi是数组第i维的长度, ji是数组元素的第i维下标,aj1j2…jn∈ElemSet }数据关系:R={R1, R2, ..., Rn } Ri={ | 0 ≤jk ≤bk -1, 1 ≤ k ≤ n 且k≠ i, 0 ≤ ji ≤bi -2, aj1…ji…jn , aj1…ji+1…jn∈D, i=2,...,n 二、数组的顺序存储和实现 存储结构:数组建立后,数组的个数及维数已经确定,故一般采用顺序存储结构存储位置:Loc(aij)= Loc(a[0][0])+( )*size(0≤i≤m, 0≤j≤n)存储次序: 按行优先存储按列优先存储 1.行优先存储行优先存储:将二维数组从第一行到最后一行,按照次序放到一维线性表中,存储位置首元素地址+((i-1)*n+j-1)*1, n为列数 2.列优先存储行优先存储:将二维数组从第一列到最后一列,按照次序放到一维线性表中,存储位置首元素地址+((j-1)*m+i-1)*1, m为行数 3.多维数组存储地址 以上述的一个四位数组为例,首先我们写一个一维数组A[4](大小和给定的维数相同),上面是四维四维数组大小分别为3 4 5 6,A[3]=1,A[2]=6,A[1]=5*6,A[0]=4*5*6,对应相乘最后因为求A1241所以结果为 A0000+1*A[0]+2*A[1]+4*A[1]+1*A[0] 三、特殊矩阵的压缩存储 1.基本概念 稀疏矩阵:矩阵存储的一种特殊情况,其元素为0个数远大于非0元素个数压缩方式:一维线性表存储,如下图:稀疏因子: 2.三角矩阵 元素个数:n*(n+1)/2按行存储的上三角矩阵:Loc[i,j]=Loc[1,1]+j*(j-1)/2+i-1按行存储的下三角矩阵:Loc[i,j]=Loc[1,1]+i*(i-1)/2+j-1 3.带状矩阵按行存储:Loc[i,j]=Loc[1,1]+2(i-1)+(j-1) 4.三元组表示法 i j 分别表示二维数组的横纵坐标,v表示坐标对应的非0值三元组转置动态演示: 编码实现: void FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示,求稀疏矩阵M的转置矩阵 T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |