Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

tabel linier

kami ingin berbicaraTabel urutan, kita harus membicarakan tabel linier terlebih dahulu, karena tabel sekuensial adalah jenis tabel linier.

Definisi tabel linier

Seperti namanya, tabel linier adalah tabel yang mengatur data seperti garis.
Hal ini dapat dipahami dengan memikirkan antrian dalam kenyataan.

Karakteristik tabel linier:

• Ada keteraturan antar elemen data tabel linier.
• Kecuali unsur pertama dan unsur terakhir, setiap unsur mempunyai pendahulu dan penerus.

Tabel urutan

Tabel urutan menggunakan paragrafAlamat fisik berurutanUnit penyimpanannya seperti orang-orang yang berbaris bersebelahan.
Struktur linier yang menyimpan elemen data secara berurutan, biasanya menggunakanHimpunanpenyimpanan.
Menyelesaikan penambahan, penghapusan, pengecekan dan modifikasi data pada array.

Implementasi antarmuka tabel urutan

Implementasikan tabel urutan sendiri (penyimpanan data tipe int), gunakan tabel urutan sebagai kelas, kami mengimplementasikan beberapa antarmuka, yaitu beberapametode anggotaUntuk mewujudkan penambahan, penghapusan, pengecekan dan modifikasi data.

public class SeqList {
     private int[] elem;
     private int usedSize;
     // 默认构造方法
     SeqList(){   }
     // 将顺序表的底层容量设置为initcapacity
     SeqList(int initcapacity){   }
     // 新增元素,默认在数组最后新增
     public void add(int data) { }
     // 在 pos 位置新增元素
     public void add(int pos, int data) { }
     // 判定是否包含某个元素
     public boolean contains(int toFind) { return true; }
     // 查找某个元素对应的位置
     public int indexOf(int toFind) { return -1; }
     // 获取 pos 位置的元素
     public int get(int pos) { return -1; }
     // 给 pos 位置的元素设为 value
     public void set(int pos, int value) {   }
     //删除第一次出现的关键字key
     public void remove(int toRemove) {   }
     // 获取顺序表长度
     public int size() { return 0; }
     // 清空顺序表
     public void clear() {   }
     
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Konstruktor bawaan

Secara default, kami awalnya membuka 10 ruang data.

private static final int DEFAULT_SIZE = 10;
    public SeqList() {
        this.elem= new int[DEFAULT_SIZE];
    }
1
2
3
4

Atur kapasitas dasar tabel urutan ke initcapacity

Masukkan panjang array dan gunakan panjang array untuk membuka ruang.

private static final int DEFAULT_SIZE = 10;
    public SeqList(int initcapacity) {
        this.elem= new int[initcapacity];
    }
1
2
3
4

sumbat ekor

Elemen baru ditambahkan di akhir array secara default.
Hal-hal yang perlu dipertimbangkan:

• Periksa apakah tabel urutan saat ini sudah penuh. Jika sudah penuh, tambahkan spasi.
• Sebuah elemen ditambahkan dan UsedSize bertambah 1.

 public void add(int data) {
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = data;
    }
     /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Tambahkan elemen pada posisi pos

Sisipkan elemen di subskrip pos.
Tindakan pencegahan:

• Periksa apakah tabel urutan saat ini sudah penuh. Jika sudah penuh, tambahkan spasi.
• Apakah posisi pos yang diberikan sah? Jika tidak, pengecualian akan diberikan.
• Gunakan loop mundur ke depan untuk memindahkan elemen setelah posisi pos ke belakang.
• Sebuah elemen ditambahkan dan UsedSize bertambah 1.

private boolean checkPosInAdd(int pos) throws PosIllegalException{

        if(pos < 0 || pos > usedSize){
            throw new PosIllegalException("位置不合法");
        }
        return true;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try{
            if(checkPosInAdd(pos)){
                if(isFull()){
                    elem = Arrays.copyOf(elem,elem.length * 2);
                }
                for (int i = usedSize; i > pos ; i--) {
                    elem[i] = elem[i-1];
                }
                elem[pos] = data;
                usedSize++;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Tentukan apakah suatu elemen terkandung

Lihat apakah data yang diberikan disertakan dalam tabel urutan.
Ulangi saja secara langsung, kembalikan nilai true jika Anda menemukannya, dan kembalikan salah jika Anda tidak menemukannya.

public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8

Temukan posisi yang sesuai dengan suatu elemen

Lihatlah indeks data yang diberikan dalam tabel urutan ini.
Cukup ulangi secara langsung dan temukan subskrip pengembalian tanpa mengembalikan -1.

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8

Dapatkan elemen di posisi pos

Keluarkan elemen pada posisi pos.
Tindakan pencegahan:

• Periksa apakah pos itu legal

public int get(int pos) {
        try{
            if(checkPosInAdd(pos)){
                return elem[pos];
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10

Atur elemen pada posisi pos ke nilai

Ubah elemen posisi pos.
Tindakan pencegahan:

• Periksa apakah pos itu legal.

public void set(int pos, int value) {
        try{
            if(checkPosInAdd(pos)){
                elem[pos] = value;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
    }
1
2
3
4
5
6
7
8
9

Hapus kemunculan pertama dari kunci kata kunci

Hapus kemunculan kunci yang pertama.
Tindakan pencegahan:

• Ulangi pencarian.
• Gunakan elemen setelah kunci yang ditemukan untuk menutupinya satu per satu ke arah depan.
• ukuran yang digunakan berkurang 1.

public void remove(int key) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == key){
                for (int j = i; j < usedSize - 1; j++) {
                    elem[j] = elem[j + 1];
                }
                usedSize--;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

Dapatkan panjang tabel urutan

Memperoleh panjang tabel urutan di sini mengacu pada jumlah data yang berguna, yaitu UsedSize.

public int size() {
        return usedSize;
    }
1
2
3

Hapus daftar urutan

Atur isi tabel urutan menjadi kosong.
Tindakan pencegahan:

• Karena tabel sekuensial sebenarnya menyimpan generik, elemen disetel ke kosong saat dilintasi satu per satu. Elemen tersebut diganti dengan menyetelnya ke 0 di bawah.
• UsedSize juga diatur ke 0.

public void clear() {
        for (int i = 0; i < usedSize; i++) {
            elem[i] = 0;
        }
        usedSize = 0;
    }
1
2
3
4
5
6

Daftar Array di Java

Kelas ArrayList disediakan di Java untuk mewakili daftar berurutan.

antarmuka yang diimplementasikan

Deskripsi Antarmuka:

1. Antarmuka RandomAccess menunjukkan dukungan untuk akses acak.
2. Antarmuka Cloneable menunjukkan dukungan untuk kloning.
3. Antarmuka Serializable menunjukkan dukungan untuk serialisasi.

Metode konstruksi

Java menyediakan 3 metode konstruksi seperti yang ditunjukkan pada tabel:

Metode umum

Metode umum yang disediakan serupa dengan yang kami terapkan di atas.

Keuntungan dan Kerugian Daftar Urutan

keuntungan

Kelebihan tabel sequence adalah sebagai berikut:

1. Akses acak didukung.
2. Meminta subskrip tertentu dilakukan dengan cepat.

kekurangan

1. Jika tidak ada cukup ruang, maka perlu diperluas, dan akan terjadi pemborosan memori.
2. Penyisipan dan penghapusan pada header dan tengah akan memindahkan data.

praktik

Tautan ke latihan ada di bawah:
Segitiga Yang Hui