Javaデータ構造とアルゴリズム(二)——配列

配列の用途は何ですか.--30個の数を大小に並べる必要がある場合は、配列のようなデータ構造で格納するのが良い選択で、クラスの担任である場合は、学生の欠勤回数を記録するたびに配列も役立ちます.配列は挿入、削除、検索などを行うことができます.
1)作成とメモリ割当て
Javaには2つのデータ型、基本型とオブジェクト型があり、参照型とも呼ばれ、Javaでは配列をオブジェクトとし、配列を作成する際にnewオペレータを使用します.

int array[] = new int[10];

オブジェクトである以上、arrayは配列の参照であり、Javaプログラミング思想(一)によると、すべてがオブジェクトのメモリ割り当てであり、arrayはスタックに空間を開き、配列が格納されたアドレスを格納し、本当にオブジェクトを保存する場所は正しい.new操作はスタックに必要な空間を開き、arrayはヘッダアドレスを指す.
初期化:

public class UseArray {
    public static void main(String[] args) {
        int array[] = new int[10];
        System.out.println(array[2]);
        UseArray a[] = new UseArray[12];
        System.out.println(a[1]);
        int array2[] ={1,2,3,4,5,5,6};
    }
}

new後の配列内の値はデフォルトで0に初期化され、オブジェクトの初期化は空です.null、もちろん{}で初期化することもできます.
2)配列パッケージング後の使用

public class UseArray {
    private int[] array;
    private int number = 0;
    public UseArray(int max){
        array = new int[max];
    }
    public void insert(int value){
        array[number] = value;
        number++;
    }
    public int find(int value){
        int index = 0;
        for (int i= 0; i < number; i++) {
            if(array[i]==value)
                return index;
        }
        return number;
    }
    
    public boolean delete(int value){
        int index = find(value);
        if(index != number){
            for (int i = index; i < number-1; i++) {
                array[i] = array[i+1];
            }
            number--;
            return true;
        }
        return false;
    }
    
    public void display(){
        for (int i = 0; i < number; i++) {
            System.out.printf(array[i]+" ");
        }
    }
    public static void main(String[] args) {
        UseArray ua  = new UseArray(5);
        ua.insert(1);
        ua.insert(2);
        ua.insert(6);
        ua.insert(7);
        ua.insert(3);
        
        ua.display();
        if(ua.find(5) != ua.number){
            System.out.println();
        }else{
            System.out.println("not found!");
        }
        if(ua.delete(5)!=true){
            System.out.println("can not delete!");
        }
        ua.display();
    }
}

配列全体をカプセル化し、配列の個数の代わりにnumberを使用し、データを挿入するときにどの下付き挿入を気にする必要はありません.もちろん、具体的な下付きの方法をカスタマイズすることもできます.
方法は比較的簡単で紹介しませんが、deleteでは削除要素から左に移動するだけなのでnumberが減少していますが、最後の要素は削除されていません.display出力展示の時に隠れているだけですが、次にエレメントを挿入すると、最後のエレメントの位置に新しいエレメントが置き換えられます.
3)検索最適化——二分検索

public int find(int value){
        int start = 0;
        int end = number-1;
        while(end>start){
            int index =(end + start)/2; 
            if(array[index]==value){
                return index;
            }else if(array[index] >value){
                end = index-1;
            }else { 
                start = index+1;
            }
        }
        return number;
    }

二分検索の前提は配列が秩序化されていることです.最初はindexがendとstartと書いて減少し、死の循環をもたらした.実は加算が必要です.1,2,3,6,7.index=2、value=7、3は7未満、start=3であると、indexは3と4の間の中間数を要するので、加算して2,6で7未満、start=4、findから7で割る.
ソートは、Javaデータ構造とアルゴリズム(3)--簡単なソートです.
オブジェクトを格納すると原理は同じです.
4)大O表現
Nをデータ総数とし,1つのデータを挿入する時間をKとする.
では、線形検索総時間T=K*N/2は、検索すると比較数の約半分になるからです.
二分検索するとT=k*log 2(N).
大きなO表現では,Oはorder ofと見なすことができ,おおよその意味であり,k/2も定数であるため,O(N)と見なすことができる.
配列の欠点は、サイズが固定され、検索が遅いことです.百万レベルのデータを常に検索する場合は、配列を使用しますか?いいえ、データ構造の選択は具体的な実情と結びつけて、最大の効率値を達成しなければなりません.