数组与广义表：稀疏矩阵相乘及压缩存储

"本资料主要讲解了数据结构课程中的第五章——数组和广义表，特别是稀疏矩阵的相乘过程以及相关数据结构的实现。课程涵盖了数组的定义、顺序表示与实现、矩阵的压缩存储，以及广义表的定义、存储结构和递归算法。在稀疏矩阵相乘过程中，介绍了如何优化计算效率，通过压缩存储非零元素来减少计算量。" 在数据结构课程中，数组是一种基本的数据组织形式，它是由同一类型的元素构成的有序集合。数组的定义包括一组下标，每个下标都有特定的取值范围，表示元素在数组中的位置。例如，一维数组是一个线性表，元素之间通过下标顺序关联。二维数组可以看作是线性表的嵌套，可以按行或列展开。在C语言中，可以使用typedef定义二维数组类型，将其视作一维数组的数组。 数组的顺序表示是指在内存中连续存储数组的所有元素。对于二维数组，有两种常见的存储方式：以列序为主序和以行序为主序。列序存储方式是将数组的第一列元素连续存储，然后是第二列，以此类推；行序存储方式则是先存储第一行，然后是第二行，依此类推。这两种方式在不同的编程语言中应用广泛，例如FORTRAN倾向于列序，而BASIC、PASCAL和C语言则常用行序。 在处理稀疏矩阵时，如果矩阵大部分元素为零，直接使用常规的二维数组表示会浪费大量存储空间。因此，通常采用压缩存储的方式，只存储非零元素。在稀疏矩阵相乘过程中，首先初始化，然后对非零矩阵进行逐行处理。对于每一行，计算积并存储到累加器中，再将非零元素压缩存储到结果矩阵中。这种做法可以显著减少运算量，复杂度为O(M.mu×N.nu+M.tu×N.tu/N.mu)，其中M.mu和N.nu分别是矩阵M和N的行数，M.tu和N.tu分别是它们的非零元素数。 此外，课程还涉及到了广义表的定义和存储结构。广义表是一种可以包含子表的表，它可以表示复杂的结构。广义表的存储通常采用链式存储结构，以便于处理不同长度的子表。同时，广义表的递归算法是其处理中的一个重要部分，用于解决与广义表结构相关的各种问题。 总结来说，这个资料详细地介绍了数组和广义表在数据结构中的应用，包括它们的定义、存储方式、特殊结构如稀疏矩阵的处理方法，以及与之相关的算法设计。这些内容对于理解和掌握数据结构的基础知识至关重要，同时也为解决实际问题提供了理论基础。