数据结构和算法

概述
数据结构的概述
排序算法
查询算法
两种物理结构
栈与队列
树结构
- 链表实现树
- 数组实现树
查询树
多路查询树
霍夫曼树
哈希表

概述

算法=输入+程序+输出

针对某个特定问题的解决方案
1. 先有解决问题的主体思路
2. 功能分解，逐步求精
算法是有好坏之分的，主要使用O进行标识
1. 时间复杂性：算法执行所需要的时间
2. 空间复杂性：算法执行所需要的空间内存
  基础算法
排序
1. 简单排序：冒泡、选择、插入
2. 高级排序：希尔、归并、计数、快速、堆
查询
1. 二分查找法

算法的特征

有穷性
有效性
确定性
输入性
输出性

（两输两有一确定）

算法的基本要求

正确性
可读性
健壮性
时间复杂度
空间复杂度

（时空正可健）

数据结构的概述

数据结构：就是在数据中存储的方式
1. 在内存中物理存储方式
  1. 数组
  2. 链表
2. 逻辑存储方式
  1. 线性表
  2. 队列
  3. 栈
3. 树结构
  1. 二叉树
  2. 查询树
  3. 平衡树
  4. 红黑树
  5. B树
4. 哈希表
5. 图
  排序算法
三种简单排序的区别，时间复杂性：O（n^2）
1. 冒泡
  1. 两个临近的数值进行对比，将大的数值放到集合尾部
  2. 遍历次数多，交换次数多
2. 选择
  1. 从未排序的集合中选择最小或者最大值，放入到已经排序好的集合中
  2. 遍历次数多，但是交换的次数少
3. 插入
  1. 从未排序的集合中获取一个值，然后从已经排序好了的集合中找到插入的位置进行插入
  2. 遍历次数少，交换次数多
高级排序（速度比较快速）
1. 快速排序
2. 计数排序
3. 希尔排序
4. 归并排序
5. 堆排序
  查询算法
传统的查询算法需要遍历整个集合，时间复杂性O(n)

使用二分查找法之后，时间复杂度O(logN)

二分查找法只要针对有序的集合

获取数组的中间值下标
将中间值和目标值进行对比
判断大小选择左右查找

基本代码

public static void binarySeach(int[] arrs,int target,int start,int end){
//1,获取数组的中间值下标
int middle = (start+end)/2;
//2，将中间值和目标进行比较
if(target == arrs[middle]){
System.out.println("找到目标，下标是："+middle);
}else if(target > arrs[middle]){
//从右边开始找
binarySeach(arrs,target,middle+1,end);
}else{
//从左边开始找
binarySeach(arrs,target,start,middle-1);
}
}

添加递归退出条件

 if(end<start){//递归退出条件
            //没有找到目标
            System.out.println("没有找到目标");
            return;
     }

  6. 带返回结果的二分查找法

public static Integer binarySeach(int[] arrs,int target,int start,int end){
        if(end<start){//递归退出条件
            //没有找到目标
            //System.out.println("没有找到目标");
            return null;
        }
        //1,获取数组的中间值下标
        int middle = (start+end)/2;
        //2，将中间值和目标进行比较
        if(target == arrs[middle]){
            //System.out.println("找到目标，下标是："+middle);
            return middle;
        }else if(target > arrs[middle]){
            //从右边开始找
            return binarySeach(arrs,target,middle+1,end);
        }else{
            //从左边开始找
            return binarySeach(arrs,target,start,middle-1);
        }
    }

两种物理结构

数组
1. 是内存中的连续空间，在创建的时候大小是固定的
2. 一般编程语言都直接支持
3. 通过下标可以直接获取数组相对应的值
4. 会有扩容的问题
链表
1. 在内存中不是连续空间，大小也不是固定的
2. 可以通过下标查找数值但是需要从开始链表一个一个查询
3. 插入和删除速度很快，没有扩容的问题，但是查询速度慢

链表的基本实现

创建一个节点类

//给链表设计一个节点
public class Node<T>{
  T data;//存储的数据
  Node next;//指向下一个节点的引用
  public Node(T data, Node next) {
      this.data = data;
      this.next = next;
  }
  public T getData() {
      return data;
  }
  public void setData(T data) {
      this.data = data;
  }
}

实现新增和查询

//新增方法
public void add(T t){
  if(head==null){
      head = new Node(t,null);
  }else{
      Node temp = head;
      //找到最后一个节点
      while(temp.next!=null){
          temp = temp.next;
      }
      //将新增的节点放入到最后一个节点的next引用
      temp.next = new Node(t,null);
  }
  size++;
}
//查询方法
public T get(int pos){
  if(pos>=size){
      throw new IndexOutOfBoundsException();
  }
  int cnt = 0;
  Node<T> temp = head;//从头部开始
  //向下移动
  while(cnt != pos){
      temp = temp.next;
      cnt++;
  }
  return temp.getData();
}

