2023年4月浙江自考《数据结构》串讲资料第五章

第五章　广义表

数组一般没有插入和删除操作，另外无论是几维数组，在机器里表示都是一维的，因此这里有一个按行优先存储还按列优先存储的这样的一个法则，要注意这问题。

在数组里，一般没有插入和删除运算，所以存好这些数据，就这样了，另外在数组这部分中，可以这样去理解它，它是一个复杂的非线性结构，因为这是针对于线性结构的每一个结点最多有一个直接前趋和最多有一个直接后继这样的特点而言的，因为数组，比如说二维数组每一个元素它可以有两个直接前趋，分别从行和列看。也可有两个直接后继，但是边上的和角上的又不同，因此比较复杂。多维的更复杂，但是也可以这样去理解，多维数组认为是向量的推广。

行优先就是最右侧下标变化最快，列优先就是最左侧下标变化最快。压缩存储就是对多个相同的非零元素只分配一个存储空间，对零元素不分配存储空间。使用压缩技术，存储一个稀疏矩阵，惟一目的仅仅是为了节省存储空间，在时间上是不合算的。

提醒大家，把顺序存储的位置、安排记住，行优先或者列优先，把有规律的特殊矩阵的压缩存储的方法记住，然后记住无规律的稀疏矩阵的三元组表存储方法，并且要知道，三元组表存储方法在时间上是不合算的，只是节省了空间。

广义表是把线性表里面每一个结点都必须是原子值的这样一个限制给突破了的表，就叫广义表。广义表也是就是说表中的每一个元素还可以是表，因此它也是一个非线性的。不但可以是表，而且可以是其自身。

广义表的括号表示和图形表示之间的转换，希望大家能够把握，一般来说括号表示它要用圆括号把广义表括起来，以逗号分隔他的元素，图形表示是一种形象化的括号表示。

例如：A是一个广义表，大写字母代表表，小写字母代表原子。

例如：取表头运算

下面看一个具体的例子：