834 数据结构（自用）
一.绪论
1.数据结构基本概念
1.基本术语:
数据元素：数据基本单位。
数据项：众多数据项组成一个数据元素，不可分割的最小单位。
数据对象：具有相同性质的数据元素集合。
数据结构：相互之间存在一种或多种特定关系的数据元素集合。
2.数据类型：一个值的集合和定义在此集合上的一组操作的总和。
原子类型：其值不可再分的数据类型（bool，int...）
结构类型：其值可以在分解为若干成分的数据类型（结构体）
抽象数据结构（ADT）：只关心逻辑结构
2.数据结构三要素（重点）
1.数据的逻辑结构分类：（重点，图背过）
线性结构：一对一。
树形结构：一对多。
网状结构：多对多。
2.数据的物理结构：
顺序结构:逻辑地址相邻元素存储在的物理地址相邻的位置。（数组）
链式结构:逻辑位置相邻物理地址用指针链接在一起。（链表）
索引结构：创立一张索引表，其中每项称为索引项，索引项形式关键字、地址。
散列结构：哈希存储。（后面会解释）
关于上述四种物理结构理解点：
（1 顺序存储各元素物理上必须连续，非顺序存储各元素物理上可以不连续。
（2 数据的存储结构会影响存储空间分配的方便程度。
（3 数据的存储结构会影响数据的运算速度。
3.数据运算：
数据运算的定义是针对逻辑结构，指出运算功能；数据运算的实现是针对存储结构，指出运算的具体步骤。
3.算法及算法评价
1.基础概念
算法五大特征：有穷性，确定性，可行性，输入，输出。
算法四个目标：正确性，可读性，健壮性，高效率和低存储量需求。
2.算法度量
时间复杂度：(考试会考常见的插入和排序算法的时间复杂度，只需要背过即可)
最好，最坏，平均。（一般衡量算法看最坏）
一般看最高阶来确定。
时间复杂度T(n)按数量级递增顺序为：
| 常数阶 | 对数阶 | 线性阶 | 线性对数阶 | 平方阶 | 立方阶 | K次方阶 | 指数阶 | 阶乘阶 |
|
| O(1) | O(log2n) | O(n) | O(nlog2n) | O(n2) | O(n3) | O(nk) | O(2n) | O(n！) | O(n的n次方) |
空间复杂度：
只分析辅助空间。
O(1)表示辅助空间为常量。
空间复杂度T(n)按数量级递增顺序与时间复杂度相同。