面试常考的数据结构Java实现

1、线性表

2、线性链表

3、栈

4、队列

5、串

6、数组

7、广义表

8、树和二叉树

二叉树：每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质：

　　性质1：在二叉树的第 i 层上至多有2i-1个结点。

　　性质2：深度为k的二叉树至多有2k-1个结点（k>=1）。

　　性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

满二叉树：一棵深度为k且有2k-1个结点的二叉树。每一层上的结点数都是最大结点数。

完全二叉树：如果对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。

特点:（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次必为lh+1。

　　性质4：具有n个结点的完全二叉树的深度为log2n+1（2为下标，取log2n最小整数）。

　　性质5：如果对一棵有n个结点的完全二叉树（其深度为log2n+1）（取log2n最小整数）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），则对任一结点i（1<=i<=n），有：

　　　　（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点i/2（取最小整数）。

　　　　（2）如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。

　　　　（3）如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。

最优二叉树（赫夫曼树）：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；（2）若它的右子树上所有结点的值均大于它的根节点的值；（3）它的左、右子树也分别为二叉排序树。

平衡二叉树：又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度只差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。

红黑树：红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

• 性质 1：每个节点要么是红色，要么是黑色。
• 性质 2：根节点永远是黑色的。
• 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
• 性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
• 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

Java 中实现的红黑树可能有如图所示结构：

备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。

根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。

性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 – 黑节点 – 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 – 红节点 – 黑节点 – 红节点 – 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。

B-树：B-数是一种平衡的多路查找树，一棵m阶B-树，或为空树，或为满足下列特性的m叉树：(m≥3)

(1)根结点只有1个，关键字字数的范围[1,m-1]，分支数量范围[2,m]；

(2)除根以外的非叶结点，每个结点包含分支数范围[[m/2],m]，即关键字字数的范围是[[m/2]-1,m-1]，其中[m/2]表示取大于m/2的最小整数；

(3)非叶结点是由叶结点分裂而来的，所以叶结点关键字个数也满足[[m/2]-1,m-1]；

(4)所有的非终端结点包含信息：(n，P₀，K₁，P₁，K₂，P₂，……，K_n，P_n)，

其中K_i为关键字，P_i为指向子树根结点的指针，并且P_i-1所指子树中的关键字均小于K_i，而P_i所指的关键字均大于K_i（i=1，2，……，n），n+1表示B-树的阶，n表示关键字个数，即[ceil(m / 2)-1]<= n <= m-1；

(5)所有叶子结点都在同一层，并且指针域为空，具有如下性质：

　　根据B-树定义，第一层为根有一个结点，至少两个分支，第二层至少2个结点，i≥3时，每一层至少有2乘以([m/2])的i-2次方个结点([m/2]表示取大于m/2的最小整数)。若m阶树中共有N个结点，那么可以推导出N必然满足N≥2*(([m/2])的h-1次方)-1 (h≥1)，因此若查找成功，则高度h≤1+log[m/2](N+1)/2，h也是磁盘访问次数(h≥1)，保证了查找算法的高效率。

    B+树：B+树是B-树的变体，也是一种多路搜索树，其定义基本与B-树同，除了：

1）非叶子结点的子树指针与关键字个数相同；

2）非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

3）为所有叶子结点增加一个链指针；

4）所有关键字都在叶子结点出现；

9、图

各种排序算法的比较：

一、插入排序

　　1、直接插入

　　稳定，平均和最坏都是O(n2)。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

　　2、Shell排序

　　不稳定，平均O(n3/2)，最坏O(n2)。它的基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

代码实现：

package com.yyq;import java.util.Arrays;/**
 * Created by Administrator on 2015/9/9.
 */
