前言
? ? ? ? 由于考研且是跨考，需要学习数据结构，在这分享学习笔记与心得。
1.1 数据结构的基本概念
?1.1.1 基本概念与术语
数据
? ? ? ? 信息的载体，计算机程序加工的原料。
数据元素
? ? ? ? 数据的基本单位，可以由若干个数据项组成。数据项是构成数据元素的不可分割的最小单位。例如，学生信息是一个数据元素，而学生的身高、年龄、性别等是数据项。
数据对象
? ? ? ? 相同性质的数据元素的集合。
数据>数据对象>数据元素>数据项。
数据类型
? ? ? ? 是一个值的集合和定义在此集合上的一组操作的总称，包括原子类型（如int 、char 、float）、结构类型（如map 、list）和抽象数据类型（抽象数据组织及与之相关的操作，及数据对象、数据关系和操作）。
数据结构
? ? ? ? 是相互之间存在一种或多种特定关系的数据元素的集合。包括三方面内容：逻辑结构、存储结构、数据的运算
1.1.2 数据结构三要素
数据的逻辑结构
? ? ? ? 分为线性结构和非线性结构，线性结构如线性表、栈和队列、串、数组；非线性结构如集合、图、树、森林
数据的存储结构
? ? ? ? 顺序存储：逻辑相邻的元素物理存储位置也相邻。优点是可以实现随机存取，每个元素占用最少的存储空间。缺点是会产生外部碎片。
? ? ? ? 链式存储：逻辑相邻但物理上不一定相邻，借用指针来表示元素之间的逻辑关系。优点是不产生碎片。缺点是指针会占用额外的存储空间，且只能顺序存取。
? ? ? ? 索引存储：在存储信息的同时还附加索引表，逻辑相邻物理不一定相邻。优点是检索时间快。缺点是索引表占用额外的存储空间，且修改索引表需要时间。
? ? ? ? 散列存储（哈希存储）：根据元素的关键字直接计算出元素的存储位置。优点是检索、增。删结点都很快。缺点是散列函数的好坏对存储效果的影响较大。
? ? ? ? 后三者又称非顺序存储。
数据的运算
? ? ? ? 包括运算的定义与实现。数据运算的定义针对逻辑结构，实现针对存储结构。
1.2 算法和算法评价
?1.2.1 算法的概念
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
算法包括下列重要特性：1、有穷性；2、确定性；3、可行性；4、输入；5、输出。
“好的”算法应包括：1、正确性；2、可读性；3、健壮性；4、效率与低存储量需求。
算法的基本要素包括：对数据对象的运算和操作、算法的控制结构。
注意，算法不等于程序，算法是解决问题的指导者，而程序是解决问题的实施者，算法必须有穷、正确，而程序可以无穷、错误。
1.2.2 算法效率的度量
1、时间复杂度
? ? ? ? 算法的时间复杂度记为
结论：1、顺序执行的代码只会影响常数项，计算时间复杂度时可以忽略；
? ? ? ? ? ?2、对于循环，只需分析其中一个操作的执行次数即可；
? ? ? ? ? ?3、若有多层嵌套循环，只需关心最深层循环执行了几次
时间复杂度包括最坏时间复杂度、最好时间复杂度和平均时间复杂度，往往使用的是最坏时间复杂度。
常用的渐进时间复杂度为：
口诀：常对幂指阶
规则：加法规则?
? ? ? ? ? 乘法规则?
计算时，只需求出程序执行次数x与问题规模n的关系即可。
例如：
void fun(int n)
{
int i =1;
while(i<=n)
i=i*2;
}根据运算规则，只需计算i=i*2的执行次数，即,所以其时间复杂度为
2、空间复杂度
定义为该算法所耗费的存储空间。非重点。