Chapter 01 引言

1. 数据结构¶

数据结构三要素:
- 逻辑结构
- 存储(物理)结构
- 运算

1.1 逻辑结构¶

逻辑结构是具体问题的 数学抽象, 反映事物 组成和逻辑关系.

用 一组数据(结点集合 \(K\)) 和数据间的 二元关系 (关系集合 \(R\)) 表示.

Tips

任何一个多元关系可以通过插入连接实体转化为二元关系

用 \(R\) 的性质来刻画数据结构的特点, 并进行分类

线性结构 (线性表, 如栈, 队列, 字符串等)
树形结构 (二叉树, Huffman树, 二叉检索树等)
图结构 (有向图, 无向图)

有如下关系:

\[ 图 \supseteq 树 \supseteq 二叉树 \supseteq 线性表 \]

1.1.1 线性结构¶

关系 \(r\) 有向, 满足全序性和单索性.
- 全序性: 任何两点可比较前后.
- 单索性: 每一个结点存在唯一前驱后继 (除头尾结点)

1.1.2 树形结构¶

每个结点有唯一前驱, 可有多个后继. (根节点无前驱)

1.1.3 图结构¶

对关系无任何约束.

总结: 树型结构和图型结构的基本区别是“每个结点是否仅仅属于一个直接前驱”. 而线性结构和树型结构的基本区别是“每个结点是否仅仅有一个直接后继”.

1.2 存储结构¶

也称物理结构, 是逻辑结构在计算机中的物理表示.

逻辑结点映射：对于每一个结点 \(j∈K\) 都对应一个唯一的存储区域 \(c∈M\).
逻辑关系映射：每一关系元组 \((j_1,j_2)∈r\), 映射为存储单元的地址顺序关系(或指针地址指向关系).

四种基本存储映射方法:
- 顺序
- 链接
- 索引
- 散列

1.2.1 顺序存储¶

结点按地址相邻关系顺序存储，结点间逻辑关系用存储单元的自然顺序关系来表达
数组是顺序存储法的具体实例

顺序存储是紧凑存储结构
- 紧凑指存储空间除存储有用数据外，不存储其他附加信息
- 存储密度：存储结构所存储‘有用数据’和该结构（包括附加信息）整个存储空间大小之比

Warning

二维数组在逻辑结构上是非线性结构, 在存储结构上是线性存储.

1.2.2 链接¶

利用 指针指向 表示两个结点的逻辑关系. (eg: 链表)

增删容易但定位困难.

1.2.3 索引方法¶

通过结点的索引值映射到结点的存储地址

1.2.4 散列方法¶

将关键码映射到一个非负整数 \(z\).

2. 抽象数据类型(Abstract Data Type)¶

抽象数据类型是由 <数据对象，数据关系，数据操作> 三个不可分割的部分组成的三元组：

ADT抽象数据类型名{

数据对象D: <数据对象的定义>

数据关系S: <数据关系的定义>

数据操作P: <基本操作的定义>

} ADT抽象数据类型名

C++
template <class T>   // 栈的元素类型为 T

class Stack {

public:                         // 栈的运算集

  void clear();  // 变为空栈

  bool push(const T item);   // item入栈，成功返回真，否则假

  bool pop(T & item);  // 弹栈顶，成功返回真，否则返回假

  bool top(T& item);            // 读栈顶但不弹出，成功真，否则假

  bool isEmpty();   // 若栈已空返回真

  bool isFull();    // 若栈已满返回真
  
};

3. 算法¶

算法的性质:
- 通用性
- 有效性
- 确定性
- 有穷性

4. 算法分析¶

算法分析是对一个算法需要多少 计算时间 和 存储空间 作定量的分析.

主要分析在数据量很大的时候算法的渐进趋势.

一般以输入规模为 \(n\) 时所需的基本操作数 \(f(n)\) 来描述时间效率.

4.1 大O表示法¶

大O表示法的定义

若存在正数 \(c\) 和 \(n_0\), 使得对任意的 \(n\geq n_0\), 都有

\[ f(n)\leq cg(n) \]

则称 \(f(n) \in O(g(n))\).

Example

\[3n\in O(n)\]

\[100n+5 \in O(n^2)\]

\[n(n-1)/2 \in O(n^2)\]

大O表示法的性质

\[f(n) \in O(g(n)), \ g(n) \in O(h(n)) \Rightarrow f(n)\in O(h(n))\]

\[f(n)\in O(h(n)), g(n) \in O(h(n)) \Rightarrow f(n)+g(n) \in O(h(n))\]

4.2 Omega表示法¶

Omega表示法的定义

若存在正数 \(c\) 和 \(n_0\), 使得对任意的 \(n\geq n_0\), 都有

\[ f(n)\geq cg(n) \]

则称 \(f(n) \in \Omega(g(n))\).

Example

\[3n\in \Omega(n)\]

\[n^3 \in \Omega(n^2)\]

4.3 Theta表示法¶

Omega表示法的定义

若存在正数 \(c_1,c_2\) 和 \(n_0\), 使得对任意的 \(n\geq n_0\), 都有

\[ c_1g(n) \leq f(n)\leq c_2g(n) \]

则称 \(f(n) \in \Theta(g(n))\).