java数据结构复习01

1.数组

package javaDataStruct.array01;

public class MyArray {
    private int[] arr;
    // 表示有效数据的长度
    private int elementsSize;

    public MyArray() {
        // TODO Auto-generated constructor stub
        arr = new int[50];
    }

    public MyArray(int maxSize) {
        arr = new int[maxSize];
    }

    /**
     * 添加数据
     */
    public void insert(int value) {
        arr[elementsSize] = value;
        elementsSize++;
    }

    /**
     * 打印数据
     */
    public void printArray() {
        System.out.print("[ ");
        for (int i = 0; i < elementsSize; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("]");
    }

    /**
     * 查找数据
     */
    public int indexSearch(int value) {
        int i;
        for (i = 0; i < elementsSize; i++) {
            if (value == arr[i]) {
                break;
            }

        }
        if (i == elementsSize) {
            return -1;
        } else {

            return i;
        }
    }

    /**
     * 二分法查找数据 前提：数组有序
     */
    public int binarySearch(int value) {
        int middle;
        int low = 0;
        int high = elementsSize;
        while (true) {
            middle = (low + high) / 2;
            if (arr[middle] == value)
                return middle;
            else if (low > high) {
                return -1;
            } else {
                if (arr[middle] < value)
                    low = middle + 1;
                else
                    high = middle - 1;
            }

        }
    }

    /**
     * 查找数据，根据索引查找
     */
    public int get(int index) {
        if (index < 0 || index >= elementsSize) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return arr[index];
        }
    }

    /**
     * 删除数据
     */
    public void delete(int index) {
        if (index < 0 || index >= elementsSize) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            for (int i = index; i < elementsSize; i++) {
                arr[i] = arr[i + 1];
            }
            elementsSize--;
        }
    }

    /**
     * 更新数据
     */
    public void update(int index, int value) {
        if (index < 0 || index >= elementsSize) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            arr[index] = value;
        }
    }
}

package javaDataStruct.array01;

public class TestMyArray {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyArray array = new MyArray();
        array.insert(13);
        array.insert(17);
        array.insert(34);
        array.insert(55);
        array.insert(90);
        array.printArray();
        System.out.println(array.indexSearch(34));
        System.out.println(array.indexSearch(90));
        System.out.println(array.indexSearch(190));
        System.out.println(array.get(2));
//        System.out.println(array.get(3));
        array.delete(1);
        array.printArray();

        array.update(1, 33);
        array.printArray();
        System.out.println(array.binarySearch(55));
        System.out.println(array.binarySearch(33));
        System.out.println(array.binarySearch(13));
        
    }

}

2.简单排序

2.1冒泡排序

https://www.cnblogs.com/jingmoxukong/p/4302718.html

假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。 

(1) 每趟排序过程中需要通过比较找到第 i 个小的元素。

所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。

(2) 假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。

所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。

package javaDataStruct.sort02;

public class BubbleSort {
    public static void sort(int[] array) {
        int temp = 0;
　　　　　// 需要遍历的次数
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = array.length - 1; j > i; j--) { // 注意 array.length - 1

　　　　　　　　　// 比较相邻的元素，如果前面的数大于后面的数，则交换
                if (array[j] < array[j - 1]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }
}

2.2选择排序

https://www.cnblogs.com/jingmoxukong/p/4303289.html

(1)从待排序序列中，找到关键字最小的元素；

(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

(3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

package javaDataStruct.sort02;

public class SelectionSort {
    public static void sort(int[] array) {

　　　　　　// 需要遍历获得最小值的次数
　　　　　　// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列

int k = 0; // 保存最小数据的索引
        int temp = 0;
        for (int i = 0; i < array.length-1; i++) {
            k = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[k])
                    k = j; // 更新最小数据的索引
            }
　　　　　　　// 将最小数据交换
            temp = array[k];
            array[k] = array[i];
            array[i] = temp;
        }
    }
}

2.3插入排序

https://www.cnblogs.com/jingmoxukong/p/4303270.html

package javaDataStruct.sort02;

public class InsertSort {

