数组与广义表的数据结构解析

"这份资料是关于数据结构的课件，主要涵盖了数组和广义表的知识。其中，表结点的定义被详细阐述，包括单元素结点的数据结构以及广义表的扩展线性链表存储结构。此外，还讨论了数组的定义、运算、顺序存储和特殊矩阵的压缩存储等概念。" 在数据结构中，表结点是一个重要的概念，它用于表示各种复杂数据结构的基础单元。在提供的描述中，表结点由三个主要部分组成：`tag`、`atom_hp`联合体和`tp`。`tag`是一个枚举类型，用来标识节点的类型，可以是`ATOM`（原子类型）或者`LIST`（列表类型）。`atom_hp`是一个联合体，用于存储不同类型的值，如果`tag`为`ATOM`，则存储`AtomType`的原子值；如果`tag`为`LIST`，则存储一个指向其他节点的指针`hp`。`tp`是一个指针，通常用于指向下一个表结点，形成链式结构。 广义表是数组和线性表的扩展，它可以包含原子数据和子表。在第5章中，提到了广义表的扩展线性链表存储结构，这种结构允许每个节点不仅存储一个元素，还可以存储一个子表。当`tag`为0时，表示当前节点存储的是一个原子，而`tag`为1时，则表示当前节点包含一个子表的头指针`hp`，`tp`则继续指向下一个节点。 数组是数据结构的基本形式，它是由固定数量的元素集合构成的。在5.1节中，数组被定义为具有固定维数的数据结构，其元素可以通过多个下标来定位。数组的抽象数据类型定义包括数据对象D，其中每个元素`aj1j2…jn`都属于一个称为`ElementSet`的集合。数据关系R定义了数组中元素间的关系，如获取和设置值的操作。数组的特点是不考虑插入和删除操作，因为它们通常涉及大量的数据移动。数组可以按行优先或列优先顺序存储，例如，二维数组的元素可以通过行索引和列索引计算其在连续存储空间中的位置。 5.2节探讨了数组的顺序存储和实现，特别是以行序为主序的方式。在顺序存储中，二维数组的元素按照行优先的顺序存储在内存中，通过一个公式可以计算出任意元素的存储位置。例如，元素`ai,j`的存储位置可以用基地址加上传递偏移量来确定。 5.3节涉及特殊矩阵的压缩存储，这是针对某些特定矩阵（如对角矩阵、三角形矩阵等）的一种节省存储空间的方法。 5.4节则是关于广义表的进一步讨论，但没有提供具体细节。 这份资料提供了关于数据结构核心概念——数组和广义表的深入理解，涵盖了它们的定义、存储结构以及相关运算。对于学习和理解数据结构的读者来说，这些内容是不可或缺的。