常见的基础数据结构和算法

常见数据结构

1 栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算(先进后出)。这一端被称为栈顶，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈.jpg

public class Stack {
    private int[] array = new int[5];// 栈
    private int top = -1;// 指针
    // 压栈
    public boolean push(int x) {
        if(top<array.length-1){
            array[++top] = x;
            return true;
        }else{
            throw new RuntimeException("overFlow");//上溢
        }
    }
    // 出栈
    public int pop() {
        if (!isEmpty()) {
            return array[top--];
        } else {
            throw new RuntimeException("underflow");//下溢
        }
    }
    // 是否为空
    public boolean isEmpty() {
        return top == -1 ? true : false;
    }
}

2 队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列.jpg

public class Queue {
    Object[] array = new Object[4]; // 对象数组，此时队列最多存储3个对象
    int first = 0; // 队首下标
    int last = 0; // 队尾下标;指向指向即将添加的下一个元素位置
    /**
     * 将一个对象追加到队列尾部
     * @return 队列满时返回false,否则返回true
     */
    public boolean add(Object obj) {
        if ((last + 1) % array.length == first) {
            return false;
        }
        array[last] = obj;
        last = (last + 1) % array.length;
        return true;
    }
    /**
     * 队列头部的第一个对象出队
     * @return 出队的对象，队列空时返回null
     */
    public Object remove() {
        if (last == first) {
            return null;
        }
        Object obj = array[first];
        first = (first + 1) % array.length;
        return obj;
    }
}

单向链表

单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。

单向链表.jpg

public class LinkedList {
    public Node head = null;

    public void add(int x) {
        Node node = new Node(x, null);
        Node p = head;
        // 注意链表为空的时候的插入
        if (head == null) {
            head = node;
        }
        // 尾插法
        else {
            while (p.next != null) {
                p = p.next;
            }
            p.next = node;
        }
    }
    /**
     * 遍历打印
     */
    public void travese(Node head) {
        Node p = head;
        while (p != null) {
            System.out.println(p.item);
            p = p.next;
        }
    }
    /*
     * 元素
     */
    private static class Node {
        int item;
        Node next;

        public Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

算法

1 排序

/** 快速排序  递归  比较povit后，povit的左边是小于它的数，povit右边是大于它的数  下次递归  */
    public void quickSort(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low];

        while (l < h) {
            while (l < h && arr[h] >= povit)
                h--;
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= povit)
                l++
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
        if (l > low) sort(arr, low, l - 1);
        if (h < high) sort(arr, l + 1, high);
    }

/** 冒泡排序  按照下标向后相邻数依次比较  大数向后走 
第一次下标0（j控制）与1比较  下一次下标1与2比较  再下一次下标2与3比较  大的放后面 每走完一圈最大数放置到了最后
*/
    public static void bubbleSort(int[] ary) {
        for (int i = 0; i < ary.length - 1; i++) {// length-1次,最后一个不用冒了.
            for (int j = 0; j < ary.length - 1 - i; j++) {
                if (ary[j] > ary[j + 1]) {
                    int t = ary[j];  ary[j] = ary[j + 1]; ary[j + 1] = t;
                }
            }
        }
    }

    /**选择排序    从下标0（i控制）开始与后面所有的数比较 ，第一轮下标0与1，2，3...比较    下一轮 2与3，4，5...比较  大的放后面  */
    public static void selectionSort(int[] ary) {
        for(int i=0;i<ary.length-1;i++){
            for(int j=i+1;j<ary.length;j++){
                if(ary[i]>ary[j]){
                    int t = ary[i];  ary[i] = ary[j];  ary[j] = t;
                }
            }
        }
    }

    /**插入排序   从下标1开始 ，与它前面所有的数比较，比它大移到后面，比较到比它小的数为止，就把它插到比他小的后面*/
    public static void insertSort(int[] ary){
        int t,i,j;
        for(i=1;i<ary.length;i++){
            System.out.println(Arrays.toString(ary));
            t = ary[i];
            for(j=i-1;j>=0&&ary[j]>t;j--){
                ary[j+1] = ary[j];
            }
            ary[j+1] = t;
        }
    }

2 二分法查找法

/*
 * 二分查找  假如数组是有序且按升序排列  取到中间的下标  如果查找数大于左边的数，则左边的数无需再搜寻，直接搜寻右边的数。
 */
public static int search(int[] nums, int num) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        // 与中间值比较确定在左边还是右边区间,以调整区域
        if (num > nums[mid]) {
            low = mid + 1;
        } else if (num < nums[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

3 位移

java中有三种移位运算符:

<<      :     左移运算符，num << 1,相当于num乘以2
>>      :     右移运算符，num >> 1,相当于num除以2
>>>    :     无符号右移，忽略符号位，空位都以0补齐

1010      十进制：10     原始数         number
10100    十进制：20     左移一位       number = number << 1;
1010      十进制：10     右移一位       number = number >> 1;

对于：>>>
无符号右移，忽略符号位，空位都以0补齐
value >>> num     --   num 指定要移位值value 移动的位数。

无符号右移的规则只记住一点：忽略了符号位扩展，0补最高位  无符号右移运算符>>> 只是对32位和64位的值有意义