    public static void sort(int[] arr) {
        int temp = 0;
        int i, j;
　　　　 // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
        for (i = 1; i < arr.length; i++) {
            temp = arr[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置

        // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp; 
        }
    }
}

package javaDataStruct.sort02;

import javaDataStruct.util.Tool;

public class TestSort {
    public static void main(String[] args) {
        int[] array = { 1, 2, 6, 8, 16, 3, 5 };
//        BubbleSort.sort(array);
//        SelectionSort.sort(array);
        InsertSort.sort(array);

        Tool.printArray(array);
    }
}

2.4希尔排序

https://www.cnblogs.com/jingmoxukong/p/4303279.html

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

该方法因DL．Shell于1959年提出而得名。

希尔排序的基本思想是：

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

我们来通过演示图，更深入的理解一下这个过程。 

在上面这幅图中：

初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

按照直接插入排序的方法对每个组进行排序。

在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。

按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

所以，希尔排序是不稳定的算法

public static void shellSort(int[] array) {

        int gap = array.length;
        while (gap > 0) {
            int temp;
            int j;
            for (int i = 1; i < array.length; i++) {
                temp = array[i];
                for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
                    array[j + gap] = array[j];
                }
                array[j + gap] = temp;
            }
            gap = gap / 2;
        }
    }

2.5快速排序

https://www.cnblogs.com/jingmoxukong/p/4302891.html

public static int division(int[] list, int left, int right) {
        // 以最左边的数(left)为基准
        int base = list[left];
        while (left < right) {
            // 从序列右端开始，向左遍历，直到找到小于base的数
            while (left < right && list[right] >= base)
                right--;
            // 找到了比base小的元素，将这个元素放到最左边的位置
            list[left] = list[right];

            // 从序列左端开始，向右遍历，直到找到大于base的数
            while (left < right && list[left] <= base)
                left++;
            // 找到了比base大的元素，将这个元素放到最右边的位置
            list[right] = list[left];
        }

        // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
        // 而left位置的右侧数值应该都比left大。
        list[left] = base;
        return left;
    }

    public static void quickSort(int[] list, int left, int right) {

        // 左下标一定小于右下标，否则就越界了
        if (left < right) {
            // 对数组进行分割，取出下次分割的基准标号
            int base = division(list, left, right);

            // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, left, base - 1);

            // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, base + 1, right);
        }
    }

2.6归并排序

归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。

package datastruct.t02sort;

import datastruct.Tookit;

public class MergeSort {
    public static void mergeSort(int[] a, int left, int right) {
        if (left >= right)
            return;
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        mergeArray(a, left, mid, right);//合并
    }

    // 两个排好序的子序列合并为一个子序列
    public static void mergeArray(int[] a, int left, int mid, int right) {
        int[] temp = new int[a.length];//辅助数组
        int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针
        while (p1 <= mid && p2 <= right) {
            if (a[p1] < a[p2])
                temp[k++] = a[p1++];
            else
                temp[k++] = a[p2++];
        }

        while (p1 <= mid) {//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
            temp[k++] = a[p1++];
        }
        while (p2 <= right) {//同上
            temp[k++] = a[p2++];
        }

        for (int i = left; i <= right; i++) {
            a[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = { 1, 5, 3, 7, 4, 8, 10 };
        System.out.println("原数组为：");
        Tookit.print(a);
        mergeSort(a, 0, a.length - 1);
        System.out.println("排序之后的数组为");
        Tookit.print(a);
    }
}

2.7堆排序

 

heapify操作顺序

 从构建好的堆进行排序

1.交换根结点和最后一个结点

 

 2.取出最后一个结点

 3.再次从根结点进行heapify

 

 4.交换根结点和最后一个结点

 5.取出最后一个结点

 重复上述步骤。。。

package datastruct.t02sort;

import util.*;

public class HeapSort {
    // 构建堆
    public static void buildHeap(int[] tree, int n) {
        int lastNode = n - 1;
        int parent = (lastNode - 1) / 2;
        int i;
        for (i = parent; i >= 0; i--) {
            heapify(tree, n, i);
        }
    }

    /**
     * 
     * @param tree
     * @param n：结点数目
     * @param i：当前的结点
     */
    public static void heapify(int[] tree, int n, int i) {
        if (i >= n)
            return;

        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }

    // 交换元素
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 堆排序
    public static void heapSort(int[] tree, int n) {
        buildHeap(tree, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(tree, i, 0);
            heapify(tree, i, 0);
        }

    }

    public static void main(String[] args) {
        /*int[] tree = { 4, 10, 3, 5, 1, 2 };
        int n = 6;
        heapify(tree, n, 0);
        Tool.printArray(tree);*/
        /*int[] tree = { 2, 5, 3, 1, 10, 4 };
        int n = 6;
        buildHeap(tree, n);*/
        int[] tree = { 23, 4, 5, 2, 1, 8, 24, 55 };
        heapSort(tree, tree.length);
        Tool.printArray(tree);
    }

}

3.栈

package javaDataStruct.ch03_stack_and_queue;

import com.sun.javafx.geom.AreaOp.AddOp;

public class MyStack {
    private int[] arr;
    private int top;

    public MyStack() {
        // TODO Auto-generated constructor stub
        arr = new int[10];
        top = -1;
    }

    /**
     * 带参数的构造方法
     */
    public MyStack(int maxSize) {
        arr = new int[maxSize];
        top = -1;
    }

    /**
     * 添加数据
     */
    public void push(int value) {
        arr[++top] = value;
    }

    /**
     * 移除数据
     */
    public int pop() {
        return arr[top--];
    }

    /**
     * 查看数据
     */
    public int peek() {
        return arr[top];
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 判断是否满了
     */
    public boolean isFull() {
        return top == arr.length - 1;
    }
}

package javaDataStruct.ch03_stack_and_queue;

public class TestMyStack {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(10);
        myStack.push(12);
        myStack.push(16);
        System.out.println(myStack.isEmpty());
        System.out.println(myStack.isFull());
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.isEmpty());
    }

}

4.队列

package javaDataStruct.ch03_stack_and_queue;

public class MyQueue {
    private int[] arr;
    private int elementsSize;
    private int front;
    private int tail;

