第一章：绪论
-
数据与数据结构
- 数据：信息的载体。
- 数据元素：数据中的一个“个体”，是数据的基本组织单位。
- 数据项：
- 简单数据项（例如：姓名，年龄）
- 组合数据项（例如：出生年月日，包含年，月，日三个简单数据项）
- 数据对象：属性相同的数据元素的集合。
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
-
逻辑结构
- 开始结点：第一个数据元素。
- 终端结点：最后一个数据元素。
- 前驱：与当前数据相邻的前面一个元素。
- 后继：与当前数据元素相邻的后一个元素。
- 集合：集合众数据元素之间除了“同属一个集合”之后数据元素之间无其他关系，他们之间的关系称为是松散的。
- 线性结构：有且仅有一个开始结点和终端结点，数据元素之间存在“一对一”的关系，开始结点没有前驱，但只有一个后继，终端结点没有后继，但只有一个前驱，其余结点只有一个前驱，一个后继。
- 树形结构：数据元素之间存在“一对多”的关系，有一个称为根节点，此结点无前驱结点，其余结点有且仅有一个前驱，所有节点都可以有多个后继。
- 图形结构：数据元素之间存在“多对多”的关系，任何结点都可以有多个前驱和后继。
-
存储结构
- 顺序存储：将所有数据元素存放在一片连续的存储空间中，并使逻辑上相邻的数据元素在对应的物理位置也相邻。
- 链式存储：不要求将逻辑上相邻的数据元素存储在物理上相邻的位置，即数据元素可以存储在任意的物理位置上，每个数据元素包含两部分，一部分用来存放数据元素值本身，另一部分用来存放表示逻辑关系的指针。
- 索引存储：在存储数据元素的同时，还增设了一个索引表，索引表中的每一项包含关键字和地址，关键字是能唯一标识一个数据元素的数据项，地址是指示数据元素的存储地址或存储区域的首地址。
- 散列存储（哈希存储）：将数据元素存储在一片连续的区域内，每一个数据元素的具体存储地址是根据该数据元素的关键字值，通过哈希函数直接计算出来的。
-
算法与算法分析
- 算法的性质：
- 有穷性：一个算法都必须在执行有限步骤后结束；
- 确定性：一方面指每一条指令都有确切的含义，另一方面指算法输出结果确定；
- 有效性：算法中每一条语句都可以被计算机正确执行；
- 输入：一个算法具有零个或多个输入；
- 输出：一个算法必须有零个或多个输出。这些输出是与输入有着某种特定关系的量，是经过处理后的信息；
- 设计算法应该考虑的目标：
- 正确性：满足具体问题的功能和性能要求；
- 可读性：便于阅读，以便后续对算法的理解和修改；
- 健壮性：具有检查错误和对某些错误进行适当处理的功能；
- 高效率：效率高低是通过算法运行所需资源的多少来反映的，这里的资源包括时间和空间需求；
- 算法的性质：
-
算法的描述
- 自然语言：俗称人话。。。通俗易懂，但是不严谨；
- 程序设计语言：可以直接运行，但是不直观；
- 伪代码：介于自然语言和程序设计语言之间，忽略语法要求，容易理解；
-
算法分析
- 时间复杂度：尝试通过计算出依据算法编制的程序中每条语句频度之和的值来估算一个算法的执行时间。语句频度是语句重复执行的次数；
- 空间复杂度：包括算法本身的代码，常量等占用的资源（固定空间需求）和临时工作单元和递归运算时的资源占用（可变空间需求）；
- 注意：算法编写时if else 的大括号以防万一，不要省略。递归中尽量不要递归的产生变量或对象或是数组什么的；
第二章：线性表
-
方法
- void clear：置空
- boolean isEmpty：判断是否为空
- int length：求线性表长度
- Object get（int i）：返回下标为i的对象
- int get（Object x）：返回对象值为 x 的下标
- void insert（int i，Object x）：在第i个数据元素之前插入一个值为x的对象
- Object remove（int i）：删除下标为i的元素，并且返回该元素对象
- display（）：顺序输出所有元素
-
顺序表相关概念
- 存储密度 = 数据元素本身之所需的存储空间 / 该数据元素实际所占用的空间
- 循环链表：也称环形链表，将单链表的首尾相连，构成一个环形结构。再这个链表中，每一个元素都有后继；
- 双向链表：在单链表中不仅包含指向后继的指针，还包含指向前驱的指针。
-
特点
- 顺序表：因为本质是数组，因此便于随机存取，但不利于插删操作，不容易扩充，只能被动的改变空间大小，访问第i个元素的时间复杂度是O（1）
- 链表：本质是对.next 的指向来确定链，在空间上较为灵活，便于插删，但不利于查找，访问第i个元素的时间复杂度为O（n）
第三章：栈与队列
-
相关概念
- 栈：类似于一个大坑，先扔进去的东西要后取出来。有顺序栈（以顺序表为本质的栈）和链栈（以链表为核心的栈）
- 队列：相当于食堂排队买饭，先排队的先买饭。有顺序队列和链队列；
- 循环队列：在循环链表的基础上建立循环队列
-
方法
- void clear：置空
- boolean isEmpty：判断是否为空
- int length：返回长度
- （栈）Object peek：读取栈顶元素
- （栈）void push（Object x）：将对象x入栈（压倒栈顶）
- （栈）Object pop：删除并返回栈顶元素，如果栈为空，返回null
- （队列）Object peek：读取队列首元素
- （队列）void offer（Object x）：将数据元素x加入队列
- （队列）Object poll：删除队列中的首元素并且返回该对象，若队列为空，返回null
-
算法
- 栈：大数问题，后缀表达式，汉诺塔
- 队列：素数环，优先队列
-
栈与队列的比较
- 都是线性结构，“一对一”的对应关系
- 插入操作都限制在表尾进行
- 都可使用顺序存储和链式存储实现
- 在增加和方法的时间复杂度上都是常数阶
第四章：串与数组
-
相关概念
- 串：字符串，本质是字符数组
- 串相等：两个串的长度与对应位置上的字符相同
- 主串：模式匹配中等待匹配的通常比较长的字符串
- 模式串：模式匹配中主动匹配的通常比较短的字符串
-
方法
- void clear：置空
- boolean isEmpty：判断是否为空
- int length：返回长度
- char charAt（int index）：读取并返回串中的第index个字符
- String substring（int begin，int end）：返回 [begin，end）的子串
- String insert（int offset，String str）：在当前串的第offset个字符前插入str，并且返回一个新的字符串
- String delete（int begin，int end）：删除当前串中[begin，end)的字符串，并且返回新字符串
- String concat（str）：连接两个新的字符串
- int compareTo（str）：将当前串与str比较，若当前串大于str，返回大于0的值，若相等，返回0，若小于，返回小于0的值
-
串的模式匹配
- Brute-Force 模式匹配算法：模式串与主串一个字符一个字符的匹配，不成功，就从主串的下一个字符开始让子串从头开始匹配
- KMP 模式匹配算法：匹配失败后，不直接从主串的下一个字符开始，而是扫描子串，跳过已经匹配过的正确的串，从主串与子串不匹配的地方开始。
-
数组
- 数组是n（n>=1）个具有相同类型的数据元素构成的有序序列
- 行优先顺序：在将多维数组存在一维数组中时以行序为主序列的存储方式
- 列优先顺序：在将多维数组存在一维数组中时以列序为主序列的存储方式
-
矩阵的压缩存储
- 目的：节省存储空间
- 三角矩阵的压缩存储
- 稀疏矩阵的压缩存储：
- 三元组表存储
- 十字链表存储
第五章：树与二叉树
-
相关概念
- 树的结点：由一个数据元素及关联其子树
- 结点的路径：从根节点到该节点所经历的结点和分支的顺序排列
- 路径的长度：结点路径中所包含的分支数
- 结点的度：指该节点拥有的子树的数目
- 树的度：树中所有结点的度的最大值
- 叶结点（终端结点）：树中度为0的结点，也称终端结点
- 分支结点（非终端结点）：树中度不为0的结点，也称非终端结点
- 孩子结点（子结点）：一个结点的孩子结点指这个结点的子树的根结点
- 双亲结点（父结点）：若树中某个结点有孩子结点，那么这个结点就称为孩子结点的双亲结点
- 子孙结点：一个节点的子孙结点是指这个结点的所有子树中的任意结点
- 祖先结点：指该结点的路径中除此结点之外的所有结点
- 兄弟结点：指具有同一双亲的结点
- 结点的层次：若规定根结点的层次为0，那么其他结点的层次是其双亲结点的层次数加1；
- 树的深度：指数中所有结点的层次数的最大值加1
- 有序树：指树中各结点的所有子树之间从左到右有严格的次序关系，不能互换（如二叉树）
- 无序树：树中各结点的所有子树之间从左到右没有严格的次序关系
- 森林：由n（n>=0）棵互不相交的树所构成的集合
-
二叉树的延伸概念
- 满二叉树：所有结点或者是叶结点，或者是左右子树都非空，并且所有叶结点都在同一层上的二叉树称为满二叉树
- 完全二叉树：相当于满二叉树结点的前n个结点的集合
- 单分支树：所有结点都没有左子树或是右子树的二叉树
-
二叉树的性质
- 二叉树中第i层上的结点数最多为 2的i次方 个
- 深度为h的二叉树中最多有 2的h次方-1 个结点（因为深度 = 层数-1，所以其实与上一条本质相同）
- 若叶结点的个数为 a 个，度为2的结点个数是 b 个，则有 a = b + 1；
- 对于具有 n 个结点的二叉树，在从左向右的基础上从上到下从0开始编号，那么编号为i的结点有：
- i = 0 时为根节点
- 2i 为该结点的左子树的根节点（如果有），2i + 1 为该结点的右子树的根节点
- 若 2i + 1 >= n ,则该结点无左孩子
- 若 2i + 2 >= n ,则该结点无右孩子
-
二叉树的存储结构
- 顺序存储：存在数组中
- 链式存储：在结点类中有链接左结点和右结点的属性
-
二叉树的遍历
- DLR先根遍历或先序遍历：先查找根节点，在一直查找左子树的左结点，然后翻上来找右结点
- LDR中根遍历或中序遍历
- LRD后根遍历或后序遍历：先处理左子树，再处理右子树，最后访问根结点
- 层次遍历：将二叉数在从左到右的基础上逐层的访问
第六章：图
-
相关概念
- 无向图：全部由无向边构成的图
- 有向图：全部由有向边构成的图
- 权：图中的每条边上都有的表示特定意义的值
- 网：边上标有权的图
- 完全图：具有n个顶点，n*(n+1)/2 条边的图，即每两个顶点都有连接
- 稠密图和稀疏图
- 子图：一个图的边或点的子集所构成的图
- 邻接点
- 顶点的度：图中与该顶点相关联边的数目
- 路径与回路：路径长度是该路径上边的数目
- 连通图：若任意两个顶点均是连通的，则该图是连通图
- 连通分量：无向图中的极大连通子图称为连通分量
- 强连通图和强连通分量：在有向图中，若任意两个顶点均连通，则称为强连通图；有向图中的极大强连通子图称为强连通分量
-
图的存储结构
- 图的类型有四种：无向图（UDG），有向图（DG），无向网（UDN），有向网（DN）
- 邻接矩阵：
- 图：在二维数组中，如果图中两个顶点连接，那么二维数组的对应坐标的位置就是1，其余位置是0
- 网：在二维数组中，如果两个顶点链接，那么二维数组中的对应坐标的位置就是他们的权值，其余的位置为无穷大
- 邻接表：一种链式存储结构
-
算法
- BFS，DFS：广度优先搜索与深度优先搜索
- 克鲁斯卡尔算法
- 普里姆算法
- 最短路径
- 拓扑排序
- 关键路径（带权搜索）
第七章：内排序
-
相关概念
- 内部排序：内部排序指待排序列完全存放在内存中进行的排序过程，适合数量不太大的数据
- 外部排序：外部排序指待排序列借助外部存储器进行的排序，适合数量大的数据
- 稳定排序与不稳定排序：关键字的前后位置关系在排序前与排序后是否一致，一致则是稳定排序，不一致就是不稳定排序
-
内排序方法
- 插入类：
- 直接插入排序：空间复杂度O（1），时间复杂度O（n2）
- 希尔排序：空间复杂度O（1），时间复杂度与增量序列的选择有关
- 交换类：
- 冒泡排序：空间复杂度O（1），时间复杂度O（n2）
- 快速排序：空间复杂度O（logn）,时间复杂度O（nlogn）
- 选择类：
- 直接选择排序：空间复杂度O（1），时间复杂度O（n2）
- 树形选择排序：时间复杂度O（nlogn）
- 堆排序：空间复杂度O（1），时间复杂度O（nlogn）
- 归并类：归并排序：空间复杂度O（n），时间复杂度O（nlogn）
- 基数排序：多关键字排序与链式奇数排序
- 插入类：
第八章：外排序
-
相关概念
- 外排序：与外部存储设备的特征有关
-
磁盘排序
- 磁盘信息的存取
- 多路归并排序
- 最优归并树
第九章：查找
-
相关概念
- 平均查找长度：ASL
-
静态表的查找（线性表，链表等）
- 顺序查找：从第一个开始查找
- 二分查找：在有序后，从中间开始，确定区间后再从区间的中部开始找
- 分块查找（索引顺序查找）：通过一个索引，使查找更加方便
-
动态表的查找（表本身就是动态生成的）
- 二叉排序树
- 平衡二叉树
- B- 与 B+ 树
- 红黑树（对称二叉B树）
-
哈希表的查找
- 概念：以关键字的值作为自变量，进行哈希函数的运算后得到一个函数值，将该值作为数据元素的地址进行存储
- 常用的哈希函数：
- 除留余数法：用自变量除一个值后取余，将余数作为函数值
- 直接地址法：例如自变量与函数值呈线性关系，可以根据自变量的值直接求出函数值
- 数字分析法
- 平方取中法
- 折叠法：将自变量进行分割，并且进行累加之类的方法，得到函数值
- 随机数法
-
处理冲突的方法
- 一旦数据元素较多时，可能会出现两个不同的值有相同的函数值，因此需要处理这种冲突的情况
- 开放地址法：如果发现冲突，就沿着发生冲突的地方继续寻找空位，遇到空位就填进去
- 链地址法（拉链法）：将所有具有相同哈希地址的不同关键字的数据元素通过链表保存起来
- 公共溢出区法：另建一个公共溢出区（称为溢出表），如果发生冲突，就存放在这里
- 再哈希法：发生冲突后就用另一个哈希函数进行运算，重新求得函数值
