数据结构第五章：数组与广义表的压缩存储

《数据结构》第五章主要讨论了数组和广义表这两个核心概念，包括数组的顺序表示和实现，特殊矩阵的压缩存储，以及广义表的定义和存储结构。 1. **数组的定义与顺序存储**： - 数组是由一组具有相同类型且下标不同的变量构成的数据结构，其元素间的顺序关系固定，通常分为一维、二维及多维数组。 - 在计算机中，由于内存是线性的，多维数组需要通过特定的规则（如行优先或列优先）将其转换为一维序列来存储。例如，二维数组可以按行存储，也可按列存储。 2. **特殊矩阵的压缩存储**： - 对于对称矩阵、三角矩阵等特殊矩阵，可以利用其结构特性进行压缩存储，节省空间。例如，对称矩阵只需存储对角线以上或以下的元素，因为其余部分可以通过对称性推导出来。 - 稀疏矩阵是指非零元素较少的矩阵，常使用三元组表示法，只存储非零元素的行号、列号和值，大大减少了存储需求。 3. **三元组表示的稀疏矩阵运算**： - 三元组表示法简化了稀疏矩阵的运算，但需要在矩阵运算中进行下标变换以保持正确性，这可能成为理解的难点。 - 例如，在矩阵加法或乘法中，需要根据三元组的行和列索引来定位对应元素，进行运算。 4. **广义表的定义与存储结构**： - 广义表是一种更通用的线性表，其元素可以是原子或子表，因此它支持更复杂的数据结构。 - 广义表的存储通常采用动态链表，便于处理元素为子表的情况，链表节点中包含元素值和指向下一个节点的指针，如果元素为子表，则指针指向子表的头节点。 5. **广义表的操作与递归算法**： - 广义表的基本操作包括创建、插入、删除和查找等，这些操作在链表结构中可以方便地实现。 - 广义表的递归算法是处理包含子表情况的关键，特别是涉及到表头和表尾的分析，例如，获取广义表的长度、深度，或提取子表等操作。 本章的学习重点是理解数组的顺序存储结构，掌握特殊矩阵的压缩存储技术，以及了解广义表的定义和基本操作。难点在于三元组表示下稀疏矩阵的运算处理，以及广义表的递归算法设计。学习者需要熟练掌握这些概念和方法，以便在后续的算法设计和数据结构应用中灵活运用。