②链接存储方法 在链接存储方法中,逻辑上相邻的结点在物理位置上未必相邻,结点间的逻辑关系是由附加的指针字段表示的。* E9 |' e# {* \- K) [
③索引存储方法 该方法通常是在存储结点信息的同时,还建立一个附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址)。关键字是能唯一标识一个结点的那些数据项。) P, p) l; B, G
④散列存储方法 在散列存储方法中,结点的存储地址是根据结点的关键字值直接计算出来的。上述四种基本的存储方法也可以组合起来对数据结构进行存储映象。
; ~. h# w6 Y, |- V# i2 _3 ?(3)数据的运算
! w2 g4 M* c3 f数据的运算定义在数据的逻辑结构之上,每种逻辑结构都有一个运算的集合。常用的运算有:查找、插入、删除、更新、排序等。显然,对数据运算的具体实现方法只有在确定了存储结构之后才能加以考虑。
0 }! S' Y4 O; Q5 ?2.算法
7 L7 S: i5 T9 e9 }, o(1)算法及其特征
0 W" w+ O8 G1 n# [) \2 K G8 _/ j, ~简单地说,一个算法就是一种解题方法,更严格地说,算法是由若干条指令组成的有穷序列,它必须具有以下特征:8 X% w$ |3 ^7 F, U! H+ D5 t$ l) ?
①有穷性 一个算法必须在执行有穷步后结束。0 o4 p! ]' p% C! i: a, u j
②确定性 算法的每一步必须是确切地定义的,无二义性。
6 R( Q2 n" i5 f* |③可行性 算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷次运算后完成。
& s; }- m% y7 D* L! R6 Y2 X④输入 一个算法具有0个或多个输入的外界量,它们是算法开始前对算法最初给出的量。
$ e6 |4 d# P, Z* _⑤输出 一个算法至少产生一个输出,它们是与输入有某种关系的量。
1 q$ N& B" ~5 S& i5 E( D) W算法的含义与程序十分相似,但二者又有区别。一个程序不一定满足有穷性,操作系统就是如此,只要整个系统不被破坏,操作系统就永远不会停止,所以操作系统程序不是一个算法。另外,程序中的指令必须是机器可以执行的,而算法中的指令则无此限制。但是,一个算法如果用机器可执行的语言书写,则它就是一个程序。 R" h+ o c# ]4 X0 U& f- |( c# d, c6 R
对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。
! `- A* K1 s1 }) }# b3 |(2)算法的分析; e8 ~8 j6 F- g' Q, q
求解同一个问题可以有多种不同的算法,评价一个算法的优劣除了正确性和简明性外,主要考虑两点:一是执行算法所耗费的时间,二是执行算法所耗费的存储空间,特别是辅助存储空间的耗费。就这两者而言,前者显得比后者更为重要,在数据结构中往往更注重对算法执行时间的分析。
) o6 P1 M7 N2 y; u F1 c* c. L* \一个算法所耗费的时间是该算法中每条语句的执行时间之和,而每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间,则一个算法的时间耗费就是该算法中所有语句的频度之和。 |