《大话数据结构》

CH1-2：数据结构基础与算法

1 基本概念

数据项：最小单位

数据元素（记录）：由若干数据项组成

数据对象：由性质相同的数据元素构成的集合，是数据的子集

数据

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

2 结构

逻辑结构：

集合（相互独立）、线性结构（1:1）、树形结构（1:N或N:1）、图形结构（N:N）

物理结构：

顺序存储结构、链式存储结构

3 抽象数据类型ADT

4 算法

算法：解决特定问题求解步骤的描述，表现为指令的有限序列，并且每条指令表示一个或多个操作。

特性：输入输出（可无输入，必须输出）；

          有穷性（步骤有限，时间可接受）；

          确定性（无二义性）；

          可行性（可通过有限次数完成）。

算法设计要求：

           正确性、可读性、健壮性、时间效率和存储量、

算法效率度量方法：

            事后统计方法、事前估算方法

算法时间复杂度：

    O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

算法空间复杂度

吃

CH3-5：线性表

栈、队列、串

CH6：树