数据结构绪论（B站王卓老师）
- 一，相关概念
+ 1，<font color=green>**数据（DATA）**</font>：各种符号的集合
分为：①数值型数据 实数等
②非数值型数据 文字图象等
+ 2，<font color=green>**数据元素（DATA element）**</font>数据的基本单位，在计算机中通常作为一个<u>整体</u>进行考虑和处理，别名为元素，顶点，记录，结点。
+ 3，<font color=green>**数据项（DATA item）**</font>是构成数据元素的不可分割的最小单位
+ 小结：数据>数据元素>数据项
+ 4，<font color=green>**数据对象（DATA object）**</font>是性质相同的数据元素的集合，是数据的一个子集
- 二，数据结构
+ 1，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包括：①逻辑结构 ②存储结构 ③数据运算
+ 2,逻辑结构的种类
+ 划分方法一：
+ 划分方法二：
+ 3，存储结构的分类
+ 1，顺序存储结构：
将数据元素存放在地址连续的存储单元中，其数据间的逻辑关系与物理关系一致。
+ 2，链接存储结构：
将数据元素存放在任意的存储单元中，这组存储单元之间通过链接的方式建立起来。（C语言中用指针实现链式存储结构）
+ 3，索引存储结构：
在存储数据元素的同时，还建立附加的索引表。
+ 4，散列存储结构：
根据元素的关键字直接计算出该元素的存储地址，又称哈希存储结构。
+ 4，数据类型(DATA type)：
+ 是指一个值的集合和定义在这个值集上的一组操作的总称。
作用:
1，数据类型决定了数据对象取值范围
2，数据类型决定了数据对象所能进行的操作
+ 抽象数据类型（Abstract data type,**ADT**）
定义格式如下：
```c
ADT 抽象数据类型名{
数据对象：
数据关系：
基本操作：
}ADT 抽象数据类型名
```
基本操作的定义格式为：
```c
操作名（参数表）
初始条件：
操作结果：
```
+ 基本操作的定义格式说明
+ ***概念小结***
三，算法效率（时间效率和空间效率）
+ 1，两种度量方法：
+ ①事后统计方法：
通过设计好的测试程序和数据，利用计算机计时器对不同算法的运行时间进行比较。
+ ②事前分析估算法：
在计算机程序编写前，依据算法所处理的数据规模大小和算法实现所消耗的时间资源、空间资源等，对算法进行估算。
+ 2，算法运行时间=一个操作所需时间（假设均为单位时间）×算法中该操作重复执行的次数（语句频度）
算法执行时间约等于语句频度总和
+ 3，两个n*n矩阵相乘算法效率分析
```c
for(i=1;i<=n;i++) //n+1
for(j=1;j<=n;j++) //n*(n+1)
for(k=1;k<=n;k++) //n*n*(n+1)
c[i][j]+=a[i][k]*b[k][j];//n*n*n
```
算法耗费时间等于每条语句频度之和
T(n)=（n+1）+n*(n+1)+n*n*(n+1)+n*n*n=n^3+3n^2+2n+1
+ 4,算法的渐进时间复杂度(O是数量级符号)
简称时间复杂度(T(n)的数量级)
+ 1，忽略低次幂项和最高次幂系数
+ 2，
+ 3，对于复杂的算法，可以分为几个部分，利用加法和乘法法则计算时间复杂度
+ 加法法则
：T(n)=T1(n)+T2(n) 取两个函数中数量级最大的
+ 乘法法则
：T(n)=T1(n)*T2(n) 数量级为两个函数的乘积
+ 4，时间复杂度T(n)按数量级递增顺序为
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
+ 5，渐进空间复杂度(S(n)的数量级)
+ 1，空间复杂度S(n)分析
+ 1，算法原地工作：算法所需 Workspace 的空间为常量，O(1)
+ 2，递归算法的空间复杂度：递归深度n*每次递归调用所需空间
+ 3，循环工作算法的空间复杂度：循环中使用的变量所占空间
+ 2，空间复杂度S(n)按数量级递增顺序为
O(1)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
例子：
