第一章绪论

数据结构

基本概念：

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成；

数据项是构成数据元素的不可分割的最小单位；

数据对象：具有相同性质的数据元素的集合，是数据的一个子集；

数据结构：相互之间存在一种或多种特定关系的数据元素的集合；

PS:同样的数据元素可以组成不同的数据结构，不同的数据元素可以组成相同的数据结构

数据类型：一个值的集合和定义在此集合上的一组操作的总称{原子类型、结构类型、抽象数据类型}；

数据类型	定义
原子类型	其值不可再分的数据类型（int bool等）
结构类型	其值可以再分解为若干成分的数据类型(struct)
抽象数据类型ADT	抽象数据组织及与之相关的操作(就是用户要知道的运算)

数据结构三要素：

逻辑结构：逻辑结构是指数据元素之间的逻辑关系；

集合结构（不是重点），线性结构（一对一关系都有唯一前驱除尾部没有后继），树形结构（一对多），图结构（网状结构多对多）；

数据的运算：针对某种逻辑结构，定义基本运算；

例：线性结构（插入，删除，查找）；

存储结构（物理结构）

类型：顺序存储（连续存放），链式存储（逻辑上相邻的物理位置上不相邻通过指针），索引存储（索引表），散列存储（Hash关键字算出）；

PS：存储结构会影响存储空间分配方便程度，影响对数据运算的速度

算法的基本概念：

定义：算法是针对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作；

算法的特性：有穷性（一个算法必须总在执行有穷步之后结束，且每一步都在有穷时间内完成）；

​ 确定性 （算法中每条指令必须有确切含义，对于相同的输入只能得出相同的输出）；

​ 可行性 （基本运算执行有限次）；

​ 输入 （0或多个输入）；

​ 输出 （有1或多个输出）；

好的算法特质：

正确性：正确结果
可读性：帮助人们理解 // 注释
健壮性：输入数据非法时，能够适当的作出反应或相应处理，不会产生莫名其妙的输出结果
高效性：时间复杂度和空间复杂度（重点考点）

算法效率的度量

和机器性能，编程语言，指令质量有关，有些不能事后再统计

算法时间复杂度（重点）

大O表示法：多项相加只考虑阶数高的部分并且系数变为1 T(n)=T1（n）+T2(n)=O(max(f(n),g(n)))；多项相乘，都保留;

排序：O(1)<O(log2N)<O(n)<O(nlog2N)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

口诀：常对幂指阶

PS：1、顺序执行的代码只会影响常数项，可以忽略；2、只需挑循环中的一个基本操作分析它的执行次数与n的关系即可；

3、如果有多层嵌套循环，只需关注最深层循环循环了几次；

算法空间复杂度

表示为S（n)，算法所需要的空间为常数时叫做算法原地工作，和时间复杂度一样只考虑高阶；

只需要看和问题规模相关的变量n；

函数递归调用时，空间复杂度等于递归调用的深度（考研大多情况）