Game.of.Thrones

數(shù)據(jù)結構研究的是數(shù)據(jù)如何在計算機中進行組織和存儲，使得我們可以高效的獲取數(shù)據(jù)或者修改數(shù)據(jù)。

1. 無序數(shù)組

package com.lq.dataStruct;

public class MyArray {
    private long[] arr;
    //表示有效數(shù)據(jù)的長度
    private int elements;

    public MyArray() {
        arr = new long[50];
    }

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

    /**
     * 添加數(shù)據(jù)
     */
    public void insert(long value){
        arr[elements] = value;
        elements++;
    }

    /**
     * 顯示數(shù)據(jù)
     */
    public void display(){
        System.out.print("[");
        for (int i = 0;i < elements;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print("]");
    }

    /**
     * 查找數(shù)據(jù)(根據(jù)元素查找)
     */
    public int search(long value){
        int i;
        for (i = 0;i < elements;i++){
            if (value == arr[i]){
                break;
            }
        }
        //是否查到最后一個了
        if (i == elements){
            return -1;  //查找不到
        }else {
            return i;
        }
    }
    /**
     * 根據(jù)索引查找
     */
    public long get(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            return arr[index];
        }
    }
    /**
     * 刪除數(shù)據(jù)
     */
    public void delete(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            for (int i = index;i < elements;i++){
                arr[index] = arr[index+1];
            }
            elements--;
        }
    }
    /**
     * 更新數(shù)據(jù)
     */
    public void update(int index,long newvalue){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            arr[index] = newvalue;
        }
    }
}

2. 有序數(shù)組(只在添加數(shù)據(jù)的時候做了改動)

package com.lq.dataStruct;

/**
 * 有序數(shù)組
 * Created by lq
 * 2018/4/4 23.28
 */
public class MyOrderArray {
    private long[] arr;
    //表示有效數(shù)據(jù)的長度
    private int elements;

    public MyOrderArray() {
        arr = new long[50];
    }

    public MyOrderArray(int maxsize) {
        arr = new long[maxsize];
    }

    /**
     * 添加數(shù)據(jù)
     */
    public void insert(long value){
        int i;
        for (i = 0;i<elements;i++){
            if (arr[i] > value){
                break;
            }
        }
        for (int j = elements;j>i;j--){
            arr[j] = arr[j-1];
        }
        arr[i] = value;
        elements++;
    }
    /**
     * 二分法查找(前提是有序數(shù)組)
     */
    public int binarySearch(long value){
        int pow = elements;
        int low = 0;
        int middle;
        while (true){
            middle = (pow+low)/2;
            if (arr[middle] == value){
                return middle;
            }else {
                if (arr[middle]>value){
                    pow = middle - 1;  //如果數(shù)組中間的值比value大，middle-1
                }else {
                    low = middle + 1; //如果小，最小屆加一
                }
            }
        }
    }

    /**
     * 顯示數(shù)據(jù)
     */
    public void display(){
        System.out.print("[");
        for (int i = 0;i < elements;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print("]");
    }

    /**
     * 查找數(shù)據(jù)(根據(jù)元素查找)
     */
    public int search(long value){
        int i;
        for (i = 0;i < elements;i++){
            if (value == arr[i]){
                break;
            }
        }
        //是否查到最后一個了
        if (i == elements){
            return -1;  //查找不到
        }else {
            return i;
        }
    }
    /**
     * 根據(jù)索引查找
     */
    public long get(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            return arr[index];
        }
    }
    /**
     * 刪除數(shù)據(jù)
     */
    public void delete(int index){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            for (int i = index;i < elements;i++){
                arr[index] = arr[index+1];
            }
            elements--;
        }
    }
    /**
     * 更新數(shù)據(jù)
     */
    public void update(int index,long newvalue){
        if (index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            arr[index] = newvalue;
        }
    }
}

3.測試

public class TestMyArray {
    public static void main(String[] args) {

//        MyArray array = new MyArray();
//        array.insert(10);
//        array.insert(20);
//        array.insert(30);
//
//        array.display();
//        System.out.println(array.search(20));
//        array.update(1,80);
//        array.display();
//        array.delete(1);
//        array.display();

        MyOrderArray orderArray = new MyOrderArray();
        orderArray.insert(10);
        orderArray.insert(20);
        orderArray.insert(30);
        orderArray.insert(20);
        orderArray.insert(0);
        orderArray.display();

        System.out.println(orderArray.binarySearch(30));

    }
}

總結

數(shù)組最大的優(yōu)勢就是：快速查詢，所以數(shù)組最好應用于“索引有語義”的情況