数组和广义表存储结构解析：压缩矩阵与递归算法

"用两个一维数组分别存储行链表的头指针和数据结构课程中的第五章 数组和广义表PPT" 在数据结构课程中，数组是一种基础且重要的数据组织形式，它是由相同类型的数据元素按照固定顺序排列的集合。在本课程的第五章“数组和广义表”中，主要讲解了数组的定义、顺序表示与实现、以及压缩存储，同时也涵盖了广义表的相关概念和存储结构。 5.1 数组的定义 数组是由一组具有相同类型的数据元素构成的集合，每个元素都有一个唯一的下标来标识其位置。在一维数组中，下标通常是从1到数组长度n。对于二维数组，例如一个m×n的矩阵，它包含了m行n列的元素，每个元素可以通过两个下标（行下标和列下标）来定位，比如(a_{ij})，其中1≤i≤m，1≤j≤n。二维数组可以看作是定长的线性表，每个元素自身也是一个线性表。 5.2 数组的顺序表示和实现 数组的存储结构通常是顺序存储，这意味着数组的元素在内存中是连续存放的。以二维数组为例，有两种主要的存储方式：以列序为主序和以行序为主序。以列序为主序时，内存中的元素按照列优先的方式存储；以行序为主序则是按照行优先的方式存储。在编程语言如FORTRAN中，通常采用列序存储，而在BASIC、PL/1、COBOL、PASCAL和C语言中，行序存储更常见。数组的地址计算可以通过简单的偏移量加法实现，例如，对于行序存储，元素a_{ij}的地址LOC(a_{ij})等于首元素a_{11}的地址LOC(A1)加上(i-1)*n+j-1的偏移量。 5.3 矩阵的压缩存储 在处理特定类型的矩阵，如稀疏矩阵（大部分元素为零）时，可以使用压缩存储以节省空间。常见的压缩方法有三元组存储和十字链表。例如，给定的三元组线性表M=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))表示的就是一个稀疏矩阵，只存储非零元素的行号、列号和值。 5.4 广义表的定义 广义表是一种更通用的数据结构，它可以包含其他子表，不仅限于单一的数据元素。广义表可以是空表，也可以是单元素或由多个子表组成的表。 5.5 广义表的存储结构 广义表的存储通常采用链式存储，每个节点包含一个元素（可以是原子或子表），并链接下一个节点。广义表的递归结构使其在表示复杂数据结构时非常有用。 5.7 广义表的递归算法 在处理广义表时，递归算法是常用的方法，因为它能有效地反映广义表的结构特性。递归算法可用于广义表的插入、删除、查找等操作。 总结，本课程的第五章深入探讨了数组和广义表的各个方面，从基本的定义、存储方式到特殊情况下如稀疏矩阵的压缩存储，再到抽象数据结构广义表的定义和处理，为理解和实现复杂数据结构奠定了坚实的基础。