指定位置的新增

public void add(int pos, T t) {
  //创建新的节点
  Node newNode = new Node(t, null);
  if(pos == 0){//在头部插入
      //先将新的节点的next指向头部
      newNode.next = head;
      head = newNode;
  }else{
      //当前位置的
      Node current = getNode(pos-1);
      //将新节点的下一个位置，执行当前节点的下一个位置
      newNode.next = current.next;
      //将当前位置的节点指向新增的节点
      current.next = newNode;
  }
  size++;
}

指定位置的删除

//删除指定位置的数据
public void remove(int i) {
  if(i==0){
      //将头节点直接移动到下一个节点
      head = head.next;
  }else{
      //找到节点
      Node current  =    getNode(i);
      Node preNode = getNode(i-1);
      //前面的节点，直接指向下后面的节点
      preNode.next = current.next;
  }
  //删除
  size--;
}

栈与队列

栈：先进后出

自定义实现栈

public class MyStack<T> {
MyLinkedList<T> datas = new MyLinkedList<>();
//压入栈
public void push(T t){
  //放在链表的尾部
  datas.add(t);
}
//出栈
public T pop(){
  //获取头部
  T t = datas.get(datas.size-1);
  datas.remove(datas.size-1);
  return t;
}
}

jdk中自带的Stack类

Stack<String> myStack = new Stack<>();
  myStack.push("aa");
  myStack.push("bb");
  myStack.push("cc");
  System.out.println(myStack.pop());
  System.out.println(myStack.pop());

队列：先进先出

自定义实现

MyQueue<String> queue = new MyQueue<>();
  queue.add("aa");
  queue.add("bb");
  queue.add("cc");
  System.out.println(queue.poll());
  System.out.println(queue.poll());

jdk自带的实现

//数组实现
Queue<String> queue = new ArrayDeque<>();
//链表实现
queue = new LinkedList<>();

树结构

是一种非线性结构
1. 既有数组查询的效率，又有链表增删的性能
树的基本特点
1. 每颗树有且仅仅有一个根节点没有父节点
2. 除了根节点，所有其他节点只有一个父节点
3. 每个节点都可以有多个子节点，也可以没有子节点
4. 最多只有两个子节点的树就是二叉树
  链表实现树

实现树节点

public class Node<T>{
     T data;//数据
     Node<T> left;//左子节点
     Node<T> right;//右子节点
}

创建一颗树

//树的根节点
 Node root;
 //创建一颗树
 public void createTree(){
     //创建根节点
     root = new Node(1);
     //左子节点
     Node left = new Node(2);
     root.setLeft(left);
     //右边子节点
     Node right= new Node(3);
     root.setRight(right);
     //左子左节点
     Node leftLeft = new Node(4);
     left.setLeft(leftLeft);
     //左子右节点
     Node leftRight = new Node(5);
     left.setRight(leftRight);
     //右子左节点
     Node rightLeft = new Node(6);
     right.setLeft(rightLeft);
     //右子右节点
     Node rightRight = new Node(7);
     right.setRight(rightRight);
 }

树的遍历

先序遍历：根节点-》左节点-》右节点

//实现先序遍历
public void preTrival(Node node){
  if(node ==null){
      return;
  }
  //直接输出根节点
  System.out.print(node.data+",");
  //遍历左子节点
  preTrival(node.left);
  //遍历右子节点
  preTrival(node.right);
}

中序遍历：左节点-》根节点-》右节点

//实现中序遍历
public void midTrival(Node node){
  if(node==null){
      return;
  }
  //遍历左子节点
  midTrival(node.left);
  //打印根节点
  System.out.print(node.data+",");
  //遍历右子节点
  midTrival(node.right);
}

后序遍历：左节点-》右节点-》根节点

//实现后序遍历
public void postTrival(Node node){
  if(node==null){
      return;
  }
  //遍历左子节点
  postTrival(node.left);
  //遍历右子节点
  postTrival(node.right);
  //打印根节点
  System.out.print(node.data+",");
}

数组实现树

基本规则
1. 使用数组存储
2. 只能构造完全二叉树
3. 左子节点 = 当前节点下标*2 +1
4. 右子节点 = 当前节点下标*2 +2

