以下是为您整理出来关于【算法与数据结构】合集内容，如果觉得还不错，请帮忙转发推荐。
一 二叉查找树 二叉查找树又叫二叉排序树，是为了解决查找的效率问题。正常情况下查找一个元素，需要O（n）的代价，但是如果查找元素有顺序，有序数组：可以用二分查找降低到 lgn 代价，但是有序链表的代价还是O（n） 因为，链表不支持随机访问，定位不到中间元素，从而不可以一次就排除掉一半元素。此时二叉查找树的出现，完美解决了这个问题，左边的全比根小，右边的全比根大。所以理想状态下也是一次淘汰一半元素（当然不理想，...
一 插入排序和希尔排序 插入排序和冒泡排序有点像，一个形象的比喻就是打扑克的时候摸牌的时候，也就是手里的牌都是有序的，新插入的找位置，其它元素一次后移package sort;import java.util.Arrays;public class ChaRu {public static void main(String[] args) {int arr[] = {2, 25, -5, 36, 89, -6};chaRu(arr);System.out.println(Arrays.toString(arr));}public static void chaRu(int []arr) {for(int i=1;i<arr.length;i++...
一、插入排序的介绍插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如下图所示：那插曲排序是如何借助上面提到的思想来实现排序的呢？首先我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的...
一、什么是数据结构 数据结构，直白地理解，就是研究数据的存储方式。我们知道，数据存储只有一个目的，即为了方便后期对数据的再利用，就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的值，因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容例如，要存储这样一组数据：{张三，张四，张五，张六，张七}，数据之间具有这样的关系：张三是张四、张五的...
一、栈的介绍栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制。进栈的时候是1先进，然后是2、3、4、5、6，出栈的时候是先6出，然后是5、4、3、2、1 二、栈中常用的方法 作为一个栈（用stack来表示...
1.问题概述 我们在介绍二分搜索树的时候提到时间复杂度为O(logn),但是这并不是绝对的，有些时候树可能退化为链表，时间复杂度回到O(n)级别，所以为了性能考虑，应尽量避免这种退化，这就用到了平衡树。2.什么是平衡二叉树 平衡二叉树的定义是，对于任意一个节点，左子树和右子树的高度差不能超过1，且平衡二叉树的高度和节点的数量之间的关系一是O(logn)的。我们前面介绍的满二叉树、完全二叉树和线段树都是平衡二叉树，如下图中的...
上篇介绍了AVL树的概述，这篇把AVL树的java代码实现贴出来 public class AVLTree<K extends Comparable<K>, V> {private class Node{public K key;public V value;public Node left, right;public int height; //树的高度public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;height = 1;}}private Node root; //根节点private int size; //元素个数public AVLTree(){root = null;size = 0;...
前面我们介绍了队列这种数据结构，不过我们在前面所介绍的队列只是一种普通的队列，即元素先进先出，其实队列还可以分优先级，优先级高的元素先出，比如操作系统的调度，会将优先级高的任务先调度执行，这种队列就叫做优先队列。 那么优先队列底层该如何实现呢？ 1.优先队列可以使用普通的线性结构，比如动态数组，入队时的时间复杂度为O(1),出队时需要遍历元素，找到优先级最大的元素出队，时间复杂度为O(n)。 2.使用顺序线性结构...
1. 问题 : 链表的整体反转 题目 : 将链表整体进行反转 例如 : 链表 1 --> 2 --> 3 --> 4 --> 5 反转为 5 --> 4 --> 3 --> 2 --> 1 //算法思想 : 记录 当前遍历结点的前一个结点和后一个结点 确保每次向后遍历能够找到 //当前结点的前一个结点 以此完成链表的反转 同时时间复杂度最小 为O(n) listNode * listReverse_all(listNode * list) {listNode * nextNode = list->next; listNode * rNode = list;listNode * beforeNode = NUL...
题记：题主工作三年，前段时间面试bat被面试官算法“血虐”，差点心灰意冷，怀疑人生，但是幸好意志坚强，遂，决定发愤图强，学好算法。每天坚持学一些，每周坚持有深度学习四小时。先慢慢来，学好基本的概念，常用的数据结构和算法，但是图的话，就不涉猎了，因为真的比较难，学习成本太高，讲究性价比嘛。 之后主要是记录学习常用数据结构和算法。像栈，队列，树精要笔记。内容也不会过于基础，特别基础的会一带而过，主要是记录...