概念

程序 = 算法 + 数据结构

数据结构

数据(data) is any sequence of one or more symbols. 如：数字、字符、声音、图象、图形等。

数据元素是数据的基本单位。

数据项是数据的不可分割的最小单位。

结论：数据元素由若干个数据项构成

数据对象是由性质相同(类型相同)的数据元素组成的集合。既可以是有限集也可以是无限集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构由三部分组成：逻辑结构，存储结构和数据的运算。

结论：逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关。

逻辑结构：

  • 线性结构
    • 线性表
    • 栈
    • 队列
    • 数组
    • 串
  • 非线性结构
    • 树
    • 图

存储结构（存储表示,物理结构,物理表示）: 顺序存储，链式存储，索引存储，散列存储（hash）

数据类型是一个值的集合和定义在这个值上的一组操作的总称。

  • 原子类型(如：int,char,float等)
  • 结构类型(如：数组,struct等

抽象数据类型(Abstract Data Type —— ADT)与计算机的实现无关的数据类型。如c++中的类便属于ADT。

形如：

ADT 抽象数据类型名 { 
    1.数据对象；
    2.数据关系:一个或多个关系；
    3.一组基本操作/运算
} ADT 抽象数据类型名

算法

五个重要特性：

  1. 有穷性：一个算法必须总是在执行有穷步后结束，且每一步都是在有穷时间内完成
  2. 确定性：无二义性。
  3. 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4. 输入（>= 0个）
  5. 输出（>=1个）

好算法的目标：

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 效率和低存储量