数据结构与算法知识点总结（上）--数据结构基础
数据结构是以某种形式将数据组织在⼀起的集合，它不仅存储数据，还⽀持访问和处理数据的操作。算法是为求解⼀个问题需要遵循的、被清楚指定的简单指令的集合。下⾯是整理的常⽤数据结构与算法相关内容，如有错误，欢迎指出。
⽬录：
⼀、线性表
1.数组实现
2.链表
⼆、栈与队列
三、树与⼆叉树
1.树
2.⼆叉树基本概念
3.⼆叉查树
4.平衡⼆叉树
5.红⿊树
四、图
⼀、线性表
线性表是最常⽤且最简单的⼀种数据结构，它是n个数据元素的有限序列。
实现线性表的⽅式⼀般有两种，⼀种是使⽤数组存储线性表的元素，即⽤⼀组连续的存储单元依次存储线性表的数据元素。另⼀种是使⽤链表存储线性表的元素，即⽤⼀组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。
数组实现
数组是⼀种⼤⼩固定的数据结构，对线性表的所有操作都可以通过数组来实现。虽然数组⼀旦创建之后，它的⼤⼩就⽆法改变了，但是当数组不能再存储线性表中的新元素时，我们可以创建⼀个新的⼤的数组来替换当前数组。这样就可以使⽤数组实现动态的数据结构。
代码1 创建⼀个更⼤的数组来替换当前数组
int[] oldArray = new int[10];
int[] newArray = new int[20];
for (int i = 0; i < oldArray.length; i++) {
newArray[i] = oldArray[i];
}
// 也可以使⽤System.arraycopy⽅法来实现数组间的复制
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
oldArray = newArray;
代码2 在数组位置index上添加元素e
//oldArray 表⽰当前存储元素的数组
/
/size 表⽰当前元素个数
public void add(int index, int e) {
if (index > size || index < 0) {
System.out.println("位置不合法...");
}
//如果数组已经满了就扩容
if (size >= oldArray.length) {
// 扩容函数可参考代码1
}
for (int i = size - 1; i >= index; i--) {
oldArray[i + 1] = oldArray[i];
}
//将数组elementData从位置index的所有元素往后移⼀位
// System.arraycopy(oldArray, index, oldArray, index + 1,size - index);
oldArray[index] = e;
size++;
}
上⾯简单写出了数组实现线性表的两个典型函数，具体我们可以参考Java⾥⾯的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素，⽐较⾼效，主要缺点在于插⼊和删除的花费开销较⼤，⽐如当在第⼀个位置前插⼊⼀个元素，那么⾸先要把所有的元素往后移动⼀个位置。为了提⾼在任意位置添加或者删除元素的效率，可以采⽤链式结构来实现线性表。
链表
链表是⼀种物理存储单元上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接
次序实现的。链表由⼀系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下⼀个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很⾼。
单链表的结构
下⾯主要⽤代码来展⽰链表的⼀些基本操作，需要注意的是，这⾥主要是以单链表为例，暂时不考虑双链表和循环链表。
代码3 链表的节点
class Node<E> {
E item;
Node<E> next;
//构造函数
Node(E element) {
this.item = element;
< = null;
}
}
代码4 定义好节点后，使⽤前⼀般是对头节点和尾节点进⾏初始化
//头节点和尾节点都为空链表为空
Node<E> head = null;
Node<E> tail = null;
代码5 空链表创建⼀个新节点
//创建⼀个新的节点并让head指向此节点
head = new Node("nodedata1");
//让尾节点也指向此节点
tail = head;
代码6 链表追加⼀个节点
//创建新节点同时和最后⼀个节点连接起来
< = new Node("node1data2");
//尾节点指向新的节点
tail = ;
代码7 顺序遍历链表
Node<String> current = head;
while (current != null) {
System.out.println(current.item);
current = ;
}
代码8 倒序遍历链表
static void printListRev(Node<String> head) {
//倒序遍历链表主要⽤了递归的思想
if (head != null) {
);
System.out.println(head.item);
}
}
代码 单链表反转
//单链表反转主要是逐⼀改变两个节点间的链接关系来完成
static Node<String> revList(Node<String> head) {
if (head == null) {
return null;
}
Node<String> nodeResult = null;
Node<String> nodePre = null;
Node<String> current = head;
while (current != null) {
Node<String> nodeNext = ;
if (nodeNext == null) {
nodeResult = current;
}
< = nodePre;
nodePre = current;
current = nodeNext;
}
return nodeResult;
}
上⾯的⼏段代码主要展⽰了链表的⼏个基本操作，还有很多像获取指定元素，移除元素等操作⼤家可以⾃⼰完成，写这些代码的时候⼀定要理清节点之间关系，这样才不容易出错。
链表的实现还有其它的⽅式，常见的有循环单链表，双向链表，循环双向链表。 循环单链表 主要是链表的最后⼀个节点指向第⼀个节点，整体构成⼀个链环。 双向链表 主要是节点中包含两个指针部分，⼀个指向前驱元，⼀个指向后继元，JDK中LinkedList集合类的实现就是双向链表。 循环双向链表 是最后⼀个节点指向第⼀个节点。
⼆、栈与队列
栈和队列也是⽐较常见的数据结构，它们是⽐较特殊的线性表，因为对于栈来说，访问、插⼊和删除元素只能在栈顶进⾏，对于队列来说，元素只能从队列尾插⼊，从队列头访问和删除。
栈
栈是限制插⼊和删除只能在⼀个位置上进⾏的表，该位置是表的末端，叫作栈顶，对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插⼊，后者相当于删除最后⼀个元素。栈有时⼜叫作LIFO(Last In First Out)表，即后进先出。
栈的模型
下⾯我们看⼀道经典题⽬，加深对栈的理解。
关于栈的⼀道经典题⽬
上图中的答案是C，其中的原理可以好好想⼀想。
因为栈也是⼀个表，所以任何实现表的⽅法都能实现栈。我们打开JDK中的类Stack的源码，可以看到它就是继承类Vector的。当
然，Stack是Java2前的容器类，现在我们可以使⽤LinkedList来进⾏栈的所有操作。
队列
队列是⼀种特殊的线性表，特殊之处在于它只允许在表的前端（front）进⾏删除操作，⽽在表的后端（rear）进⾏插⼊操作，和栈⼀样，队列是⼀种操作受限制的线性表。进⾏插⼊操作的端称为队尾，进⾏删除操作的端称为队头。
队列⽰意图
我们可以使⽤链表来实现队列，下⾯代码简单展⽰了利⽤LinkedList来实现队列类。
代码9 简单实现队列类
public class MyQueue<E> {
private LinkedList<E> list = new LinkedList<>();
// ⼊队二叉树的基本性质
public void enqueue(E e) {
list.addLast(e);
}
// 出队
public E dequeue() {
veFirst();
}
}
普通的队列是⼀种先进先出的数据结构，⽽优先队列中，元素都被赋予优先级。当访问元素的时候，具有最⾼优先级的元素最先被删除。优先队列在⽣活中的应⽤还是⽐较多的，⽐如医院的急症室为病⼈赋予优先级，具有最⾼优先级的病⼈最先得到。在Java集合框架中，类PriorityQueue就是优先队列的实现类，具体⼤家可以去阅读源码。
三、树与⼆叉树
树型结构是⼀类⾮常重要的⾮线性数据结构，其中以树和⼆叉树最为常⽤。在介绍⼆叉树之前，我们先简单了解⼀下树的相关内容。
树
树 是由n（n>=1）个有限节点组成⼀个具有层次关系的集合。它具有以下特点：每个节点有零个或多个⼦节点；没有⽗节点的节点称
为 根 节点；每⼀个⾮根节点有且只有⼀个 ⽗节点 ；除了根节点外，每个⼦节点可以分为多个不相交的⼦树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。