《算法与数据结构考研试题精析》笔记(5) - 数组与广义表

Published: September 26, 2020 by Authur Lee

数组

n维数组中，每个元素受着n个关系的约束。就其单个关系而言，这n个关系仍是线性关系。和线性表一样，所有数据元素都必须属于同一数据类型。

在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型；同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。(数组通常具有两种基本操作：查找和修改。)

稀疏矩阵一般的压缩存储方法有：三元组和十字链表。

稀疏矩阵在矩阵的非零元个数和位置在操作过程中变化不大时较有效。

【计算三元组所需字节】除了存储非零元所需的字节数之外，还要加上三元组表中行数、列数和总的非零元素个数所占的字节数。

【稀疏矩阵】非零元很少且没有分布规律的矩阵。

【广义表】零个或多个原子或子表组成的有限序列。

【原子与表的差别】原子是结构上不可再分的，可以是一个数或一个结构；而表的本质，就是广义表，因作为广义表的子表故而称为子表。为了区分原子和表，一般用大写字母表示表，用小写字母表示原子。

【表头、表尾】当广义表LS非空时，称第一个元素为广义表LS的表头，其余元素组成的表是广义表LS的表尾。

【广义表的深度】括号的重数

【广义表的长度】由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。

【正确选项】对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。

注意此处无穷大的是“长度”，和递归定义的A=(a,A)不是一个所指。A=(a,A)的长度为2，并非无穷大。

【广义表的存储】由于广义表中既可存储原子（不可再分的数据元素），也可以存储子表，因此很难使用顺序存储结构表示，通常情况下广义表结构采用链表实现。

使用顺序表实现广义表结构，不仅需要操作 n 维数组（例如 {1,{2,{3,4}}} 就需要使用三维数组存储），还会造成存储空间的浪费。

广义表的表尾总是一个广义表。

广义表可以是一个多层次的结构。

二维以上的数组其实是一种特殊的广义表。

【错误选项】广义表是线性表的推广，是一类线性数据结构。

广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。

设数组A[1..8,1..10]，数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存中，主内存字长为16位，那么

任一元素占48个二进制，而主内存字长为16，故而每个元素所占单元素为48/16=3个单位。