空间数据结构复习（一）

先来说说考试大纲吧，根据老师给的重点，归纳成了下面12点：

1.数组的地址

2.广义表的存储结构

3.四种排序

4.算法的评价

5.AOV网络

6.最小代价生成树

7.树与二叉树的遍历

8.二进制编码与哈弗曼编码

9.二叉树的性质

10.数据结构的特点

11.稀疏矩阵概念及表示方法

12.正配算法

一. 重点的概念归纳

1.数组地址：

一维数组： 常用于顺序存储的线性数据结构中，数组通常采用顺序表示，即数组中的元素按一定的顺序存放在一个连续的存储区域，一个一维数组可以直接映射到一维的存储空间，由于数组元素具有相同的类型，每个元素占有相同的存储单元，因此根据数组元素的下标可以方便的计算元素的存放地址。

二维数组： 下标是二维的，可以理解成，二维数组是每个元素都是一维数组的数组。将一个二维数组映射到一维的存储空间一般有两种排序：行优先顺序和列优先顺序。其中大多数语言是按行优先顺序存储二维数组元素的，我们这本书中用到的c语言就是这样。

对于二维数组，例如存在一个二维数组a，那么我们此时把Loc(a[0][0])叫做该二维数组的基地址，即第一行第一列这个元素指针所指向的地址。因为数据类型相同，所以二维数组中每一个元素占有相同的存储空间k个存储单元，那么对这样的数组存取任何一个元素所需的时间是相同的。我们称具有这一存取特点的存储结构为随机存取的存储结构（random access storage structure）。

上述内容比较容易考到概念填空,所以个别重点不要一扫而过，而是要背，还会考到类似于下面这道例题：

已知A(M*N)，和基地址Loc(A[0][0])以及其中两个数组元素的地址例如Loc(A[2][3]),Loc(A[4][6]),让我们求解另一个未知的Loc(A[3][2])

那么我们的解法就比较容易了，先求每个元素所占的存储单元K再求出M,N这样题目想要哪一个元素的地址我们都能很容易解出。