Condivisione della tecnologia

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

tavola lineare

vogliamo parlareTabella delle sequenze, dobbiamo prima parlare delle tabelle lineari, perché le tabelle sequenziali sono un tipo di tabelle lineari.

Definizione di tavola lineare

Come suggerisce il nome, una tabella lineare è una tabella che organizza i dati come linee.
Lo si capisce pensando di fare la fila nella realtà.

Caratteristiche delle tavole lineari:

• Esiste un ordine tra gli elementi dati di una tabella lineare.
• Ad eccezione del primo e dell'ultimo elemento, ogni elemento ha un predecessore e un successore.

Tabella delle sequenze

La tabella di sequenza è un paragrafoGli indirizzi fisici sono consecutiviI contenitori sono come persone in fila una accanto all’altra.
Una struttura lineare che memorizza gli elementi di dati in sequenza, solitamente utilizzandovettoremagazzinaggio.
Completare l'aggiunta, la cancellazione, il controllo e la modifica dei dati sull'array.

Implementazione dell'interfaccia della tabella di sequenza

Implementa tu stesso una tabella di sequenza (dati di tipo storage int), utilizza la tabella di sequenza come classe, implementiamo alcune interfacce, ovvero alcunemetodo dei membriPer realizzare l'integrazione, la cancellazione, il controllo e la modifica dei dati.

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

Costruttore predefinito

Per impostazione predefinita, inizialmente apriamo 10 spazi di dati.

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

Imposta la capacità sottostante della tabella di sequenza su initcapacity

Passa la lunghezza dell'array e usa la lunghezza dell'array per liberare spazio.

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

tappo di coda

Per impostazione predefinita, i nuovi elementi vengono aggiunti alla fine dell'array.
Punti da considerare:

• Controlla se la tabella della sequenza corrente è piena. Se è piena, aggiungi spazio.
• Viene aggiunto un elemento e usedSize viene aumentato di 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

Aggiungi elemento nella posizione pos

Inserisci l'elemento nel pedice pos.
Precauzioni:

• Controlla se la tabella della sequenza corrente è piena. Se è piena, aggiungi spazio.
• Controlla se la posizione pos specificata è legale. Se non è legale, verrà lanciata un'eccezione.
• Utilizzare un ciclo back-to-front per spostare indietro gli elementi dopo la posizione pos.
• Viene aggiunto un elemento e usedSize viene aumentato di 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

Determina se un elemento è contenuto

Verifica se i dati forniti sono inclusi nella tabella di sequenza.
Basta scorrerlo direttamente, restituire true se lo trovi e restituire false se non lo trovi.

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

Trova la posizione corrispondente a un elemento

Guarda l'indice dei dati forniti in questa tabella di sequenza.
Basta scorrere direttamente e trovare l'indice di ritorno senza restituire -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

Ottieni l'elemento nella posizione pos

Emette l'elemento nella posizione pos.
Precauzioni:

• Controlla se il POS è legale

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

Imposta l'elemento in posizione pos su valore

Modificare l'elemento posizione pos.
Precauzioni:

• Controlla se il POS è legale.

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

Elimina la prima occorrenza della chiave della parola chiave

Elimina la prima occorrenza della chiave.
Precauzioni:

• Passa attraverso la ricerca.
• Usa gli elementi dopo la chiave trovata per coprirli uno per uno verso la parte anteriore.
• usedSize diminuisce di 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

Ottieni la lunghezza della tabella di sequenza

Ottenere la lunghezza della tabella di sequenza in questo caso si riferisce al numero di dati utili, ovvero usedSize.

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

Cancella elenco sequenze

Imposta il contenuto della tabella di sequenza su vuoto.
Precauzioni:

• Poiché la tabella sequenziale reale memorizza i generici, gli elementi vengono impostati su vuoti quando attraversati uno per uno e vengono sostituiti impostandoli su 0 di seguito.
• Anche UsedSize è impostato su 0.

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

ArrayList in Java

La classe ArrayList viene fornita in Java per rappresentare un elenco sequenziale.

interfaccia implementata

Descrizione dell'interfaccia:

1. L'interfaccia RandomAccess indica il supporto per l'accesso casuale.
2. L'interfaccia Cloneable indica il supporto per la clonazione.
3. L'interfaccia Serializable indica il supporto per la serializzazione.

Metodo di costruzione

Java prevede 3 metodi di costruzione come mostrato nella tabella:

Metodi comuni

I metodi comuni forniti sono simili a quelli implementati sopra.

Vantaggi e svantaggi degli elenchi di sequenze

vantaggio

I vantaggi delle tabelle di sequenza sono i seguenti:

1. È supportato l'accesso casuale.
2. L'interrogazione di un determinato pedice è veloce.

discordanza

1. Se non c'è abbastanza spazio, è necessario espanderlo e si perderà memoria.
2. L'inserimento e l'eliminazione nell'intestazione e nel centro sposteranno i dati.

pratica

Di seguito i link agli esercizi:
Triangolo Yang Hui