    public MyQueue() {
        // TODO Auto-generated constructor stub
        arr = new int[10];
        elementsSize = 0;
        front = 0;
        tail = -1;
    }

    public MyQueue(int maxSize) {
        // TODO Auto-generated constructor stub
        arr = new int[maxSize];
        elementsSize = 0;
        front = 0;
        tail = -1;
    }

    /**
     * 从队尾插入数据
     */
    public void insert(int value) {
        arr[++tail] = value;
        elementsSize++;
    }

    /**
     * 从对头删除数据
     */
    public int remove() {
        elementsSize--;
        return arr[front++];
    }

    /**
     * 从对头查看数据
     */
    public int peek() {
        return arr[front];
    }

    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return elementsSize == 0;
    }

    /**
     * 判断是否满了
     */
    public boolean isFull() {
        return elementsSize == arr.length;
    }
}

package javaDataStruct.ch03_stack_and_queue;

public class TestMyQueue {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyQueue mq = new MyQueue();
        mq.insert(1);
        mq.insert(2);
        mq.insert(3);
        mq.insert(4);
        System.out.println(mq.isEmpty());
        System.out.println(mq.isFull());
        System.out.println(mq.peek());
        while (!mq.isEmpty()) {
            System.out.print(mq.remove() + " ");
        }
        System.out.println();
    }

}

5.链表

5.1普通单向链表

1.在头部插入一个节点

2.在头部删除一个节点

package cn.jxufe.ch04_link;

/*
 * 链结点，相当于是车厢
 */
public class Node {
    public int data;
    public Node next;

    public Node(int value) {
        this.data = value;
    }

    /**
     * 显示方法
     */
    public void display() {
        System.out.print(data + " ");
    }
}

package cn.jxufe.ch04_link;

/**
 * 链表相当于火车
 */
public class LinkList {
    private Node first;

    public LinkList() {
        first = null;
    }

    /**
     * 插入一个节点，在头部进行插入
     */
    public void insertNode(int value) {
        Node node = new Node(value);
        if (first == null) {
            first = node;
        } else {
            node.next = first;
            first = node;
        }
    }

    /**
     * 在头部进行删除
     */
    public Node deleteFirst() {
        Node temp = first;
        first = temp.next;
        return temp;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 查找方法
     */
    public Node find(int value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    /**
     * 删除方法
     */

    public Node delete(int value) {
        Node current = first;
        Node previous = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            previous = current;
            current = current.next;
        }
        if(current==first){
            first = first.next;
        }else {
            previous.next = current.next;
        }
        return current;

    }
}

package cn.jxufe.ch04_link;

public class TestLinkList {
    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.insertNode(34);
        linkList.insertNode(23);
        linkList.insertNode(12);
        linkList.insertNode(0);
        linkList.insertNode(-1);
        linkList.display();
        linkList.deleteFirst();
        linkList.display();

        Node node = linkList.find(23);
        node.display();
        System.out.println();
        Node node1 = linkList.delete(0);
        node1.display();
        System.out.println();
        linkList.display();
        linkList.display();
    }
}

5.2双端链表

1.在尾部插入一个节点

