|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 >
|
被考次数：3次
被考频率：中频率
总体答错率：32%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：熟悉
相关知识点：31个
|
|
|
|
|
|
|
数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。数组可以看成是线性表的推广，数组的每个元素由一个值和一组下标确定，在数组中，对于每组有定义的下标都存在一个与之相对应的值；而线性表是有限结点的有序集合，若将其每个结点的序号看成下标，线性表就是一维数组（向量）；当数组为多维数组时，其对应线性表中的每个元素又是一个数据结构而已。数组使用时需要的内存空间远远大于普通变量的空间，所以按内存开辟空间的时机来划分数组，在程序编译时开辟内存区的数组称为静态数组，运行时根据需要开辟内存区的数组称做动态数组。简单来说，使用数值常量或符号常量定义下标的数组为静态数组，首先声明一个没有下标的数组名，然后在使用时再次声明数组的下标，称为动态数组。用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。
|
|
|
|
|
|
广义表是5.2节提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（即另一个线性表）。它是n≥0个元素a1, a2, …，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=（a1, a2, …，an），其中LS为广义表的名字，n为广义表的长度，每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。
|
|
|
|
|
|
（1）用LS=（a1， a2, …，an）形式，其中每一个ai为原子或广义表。
|
|
|
|
|
|
（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套。
|
|
|
|
|
|
|
|
（3）将广义表用树和图来描述，一个广义表的深度指的是该广义表展开后所含括号的层数。例如，A=（b，c）的深度为1，B=（A，d）的深度为2，C=（f，B,h）的深度为3；如下图所示。
|
|
|
|
|
|
|
|
由于广义表的元素类型不一定相同，因此，难以用顺序结构来存储表中的元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。广义表需要两种结构的结点，一种是表结点，表示列表；一种是原子节点，表示原子。一个表结点可以由标志域、指示表头的指针域和指示表尾的指针域组成；而原子结点由标志域和值域组成，如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
