数据结构课件：广义表与子表的组合

"这篇资料主要讨论了如何使用子表组合成广义表，涉及数据结构中的数组、稀疏矩阵的压缩存储以及广义表的类型定义、表示方法和操作。内容涵盖二维数组的定义、顺序表示与实现，特别是以行序和列序为主序的存储映射方式。" 在数据结构中，广义表是一种非常重要的抽象数据类型，它能够表示各种复杂的数据结构，包括线性结构和非线性结构。广义表是由子表组成的，每个子表可以是单个元素或者另一个广义表。组合广义表的关键在于理解其内部的存储结构。 首先，我们要理解广义表的存储结构。通常，广义表的头部指向一个元素或者另一个广义表，这个元素可以是原子（无法再分的元素）或者是另一个广义表的头指针。这样的结构形成了广义表的递归特性。例如，如果一个广义表的第一个元素是一个子表，那么这个子表的头指针会被存放在广义表的头指针中。 接着，我们来看看数组的类型定义。数组是一种具有固定大小和特定数据类型的集合，其中每个元素都有一个唯一的索引。二维数组可以看作是由多个一维数组构成的，它的数据对象是所有元素aij，其中0≤i≤b1-1,0≤j≤b2-1。数组的基本操作包括初始化、销毁、获取和设置元素的值。 在顺序表示和实现数组时，有以行序为主序和以列序为主序两种方式。以行序为主序的方式，数组中的元素按照行优先的顺序存储，这意味着同一行内的元素相邻，对于一个m行n列的数组，元素ai,j的存储位置可以通过公式LOC(i,j)=LOC(0,0)+(n×i+j)×L计算。反之，以列序为主序则是按照列优先的顺序存储元素，公式变为LOC(i,j)=LOC(0,0)+(m×j+i)×L。 在处理稀疏矩阵时，如果矩阵大部分元素都是0，使用压缩存储可以节省大量空间。这种技术通常只存储非零元素，并且用三元组来表示每个非零元素的位置和值。 至于广义表的操作，通常会使用递归函数来实现，因为广义表的结构允许自身包含自身。这些操作可能包括创建广义表、插入元素、删除元素、查找元素以及打印广义表等。 广义表是通过组合子表来构建的复杂数据结构，其核心在于理解递归和链式存储的概念。数组作为基本的数据结构，其顺序表示和实现方式对于理解和处理广义表至关重要。无论是二维数组还是稀疏矩阵，它们的存储和操作都需要深入理解内存布局和数据访问的逻辑。