00、数据结构绪论

数据是信息的载体

数据元素：每一个个体，往下拆分是不可分割的数据项。

数据对象：具有相同数据类型的数据元素构成数据对象。

数据结构：关心个体之间的关系，不同数据对象也有组成相似的数据结构。

1、数据三要素

1. 逻辑结构：
   1. 集合
   2. 线性
   3. 树形
   4. 图状
2. 数据的运算
3. 存储结构：物理层面如何实现
   1. 顺序（数组）-物理上也是相连
   2. 链式-散列在内存当中，前后关系通过指针
   3. 散列-
   4. 索引-关键字作为索引表当中的关键字

运算的定义是根据逻辑结构，指运算的功能。

运算的实现需要的是物理层面如何实现。

2、算法

简述：对数据的一系列操作，是求解问题的步骤。

1. 有穷性，有限个步骤内解决问题。
2. 确定性：相同的输入有相同的输出。
3. 有输入和输出。

好算法的特征：

1. 正确性：可以正确的解决问题，并且无歧义
2. 健壮性：在非法输入的时候，做出反应
3. 时间复杂度和空间复杂度小

3、时间复杂度

算法效率的度量。

1. 忽略顺序执行的代码，找到关键语句和基本操作，找出和问题规模n之间的关系。
2. 如果是多层循环，只要关心最深层当中的循环执行了多少次。
3. 算法执行时间和输入数据有很大关系，但是我们一般只考虑最坏和平均的时间复杂度。
4. 时间复杂度是计算机科学中描述算法运行所需计算机时间的一种计算复杂度。通常通过计算算法执行的基本操作次数来估计时间复杂度，假设每个基本操作需要固定的时间来执行1。理解算法的时间复杂度可以帮助程序员选择最适合他们需求的算法2。

4、空间复杂度

空间复杂度是指算法在运行过程中临时占用存储空间大小的量度

1. 算法运行时新开辟的辅助空间和问题规模n之间的关系
2. 如果O(1)的话，程序原地工作
3. 只需要关心数量级
4. 计算空间复杂度：
   1. 新开辟的内存空间
   2. 如果递归函数内容相同，则为递归函数所调用的深度