实际上，无论学什么，都是要努力才能学到真东西！
一、绪论
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合
1.1 逻辑结构和物理结构
逻辑结构：是指数据对象中数据元素之间的相互关系
逻辑结构包括四种：集合结构、线性结构、树形结构、图形结构
物理结构：是指数据的逻辑结构在计算机中的存储形式
物理结构包括两种：顺序存储、链式存储
二、算法
定义：算法是解决特定问题求解步骤的描述
算法特性：有穷性、确定性、可行性、输入、输出
算法设计的要求：正确性、可读性、健壮性、高效率和低存储
算法效率衡量：时间复杂度
常见的时间复杂度排序：
最坏时间复杂度、平均时间复杂度。一般默认指最坏时间复杂度。
存储衡量：空间复杂度。一般可以采用空间换时间的策略
三、线性表
线性表：零个或多个数据元素的有限序列
3.1 线性表的顺序存储结构
存取速度快，插入删除速度慢。时间复杂度分别为O(1)、O(n)。
3.2 线性表的链式存储结构
头指针：链表中第一个结点的存储位置
3.3 顺序存储结构与链式存储结构对比
3.4 循环链表
将单链表中的尾指针指向头结点，形成头尾相接的单链表，称为循环链表。
在循环链表中，可以从任意一个结点出发，访问到全部结点。
3.5 双向链表
插入结点如下图：
s->prior = p; // 图中步骤1s->next = p->next; // 图中步骤2p->next->prior = s; // 图中步骤3p->next = s; // 图中步骤4
删除结点如下图：
p->prior->next = p->next; // 图中步骤1p->next->prior = p->prior; // 图中步骤2delete p;
3.6 总结
四、栈和队列
栈是限定仅在表尾进行插入和删除操作的线性表 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
4.1 栈
栈可以用顺序存储结构实现，也可以用链式存储结构实现。
栈的应用：递归，逆波兰表达式
递归：把一个直接调用自己或通过一系列调用语句间接的调用自己的函数，称为递归函数。
逆波兰表达式：利用栈进行求解计算。从左到右遍历表达式，遇到数字就入栈，遇到符号就将栈顶两个数字出栈进行计算，将结果入栈，直到获得结果。
标准四则运算表达式转为逆波兰表达式：从左到右遍历表达式，若是数字就直接输出，成为逆波兰表达式的一部分；若是符号则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先于加减），则栈内元素依次出栈并输出，并将当前符号进栈。直到遍历结束。
4.2 队列
队列可以用顺序存储结构实现，也可以用链式存储结构实现。
4.3 总结
当用顺序存储结构实现栈和队列时，都存在一些弊端，它们各自有各自的技巧来解决这个问题。
对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。
对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。
解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。
它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。
五、串
串（string）是由零个或多个字符组成的有限序列，又叫字符串。
5.1 编码
ASCII编码：
- ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。
- 标准ASCII 码也叫基础ASCII码，使用7 位二进制数（剩下的1位，即最高位为0）来表示所有的大写和小写字母，数字0~9、标点符号， 以及在美式英语中使用的特殊控制字符。其中最后一位用于奇偶校验。
问题：
- ASCII是单字节编码，无法用来表示中文（中文编码至少需要2个字节），所以，中国制定了GB2312编码，用来把中文编进去。
- 中文编码的问题需要专文讨论，这篇笔记不涉及。这里只指出，虽然都是用多个字节表示一个符号，但是GB类的汉字编码与后文的 Unicode 和 UTF-8 是毫无关系的。
Unicode：
- Unicode最常用的是用两个字节表示一个字符（如果要用到非常偏僻的字符，就需要4个字节）。现代操作系统和大多数编程语言都直接支持Unicode。
- Unicode兼容ASCII，字母A用ASCII编码是十进制的65，二进制的01000001；而在Unicode中，只需要在前面补0，即为：00000000 01000001。
- 如果统一成Unicode编码，乱码问题从此消失了。但是，如果你写的文本基本上全部是英文的话，用Unicode编码比ASCII编码需要多一倍的存储空间，在存储和传输上就十分不划算。
UTF8：
- UTF-8 是在互联网上使用最广的一种 Unicode 的实现方式。
- UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度。常用的英文字母被编码成1个字节，汉字通常是3个字节，只有很生僻的字符才会被编码成4个字节。
- 从上面的表格还可以发现，UTF-8编码有一个额外的好处，就是ASCII编码实际上可以被看成是UTF-8编码的一部分，所以，大量只支持ASCII编码的历史遗留软件可以在UTF-8编码下继续工作。
5.2 串的模式匹配——KMP算法
详细算法讲解见：https://www.yuque.com/zerojinian/ixuz3g/muxrgb
0028.实现strStr
六、树
6.1 基础概念
结点拥有的子树个数称为结点的度，度为0的结点是叶子结点。
树的度是树内各结点的度的最大值。
森林是m（m>=0）棵互不相交的树的集合。
6.2 树的存储结构
双亲表示法、孩子表示法、孩子兄弟表示法
6.3 二叉树
二叉树是重中之重！！！
二叉树理论基础
一些性质：
- 二叉树的第i层上至多有
个结点 - 深度为k的二叉树至多有
个结点 - 对任意一棵二叉树，如果其叶子结点数为
，度为2的结点数为
，则
- 具有n个结点的完全二叉树的深度为
二叉树的前序、中序、后序和层序遍历
前序和中序可以唯一确定一棵二叉树，后序和中序也可以唯一确定一棵二叉树。 那么前序和后序可不可以唯一确定一棵二叉树呢？ 前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。
二叉树的建立
序列化二叉树
线索二叉树
树、森林与二叉树的转换
哈夫曼编码、哈夫曼树及其应用
七、图
7.1 图的存储结构
7.2 图的遍历
7.3 最小生成树
最小生成树：构造连通网的最小代价生成树
7.4 最短路径
Dijkstra（迪杰斯特拉）算法、Floyd（弗洛伊德）算法
7.5 拓扑排序
7.6 关键路径
八、查找
8.1 有序表查找
8.2 线性索引查找
线性索引即索引表
8.3 二叉搜索树
二叉搜索树查找、插入、删除操作，对应的代码实现
如下两个二叉搜索树进行查找操作时没有达到最快，因为树的分布极不平衡。因此引入平衡二叉树的概念，构成平衡二叉搜索树。
8.4 多路查找树（B树）
在进行大量查找时，为了减少磁盘的读取次数，减少IO时间消耗，提出多路查找树结构。
多路查找树：每个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素
四种特殊形式：2-3树，2-3-4树，B树，B+树
B+树介绍，P351页。
B树的缺陷：
对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行。
可是在 B 树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问，如下图所示，我们希望遍历这棵 B 树，假设每个结点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面 2→页面1→页面3→页面1→页面 4→页面1→页面 5。而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢？
B+树是应文件系统所需而出的一种 B 树的变形树，注意严格意义上讲，它其实已经不是树了。在 B 树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在 B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
如下图所示，就是一棵 B+树的示意，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。
这样的数据结构最大的好处就在于，如果是要随机查找，我们就从根结点出发，与 B 树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。
如果我们是需要从最小关键字进行从小到大的顺序查找，我们就可以从最左侧的叶子结点出发，不经过分支结点，而是延着指向下一叶子的指针就可遍历所有的关键字。
B+树的结构特别适合带有范围的查找。比如查找我们学校 18～22 岁的学生人数，我们可以通过从根结点出发找到第一个 18 岁的学生，然后再在叶子结点按顺序查找到符合范围的所有记录。
B+树的插入、删除过程也都与 B 树类似，只不过插入和删除的元素都是在叶子结点上进行而已
8.5 哈希表
散列函数：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法（P357）
处理哈希冲突的方法（P360）：
冒泡排序、简单选择排序、直接插入排序
希尔排序、堆排序、归并排序、快速排序
若有收获，就点个赞吧
0 人点赞
