|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
|
|
|
|
数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
|
|
|
|
|
|
|
|
（2）给定一组下标，修改相应的数据元素中某个数据项的值。
|
|
|
|
|
|
一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
|
|
|
|
由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
|
|
|
|
设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
|
|
|
|
Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
|
|
|
|
|
|
Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
算法（algorithm）就是解决特定问题的方法。描述一个算法可以采用文字描述，也可以采用传统流程图、N-S图或PAD图等。作为一个算法应该具备以下5个特性：
|
|
|
|
|
|
.确定性。算法的每一步都应该具有确切的含义，没有二义性。
|
|
|
|
|
|
|
|
.输出。一个算法执行结束后至少要有一个输出量，表示算法对输入量进行运算和处理的结果。
|
|
|
|
注意，算法和程序是有区别的——程序未必能满足有穷性。在本书中，只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。
|
|
|
|
算法可以借助各种工具描述出来。一个算法可以是用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如流程图、Pascal语言、C语言、伪代码或决策表等。下面以从n个元素中查找最大值为例，来讲解用流程图和伪代码这两种常见方法对算法的不同描述：
|
|
|
|
|
|
从n个整数元素中查找出最大值，若用流程图描述如下图所示。
|
|
|
|
|
|
|
|
|
|
除了可以用流程图描述之外，还可以用伪代码来进行描述。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
