数据结构：数组与广义表——压缩存储与十字链表

"十字链表存储表示-数据结构课程中的第五章 数组和广义表PPT" 在数据结构课程中，数组和广义表是重要的概念，它们在计算机科学中有着广泛的应用。第五章主要涵盖了数组的定义、顺序表示与实现、矩阵的压缩存储，以及广义表的相关内容。 5.1 数组的定义 数组是一种数据结构，其中的元素通过一组有序的下标来访问。在一维数组中，元素间的关系由下标顺序决定，所有元素通常具有相同的类型。例如，一个二维数组可以视为由多个一维数组（行）组成的，每个元素本身也包含一个一维数组（列）。数组的定义可以通过下标范围1≤ji≤bi来描述，其中bi表示第i维的长度。对于二维数组，可以按照行或列进行展开，形成不同的线性表。 5.2 数组的顺序表示和实现 数组在内存中通常采用顺序存储，这意味着数组元素在物理存储上是连续的。二维数组有两种常见的存储方式：以列序为主序和以行序为主序。以列序为主序时，数组元素按列存储，相邻的元素在内存中也是相邻的；而以行序为主序则按照行存储，优先考虑行的连续性。在C语言中，数组的地址计算通常是线性的，比如LOC(A[i][j]) = LOC(A[0][0]) + (i * n + j) * sizeof(ElemType)，其中n是每行的元素数量。 5.3 矩阵的压缩存储 在处理稀疏矩阵（非零元素较少）时，为了节省空间，可以采用压缩存储，例如十字链表存储表示。十字链表主要用于存储稀疏矩阵，它只存储非零元素，并通过两个指针（right和down）分别指向行链表和列链表的下一个非零元素。结构体OLNode包含了非零元的行和列下标、元素值以及这两个链域指针。通过这种方式，可以有效地表示和操作稀疏矩阵，提高效率。 5.4 广义表的定义 广义表是一种可以容纳不同类型的元素（包括其他表）的表，它是一种递归数据结构。它可以表示复杂的组合数据，例如树形结构或图。 5.5 广义表的存储结构 广义表的存储结构通常采用链式存储，以便能容纳不同类型的数据。在链式存储的广义表中，每个元素可以是单个原子或者另一个广义表的引用，这种结构允许表嵌套。 5.7 广义表的递归算法 广义表的处理经常涉及到递归算法，例如表的复制、插入、删除和查找等操作。递归算法能够很好地处理广义表的层次结构，使得代码简洁且易于理解。 总结来说，这个数据结构课程的第五章深入讲解了数组的定义、存储方式以及在特殊情况下如何优化存储（如稀疏矩阵的十字链表存储），还介绍了广义表这一灵活的数据结构及其操作方法。这些知识对于理解和实现复杂数据结构的算法至关重要。