《严蔚敏数据结构C语言版描述》

一、数据,数据元素（数据项),数据对象

  • 数据是对客观事物的符号表示；
  • 数据元素是数据的基本单位，作为一个整体进行考虑和处理，复杂的数据元素可以由若干数据项组成，数据项是数据不可分割的最小的单位；
  • 数据对象是性质相同的数据元素的集合

二、数据元素之间的关系称之为结构

数据结构常见的有4类基本结构:

  1. 集合，无关系
  2. 线性结构，一对一
  3. 树形结构，一对多
  4. 图或网状结构，多对多
    数据结构就是数据元素的集合+元素关系的集合
    数据结构是逻辑结构

三、数据结构在计算机中的表示称为数据的物理结构或存储结构

  • 位-计算机中表示信息的最小单位
  • 位串-计算机中表示信息或编码的若干位组合形式,数据元素，如字节(8bit),字(32bit)
  • 数据域-数据元素由各个数据项组成，里面的子位串

四、数据元素之间的关系在计算机中有两种不同的存储结构

  1. 顺序存储结构，通过下标，连续地址空间，随机访问
  2. 链式存储结构，通过地址指针，地址不连续，顺序访问
    任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构

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

  • 数据类型分成两类：
    1. 原子类型，值不可分解,例如:基本类型(整型，实型，字符型，枚举型),指针类型,空类型
    2. 结构类型, 值是可分解的，若干分量组成
  • 抽象数据类型是指一个数学模型及定义在该模型上的一组操作的集合
  • 一个含抽象数据类型的软件模块通常应包含定义，表示和实现3部分。
  • 抽象数据类型的定义由一个值域和定义在改值域上的一组操作组成。
  • 根据值的不同特性，可细分为下列三种数据类型:
    1. 原子类型
    2. 固定聚合类型
    3. 可变聚合类型
ADT 抽象数据类型名 {
    数据对象，
    数据关系，
    数据操作
} ADT 抽象数据类型名

def 基本操作名(参数表){
    初始条件:<初始条件描述>
    操作步骤:<操作逻辑描述>
    操作结果:<操作结果描述>
}

六、算法是对特定问题求解步骤的描述，是指令的有限序列，每一条指令表示一个或多个操作。

  • 算法的5个重要特性：
    1. 有穷性：有限步骤，有限时间
    2. 确定性：相同的输入必定是相同的输出
    3. 可行性：基本运算执行有限次完成
    4. 输入: 0个或多个输入
    5. 输出: 1个或多个输出
  • 算法设计的要求：
    1. 正确性
    2. 可读性
    3. 健状性
    4. 效率与低存储量的需求
  • 算法的度量:
    1. 时间复杂度: O(log n),O(1),O(n),O(n2),O(2n),对数阶，常数阶，线性阶，平方阶，指数阶
    2. 空间复杂度: 内存空间消耗