Java 数据结构

作者: 潜心之力 | 来源:发表于2020-03-21 16:39 被阅读0次

Java数据结构算法（二）栈和队列
Java（Android）数据结构汇总 -- 总纲
Java数据结构
java 数据结构（collections）
文集总目录
Java数据结构算法（三）树
Java数据结构算法（四）图
Java高级特性-难点汇总
Java数据结构算法（五）排序
思维导图之数据结构+算法

冒泡排序，把数组里大小排序混乱的元素重新排序

private static int[] bubble(int[] arr) { -> 从左往右排序
    boolean hasChange = true;
    for (int i = 0; i < arr.length - 1 && hasChange; i++) {
        hasChange = false;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                hasChange = true;
            }
        }
    }
    return arr;
}

private static int[] bubble(int[] arr) { -> 从右往左排序
    boolean hasChange = true;
    for (int i = 0; i < arr.length - 1 && hasChange; i++) {
        hasChange = false;
        for (int j = arr.length - 1; j > 0; j--) {
            if (arr[j-1] > arr[j]) {
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
                hasChange = true;
            }
        }
    }
    return arr;
}

int[] arr = {3, 8, 10, 2, 6, 4, 9, 5, 7, 1};
int[] sort = bubble(arr);

插入排序，按元素大小从左往右排序

private static int[] insert(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && temp < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}

int[] arr = {3, 8, 10, 2, 6, 4, 9, 5, 7, 1};
int[] sort = bubble(arr);

选择排序，依次在数组中找出最小的元素从左往右排序

private static int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int k = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < arr[k]) {
                k = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    return arr;
}

折中查找，要求数组元素按大小从左往右排序

private static int binary(int[] array, int value) {
    int low = 0;
    int high = array.length;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == value) {
            return mid;
        } else if (array[mid] > value) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int[] array = {1,2,3,...,98,99,100}; -> 创建1~100的有序数组
int index = binary(array,55);

阶乘，指所有小于或等于该数的正整数相乘的积，0的阶乘是1

private static int factorial(int i) {
    if(i==1){
        return 1;
    }
    return i*factorial(i-1);
}

int value = factorial(3); -> 3*2*1=6

斐波那契数列，满足：f(1)=1;f(2)=1;f(n)=f(n-1)+f(n-2);

private static int fibonacci(int n) {
    if(n==1 || n==2){
        return 1;
    }
    return fibonacci(n-1)+fibonacci(n-2);
}

有一堆桃子，每天吃总量的一半加一个，第10天的时候只剩下一个，求第n天时共有多少个桃子(0<n<10)？

private static int peace(int n) {
    if(n==10){
        return 1;
    }
    return 2*(peace(n+1)+1);
}
int amount = peace(9); -> 4个,一天吃一半加一个即3个

二叉树，获取树节点数

public class TreeNode {
    String name;
    TreeNode leftNode;
    TreeNode rightNode;
    public TreeNode(String name,TreeNode rightNode,TreeNode rightNode){
        this.name=name;
        this.leftNode=leftNode;
        this.rightNode=rightNode;
    }
}

private static int getNodeAmount(TreeNode node) {
    if(node==null){
        return 0;
    }if(node.leftNode==null && node.rightNode==null){
        return 1;
    }
    return getNodeAmount(node.leftNode)+getNodeAmount(node.rightNode);
}

循环队列

public class CircleQueue {
    private final int MAX=100;
    private int[] arr=new int[MAX];
    private int front=0;
    private int rear=0;
    
    public void enter(int value){
        if((rear+1)%MAX == front){
            System.out.println("队列满了");
            return ;
        }
        arr[rear]=value;
        rear=(rear+1)%MAX;
    }

    public void leave(){
        if(front == rear){
            System.out.println("空队列");
            return ;
        }
        front = (front+1)%MAX;
    }

   public void println() {
        if (front == rear) {
            System.out.println("空队列");
            return;
        }
        if (rear > front) {
            for (int i = front; i < rear; i++) {
                System.out.print(arr[i] + " ");
            }
        } else {
            for (int i = front; i < MAX; i++) {
                System.out.print(arr[i] + " ");
            }
            for (int i = 0; i < rear; i++) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println("本次打印完成");
    }
}

顺序队列

public class SequenceQueue {
    private final int MAX =100;
    private int[] arr=new int[MAX];
    private int front =0;
    private int rear =0;

