【數據結構與算法01】數組 - shanheyongmu－IT工程師數位筆記本

文章出處

數組是應用最廣泛的數據存儲結構。它被植入到大部分的編程語言中，由于數組十分易懂，所以在這里就不贅述，主要附上兩端代碼，一個是普通的數組，另一個是有序數組。有序數組是按關鍵字升序（或降序）排列的，這種排列使快速查找數據項成為可能，即可以使用二分查找。

普通數組的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("");  
    }  
}