|
|
|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 数组和广义表 >
|
|
|
被考次数：2次
|
|
|
被考频率：
低频率
|
|
|
总体答错率：
34%
|
|
知识难度系数：
|
|
|
考试要求：
熟悉
|
|
|
相关知识点：2个
|
|
|
|
|
数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。数组可以看成是线性表的推广，数组的每个元素由一个值和一组下标确定，在数组中，对于每组有定义的下标都存在一个与之相对应的值；而线性表是有限结点的有序集合，若将其每个结点的序号看成下标，线性表就是一维数组（向量）；当数组为多维数组时，其对应线性表中的每个元素又是一个数据结构而已。数组使用时需要的内存空间远远大于普通变量的空间，所以按内存开辟空间的时机来划分数组，在程序编译时开辟内存区的数组称为静态数组，运行时根据需要开辟内存区的数组称做动态数组。简单来说，使用数值常量或符号常量定义下标的数组为静态数组，首先声明一个没有下标的数组名，然后在使用时再次声明数组的下标，称为动态数组。用C语言来描述数组如下：
|
|
|
|
|
|
由于数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，一般采用顺序存储结构表示数组。多维数组的顺序存储有两种形式：以列序为主序和以行序为主序。
|
|
|
|
|
|
行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……
|
|
|
|
在Basic语言、Pascal语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如下形式存放到内存：a00，a01,…a0 n-1, a10，all，…，a1 n-1, …，am-1 0, am-1 1,…，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。
|
|
|
|
因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。
|
|
|
|
|
|
由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其他元素的内存地址？可以将它们的地址排列看成是一个等差数列，假设每个元素占1个字节，元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij的前面有i行（0～i-1）共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的内存地址为LOC （a00），则aij的内存地址按等差数列计算为LOC （aij）=LOC（a00）+（i×n+j）×1。同理，三维数组Am×n×p按行优先存放的地址计算公式为：LOC （aijk）=LOC（a000）+（i×n×p+j×p+k）×1。
|
|
|
