数据结构第06章--数组和广义表课件

1、数据结构（C+版）第1章 绪论第2章 线性表第3章 排序第4章 串第5章 栈与队列第6章 数组和广义表第7章 树和二叉树第8章 查找第9章 图第10章 综合应用设计第6章 数组和广义表6.1 数组6.2 矩阵类 6.3 特殊矩阵的压缩存储 6.4 稀疏矩阵6.5 广义表数据结构（C+版）叶核亚6.1 数组6.1.1 一维数组6.1.2 多维数组数据结构（C+版）叶核亚6.1.1 一维数组数组分配内存空间的方式有2种静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。动态数组：声明时不指定数组长度。当程序运行中需

2、要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。数据结构（C+版）叶核亚6.1.2 多维数组多维数组的概念多维数组的遍历行优先次序a1,1，a1,2，a1,n，a2,1，a2,2，a2,n，am,1，am,2，am,n列优先次序a1,1，a2,1，am,1，a1,2，a2,2，am,2，a1,n，a2,n，am,n数据结构（C+版）叶核亚3多维数组的顺序存储结构将二维数组Amn按行优先次序存储在内存以后，元素ai,j的地址计算函数为：按列优先次序存储数组时，元素ai,j的地址计算函数为：数据结构（C+版）叶核亚4. 多维数组的随机存

3、储机制 数据结构（C+版）叶核亚6.2 矩阵类 6.2.1 矩阵类的声明6.2.2 矩阵类的操作 数据结构（C+版）叶核亚6.2.1 矩阵类的声明数据结构（C+版）叶核亚6.2.2 矩阵类的操作 数据结构（C+版）叶核亚例6-1 矩阵相加运算 数据结构（C+版）叶核亚6.3 特殊矩阵的压缩存储 a11，a21，a22，am1，am2，amn 数据结构（C+版）叶核亚6.4 稀疏矩阵6.4.1 稀疏矩阵的三元组线性表6.4.2 三元组顺序表6.4.3 三元组链表数据结构（C+版）叶核亚6.4.1 稀疏矩阵的三元组线性表稀疏矩阵的非零元素由三部分组成：行下标、列下标和矩阵元素值，这称为稀疏矩阵的三

4、元组。用稀疏矩阵的三元组序列表示为：1,1,1,3,1,2,3,3,7,4,3,8,4,4,9。 数据结构（C+版）叶核亚6.4.2 三元组顺序表表6-1 稀疏矩阵的三元组顺序表数组下标行下标列下标数据元素值01111312233734384449数据结构（C+版）叶核亚6.4.3 三元组链表1行的单链表示数据结构（C+版）叶核亚2十字链表数据结构（C+版）叶核亚6.5 广义表6.5.1 广义表的概念6.5.2 广义表的存储结构数据结构（C+版）叶核亚6.5.1 广义表的概念广义表的定义广义表（general list）是n（n0）个数据元素a1, a2, an组成的有限序列，记为：List=(a1, a2, an)L(a，b)/线性表，长度为2T(c，L)(c，(a，b)/L为T的子表，T的长度为2G(d，L，T)(d，(a，b)，(c，(a，b) /L、T为G的子表，G的长度为3S()/空表，长度为0S1(S)()/非空表，元素是一个空表，长度为1Z(e，Z)(e，(e，(e，() /递归表，Z的长度为2数据结构（C+版）叶核亚2广义表的特性（1）广义表是一种线性结构（2）广义表也是一种多层次的结构（3）广义表可为其他广义表共享（4）广义表可