遍历

 //实现先序遍历
 public void preTrival(int index){
     if(index>= datas.length){
         return;
     }
     //打印根节点
     System.out.print(datas[index]+",");
     //遍历左子节点
     preTrival(2*index+1);
     //遍历右子节点
     preTrival(2*index+2);
 }
 //实现先序遍历
 public void midTrival(int index){
     if(index>= datas.length){
         return;
     }
     //遍历左子节点
     midTrival(2*index+1);
     //打印根节点
     System.out.print(datas[index]+",");
     //遍历右子节点
     midTrival(2*index+2);
 }

堆排序
1. 使用数组树
2. 构造一个大顶堆（所有的父类节点都比子节点要大，最大的值就会在根节点）
3. 在构造完毕大顶堆之后，将根节点和最后一个叶子节点进行交换，并且脱离树结构
4. 再将树结构继续构造大顶堆，然后再和最后一个叶子节点交换，直到排序完毕
  查询树
树既有链表插入删除的优势，又有数组的查询的效率
一般的树是不具备快速查询的能力的，只有二分查找树，可以天然的支持二分查找法，以快速实现数据的查询
查找树特点
1. 左子树的节点要比右边子树要小
2. 在构造查询树的时候，有可能会出现左右失去平衡的问题
二叉平衡树（AVL）
1. 是一个特殊的查找树
2. 在构造树的时候，会通过旋转算法，使得树达到平衡
3. 当左子树和右子树的高度差大于1的时候，树就失去了平衡，需要旋转来达到平衡
4. 由于平衡失去平衡的规则限制太高，会导致树在旋转的时候，次数增加，从而影响性能
红黑树（RBTree）
1. 也是一颗特殊的查找树
2. 主要将树节点的颜色分为黑色和红色
3. 任意节点到每个叶子节点的的黑色节点的数量是一致，如果不一致，那么则失去平衡进行旋转
4. 无论树的层有多高，每次旋转次数不会超过3次
  多路查询树
二叉查找树的问题，在于数据很多时候，树高度会很高，从而影响的性能
多路查找树，不像二叉树之后两子节点，它具备多个子节点，可以有效降低树的高度提高查询效率
多路查找树就是B树，B+树就是在B的基础，将所以的叶子节点通过链表链接起来了

霍夫曼树
是带权重的树
主要用压缩算法

哈希表
哈希表的查询速度非常，可以到达O(1)
主要原理
1. 创建一个Entry用于存储数据的key 和 value值
2. 主要是通过hash散列算法，计算出插入的元素所在位置
3. 然后根据计算出的问题，将Entry插入到对应数组中

基本实现

public class MyHashTable<K,V> {
 Entry<K,V>[] elements ;//用于存储Entry的数组
 public MyHashTable(){
     //创建Entry的数组
     elements = new Entry[10];
 }
 //计算所在的位置，散列算法
 public int hash(K k){
        return k.hashCode()%elements.length;
 }
 //插入
 public void put(K k ,V v){
     //使用K执行相关散列算法，获取存储在位置
     int pos = hash(k);
     //创建Entry放入到指定的位置
     elements[pos] = new Entry<>(k,v);
 }
 //获取
 public V get(K k){
     //通过散列算法获取位置
     int pos = hash(k);
     //通过位置获取Entry
     Entry<K,V> entry = elements[pos];
     return entry.getValue();
 }
 //定义一个Entry用于存储key和value
 public static class Entry<K,V>{
     K key;
     V value;
     public Entry(K key, V value) {
         this.key = key;
         this.value = value;
     }
     public K getKey() {
         return key;
     }
     public void setKey(K key) {
         this.key = key;
     }
     public V getValue() {
         return value;
     }
     public void setValue(V value) {
         this.value = value;
     }
 }
}

散列冲突问题
1. 由于数组长度是有限的，在计算entry插入的位置的时候，必然会出现冲突的问题
2. 解决方案1：开放寻址法
  1. 在发生冲突的时候，通过重新计算，或者是扩容的方式，来解决冲突的问题
  2. 好处可以保证entry是在数组中，方便序列化
  3. 缺点，会浪费更多空间，而且在重写计算的时候可能会影响效率
  4. 适合数据量不大的数据
3. 解决方案2：链表式
  1. 在发生冲突的时候，在冲突的位置上，通过链表添加新的数据
  2. 好处是插入的时候不需要考虑数组扩容的问题
  3. 坏处是链表逐步增大，会导致性能问题
  4. 将entry转换成链表
```
public static class Entry<K,V>{
K key;
V value;
Entry<K,V> next;//指向下个节点的引用
}
```
  5. 修改插入和查询方法 ```java //插入 public void put(K k ,V v){ //使用K执行相关散列算法，获取存储在位置 int pos = hash(k);
    
    //判断是否发生碰撞 if(elements[pos]==null){ //创建Entry放入到指定的位置 elements[pos] = new Entry<>(k,v); }else{ Entry temp = elements[pos]; //链表的遍历 while(temp.next!=null){
```
   temp = temp.next;
