数据结构5章 数组、广义表.pptVIP

第5章 数组和广义表 5.1 数组 5.2 稀疏矩阵 5.3 广义表 5.1 数组 5.1.1 一维数组 5.1.2 多维数组 5.1.1 一维数组 数组分配内存空间的方式有2种 静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。 动态数组：声明时不指定数组长度。当程序运行中需要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。 在Java中，数组元素既可以简单数据类型，也可以是引用类型。而且Java中的数组都是动态数组。 5.1.2 多维数组 1．多维数组的概念 2．多维数组的遍历 （1）行优先次序 a1,1，a1,2，…，a1,n，a2,1，a2,2，…，a2,n，…，am,1，am,2，…，am,n （2）列优先次序 a1,1，a2,1，…，am,1，a1,2，a2,2，…，am,2，…，a1,n，a2,n，…，am,n 3．多维数组的顺序存储结构 将二维数组Am×n按行优先次序存储在内存以后，元素ai,j的地址计算函数为： 按列优先次序存储数组时，元素ai,j的地址计算函数为： 【例5.1】 矩阵相加。 5.2 稀疏矩阵 5.2.1 稀疏矩阵的三元组 5.2.2 三元组的顺序存储结构 5.2.3 三元组的链式存储结构 5.2.1 稀疏矩阵的三元组 稀疏矩阵的非零元素由三部分组成：行下标、列下标和矩阵元素值，这称为稀疏矩阵的三元组。 用稀疏矩阵的三元组序列表示为：{{1,1,1},{3,1,2},{3,3,7},{4,3,8},{4,4,9}}。 5.2.2 三元组的顺序存储结构 5.3 广义表 5.3.1 广义表的概念 5.3.2 广义表的存储结构 5.3.1 广义表的概念 1．广义表的定义 广义表（general list）是n（n≥0）个数据元素a1, a2,…, an组成的有限序列，记为： List=(a1, a2,…, an) L＝(a，b) //线性表，长度为2 T＝(c，L)＝(c，(a，b)) //L为T的子表，T的长度为2 G＝(d，L，T)＝(d，(a，b)，(c，(a，b))) //L、T为G的子表，G的长度为3 S＝() //空表，长度为0 S1＝(S)＝(()) //非空表，元素是一个空表，长度为1 Z＝(e，Z)＝(e，(e，(e，(……)))) //递归表，Z的长度为2 2．广义表的特性 （1）广义表是一种线性结构 （2）广义表也是一种多层次的结构 （3）广义表可为其他广义表共享 （4）广义表可以是一个递归表 《数据结构（Java版）》叶核亚 * * 表5.1 稀疏矩阵三元组的顺序存储结构 9 4 4 4 8 3 4 3 7 3 3 2 2 1 3 1 1 1 1 0 数据元素值 列下标 行下标 数组下标