数据结构是以某种形式组织在一起的数据的集合。 它不仅存储数据，还支持访问和处理数据的操作。 算法是解决问题时需要遵循的一组明确指定的简单指令。 以下是我整理的常用数据结构和算法相关的内容。 如有错误，请指出。
为了描述方便，文中涉及的代码部分均采用Java语言编写。 其实Java本身就提供了几种常见数据结构的更好的实现，比如我们经常使用的线性表、栈、队列等。 Java集合框架，有需要的可以阅读这篇文章。 Java - 集合框架完全解决
1. 线性表 1. 数组实现 2. 链表
2. 栈和队列
3. 树和二叉树 1. 树 2. 二叉树的基本概念 3. 二叉搜索树 4. 平衡二叉树 5. 红黑树
4. 图片
5. 总结
1. 线性工作台
线性表是最常用和最简单的数据结构。 它是 n 个数据元素的有限序列。
通常有两种方法来实现线性表。 一种是使用数组来存储线性表的元素，即使用一组连续的存储单元按顺序存储线性表的数据元素。 另一种是用链表来存储线性表的元素，即用一组任意的存储单元来存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。
数组实现
数组是一种固定大小的数据结构，所有对线性表的操作都可以通过数组来实现。 虽然数组的大小一旦创建就无法更改，但是当数组无法再存储线性列表中的新元素时，我们可以创建一个新的大数组来替换当前数组。 这样，数组就可以用来实现动态数据结构。
int[] = new int[10];int[] = new int[20];for (int i = 0; i < .; i++) {
[一世] = [一世];
}// 您也可以使用 . 在数组之间复制的方法 // .(, 0, , 0, .); = ;
//表示当前存储元素的数组 //size表示当前元素个数 void add(int index, int e) { if (index > size || index < 0) {
.out.("该位置非法...");
} //如果数组已满，则扩展它
if (size >= .) { // 扩展函数请参考代码1
} for (int i = size - 1; i >= 索引; i--) {
[i + 1] = [i]；
} //将数组从位置索引处的所有元素向后移一位
// .(, 索引, , 索引 + 1,大小 - 索引);
[索引] = e;
尺寸++；
上面简单写了两个典型的数组实现线性表的函数。 具体可以参考Java中集合类的源码。 数组实现的线性表的优点是可以通过下标来访问或修改元素，效率相对较高。 主要缺点是插入和删除的成本很高。 例如，当在第一个位置之前插入一个元素时，必须先插入所有元素。 该元素向后移动一位。 为了提高任意位置添加或删除元素的效率，可以使用链式结构来实现线性列表。
链表
链表是物理存储单元上的一种不连续、非顺序的存储结构。 数据元素的逻辑顺序是通过链表中指针的链接顺序来实现的。 链表由一系列在内存中不一定相连的节点组成。 每个节点由数据部分Data和链部分Next组成。 Next 指向下一个节点。 这样，在添加或删除时，只需要改变相关节点的Next点即可，效率很高。
单链表的结构
下面主要用代码来展示链表的一些基本操作。 需要说明的是，这里我们主要以单链表为例，暂时不考虑双向链表和循环链表。
类节点{
E 项； 下一个节点； //构造函数节点(E) {
这个.item = ;
this.next = null;
//头节点和尾节点都为空。 链接列表为空。 节点头 = null; 节点尾= null;
//创建一个新节点，让head指向这个节点 head = new Node(""); //让尾节点也指向这个节点 tail = head;
//创建一个新节点并连接到最后一个节点 tail.next = new Node(""); //尾节点指向新节点 tail = tail.next;
节点 = 头; while ( != null) {
.out.(.item);
= .下一个；
void (Node head) {//逆序遍历链表主要利用了递归的思想
如果（头！=空）{
(头.下一个);
.out.(head.item);
//单链表反转主要是把两个节点之间的链接关系一一改变来完成 Node (Node head) { if (head == null) { null;
节点=空；
节点=空；
节点=头； 而（！=空）{
节点=.下一个； 如果（==空）{
= ;
.下一个 = ;
= ;
= ;
};
上面几段代码主要展示了链表的几个基本操作。 还有很多诸如获取指定元素、移除元素等操作都可以自己完成。 在编写这些代码时，必须明确节点之间的关系，以免容易出错。
还有其他方法可以实现链表。 常见的有循环单链表、双向链表、循环双向链表。 循环单链表主要是链表的最后一个节点指向第一个节点，整体形成一个链接。 双向链表在节点中主要包含两个指针部分，一个指向前驱元素，另一个指向后继元素。 JDK中集合类的实现是双向链表。 循环双向链表是最后一个节点指向第一个节点的位置。
2. 栈和队列
栈和队列也是比较常见的数据结构。 它们是特殊的线性表，因为对于栈来说，元素的访问、插入和删除只能在栈顶进行，而对于队列来说，元素只能从队列尾部插入。 从队列头部开始访问和删除。
堆
堆栈是一张表，将插入和删除限制在一个位置。 这个位置就是表的末尾，称为栈顶。 栈的基本操作包括入栈（入栈）和出栈（出栈）。 前者相当于插入，后者相当于删除最后一个元素。 堆栈有时称为 LIFO（后进先出）表，意思是后进先出。
堆栈模型
我们看一个经典问题来加深对栈的理解。
一个关于栈的经典问题
上图中答案是C，大家可以仔细想一下原理。
因为栈也是一张表，所以任何实现表的方法都可以实现栈。 当我们打开JDK中Stack类的源码时，我们可以看到它继承了该类。 当然，Stack在Java 2之前是一个容器类，现在我们可以用它来执行对栈的所有操作。
队列
队列是一种特殊的线性表。 特殊的是它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。 和栈一样，队列也是受限制线性表的操作。 执行插入操作的一端称为队列尾部，执行删除操作的一端称为队列头。
队列图
我们可以使用链表来实现队列。 下面的代码简单展示了如何实现队列类。
类 { 列表 = new (); // 加入队列
void (E e) { 列表。(e);
} // 出队
E () { 列表。();
普通队列是先进先出的数据结构，而在优先级队列中，元素被赋予优先级。 访问元素时，首先删除优先级最高的元素。 生活中优先级队列的应用还是很多的。 例如，医院急诊科为患者分配优先级，优先级最高的患者首先接受治疗。 在Java集合框架中，一个类就是优先级队列的实现类。 您可以阅读源代码了解详细信息。
3. 树和二叉树
树结构是一种非常重要的非线性数据结构，其中树和二叉树是最常用的。 在介绍二叉树之前，我们先简单了解一下树的相关内容。
树
树是由n（n>=1）个有限节点组成的层次关系的集合。 它具有以下特点：每个节点有零个或多个子节点； 没有父节点的节点称为根节点； 每个非根节点只有一个父节点； 除根节点外，每个子节点还可以分为多个不相交的子树。
树结构
二叉树的基本概念
二叉树是一种树结构，其中每个节点最多有两个子树。 通常子树被称为“左子树”和“右子树”。 二叉树通常用于实现二叉搜索树和二叉堆。
二叉树的每个节点最多有2个子树（没有度大于2的节点）。 二叉树的子树分为左子树和右子树，并且顺序不能颠倒。
二叉树的第 i 层最多有 2^(i-1) 个节点； 深度为 k 的二叉树最多有 2^k-1 个节点。
深度为 k、节点数为 2^k-1 的二叉树称为满二叉树；
深度为 k、有 n 个节点的二叉树称为完全二叉树，当且仅当每个节点对应于深度为 k 的满二叉树中编号为 1 到 n 的节点。
在二叉树的一些应用中，常常需要找到树中具有某种特征的节点，或者对树中的所有节点进行某种处理，这就涉及到二叉树的遍历。 二叉树主要由根节点、左子树和右子树三个基本单元组成。 如果限制为先左后右，那么根据这三部分遍历的顺序不同，可以分为前序遍历、中序遍历和后序遍历三种。
（1）前序遍历：如果二叉树为空，则不进行操作，否则先访问根节点，然后依次遍历左子树，最后依次遍历右子树。 (2)中序遍历时，如果二叉树为空，则不进行任何操作。 否则，先中序遍历左子树，然后访问根节点，最后中序遍历右子树。 (3)如果后序遍历二叉树为空，则为空操作； 否则，先遍历左子树访问根节点，然后后序遍历右子树，最后访问根节点。
给定一棵二叉树，写出三个遍历结果
(1)二叉树的每个节点最多有2个子节点，树上没有限制。 (2)二叉树中节点的子树分为左子树和右子树。 即使一个节点只有一颗子树，也必须指定该子树是左子树还是右子树，即二叉树是有序的。 (3)一棵树永远不可能为空，它至少有一个节点，而二叉树可以为空。
上面我们主要介绍了二叉树的相关概念。 接下来我们将从二叉搜索树开始，介绍几种常见的二叉树类型，并用代码实现前面的理论部分。
二叉搜索树
二叉搜索树是二叉排序树，也称为二叉搜索树。 二叉搜索树要么是空树，要么是具有以下性质的二叉树：（1）如果左子树不为空，则左子树上所有节点的值都小于其根节点的值; （2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值； (3) 左右子树也分别是二叉排序树； (4) 不存在具有相同值的关键节点。
典型的二叉搜索树构建过程
对于二叉搜索树来说，当给定值相同但顺序不同时，构造出的二叉搜索树的形状是不同的。 让我们看一个例子。
不同形状的平衡二叉树的ASL是不同的
可见，包含n个节点的二叉搜索树的平均搜索长度与树的形状有关。 在最坏的情况下，当依次插入的关键字是有序的时，形成的二叉搜索树将转变为单分支树。 树的深度为n，其平均搜索长度为(n+1)/2（与顺序搜索相同）。 ，最好的情况是二分搜索树的形状与二分搜索的决策树相同，其平均搜索长度与log2(n)成正比。 平均而言，二叉搜索树的平均搜索长度与logn是同一数量级，因此为了获得更好的性能，在二叉搜索树的构建过程中通常需要进行“平衡处理”。 稍后我们会介绍平衡二叉树。 和红黑树，都可以使搜索树的高度为O(log(n))。
班级 {
E ;
左边;
正确的; (E e) {
=e;
二叉搜索树的所有三种遍历都可以直接使用递归方法实现：
void (root) { if (root == null);
.out.(根。+“”);
(根.左);
(root.right);
void (root) { if (root == null);
(根.左);
.out.(根。+“”);
(root.right);
void (root) { if (root == null);
(根.左);
(root.right);
.out.(根。+“”);
/**
*@
*/ 类 > {
// 根
根; //默认构造函数
() {
} // 搜索二叉搜索树
(E e) { = 根； while ( != null) { if ((.) < 0) {
= .左；
} 否则如果 ((.) > 0) {
= .右；
}否则{真;
} 错误的;
} //插入二叉搜索树
(E e) { // 如果插入的元素之前是空二叉树，则将其用作根节点。
如果（根==空）{
根=（e）；
} else { // 否则，从根节点开始遍历，直到找到合适的父节点。
= 空； = 根； while ( != null) { if ((.) < 0) {
= ;
= .左；
} 否则如果 ((.) > 0) {
= ;
= .右；
}否则{假;
} // 插入
如果 ((.) < 0) {
.left = (e);
} 别的 {
.right = (e);
} 真的;
} // 创建新节点
(E e) { 新的 (e);
}//二叉树的节点类 > {
E ; 左边; 正确的;
(E e) {
=e;
上面的代码15主要展示了自己实现的一个简单的二叉搜索树，其中包含了几个常用的操作。 当然，更多的操作还是需要自己完成。 因为二叉搜索树删除节点的操作比较复杂，所以下面详细介绍一下。
要删除二叉搜索树中的元素，首先需要找到包含该元素的节点及其父节点。 假设它指向二叉搜索树中包含该元素的节点，并指向该节点的父节点。 该节点可能是该节点的左子节点，也可能是右子节点。 这里有两种情况需要考虑：
如果该节点没有左子节点，则只需将该节点连接到该节点的右子节点即可。
一个节点有一个左子节点，假设它指向包含该节点左子树中最大元素的节点，左子树指向该节点的父节点。 然后先用该节点中的元素值替换该节点中的元素值，将该节点连接到该节点的左子节点，然后删除该节点。
//删除二叉搜索树的节点
(E e) { = 空; = 根； // 找到要删除的节点位置
while ( != null) { if ((.) < 0) {
= ;
= .左；
} 否则如果 ((.) > 0) {
= ;
= .右；
} 否则{ 中断;
} // 没有找到要删除的节点
如果 (== null) { false;
} // 考虑第一种情况
if (.left == null) { if (== null) {
根=.right；
} 否则 { 如果 ((.) < 0) {
.左=.右；
} 别的 {
.right = .right;
} else { // 考虑第二种情况
= ; = .左； // 查找左子树中最大的元素节点
while (.right!= null) {
= ;
= .右；
} // 代替
。 = .; // 连接到左孩子
如果 (.right == ) {
.右=.左；
} 别的 {
.左= .左；
} 真的;
平衡二叉树
平衡二叉树也称为AVL树。 它要么是空树，要么是二叉树，具有以下性质：它的左子树和右子树都是平衡二叉树，并且左子树和右子树的深度差的绝对值不超过1。
平衡二叉树
AVL树是第一个发明的自平衡二叉搜索树算法。 在AVL中，任意节点的两个子子树之间的最大高度差为1，因此也称为高度平衡树。 具有 n 个节点的 AVL 树的最大深度约为 1。在平均情况和最坏情况下，查找、插入和删除都是 O(log n)。 添加和删除可能需要通过一次或多次树轮换来重新平衡树。
红黑树
红黑树是一种平衡二叉树，它保证基本动态集合操作的事件复杂度在最坏情况下为O(log n)。 红黑树与平衡二叉树的区别如下： (1)红黑树放弃追求完全平衡，追求粗略平衡。 虽然时间复杂度与平衡二叉树相差不大，但保证每次插入最多只需要旋转3次。 平衡是可以实现的，而且更容易实现。 (2)平衡二叉树追求绝对平衡。 条件比较苛刻，实施起来比较麻烦。 插入新节点后所需的旋转次数是不可预测的。点击查看更多
4. 图片
图是比线性表和树更复杂的数据结构。 在线性表中，数据元素之间仅存在线性关系。 在树结构中，数据元素之间存在明显的层次关系。 在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素都可能相关。 图的应用相当广泛，特别是近年来发展迅速，已渗透到语言学、逻辑学、物理、化学、电信工程、计算机科学和数学等其他学科。
由于这部分图片的内容比较大，这里就不详细介绍了。 如果您有需要，可以自行搜索相关信息。
(1)《百度百科图片简介》
(2)《数据结构图（存储结构、遍历）》
5. 总结
至此，常用数据结构的编译就结束了。 断断续续写了大约两天。 在总结的过程中，通过查阅相关资料并结合书本内容，我收获颇多。 我将在下一篇文章中讨论它。 凡信博客将介绍常用数据结构与算法总结（第二部分）的算法章节。 欢迎大家关注。
