（一）数据结构的基本概念
1.相关名词
【1】数据
1.信息的载体，描述客观事物
2.能被输入到计算机中
3.能被计算机程序识别和处理的符号的集合。
【2】数据元素
1.数据的一个“个体”
2.数据的基本单位
3.有时候也被称为元素、结点、顶点、记录等，这时候用于完整描述一个对象。ex：一条学生记录
【3】数据项
1.组成数据元素具有特定意义不可分割的最小单位
2.数据元素是数据项的集合
3.比如说在学生信息表中的一条学生记录（数据元素）中这个学生的学号或者性别这些都是数据项
【4】数据对象
1.具有相同性质的数据元素的集合
2.是数据的一个子集
【5】数据结构：通过抽象方法研究一组具有特定关系的数据的存储和处理，主要研究三个方面（三要素）：逻辑结构、存储结构和数据运算。
2.数据结构的三要素=逻辑结构+存储结构+数据运算
【1】逻辑结构
有2种划分方式:1.按照线性和非线性分 2.按照结构分
1.线性和非线性
（1）线性：线性表、栈和队列、字符串、数组和广义表
（2）非线性：树和图
2.结构分（4种）
（1）集合结构：在同一个集合中，它们之间无关系
（2）线性结构：任意一个元素之间有且仅有一个前驱和后继，1对1
（3）树形结构：有一个前驱多个后继，1对多
（4）图形结构：有多个前驱多个后继，多对多
【2】存储结构（存储的逻辑结构4种）：顺序、链式、索引、散列（哈希）
*索引：类似课本目录，每页都有页码i，检索时利用结点（页）的顺序号i确定位置
*散列：也称哈希存储，用哈希函数将数据元素按照关键字和唯一的存储位置关联
【3】数据运算：插入、删除、查找、修改、排序等
（二）算法和算法分析
1.算法的基本概念
1.指令的有限序列
2.可以用自然语言描述
3.算法具有5个重要特性：有穷、确定、可行、输入输出
*有穷：步骤和执行时间有限
*确定：有确切含义、无二义、只有唯一的一条执行路径（对于相同的输入有唯一的执行结果）
*可行：执行有限次实现
*输入：0或多个
*输出：1或多个（最少1个结果）
4.算法和程序是两个不同的概念（区别）
*执行时间：算法步骤有限（有穷性），程序无限次执行
*语言描述：程序必须用规定语言，算法无限制可自然语言。
5.算法的基本目标：正确、易读、健壮、高效率
*健壮：当环境发生变化（非法输入）时候可以适当做出反应或者处理，不会产生不正确的结果
*高效率：较高的时间（用时少）和空间性能（占用空间少）
6.算法的评价方法：事前分析、事后统计
2.算法的时间和空间性能分析
【1】时间复杂度
1.T（N）表示该算法时间耗费，N为求解问题的规模
2.当N趋向于无穷时候，仅考虑数量级（阶），就是算法的渐进时间复杂度，用大o表示法
3.大o表示法就是忽略系数，类似数学的“抓大头”
4.语句频度：重复执行的次数
【2】用大o表示法求解算法的渐进时间复杂度（有6类）
1. 常量阶 O(1)：算法的执行时间不随输入数据的规模n变化，即无论输入数据有多大，算法的执行时间都是固定的。这类算法通常只包含基本操作，如赋值、比较等。
2. 对数阶 O（log n)：算法的执行时间随输入数据的规模n的对数增长。这类算法通常涉及到二分搜索或树结构的深度遍历。
3. 线性阶 O(n)：算法的执行时间随输入数据的规模n线性增长。这类算法通常涉及到对数据的顺序访问，如数组或列表的遍历。
4. 平方阶 O(n^2)：算法的执行时间随输入数据的规模n的平方增长。这类算法通常涉及到两层嵌套循环，如矩阵的乘法或对数组的每个元素进行比较。
5. 线性对数阶 O(n log n)：算法的执行时间是输入数据的规模n与对数的乘积。这类算法通常涉及到排序操作，如快速排序或归并排序。
6. 立方阶 O(n^3)：算法的执行时间随输入数据的规模n的立方增长。这类算法通常涉及到三层嵌套循环，如矩阵乘法的直接实现。
