数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中，数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表，在算法与应用中扮演着重要的角色。
无论你是初学者还是进阶者，本文将为你提供简单易懂、实用可行的知识点，帮助你更好地掌握数组和广义表在数据结构和算法中的重要性，进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。
目录
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
广义表的定义
广义表的存储结构
数组的定义
数组是一组偶对(下标值，数据元素值)的集合。在数组中对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。
数组是由n(n>1)个具有相同数据类型的数据元素
组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。数组具有以下特点：
1）数组中的数据元素具有相同数据类型
2）数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。
3）数组中的数据元素个数是固定的。
数组的抽象数据类型定义：
由上述定义知，n维数组中有个数据元素，每个数据元素都受到n维关系的约束。
数组的顺序表示和实现
数组一般不做插入和删除操作，也就是说数组一旦建立，结构中的元素的个数和元素间的关系就不再发生变化。因此一般都是采用顺序存储的方法来表示数组。
计算机的内存结构是一堆(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。
二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。
二维数组的两种存储方式（以行序为主、以列序为主）：
举个例子：
矩阵的压缩存储
在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维矩阵。这样可以对其元素进行随机存取，各种矩阵运算也非常简单。
对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。所以要对这类矩阵进行压缩存储。
注意：多个相同的非零元素只分配一个存储空间；零元素不分配空间。
接下来我们要掌握 特殊矩阵 与 稀疏矩阵 的压缩存储方式。
广义表的定义
广义表是线性表的推广和扩充，在人工智能领域中应用十分广泛。我们把线性表定义为n(n0)个元素
的有穷序列，该序列中的所有元素具有相同的数据类型且只能是原子项(所谓原子项可以是一个数或一个结构，是指结构上不可再分的。)若放松对元素的这种限制，容许它们具有其自身结构，就产生了广义表的概念。
广义表(Lists，又称为列表)：是由n(n0)个元素组成的有穷序列：LS=(
)
广义表的存储结构
由于广义表中的数据元素具有不同的结构，通常用链式存储结构表示，每个数据元素用一个结点表示。因此，广义表中就有两类结点：
一类是表结点：用来表示广义表项，由标志域，表头指针域，表尾指针域组成
一类是原子结点：用来表示原子项，由标志域，原子的值域组成。
只要广义表非空，都是由表头和表尾组成。即一个确定的表头和表尾就唯一确定一个广义表。
什么是广义表？请简述广义表与线性表的区别？
广义表（Generalized List）是一种扩展了线性表的数据结构，它允许元素既可以是单值，也可以是子表。广义表通过递归方式定义，可以包含任意嵌套层级的子表，从而形成一个更加复杂和有层次结构的数据集合。
与广义表相对应的是线性表（Linear List），线性表仅包含单值元素，每个元素都有一个后继元素，形成一个线性结构。线性表是最简单和最常见的数据结构之一，例如数组就是线性表的一种实现。
广义表与线性表的区别主要有以下几点：
1. 元素类型：线性表的元素只能是单值，而广义表的元素可以既是单值，也可以是子表。这使得广义表能够表示更加复杂和有层次结构的数据关系。
2. 结构特点：线性表是一种线性结构，每个元素都有唯一的后继元素，形成了一个简单的序列。而广义表则具有更加复杂的层次结构，可以包含任意嵌套层级的子表，形成了一个树状结构。
3. 操作灵活性：由于广义表具有更复杂的结构，因此在操作和处理数据时，广义表比线性表更加灵活。广义表可以使用递归的方式进行遍历和操作，可以处理各种复杂的数据关系，而线性表则相对简单。
综上所述，广义表是一种扩展了线性表的数据结构，允许元素既可以是单值，也可以是子表。广义表具有更加复杂的层次结构和操作灵活性，可以更好地表示和处理各种复杂的数据关系。
一个广义表是(a,(a,b),d,e,(a,(i,j),k))，请画出该广义表的链式存储结构：
+---+ +---+ +---+ +---+| a |---+ | |---+ | d |---+ | e |+---+ | +---+ | +---+ | +---+| | || +---+ | +---+ |+---->| a | +---->| b | || +---+ | +---+ || | || +---+ | |+---->| i | +-------------++---+|||| +---++---->| j |+---+||||| +---++---->| k |+---+