public class InsertSort {
    public static void insertDirectlySort(int a[]) {
        if (a == null) return;
        int len = a.length;
        try {
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len && j > 0; j--) {
                    if (a[j] < a[j - 1]) {
                        int temp = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = temp;
                    }
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }    public static void shellSort(int data[]) {
        if (data == null) return;
        int j = 0;
        int temp = 0;
        int len = data.length / 2;
        for (int increment  = len; increment > 0; increment /= 2) {
            for (int i = increment; i < data.length; i++) {
                temp = data[i];
                for (j = i; j >= increment; j -= increment) {
                    if(temp < data[j - increment]){
                        data[j] = data[j - increment];
                    }else{
                        break;
                    }
                }
                data[j] = temp;
            }
        }
    }    public static void Test(int a[],int b[]) {
        System.out.println("The Source Secquence:");
        if (a == null) return;
        System.out.println(Arrays.toString(a));        insertDirectlySort(a);
        System.out.println("InsertDirectlySort Result: ");
        System.out.println(Arrays.toString(a));        shellSort(b);
        System.out.println("ShellSort Result:");
        System.out.println(Arrays.toString(b));
        System.out.println();
    }
    public static void main(String[] args){
        int a1[] = null;
        int a2[] = {1};
        int a3[] = {3, 6, 1, 8, 2, 9, 4};
        int a4[] = {1, 3, 5, 7, 9};
        int a5[] = {6, 9, 4, 8, -1};
        int a6[] = {9, 5, 4, 2, 1};
        int b1[] = null;
        int b2[] = {1};
        int b3[] = {3, 6, 1, 8, 2, 9, 4};
        int b4[] = {1, 3, 5, 7, 9};
        int b5[] = {6, 9, 4, 8, -1};
        int b6[] = {9, 5, 4, 2, 1};
        Test(a1,b1);
        Test(a2,b2);
        Test(a3,b3);
        Test(a4,b4);
        Test(a5,b5);
        Test(a6,b6);
    }
}

输出结果：

二、选择排序

　　1、直接选择

　　不稳定，平均和最坏都是O(n2)。是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此类推，直到所有元素均排序完毕。

　　2、堆排序

　　不稳定，平均和最坏都是O(nlogn)，辅助存储O(1)。利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

package com.yyq;import java.util.Arrays;/**
 * Created by Administrator on 2015/9/9.
 */
public class SelectSort {
    public static void selectDirectlySort(int[] a) {
        if (a == null) return;
        int min = 0;
        int i = 0;
        int j = 0;
        int index = 0;
        int len = a.length;
        for (i = 0; i < len - 1; i++) {
            min = a[i];
            index = i;
            for (j = i + 1; j < len; j++) {
                if (a[j] < min) {
                    min = a[j];
                    index = j;
                }
            }
            a[index] = a[i];
            a[i] = min;
        }
    }    public static void heapSort(int[] array) {
        if (array == null) return;
        buildHeap(array);//构建堆
        int n = array.length;
        int i = 0;
        for (i = n - 1; i >= 1; i--) {
            swap(array, 0, i);
            heapify(array, 0, i);
        }
    }
    //构建
    public static void buildHeap(int[] array) {
        int n = array.length;//数组中元素的个数
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(array, i, n);
    }
    public static void heapify(int[] A, int idx, int max) {
        int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）
        int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）
        int largest = 0;//寻找3个节点中最大值节点的下标
        if (left < max && A[left] > A[idx])
            largest = left;
        else
            largest = idx;
        if (right < max && A[right] > A[largest])
            largest = right;
        if (largest != idx) {
            swap(A, largest, idx);
            heapify(A, largest, max);
        }
    }
    public static void swap(int[] array, int i, int j) {
        int temp = 0;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }    public static void Test(int a[], int b[]) {
        System.out.println("The Source Secquence:");
        if (a == null) return;
        System.out.println(Arrays.toString(a));        selectDirectlySort(a);
        System.out.println("BubbleSort Result: ");
        System.out.println(Arrays.toString(a));        heapSort(b);
        System.out.println("QuickSort Result:");
        System.out.println(Arrays.toString(b));
        System.out.println();
    }    public static void main(String[] args) {
        int a1[] = null;
        int a2[] = {1};
        int a3[] = {3, 6, 1, 8, 2, 9, 4};
        int a4[] = {1, 3, 5, 7, 9};
        int a5[] = {6, 9, 4, 8, -1};
        int a6[] = {9, 5, 4, 2, 1};
        int b1[] = null;
        int b2[] = {1};
        int b3[] = {3, 6, 1, 8, 2, 9, 4};
        int b4[] = {1, 3, 5, 7, 9};
        int b5[] = {6, 9, 4, 8, -1};
        int b6[] = {9, 5, 4, 2, 1};
        Test(a1, b1);
        Test(a2, b2);
        Test(a3, b3);
        Test(a4, b4);
        Test(a5, b5);
        Test(a6, b6);
    }
}

输出结果：

三、交换排序

　　1、冒泡排序

　　稳定，平均和最坏都是O(n2)。是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

　　2、快速排序

　　不稳定，平均O(nlogn)，最坏O(n2)，辅助存储O(logn)。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

package com.yyq;import java.util.Arrays;/**
 * Created by Administrator on 2015/9/10.
 */
public class ChangeSort {
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void bubbleSort(int[] array){
        if (array == null) return;
        int len = array.length;;
        for(int i = 0; i < len-1; i++){
            for (int j = len-1; j > i; j--){
                if (array[j] < array[j-1] ){
                    swap(array,j,j-1);
                }
            }
        }
    }
    public static void quickSort(int[] array, int low, int high){
        if (array == null || low < 0 || high < 0 || low >= array.length) return;
        int pivotloc = partition(array, low, high);
        if(low < high){
            quickSort(array, low, pivotloc-1);
            quickSort(array,pivotloc+1,high);
        }
    }
    public static int partition(int[] array, int low, int high){
        int pivokey = array[low];
        while(low < high){
            while(low < high && array[high] >= pivokey)
            {
                high--;
            }
            array[low] = array[high];
            while(low < high && array[low] <= pivokey)
            {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = pivokey;
        return low;
    }
    public static void Test(int a[],int b[]) {
        System.out.println("The Source Secquence:");
        if (a == null) return;
        System.out.println(Arrays.toString(a));        bubbleSort(a);
        System.out.println("BubbleSort Result: ");
        System.out.println(Arrays.toString(a));        quickSort(b, 0, b.length-1);
        System.out.println("QuickSort Result:");
        System.out.println(Arrays.toString(b));
        System.out.println();
    }
    public static void main(String[] args){
        int a1[] = null;
        int a2[] = {1};
        int a3[] = {3, 6, 1, 8, 2, 9, 4};
        int a4[] = {1, 3, 5, 7, 9};
        int a5[] = {6, 9, 4, 8, -1};
        int a6[] = {9, 5, 4, 2, 1};
        int b1[] = null;
        int b2[] = {1};
        int b3[] = {3, 6, 1, 8, 2, 9, 4};
        int b4[] = {1, 3, 5, 7, 9};
        int b5[] = {6, 9, 4, 8, -1};
        int b6[] = {9, 5, 4, 2, 1};
        Test(a1,b1);
        Test(a2,b2);
        Test(a3,b3);
        Test(a4,b4);
        Test(a5,b5);
        Test(a6,b6);
    }
}

输出结果：

四、归并排序(台湾译作：合并排序)：

　　稳定，平均和最坏都是O(nlogn)，辅助存储O(n)。是建立在归并操作上的一种有效的排序算法。将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

package com.yyq;import java.util.Arrays;/**
 * Created by Administrator on 2015/9/10.
 */
public class MergingSort {    public static void Test(int a[]) {
        System.out.println("The Source Secquence:");
        if (a == null) return;
        System.out.println(Arrays.toString(a));        mergeSort(a,0,a.length-1);
        System.out.println("MergeSort Result: ");
        System.out.println(Arrays.toString(a));
        System.out.println();
    }
    public static void main(String[] args){
        int a1[] = null;
        int a2[] = {1};
        int a3[] = {3, 6, 1, 8, 2, 9, 4};
        int a4[] = {1, 3, 5, 7, 9};
        int a5[] = {6, 9, 4, 8, -1};
        int a6[] = {9, 5, 4, 2, 1};
        Test(a1);
        Test(a2);
        Test(a3);
        Test(a4);
        Test(a5);
        Test(a6);
    }
    public static int[] mergeSort(int[] nums, int low, int high) {
        if (nums == null || low < 0 || low > nums.length-1 || high < 0) return nums;
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(nums, low, mid);
            // 右边
            mergeSort(nums, mid + 1, high);
            // 左右归并
            merge(nums, low, mid, high);
        }
        return nums;
    }
    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }
}

输出结果：

五、基数排序又称“桶子法”：

　　稳定，平均和最坏都是O(d(n+rd))，对于n个记录，每个记录含d个关键字（即位数），每个关键字的取值范围为rd个值。它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

package com.yyq;import java.util.Arrays;/**
 * Created by Administrator on 2015/9/10.
 */
public class RadixSort {
    public static void radixSort(int[] array, int num, int radix) {
        if (array == null) return;
        int k = 0;
        int n = 1;
        int index = 1;
        int len = array.length;
        //分成nums.length个桶
        int[][] radixArray = new int[radix][radix];
        //每个桶放的个数组成的数组
        int[] tempArray = new int[radix];
        for (int i = 0; i < tempArray.length; i++){
            tempArray[i] = 0;
        }
        //还在位数内
        while (index <= num) {
            for (int i = 0; i < len; i++) {
                //个,十,百,千...
                int temp = (array[i] / n) % 10;
                //存入特定桶的特定位置
                radixArray[temp][tempArray[temp]] = array[i];
                tempArray[temp] = tempArray[temp] + 1;
            }
            for (int i = 0; i < radix; i++) {
                if (tempArray[i] != 0) {
                    for (int j = 0; j < tempArray[i]; j++) {
                        //数组重组
                        array[k] = radixArray[i][j];
                        k++;
                    }
                    //重置,以防下次循环时数据出错
                    tempArray[i] = 0;
                }
            }
            //重置,以防下次循环时数据出错
            k = 0;
            //进位
            n *= 10;
            index++;
        }
    }    // 基数排序的实现
    public static void Test(int a[]) {
        System.out.println("The Source Secquence:");
        if (a == null) return;
        System.out.println(Arrays.toString(a));
        int num = 0;
        int max_num = num;
        for (int i = 0; i < a.length; i++){
            int temp = a[i];
            while(temp != 0){
                num++;
                temp = temp / 10;
            }
            if (num > max_num){
                max_num = num;
            }
            num = 0;
        }
        System.out.println("The largest number'length is:"+max_num);
        radixSort(a, max_num,10);
        System.out.println("RadixSort Result: ");
        System.out.println(Arrays.toString(a));
        System.out.println();
    }    public static void main(String[] args) {
        int a1[] = null;
        int a2[] = {1};
        int a3[] = {3, 6, 1, 8, 2, 9, 4};
       int a4[] = {110, 35, 4855, 2726,562599};
        int a5[] = {278, 109, 930, 184, 505, 269, 800, 831};
        int a6[] = {9, 35, 4, 2, 1};
        Test(a1);
        Test(a2);
        Test(a3);
        Test(a4);
        Test(a5);
        Test(a6);
    }
}

输出结果：