package cn.jxufe.ch05_first_last_link;

import cn.jxufe.ch04_link.Node;

/**
 * 双端链表
 */
public class FirstLastLink {
    private Node first;
    private Node last;

    public FirstLastLink() {
        first = null;
        last = null;
    }

    /**
     * 插入一个节点，在头部进行插入
     */
    public void insertNode(int value) {
        Node node = new Node(value);
        if (isEmpty()) {
            last = node;
        }
        node.next = first;
        first = node;
    }

    /**
     * 插入一个节点，从尾部插入
     */
    public void insertLast(int value) {
        Node node = new Node(value);
        if (isEmpty()) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    /**
     * 在头部进行删除
     */
    public Node deleteFirst() {
        Node temp = first;
        if(first.next == null){
            last = null;
        }
        first = temp.next;
        return temp;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 查找方法
     */
    public Node find(int value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    /**
     * 删除方法
     */

    public Node delete(int value) {
        Node current = first;
        Node previous = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            previous = current;
            current = current.next;
        }
        if (current == first) {
            first = first.next;
        } else {
            previous.next = current.next;
        }
        return current;

    }

    /**
     * 判读是否为空
     */
    public boolean isEmpty() {
        return first == null;
    }
}

package cn.jxufe.ch05_first_last_link;

public class TestFirstLastLink {
    public static void main(String[] args) {
        FirstLastLink fl = new FirstLastLink();
        fl.insertNode(34);
        fl.insertNode(22);
        fl.insertNode(4);
        fl.insertNode(56);
        fl.display();
        fl.deleteFirst();
        fl.deleteFirst();
        fl.display();
        fl.insertLast(28);
        fl.insertLast(90);
        fl.display();
    }
}

5.3双向链表

1.在头部插入一个节点

 

2.在尾部插入一个节点

 

3.从头部进行删除

 

package cn.jxufe.ch05_first_last_link;


/**
 * 双向链表
 * 每个列表除了保存对下一个节点的引用，同时还保存对前一个节点的引用。
 */
public class DoubleLink {
    private Node first;
    private Node last;

    public DoubleLink() {
        first = null;
        last = null;
    }

    /**
     * 插入一个节点，在头部进行插入
     * 首先对列表进行判断，如果为空，则设置尾结点为新添加的节点；如果不为空，则设置头节点的前一个节点为新添加的节点。
     */
    public void insertFirst(int value) {
        Node node = new Node(value);
        if (isEmpty()) {
            last = node;
        } else {
            first.prev = node;
        }
        node.next = first;
        first = node;
    }

    /**
     * 插入一个节点，从尾部插入
     * 如果为空，则直接设置头节点为新添加的节点；否则设置尾结点的后一个节点为新添加的节点，同时设置新添加的
     * 节点的前一个节点为尾结点。
     */
    public void insertLast(int value) {
        Node node = new Node(value);
        if (isEmpty()) {
            first = node;
        } else {
            last.next = node;
            node.prev = last;

        }
        last = node;
    }

    /**
     * 在头部进行删除
     */
    public Node deleteFirst() {
        Node temp = first;
        if (first.next == null) {
            last = null;
        } else {
            first.next.prev = null;
        }
        first = temp.next;
        return temp;
    }

    /**
     * 从尾部进行删除
     * 如果头节点后没有其他节点，则设置尾节点为null；否则设置尾节点的前一个节点的next为null。设置为节点为其前一个节点。
     */
    public Node deleteLast() {
        Node temp = last;
        if (first.next == null) {
            last = null;
        } else {
            last.prev.next = null;
        }
        last = last.prev;
        return last;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 查找方法
     */
    public Node find(int value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    /**
     * 删除方法
     */

    public Node delete(int value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        if (current == first) {
            first = first.next;
        } else {
            current.prev.next = current.next;
        }
        return current;

    }

    /**
     * 判读是否为空
     */
    public boolean isEmpty() {
        return first == null;
    }
}

package cn.jxufe.ch05_first_last_link;

public class TestDoubleLink {
    public static void main(String[] args) {
        DoubleLink dl = new DoubleLink();
        dl.insertLast(45);
        dl.insertLast(23);
        dl.insertLast(-1);
        dl.insertLast(56);
        dl.display();
        dl.insertFirst(21);
        dl.insertFirst(1);
        dl.insertFirst(27);
        dl.display();
        dl.deleteFirst();
        dl.display();
        dl.deleteLast();
        dl.display();
        dl.delete(21);
        dl.display();
    }
}