    public int length(){
        return rear-front;
    }

    public void enter(int value){
        if(rear==MAX){
            System.out.println("队列已满");
            return ;
        }
            arr[rear]=value;
            rear++;
    }
    public void leave(){
        if(rear==front){
            System.out.println("空队列");
            return ;
        }
        front++;
    }
}

public class SequenceStack {
    private final int MAX=100;
    private int[] arr=new int[MAX];
    private int top=-1;
    
    public void push(int value) {
        if(top==MAX) {
            System.out.println("存放空间已满");
            return ;
        }
        arr[top+1]=student;
        top++;
    }

    public void pop() {
        if(top==-1) {
            System.out.println("这是一个空栈");
            return ;
        }
        top--;
    }
}

元素链

public class LinkNode{
    LinkNode next;
    User user;
}

public class LinkList{
  LinkNode front = new LinkNode();

  private int length(){ -> 返回链的长度
    int length = 0;
    for(LinkNode node = front.next;node != null;node = node.next){
      length++;
    }
    return length;
  }

  public void header(User user){ -> 头部添加元素
    LinkNode node = new LinkNode();
    node.user = user;
    node.next = head.next;
    head.next = node;
  }

  public void middle(User user){ -> 中部添加元素
    for(LinkNode node = front.next;node != null;node = node.next){
      if(condition){ -> 自定义条件
        LinkNode linkNode = new LinkNode();
        linkNode.user = user;
        linkNode.next = node.next;
        node.next = linkNode;
      }
    }
  }

  public void footer(User user){ -> 尾部添加元素
    LinkNode tail = head;
    while(tail.next != null){
      tail = tail.next;
    }
    LinkNode node = new LinkNode();
    node.user = user;
    tail.next = node;
    }

  public void delete(User user){ -> 删除指定元素
    for(LinkNode node = front.next;node != null;node = node.next){
      if(node.user == user){
        node = node.next;
        break;
      }
    }
  }
}

public class LinkQueue{
  private LinkNode header = new LinkNode();
  private LinkNode footer = header; -> 移动指针

  public void enter(User user){
    LinkNode node = new LinkNode();
    node.user = user;
    footer.next = node;
    footer = node;
  }

  public void leave(User user){
    if(header.next == null) return;
    if(header.next == footer) footer = header;
    for(LinkNode node = header.next;node != null;node = node.next){
      if(node.user == user){
        node = node.next;
        break;
      }
    }
  }
}

public class LinkStack{
  private LinkNode = header = new LinkNode(); -> 栈顶

  public void push(User user){ -> 入栈
    LinkNode node = new LinkNode();
    node.user = user;
    node.next = head.next; -> 栈中元素放置底部
    header.next = node; -> 新增元素放置顶部
  }

  public void pop(){ -> 出栈
    if(header.next == null) return;
    header.next = header.next.next; -> 移出栈顶元素
  }
}

Java数据结构算法（二）栈和队列
本文旨作于收集整理使用！！导航 Java数据结构算法（一）链表 Java数据结构算法（三）树 Java数据结构算...
Java（Android）数据结构汇总 -- 总纲
目录：Java（Android）数据结构汇总（一）-- List（上）Java（Android）数据结构汇总（一）...
Java数据结构
Java 数据结构 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类：枚举（E...
java 数据结构（collections）
JAVA中常用的数据结构（java.util. 中） java中有几种常用的数据结构，主要分为Collection...
文集总目录
数据结构 [Java] 目录算法 [Java] 目录LeetCode [Java] 目录设计模式 [Java] 目...
Java数据结构算法（三）树
本文旨作于收集整理使用！！导航 Java数据结构算法（一）链表 Java数据结构算法（二）栈和队列 Java数据...
Java数据结构算法（四）图
本文旨作于收集整理使用！！导航 Java数据结构算法（一）链表 Java数据结构算法（二）栈和队列 Java数据...
Java高级特性-难点汇总
Java 数据结构（Java 2之前）（高级） Java工具包提供了强大的数据结构，主要是以下几种：枚举（Enu...
Java数据结构算法（五）排序
算法这点粗略整理一下，后面完善 Java数据结构算法（一）链表 Java数据结构算法（二）栈和队列 Java数据结...
思维导图之数据结构+算法
数据结构+算法 = 程序数据结构比较参考文章数据结构与算法数据结构与算法（java）