```
    } //插入到链表下一个为null的位置 temp.next = new Entry<>(k,v); }

}
//获取
public V get(K k){
    //通过散列算法获取位置
    int pos = hash(k);
    //通过位置获取Entry
    Entry<K,V> entry = elements[pos];
    //判断Entry的key的值是否一致
    if(entry.getKey().equals(k)){
        return entry.getValue();
    }else{
        //遍历链表，根据key判断
        while(entry.next!=null){
            entry = entry.next;
            //判断key值是否相同
            if(entry.getKey().equals(k)){
                return entry.getValue();
            }
        }
    }
    return null;
}


5. JDK中的哈希表
   1. 在jdk早期哈希表主要是Hashtable
   1. 之后为了提高效率，jdk提供HashMap
      1. 没有使用锁了
      1. 可以对空值进行处理
      1. 提高的了hash算法的效率
      1. 在处理哈希冲突的时候，也使用链表法，但是在链表数量超过8个，会将链表转换成红黑树
<a name="SVhKX"></a>
## 图
1. 图是一种网状结构，和树结构最大区别在于图可以有多个父类节点
   1. 图主要由顶点 (Vertex) 和边 (Edge) 构成
   1. 边是顶点和顶点之间的连线
   1. 边可以是有向的, 也可以是无向的.(比如A --- B, 通常表示无向. A --> B, 通常表示有向)2
   1. 图可以带权重，例如A->B花费的时间
   1. 路径是一个顶点到另一个顶点所经过的边的序列
2. 通过二维数组定义图
```java
public class MyGraph {
    //存储顶点
    Vertex[] vertices;
    //需要一个矩阵用于存储边
    int[][] adjMat;
    int verNum;//顶点的数量
    public MyGraph(int num){
        //初始化数组存储顶点
        vertices = new Vertex[num];
        //初始化边
        adjMat = new int[num][num];
        verNum=0;
    }
    //添加顶点
    public void addVertex(String label){
        //创建订单对象
        Vertex vertex = new Vertex(label);
        vertices[verNum++] = vertex;
    }
    //添加边
    public void addEdge(String start,String end){
        int sIndex =0;//start这个顶点的坐标
        int eIndex =0;
        //遍历顶点
        for (int i=0;i<vertices.length;i++){
            if(vertices[i].label.equals(start)){
                //第一个顶点的坐标
                sIndex =i;
            }
            //找到第二个顶点的坐标
            if(vertices[i].label.equals(end)){
                eIndex =i;
            }
        }
        //定义边
        adjMat[sIndex][eIndex] = 1;
        adjMat[eIndex][sIndex] = 1;
    }
    //定义顶点类
    public static class Vertex{
        String label;//存储顶点的标签
        public Vertex(String label){
            this.label= label;
        }
    }
}

两种遍历方式

深度优先遍历：其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次（可以栈来实现）

Stack stack = new Stack<>();
  //当前值已经被遍历了
  vertices[pos].isVisited = true;
  int current = pos;
  //将位置入栈
  stack.push(pos);
  System.out.println(vertices[pos].label);
  out:while(!stack.empty()) {
      for (int i=0;i< vertices.length; i++) {
          if(adjMat[current][i]==1&&vertices[i].isVisited==false) {
              //入栈
              stack.push(i);
              vertices[i].isVisited= true;
              current = i;
              System.out.println(vertices[current].label);
              continue out;
          }
      }
      //没有找到可以连接的位置的时候，那么就出栈
      stack.pop();
      //出栈后要重新设置栈顶的位置
      if(!stack.empty()) {
          current =  (int) stack.peek();
      }
  }

广度优先遍历：其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次(队列实现)

//广度优先遍历
public void bfs(int pos) {
  //创建队列
  Queue queue = new LinkedList<>();
  queue.add(pos);//入队列
  System.out.println(vertices[pos].label);//打印
  vertices[pos].isVisited = true;
  int current = pos;
  while(!queue.isEmpty()) {
      current = (int) queue.poll();//出列
      for (int i=0;i< vertices.length; i++) {
          if(adjMat[current][i]==1&&vertices[i].isVisited==false) {
              //入队列
              queue.add(i);//入队列
              System.out.println(vertices[i].label);//打印
              vertices[i].isVisited = true;
          }
      }
  }
}

概述

算法=输入+程序+输出

基础算法

算法的特征

算法的基本要求

数据结构的概述

排序算法

查询算法

两种物理结构

栈与队列

树结构

链表实现树

数组实现树

查询树

多路查询树

霍夫曼树

哈希表