数据结构-对称矩阵的压缩存储

"这篇讲义来自清华大学的教材，主要讨论了数据结构中的压缩存储方法，特别是针对阶对称矩阵的存储。文中指出，可以通过特定的公式计算矩阵元素aij在压缩存储序列sa[k]中的位置，即LOC(aij)可以通过 LOC(sa[0]) + k*d 计算得出，其中k由下标关系I*(I+1)/2+J给出。这种方法允许快速查找和定位矩阵元素，同时展示了如何将矩阵的对称特性利用于节省存储空间。讲义还提到了数据结构的基本概念，强调数据结构是研究数据的逻辑结构、物理结构及其运算的重要学科，并通过多个实例说明了数据结构在实际问题解决中的关键作用。" 在这篇讲义中，主要涉及以下知识点： 1. **数据结构**：数据结构是计算机科学中的核心概念，它研究数据如何组织、存储和操作，以便更有效地执行算法。数据结构包括逻辑结构（如线性结构、树形结构、图形结构等）和物理结构（如顺序存储、链式存储等）。 2. **压缩存储**：在阶对称矩阵的例子中，通过特定的公式实现了矩阵的压缩存储。这种存储方式减少了存储需求，因为对称矩阵的下半部分可以共享上半部分的信息。 3. **阶对称矩阵**：一种特殊的矩阵，其中对角线以下的元素与对角线以上的对应元素相等。在压缩存储中，这种对称性被用来减少存储空间。 4. **地址计算公式**：LOC(aij) = LOC(sa[0]) + k*d，其中k = I*(I+1)/2 + J，用于计算矩阵元素aij在压缩序列sa[k]中的位置。这个公式适用于所有的i, j，使得可以快速从下标转换到存储位置。 5. **算法与效率**：讲义中提到算法是解决问题的步骤，设计算法时需要考虑其效率和存储空间的需求。算法效率通常通过时间复杂性和空间复杂性来衡量。 6. **抽象数据类型**：是数据结构的一个扩展，它不仅定义了数据的组织方式，还包括操作这些数据的函数集合，提供了更高级别的数据操作接口。 7. **实例应用**：讲义通过电话号码查询系统、图书馆书目检索系统、教师资料档案管理和多叉路口交通灯管理等例子，说明数据结构在解决实际问题中的重要性。 通过对这些概念的理解，读者可以更好地掌握如何设计和分析数据结构，以及如何根据问题的特性选择合适的数据结构以提高算法效率。在实际编程和系统设计中，理解并熟练运用这些知识至关重要。