3.数据结构
3.1.链表
3.1.1.数组
- CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的地址，所以数组的全部元素或者部分元素均被读取进CPU缓存里，而链表的结点无规律的分布在堆空间里，效率远不如缓存高，读取多个数据的时候远不如数组高。
- 局部性原理：CPU的工作需要速度，因此我们希望CPU更多的数据储存在L1缓存里，所以当CPU使用数据的时候，计算机会存储可能用到的数据到L1，L2，L3缓存里，用到的可能性越大，存储的缓存级别越高。
- 时间局部性：如果一个信息正在被访问，那么近期它可能还会被再次访问。
- 空间局部性：不久后要用到的信息很可能和当前正在使用的信息在空间地址上是临近的，正在使用的这个数据地址旁边的数据，也是很可能被用到的。
3.1.2.分类
- 单链表
- 双链表
- 循环链表
- 双向循环链表
//定义通用的链表结点，使用public修饰便于修改
public class ListNode{
public int value;
public ListNode pre;
public ListNode next;
public ListNode() {}
public ListNode(int value) {
this.value = value;
}
public ListNode(int value, ListNode next) {
this.value = value;
this.next = next;
}
public ListNode(int value, ListNode pre, ListNode next) {
this.value = value;
this.pre = pre;
this.next = next;
}
}
//有关链表的操作
public class LinkedList {
ListNode head;
int size;
// 尾插法添加结点
public boolean addVal(int val){
// 判断链表是否为空
if (head == null || size == 0){
// 代表是一个空链表
head = new ListNode(val ,null);
size++;
return true;
}
// 查找尾结点
ListNode temp = head;
while (temp.next != null){
temp = temp.next;
}
// 上述循环的跳出条件, 就是temp是尾结点
temp.next = new ListNode(val, null);
size++;
return true;
}
// 删除第一个值为val的结点
public int deleteVal(int val){
// TODO:参数验证:
if (head == null||size == 0) throw new RuntimeException("linked is null");
// 如果要删除的是头结点
if (head.val == val){
// 要删除的结点是头结点
head = head.next;
size--;
return val;
}
// 删除不是头结点
ListNode temp = head;
// 向后查找要删除的结点
while (temp.next != null && temp.next.val != val){
temp = temp.next;
}
//意味着,
// 1, mid.next = null, 没有删除的元素
// 2, mid.next 就是要删除的结点
// 没找到
if (temp.next == null) return -1;
// mid.next要找的结点
temp.next = temp.next.next;
size--;
return val;
}
// 查找第一个值为val的结点
public boolean find(int val){
//判空
if(head == null || size == 0) throw new RuntimeException("linked is null");
ListNode temp = head;
while(temp.next != null && temp.next.val != val){
temp = temp.next;
}
return temp.next != null;
}
// 根据索引删除
public int deleteIndex(int index){
// TODO:参数验证:
if(head == null || size == 0) throw new RuntimeException("linked is null");
if(index > size - 1) throw new IndexOutOfBoundsException("index out of length");
//判断要删除的结点是否是头结点
if (index == 0){
// 要删除的结点是头结点
head = head.next;
size--;
return index;
}
//判断要删除的结点是不是索引为1的结点
else if (index == 1){
// 要删除的结点是头结点
head.next = head.next.next;
size--;
return index;
}
//要删除的结点不是头结点同时也不是索引为1的结点
else {
ListNode temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
size--;
temp.next = temp.next.next;
}
return index;
}
//根据索引添加
public boolean addIndex(int index , int val){
// TODO:参数验证:
if(head == null || size == 0) throw new RuntimeException("linked is null");
if(index > size ) throw new IndexOutOfBoundsException("index out of length");
ListNode node;
//判断要添加的结点是否是头结点
if (index == 0){
// 要添加的结点是头结点
node = new ListNode(val,head);
head = node;
size++;
}
//要添加的结点不是头结点
else {
node = new ListNode(val);
ListNode temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
size++;
node.next = temp.next;
temp.next = node;
}
return true;
}
// 修改原来值是oldVal的结点为newVal
public boolean set(int oldVal, int newVal){
// TODO:参数验证:
if (head == null||size == 0) throw new RuntimeException("linked is null");
// 修改是否是头结点
if (head.val == oldVal){
// 就是要修改头结点
head.val = newVal;
return true;
}
// 修改的不是头结点
ListNode mid = head;
// 查找要替换的元素
while (mid.next != null && mid.next.val != oldVal){
mid = mid.next;
}
// 没找到
if (mid.next == null){
return false;
}
// 必然找到
mid.next.val = newVal;
return true;
}
}
3.1.3.栈、队列
- 本质上就是一个受限制的线性表
- 栈：只能一端加入，同时在这一端移除，称为后入先出(LIFO)
- 队列：只能一端加入，另一端移除，称为先入先出(FIFO)
/**
* 构建一个栈: 这个栈的底层通过链表实现
*/
public class MyStack<E> {
Node top;// 维护一个栈顶
int size;
// push
// pop
// peek
/**
* 栈的入栈操作
* @param e 入栈的元素
* @return 入栈是否成功
*/
public boolean push(E e){
// 采用'头插法', 把新添加元素, 头插到链表中
top = new Node(e, top);
size++;
return true;
}
/**
* 栈的出栈操作
* @return: 出栈的元素
*/
public E pop(){
if (size == 0){
// 原栈中没有任何元素
return null;
}
// 记录要删除的值
E oldValue = top.value;
top = top.next;
size--;
return oldValue;
}
/**
* 查看栈顶元素
* @return: 栈顶元素的内容
*/
public E peek(){
if (size == 0){
// 原栈中没有任何元素
return null;
}
return top.value;
}
/**
* 栈的size方法:
* @return: 此时栈中的元素数量
*/
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
/**
* Node: 链表中的结点类型
*/
class Node{
E value;
Node next;
public Node(E value, Node next) {
this.value = value;
this.next = next;
}
}
}
/**
* 用链表来实现一个队列:
*
*/
public class MyQueue<E> {
Node top;// 头结点
Node end;// 尾结点
int size;
// offer: 入队列
// poll: 出队列
// peek: 查看队头元素
/**
* 入队列操作
* @param e 要入队列的元素
* @return 返回添加是否成功
*/
public boolean offer(E e){
// 创建一个新节点
Node node = new Node(e, null);
if (size == 0){// 代表着是一个空链表
end = node;
top = node;
size++;
return true;
}
// 让原本链表的尾结点的下一个结点, 指向这个新结点
end.next = node;
// 尾结点后移
end = node;
size++;
return true;
}
/**
* 出队列操作
* @return 被出队列的元素
*/
public E poll(){
if (size == 0) {// 空链表
return null;
}
E oldValue = top.value;
top = top.next;
// 如果原本链表中仅有一个元素, 删除元素, 需要把头尾结点都置空
if (size == 1) end = null;
size--;
return oldValue;
}
/**
* 队列头元素
* @return 队列头元素
*/
public E peek(){
if (size == 0) {// 空链表
return null;
}
return top.value;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
class Node{
E value;
Node next;
public Node(E value, Node next) {
this.value = value;
this.next = next;
}
}
}
3.2.树
- 树(Tree)是n( n>=0 )个结点的有限集合，没有结点的树称为空树，在任意一颗非空树中：
- 有且仅有一个特定的称为根(root)的结点
- 当n>1的时，其余结点可分为 m( m>0 ) 个互不相交的有限集T1，T2，…, Tm，其中每一个集合 Ti 本身又是一棵树，并且称之为根的子树。
- 特殊二叉树：
- 平衡二叉树：每颗左子树和右子树的高度差距不超过1
- 二叉搜索树(BST)：又称二叉查找树或二叉排序树。右子树比根节点的值大，左子树比根节点的值小。
- 自平衡的二叉搜索树(AVL)：左子树和右子树的高度至多相差1
- 红黑树(RBT)：树的高度是log(n)
- 结点是红色或黑色。
- 根结点是黑色。
- 所有叶子都是黑色。(叶子是NIL结点)
- 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
- 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
- 完全二叉树：从上到下，从左到右，依次排列结点
- 满二叉树：只有度为0和2的结点，无其他结点
- 完美二叉树：完全二叉树的满二叉树版本，每一层节点数都达到最大值
- 二叉树具有以下重要性质：
- 二叉树在第i层至多有2i-1个节点
- 层次为k的二叉树至多有2k-1个节点
- 对任何一颗二叉树T，如果其叶子节点数为n0 , 度为2的节点数为n2，则n0 = n2 + 1
- 具有n个节点的完全二叉树，树的高度为log2n (向下取整)。
- 如果对一颗有n个结点的完全二叉树的结点按层序从1开始编号，则对任意一结点有：
- 如果编号i为1，则该结点是二叉树的根;
- 如果编号i > 1，则其双亲结点编号为 parent(i) = i/2,
- 若 2i > n 则该结点没有左孩子，否则其左孩子的编号为 2i,
- 若 2i + 1 > n 则该结点没有右孩子，否则其右孩子的编号为 2i + 1。
- 二叉树的遍历：
- 深度优先遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 广度优先遍历
- 层次遍历
根据中序+后续或前序，可以唯一确定一颗树。而前序+中序则不可以。
- 深度优先遍历
//二叉搜索树的实现
public class MyBSTree<E extends Comparable<E>> {
Node root; // 整个二叉搜索树的根节点
int size;
/**
* 给二叉搜索树实现添加功能
* @param e
* @return
*/
public boolean add(E e){
// 二叉搜索树中不能是null
if (e == null) throw new IllegalArgumentException("parame is null");
// 树是否是空树
if (size == 0){// 如果是空树, 那么把这个新添加的元素, 作为根节点
root = new Node(null, e, null);
size++;
return true;
}
// 必定非空树:
Node mid = root;
Node midF = null;
int com = 0;
while (mid != null){
// 把当前遍历结点 和 要存储的值作比较
com = e.compareTo(mid.value);
// midF 保存 最终遍历到的存储的位置的父节点
midF = mid;
if (com > 0){
// e的值 比当前结点大, 向right子树走, 最终存储到right子树上
mid = mid.right;
} else if (com < 0){
// e的值 比当前结点小, 向left子树走, 最终存储到left子树上
mid = mid.left;
} else {
// e的值 和当前结点 相等
// 理论:
// 计数法
// 拉链法
// 修正的BSTree
// 不允许存储重复元素: compareTo 结果 = 0
return false;
}
}
//把最终元素, 添加到具体位置
if (com > 0){
midF.right = new Node(null, e, null);
}else {
midF.left = new Node(null, e, null);
}
size++;
return true;
}
/**
* 在二叉搜索树上删除一个结点
* @param e 要删除的结点
* @return 删除是否成功
*/
public boolean remove(E e){
// 参数效验
if (e == null) throw new IllegalArgumentException("parame is null");
if (size == 0) throw new RuntimeException("tree is null");
// 找到要删除的结点 和 他的父节点
Node mid = root;
Node midF = null;
int com = 0;
while (mid != null){
// 把当前遍历结点 和 要存储的值作比较
com = e.compareTo(mid.value);
if (com > 0){
// midF 保存 最终遍历到的存储的位置的父节点
midF = mid;
// 要查找的值在right子树
mid = mid.right;
} else if (com < 0){
// midF 保存 最终遍历到的存储的位置的父节点
midF = mid;
// 要查找的值在left子树
mid = mid.left;
} else {
// 找到了
break;
}
}
// 唯有两种情况走到这一步
// 第一种: 没找到 mid == null
if (mid == null){// 没找到
return false;
}
// 找到了: mid 删除的值, midF要删除值的父节点
if (mid.left != null && mid.right != null){// 必定是双分支结点
// 找right子树的最小值
Node min = mid.right;
Node minF = mid;
// 一直在right子树的left方向上一直移动, 直到找到一个最小值
while (min.left != null){
minF = min;
min = min.left;
}
// 必定 min : 就是最小值
// 替换
mid.value = min.value;
// 转成删除min
mid = min;
midF = minF;
}
// mid 要删除的元素
// Node ch = mid.left != null ? mid.left : mid.right;
Node ch = mid.right != null ? mid.right : mid.left;
if (midF == null){
// 要删除的是一个根节点, 并且这个根节点 还是单分支
root = ch;
size--;
return true;
}
// 删除最终的单分支或者叶子结点: 删除方式--> 上移
if (midF.left == mid){
midF.left = ch;
} else {
midF.right = ch;
}
size--;
return true;
}
/**
* 获得该BSTree 前序遍历结果
* @return
*/
public List<E> preOrder() {
// 存储遍历结果(出栈的元素)
List<E> list = new ArrayList<>();
// 辅助的栈, 用来帮助遍历
LinkedList<Node> stack = new LinkedList<>();
// 根节点入栈
stack.push(root);
while (!stack.isEmpty()){
// 从栈中取出元素
Node pop = stack.pop();
list.add(pop.value);// 把遍历的元素放到遍历的结果中
// 把 right 和 left子节点入栈
if (pop.right != null)stack.push(pop.right);
if (pop.left != null)stack.push(pop.left);
}
return list;
}
/**
* 实现前序遍历: 使用递归
* @return 遍历结果
*/
public List<E> preOrder2() {
ArrayList<E> list = new ArrayList<>();
preOrder2(list, root);
return list;
}
private void preOrder2(ArrayList<E> list, Node root) {
if (root == null){// 递归出口
return;
}
// 先遍历根节点
list.add(root.value);
// 遍历left子树
preOrder2(list, root.left);
// 遍历right子树
preOrder2(list, root.right);
}
/**
* 中序遍历: 利用栈来实现
* @return 遍历的序列
*/
public List<E> inOrder(){
// 创建存储遍历结果的 list
ArrayList<E> list = new ArrayList<>();
// 创建一个栈用来遍历
LinkedList<Node> stack = new LinkedList<>();
// 标记结点
Node tagNode = root;
// 循环条件: 栈不为空 或者 标记结点不为null
while (!stack.isEmpty() || tagNode != null){
// 小循环: 标记结点的left序列入栈
while (tagNode != null){
stack.push(tagNode);
tagNode = tagNode.left;
}
// 出栈一个元素, 遍历
Node pop = stack.pop();
list.add(pop.value);
// 让标记结点, 指向出栈结点的right结点
tagNode = pop.right;
}
return list;
}
public List<E> inOrder2(){
ArrayList<E> list = new ArrayList<>();
inOrder2(list, root);
return list;
}
private void inOrder2(ArrayList<E> list, Node root) {
if (root == null)return;// 递归出口
// left 根 right
// 先遍历left子树
inOrder2(list, root.left);
// 遍历根节点
list.add(root.value);
// 遍历right子树
inOrder2(list, root.right);
}
class Node {
E value;// 值域
Node left;// 左子树结点
Node right;// 右子树结点
public Node(Node left, E value, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/181078.html
