数据结构学习
数据结构
数据结构在学什么？
用程序代码把现实世界的问题信息化，并利用计算机高效的处理这些信息并且创造价值。
数据
数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号集合，数据是计算机程序加工的原料。对于计算机来说就是0 1。
数据元素:是数据的基本单位，通常作为一个整体进行考虑和处理。由数据项组成，数据项是构成数据元素不可分割的最小单位。
数据结构、数据对象：
数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合。
数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构的三要素（要关注的三个方面）：
逻辑结构：数据元素之间的逻辑关系
数据的逻辑结构：
集合：各个元素同属一个集合，别无其他关系。
线性结构：数据元素之间是一对一的关系；除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
树形结构：数据元素之间是一对多的关系。
图状结构（网状结构）：数据元素之间是多对多的关系。
物理结构（存储结构）：用计算机表示数据元素的逻辑关系
数据的存储结构：（存储结构会影响存储空间的分配方便程度）
顺序存储（物理上必须是连续的）：
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，它们之间的关系由存储单元的邻接关系体现。（分配一段连续的存储空间）
非顺序存储（物理上可以是离散的，对空间的分配更方便）：
- 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指针来表示元素间的逻辑关系。
- 索引存储：在存储元素信息的同时建立索引表，索引表中的每项称索引项其一般形式是（关键字，地址）
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，称哈希存储（hash）
不同的存储结构影响都数据的运算速度。
数据运算：
施加在数据上的运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能，运算的实现是针对存储结构的，指出运算的具体操作步骤。
数据类型、抽象数据类型
数据类型（一个值的集合和定义在此集合上的一组操作的总称）：
- 原子类型（值不可再分割）：bool、int
- 结构类型（值可在分割为若干成分的数据类型）：结构体
抽象数据类型（adt）：是抽象数据组织及与之相关的操作。
算法
程序=数据结构+算法：数据结构是把现实世界的问题信息化，将信息存入计算机，同时 还要实现对数据结构的基本操作。算法是处理这些信息以解决实 际问题。
算法的特性：
- 有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。（算法 有穷程序可无穷）
- 确定性：对于相同的输入只能有相同输出。
- 可行性：算法中描述的操作可以通过已经实现地基本运算执行有限次来实现。
- 输入：一个算法中有0个或多个输入，输入来自某特定的对象集合。
- 输出：一个算法有一个或多个输出。输入输出有某种特定关系的量。
好算法的特性：
- 正确性：算法能够正确的解决求解问题。
- 可读性：良好的可读性帮助人们理解。
- 健壮性：输入非法数据时算法能适当的做出反应或进行处理，不会产生莫名结果。
- 高效率与低存储需求：执行速度快时间复杂度低，不废内存空间复杂度。
算法的效率度量：
时间复杂度（算法时间开销）：随问题n的增大算法执行的时间的增长率和f(n)的增长率相同
让算法先运行，事后统计。问题：
- 和机器的性能有关，超级计算机和单片机
- 和编程语言有关，越高级的语言执行效率越低
- 和编译程序产生地机器指令质量有关
- 有些算法是不能事后统计的如导弹控制算法
排除算法本身无关的外界因素事前估计：
事前预估算法时间开销（时间time）T（n）与问题规模n的关系：
简单代码可以一行一行的数和计算。
忽略表达式的某些部分：去掉低阶部分只保留高阶部分，系数化1: “T(n)=O(高阶)”
加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则：T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))
常见算法复杂度排序：O(1)<O(log2n)<O(n)<O(nlogn)<O(n方)<O(n立方)<O(2的n次方)<O(n阶乘)<O(n的n次方) 魔法：常对幂指阶（上升)
好几千行代码的处理（只需考虑最深层循环）：
顺序执行的代码只会影响常数项，可以忽略（只关注循环）
只需调循环中的一个基本操作分析他的执行次数与n的关系即可
嵌套循环为n的几次嵌套次方：多层嵌套循环只需关注最深层循环循环了几次
最好时间复杂度：算法在最好情况下的时间复杂度，算法尽可能的达到最小值
最坏时间复杂度：算法在最坏情况下的时间复杂度，算法尽可能的达到最大值
平均时间复杂度：指算法在所有可能的情况下，按照输入势力以等概率出现时，
算法计算量的加权平均值
在计算算法时间复杂度时一般考虑最坏和平均复杂度
算法的空间复杂度：（解决空间开销与问题规模n之间的关系）
- 算法的空间复杂度：（与时间复杂度表示法类似也是O表示法保留最高阶数）
S(n)=O(f(n)) :S表示为“Space”
当S(n)=O(1)表示算法原地工作，算法所需内存空间为常量，算法所需空间与问题n的规模无关
通过定义的变量来计算空间复杂度，还有递归调用函数调用也需要计算空间
魔法：空间复杂度=递归调用的深度