【图解数据结构】数组和广义表全面总结 |
您所在的位置：网站首页 › 线性表图解 › 【图解数据结构】数组和广义表全面总结 |
【图解数据结构】数组和广义表全面总结
|
目录 一、数组的定义 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.多维数组存储地址
 稀疏因子： 
2.三角矩阵
按行存储：Loc[i,j]=Loc[1,1]+2(i-1)+(j-1) 4.三元组表示法
三元组转置动态演示： 
编码实现： 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 |
【本文地址】