Bagaimana untuk menyesuaikan tatasusunan enkapsulasi kelas dalam java untuk melaksanakan operasi data

Sebagai struktur penyimpanan data asas, tatasusunan digunakan secara meluas. Tatasusunan ialah struktur data yang menggunakan ruang memori berterusan untuk menyimpan panjang tetap dan jenis data yang sama. Struktur data adalah bebas bahasa Di sini, Java digunakan untuk melaksanakan operasi berkaitan tatasusunan. Indeks tatasusunan bermula dari 0.

Permulaan tatasusunan

Terdapat dua cara untuk mencipta data, satu ialah mengisytiharkan data panjang tetap dahulu, dan kemudian memberikan nilai kepada tatasusunan , yang lain Yang pertama ialah tugasan langsung.

Jenis pertama:

数据类型[] 数组名称 = new 数据类型[长度];

Tanda [] di sini mengisytiharkan tatasusunan Selain meletakkannya selepas jenis data, [] ini juga boleh diletakkan Selepas kata nama tatasusunan, kesannya adalah sama. Jika saya mengisytiharkan tatasusunan jenis 2 dengan panjang long dan tetapkan nilai:

long[] arr = new long[2];
arr[0] = 1;
arr[1] = 2;

Jenis kedua :

数据类型[] 数组名称 = {元素1,元素2, ...};

seperti ini Apabila memulakan tatasusunan, tetapkan nilai terus kepada tatasusunan Panjang tatasusunan ditentukan oleh bilangan elemen.

Dua kelas tersuai merangkum tatasusunan untuk melaksanakan operasi data

public class MyArray {

    // 自定义数组    private long[] arr;
    // 有效数据长度    private int element;

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

