Data Structure Notes
Author : "ebxeax"
Version : 1.0
Refresh Date 2020.11.26
Description :
Just record and review some points about Data Structure.
Have mistakes that please correct it yourself.
数据结构的基本概念
1.数据
2.数据元素：
数据的基本单位，一个数据元素可有若干个数据项构成，数据项是不可分割的最小单位
3.数据类型
4.抽象数据类型(ADT[Abstract Data Type]):
数学模型在计算机的一种实现，包括数据对象、数据关系、基本操作，如建立一个有限状态机模型
5.数据结构：数据元素之间的关系称之为结构，数据结构包括三方面：逻辑结构、存储结构、数据运算(程序=算法+数据结构)
6.逻辑结构：数据间的逻辑关系，与数据存储独立，分为线性结构和非线性结构
graph TD 逻辑结构--线性结构 逻辑结构--非线性结构 线性结构--一般线性表 线性结构--受限线性表 线性结构--线性表推广 受限线性表--栈和队列 受限线性表--串 线性表推广--数组 线性表推广--广义表 非线性结构--非线性表 非线性表--集合 非线性表--树形结构 非线性表--图形结构 树形结构--一般树 树形结构--二叉树 图形结构--有向图 图形结构--无向图7.物理结构：数据元素的表示以及关系的表示，主要有：顺序存储、链式存储、索引存储、散列存储
8.算法评估
（1）特性：有穷、确定、可行、输入、输出
（2）时间复杂度：衡量算法随问题规模的增大，算法执行的时间增长的快慢
T(n)=O(f(n))，f(n)为算法运算频度，一般采用最坏情况下的时间复杂度
计算方法：取算法时间增长最快的函数项，忽略其系数
a加法规则：
$$
T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
$$
多项式相加，只保留最高阶的项，且系数变为1
b乘法规则：
$$
T(n)=T_1(n)*T_2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
$$
多项式相乘，都保留
从左到右性能依次降低：
$$
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)
$$
单循环体型：
例题1：计算下列程序的时间复杂度
```C++
int i,sum //执行1次
sum=0 //执行1次
for(i=0;i<=n;i++)//int i=0执行1次，i<=n执行n+2次，i++执行n+1次
sum+=i; //执行n+1次
```
时间分析： 该算法执行了3n+6个语句。 假设每个语句执行时间一致，均为常数t。则总时间
$$
T=(3n+6)*t
$$
随着问题规模n的增大，总时间的增长率与n的增长率一致，所以复杂度为
$$
O(n)
$$
结论：
复杂度是关于增长率的，所以可以直接忽视常数项
一般可以直接关注循环段基本操作语句
```c++
sum+=i;
```
的执行次数
例题2：
int sum,i;
sum=0;
for (i = 1;i <= n;i=2*i){
sum=sum+i;
时间分析：
i 取值：1,2,4,8…
满足条件：2^