1.概论

数据结构

好的算法必须建立在研究数据的特性及数据之间存在的关系的基础之上.

数据结构一般包括三方面内容:

1. 数据之间的逻辑 (或抽象) 关系, 即逻辑结构. 包括:

   • 线性结构 (如线性表, 栈, 队列).
   • 非线性结构 (如树, 图).

2. 数据元素及其关系在计算机内的存储方式, 即存储结构(物理结构):

   • 顺序存储: 逻辑上相邻的点在物理位置上也相邻. 通常用于线性结构数据, 但非 线性结构也可以通过线性化方法用顺序存储.
   • 链接存储: 元素间的关系用附加的指针域表示, 物理位置不一定连续.
   • 索引存储: 存储元素的同时, 附加建立一份索引表.
   • 散列存储: 根据元素关键字直接计算出元素的存储地址.

3. 数据的运算, 如增删改查等:

   运算的具体实现是在存储结构上进行的, 因此在逻辑结构上定义的运算, 只要给出运算 的功能是 "做什么",至于 "怎么做" 等实现细节, 只有待确定了存储结构之后才能考虑.

   对于不同问题, 需要的运算可能不同.

   复杂的运算, 可用基本运算的组合来实现.

数据结构 vs. 数据类型 vs. 抽象数据类型 (ADT):

• 数据类型可看作是程序设计语言中已实现的数据结构.
• 抽象数据类型可看做是描述问题的模型, 它独立于具体实现, 等价于在数据的逻辑结构以 及在逻辑结构上定义的抽象操作.

算法

算法是对问题求解步骤的描述. 必须满足以下五个准则:

1. 给定输入.
2. 至少有一个或多个输出.
3. 有穷: 每个步骤的执行次数必须有限, 且在有穷时间内完成.
4. 确定: 每个步骤的含义明确无二义.
5. 可行: 每个步骤都可以通过有限次的基本运算来实现.

算法不依赖于计算机程序语言, 可用自然语言, 程序语言, 约定的符号语言等描述.

对算法的评价和分析包括:

• 最主要的是时间复杂性, 即算法耗费的时间.
• 空间复杂性, 即算法耗费的存储空间.
• 可读性和可操作性.