一、数据结构

1.1 定义

数据项——>数据元素——>数据对象——>数据

数据对象+结构——>数据结构

数据结构包括以下几个方面：

1.数据的逻辑结构（数学模型）

2.数据的存储结构（物理结构）

3.数据的运算

所以数据结构是带结构的数据元素的集合

数据类型是一个值的集合及其一组操作

1.2 逻辑结构类型

集合

线性结构一对一

树形结构一对多

图形结构多对多

堆结构

1.3 存储结构类型

1.内存存储

（1）顺序存储结构（例如数组）：优点--节省存储空间，因为结点间的逻辑关系不占用额外的存储空间，不占用空间不代表没有

缺点--不便于修改

（2）链式存储结构（例如指针）：优点--便于修改
缺点--存储空间利用率低，存了逻辑关系；不能对结点随机存取

2.外存存储

（3）索引存储结构：建立附加的索引表。优点--便于查找和修改

缺点--存储空间利用率低，因为增加了索引表

（4）哈希存储结构：给一个结点的关键字，使用哈希函数算出一个值作为该结点的存储地址。优点--查找速度快。缺点--与前三种不同的是只存储结点数据，不存储结点间的逻辑关系

二、算法

2.1 定义

数据元素对应的运算有逻辑结构上的运算功能和存储结构上的运算实现，把存储结构上的运算实现称为算法。

算法五要素：有穷性、确定性、可行性、有输入、有输出

2.2 算法效率分析（时间复杂度）

$T(n)=O(f(n))$

n为问题规模，T（n）为基本运算次数，只用看最高阶，忽略低阶项和常系数

例题：

注：有时很难直接计算基本运算次数，可采用最坏时间复杂度或平均时间复杂度

【定义】设一个算法的输入规模为n， $D_{n}$ 是所有输入的集合，任一输入 $I\epsilon D_{n}$ ,P(I)是I出现的频率，有 $\sum_{I\epsilon D_{n} }^n P(I)=1$ ,T(I)是算法在输入I下所执行的基本运算次数，则该算法的期望复杂度为

$E（n）=\sum_{I\epsilon D_{n} }^n {(P(I)*T(I))}$

例题：

2.2 算法存储空间分析（空间复杂度）

对一个算法在运行过程中临时占用的存储空间大小的度量，记为：

$S(n)=O(g(n))$

基础定义