登录
数据结构基础
程序=数据结构+算法（物体结构+物体行为），数据结构是数字世界模拟现实世界的基础，是一切程序的地基。
本篇文章主要是将数据结构的基础内容过一遍，查漏补缺的同时为考研408做准备。
绪论
信息化世界的组成
- 由此可见，【计算机组成原理、操作系统、数据结构、计算机网络】共同组成了我们的信息化世界。
数据结构的基本概念
数据
数据元素和数据项
数据对象
数据结构的三要素
物理存储结构
- 线性存储
- 链式存储
- 索引存储
- 散列存储
数据类型和抽象数据类型
数据结构基本概念总结
算法
时间复杂度
空间复杂度
递归调用算法空间复杂度的示例
总结
线性表
线性表的定义
线性表的基本操作
总结
顺序表
定义
总结
基本操作
链表
注意上述红框中的内容，LinkList和LNode*实际上是一样的东西，但是含义有区别。
单链表的定义
单链表的基本操作
指定节点前插
巧妙方法：指定节点前插操作，除了通过遍历找到该节点的前一个节点之外，还有一种更快速的实现方法，就是在指定节点后面插入新节点，然后将新节点与指定节点的数据域互换。
删除指定节点
巧妙方法：与上面说的指定节点前插的方法异曲同工，详细步骤见下图。不过这段代码有Bug，因为如果p结点是最后一个节点的话，p->next->data会发生异常。
插入操作总结
查找操作总结
单链表的建立
尾插法：
头插法：
双链表
循环链表
静态链表
栈
基本概念
栈的顺序存储实现
总结
栈的链式存储实现
队列
基本概念
队列的顺序存储实现
队列的链式存储实现
双端队列
总结
栈的应用
括号匹配算法
实现
总结
表达式求值
表达式详解
中缀、后缀、前缀表达式
其实就是树的三种遍历顺序。
中缀转后缀
后缀表达式计算
中缀转前缀
总结
使用栈进行表达式求值
中缀转后缀（机算）
中缀表达式计算
总结
栈在递归中的应用
队列的应用
树的层序遍历
图的广度优先遍历
CPU先到先服务
缓冲区队列
电脑是快速设备，打印机是慢速设配，通过缓冲区队列解决快速设备和慢速设备之间的速度不匹配问题。
特殊矩阵的压缩存储
二维数组的存储结构
行优先存储计算方法
列优先存储计算方法
对称矩阵的压缩存储
三角矩阵压缩存储
与对称矩阵的存储方式基本一致，只需要多加一个常量存储位置即可。
三对角矩阵的压缩存储
稀疏矩阵的压缩存储
使用三元组
使用三元组有个缺点，就是会使其失去随机存取的特性，每次找数据都要遍历所有三元组。
十字链表法
总结
串
定义
基本操作
总结
串的存储结构
串的顺序存储
串的链式存储
总结
字符串模式匹配
朴素模式匹配算法
总结
KMP算法
其实就是先对模式串进行处理，找到模式串中重复的部分，比如我们已经匹配到了第五个字母，说明前四个字母goog在主串与模式串中是一样的我们会发现第四个字母与前面是存在重复部分的，即字母g，因此当我们匹配到第五个字母的时候，我们知道主串中在匹配第四个字母的时候已经有一个g了，就不需要再比一次了，所以模式串的指针直接从第二个字母开始比较。
换句话说，当我们匹配到第五个字符时，如果发现不匹配，根据部分匹配表，我们可以知道“goog”（前四个字符）中有多少字符是重复的前缀。在这个例子中，“g”是一个重复的前缀（在第一位和第四位）。如果第五个字符不匹配，我们可以将模式串移动，使模式串的第二个字符与主串中当前位置的字符对齐，而不是重新从“google”的第一个字符开始匹配。
next数组求法
KMP算法总结
next数组的进一步优化
树与二叉树
基本概念
结点、树的属性描述
有序树和无序树
森林
总结
常考性质
总结
二叉树
几个特殊的二叉树
总结