    public MyArray(int maxsize){
        arr = new long[maxsize];
    }
    /**
     * 显示数组元素
     */    public void display(){
        System.out.print("[");
        for (int i = 0; i < element; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.print("]");
    }
}

2.1 Tambah elemen

Tatasusunan menggunakan ruang memori berterusan untuk menyimpan data, setiap kali ia ditambah Apabila elemen ditambah pada elemen terakhir tatasusunan semasa, elemen itu boleh ditambah sekali gus, jadi kerumitannya ialah O(1). kemudian Tambah elemen ketiga seperti berikut: 9

public void add(long value){
    arr[element] = value;
    element++;
}

2.2 Kedudukan elemen pertanyaan berdasarkan nilai

Kaedah carian ini juga dipanggil carian linear, iaitu berdasarkan gelung masuk Nilai melalui unsur-unsur untuk mendapatkan kedudukan yang sepadan Secara teori, ia mengambil masa N/2 kali untuk menanyakan unsur secara purata, jadi kerumitannya ialah O(N).

public int find(long value){
    int i;
    for (i = 0; i < element; i++) {
        if(value == arr[i]){
            break;
        }
    }
    if(i == element){
        return -1;
    }else {
        return i;
    }
}

2.3 Pertanyaan elemen mengikut indeks

Untuk mencari elemen mengikut indeks, iaitu, untuk mendapatkan elemen pada kedudukan yang sepadan, kerumitannya ialah O(1).

public long get(int index){
    if(index >= element || index < 0){
        throw new ArrayIndexOutOfBoundsException();
    }else {
        return arr[index];
    }
}

2.4 Padam elemen berdasarkan indeks

Selepas memadamkan elemen yang sepadan dengan indeks, kita perlu mengalihkan semua elemen selepas indeks ke hadapan satu kedudukan. Jika saya ingin memadamkan elemen dengan indeks 2, seperti berikut:

Secara teorinya, untuk memadam elemen secara purata, kita perlu mengalihkan N/2 kali, jadi masanya kerumitan juga O(N).

public void delete(int index){
    if(index >= element || index < 0){
        throw new ArrayIndexOutOfBoundsException();
    }else {
        for (int i = index; i < element; i++) {
            arr[index] = arr[index+1];
        }
        element --;
    }
}

2.5 Ubah suai elemen

Ubah suai elemen pada kedudukan tertentu dan ubah suai unsur sepadan terus mengikut indeks sekali, jadi kerumitan masanya ialah O(1).

public void change(int index,long newValue){
    if(index >= element || index < 0){
        throw new ArrayIndexOutOfBoundsException();
    }else {
        arr[index] = newValue;
    }
}

3 Tatasusunan tertib

Tatasusunan tertib ialah jenis tatasusunan khas Unsur-unsur dalam tatasusunan tersusun dalam susunan tertentu.

3.1 Menambah elemen

Apabila menambah elemen, tambah elemen pada kedudukan tertentu mengikut tertib. Seperti berikut, tambahkan elemen

pada tatasusunan. 33

Mula-mula, alihkan elemen dengan indeks 3 ke kedudukan indeks 4, kemudian alihkan elemen dengan indeks 2 ke kedudukan indeks 3, dan akhir sekali tambahkan 33 pada indeks 2. Secara teorinya, memasukkan elemen memerlukan elemen N/2 yang bergerak, jadi kerumitan masanya ialah O(N).

public void add(long value){
    int i;
    for (i = 0; i < element; i++) {
        if(arr[i]>value){
            break;
        }
    }

    for (int j = element; j > i; j--){
        arr[j] = arr[j-1];
    }
    arr[i] = value;
    element++;
}

3.2 Kaedah dikotomi untuk menanyakan indeks berdasarkan elemen

Dalam tatasusunan yang tidak tertib, gunakan kaedah linear untuk mencari elemen yang berkaitan Kaedah linear ialah mencari satu persatu mengikut indeks. Tatasusunan yang diisih boleh menggunakan kaedah dikotomi untuk mencari unsur Dikotomi bermaksud membahagikan tatasusunan kepada dua dari tengah, menentukan tatasusunan mana elemen itu berada, dan kemudian mengulangi operasi ini.

Andaikan terdapat tatasusunan dengan elemen

dan kandungan tatasusunan ialah urutan tertib 0-7 Untuk mencari elemen 5, ia dibahagikan kepada dua tatasusunan 0-3 dan 4-. 7 buat pertama kalinya. Kemudian bahagikan 4-7 kepada dua tatasusunan 4-5 dan 6-7, dan akhirnya bahagikan 4-5 kepada 4 dan 5 untuk menanyakan elemen tertentu Dengan cara ini, selepas membahagikan 3 kali, anda boleh bertanya tatasusunan dengan panjang 8. Untuk elemen tertentu, kerumitannya ialah O(logN) (asas logN dalam komputer umumnya merujuk kepada 2, yang bermaksud kuasa 2 adalah sama dengan n). 8

public int search(long value){
    // 中间值    int middle = 0;
    // 最小值    int low = 0;
    // 最大值    int pow = element;
    while (true){
        middle = (low + pow) / 2;
        if(arr[middle] == value){
            return middle;
        }else if (low > pow){
            return -1;
        }else{
            if(arr[middle] > value){
                pow = middle - 1;
            }else{
                low = middle + 1;
            }
        }
    }
}

Empat Ringkasan

Semakin rendah kerumitan, semakin baik algoritmanya, jadi O(1) > O(N) > 2).

算法	复杂度
线性查找	O(N)
二分法查找	O(logN)
无序数组插入	O(1)
有序数组插入	O(N)
无序数组删除	O(N)
有序数组删除	O(N)

1. Sisipan tatasusunan tidak tertib adalah pantas, carian dan pemadaman adalah perlahan

2. Carian tatasusunan tersusun adalah pantas, pemasukan dan pemadaman adalah perlahan

Atas ialah kandungan terperinci Bagaimana untuk menyesuaikan tatasusunan enkapsulasi kelas dalam java untuk melaksanakan operasi data. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!