数据结构与算法01 之数组

       数组是应用最广泛的数据存储结构。它被植入到大部分的编程语言中，由于数组十分易懂，所以在这里就不赘述，主要附上两端代码，一个是普通的数组（无序数组），另一个是有序数组。有序数组是按关键字升序（或降序）排列的，这种排列使快速查找数据项成为可能，即可以使用二分查找。

    普通数组的java代码：

 

public class GeneralArray {
    private int[] a;
    private int size; //数组的大小
    private int nElem; //数组中有多少项
    public GeneralArray(int max) { //初始化数组
        this.a = new int[max];
        this.size = max;
        this.nElem = 0;
    }
    public boolean find(int searchNum) { //查找某个值
        int j;
        for(j = 0; j < nElem; j++){
            if(a[j] == searchNum)
                break;
        }
        if(j == nElem)
            return false;
        else
            return true;
    }
    public boolean insert(int value) { //插入某个值
        if(nElem == size){
            System.out.println("数组已满！");
            return false;
        }
        a[nElem] = value;
        nElem++;
        return true;
    }
    public boolean delete(int value) {//删除某个值
        int j;
        for(j = 0; j < nElem; j++) {
            if(a[j] == value) {
                break;
            }
        }
        if(j == nElem)
            return false;
        if(nElem == size) {
            for(int k = j; k < nElem - 1; k++) {
                a[k] = a[k+1];
            }
        }
        else {
            for(int k = j; k < nElem; k++) {
                a[k] = a[k+1];
            }
        }
        nElem--;
        return true;
    }
    public void display() { //打印整个数组
        for(int i = 0; i < nElem; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}

 

    有序数组的java代码：

public class OrderedArray {
    private long[] a;
    private int size; //数组的大小
    private int nElem; //数组中有多少项
    public OrderedArray(int max) { //初始化数组
        this.a = new long[max];
        this.size = max;
        this.nElem = 0;
    }
    public int size() { //返回数组实际有多少值
        return this.nElem;
    }
//--------------二分法查找某个值----------------//
    public int find(long searchNum) {
        int lower = 0;
        int upper = nElem - 1;
        int curr;
        while(true) {
            curr = (lower + upper) / 2;
            if(a[curr] == searchNum)
                return curr;
            else if(lower > upper)
                return -1;
            else {
                if(a[curr] < searchNum)
                    lower = curr + 1;
                else
                    upper = curr - 1;
            }

        }
    }
    public boolean insert(long value) { //插入某个值
        if(nElem == size){
            System.out.println("数组已满！");
            return false;
        }
        int j;
        for(j = 0; j < nElem; j++){
            if(a[j] > value)
                break;
        }

        for(int k = nElem; k > j; k--) {
            a[k] = a[k-1];
        }
        a[j] = value;
        nElem++;
        return true;
    }
    public boolean delete(long value) { //删除某个值
        int j = find(value);
        if(j  == -1){
            System.out.println("没有该元素！");
            return false;
        }
        if(nElem == size) {
            for(int k = j; k < nElem - 1; k++) {
                a[k] = a[k+1];
            }
            a[nElem-1] = 0;
        }
        else {
            for(int k = j; k < nElem; k++) {
                a[k] = a[k+1];
            }
        }
        nElem--;
        return true;
    }
    public void display() { //打印整个数组
        for(int i = 0; i < nElem; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}

    对于数组这种数据结构，线性查找的话，时间复杂度为O(N)，二分查找的话时间为O(longN)，无序数组插入的时间复杂度为O(1)，有序数组插入的时间复杂度为O(N)，删除操作的时间复杂度均为O(N)。

 

http://blog.csdn.net/eson_15/article/details/51126182