Κοινή χρήση τεχνολογίας

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

γραμμικός πίνακας

θέλουμε να μιλήσουμεΠίνακας ακολουθιών, πρέπει να μιλήσουμε πρώτα για γραμμικούς πίνακες, γιατί οι διαδοχικοί πίνακες είναι ένας τύπος γραμμικών πινάκων.

Ορισμός γραμμικού πίνακα

Όπως υποδηλώνει το όνομα, ένας γραμμικός πίνακας είναι ένας πίνακας που οργανώνει δεδομένα σαν γραμμές.
Μπορεί να γίνει κατανοητό με τη σκέψη της ουράς στην πραγματικότητα.

Χαρακτηριστικά γραμμικών πινάκων:

• Υπάρχει μια σειρά μεταξύ των στοιχείων δεδομένων ενός γραμμικού πίνακα.
• Εκτός από το πρώτο στοιχείο και το τελευταίο στοιχείο, κάθε στοιχείο έχει έναν προκάτοχο και έναν διάδοχο.

Πίνακας ακολουθιών

Ο πίνακας ακολουθίας είναι μια παράγραφοςΟι φυσικές διευθύνσεις είναι διαδοχικέςΟι μονάδες αποθήκευσης είναι σαν άνθρωποι που παρατάσσονται ο ένας δίπλα στον άλλο.
Μια γραμμική δομή που αποθηκεύει στοιχεία δεδομένων με τη σειρά, συνήθως χρησιμοποιώνταςπίνακαςαποθήκευση.
Ολοκληρώστε την προσθήκη, διαγραφή, έλεγχο και τροποποίηση δεδομένων στον πίνακα.

Υλοποίηση διεπαφής πίνακα ακολουθιών

Υλοποιήστε μόνοι σας έναν πίνακα ακολουθιών (αποθήκευση δεδομένων τύπου int), χρησιμοποιήστε τον πίνακα ακολουθιών ως κλάση, υλοποιούμε ορισμένες διεπαφές, δηλαδή μερικέςμέθοδος μέλουςΝα πραγματοποιήσει την προσθήκη, διαγραφή, έλεγχο και τροποποίηση δεδομένων.

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

Προεπιλεγμένος κατασκευαστής

Από προεπιλογή, ανοίγουμε αρχικά 10 κενά δεδομένων.

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

Ορίστε την υποκείμενη χωρητικότητα του πίνακα ακολουθιών σε initcapacity

Περάστε το μήκος του πίνακα και χρησιμοποιήστε το μήκος του πίνακα για να ανοίξετε χώρο.

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

ουρά βύσμα

Νέα στοιχεία προστίθενται στο τέλος του πίνακα από προεπιλογή.
Σημεία που πρέπει να ληφθούν υπόψη:

• Ελέγξτε εάν ο τρέχων πίνακας ακολουθίας είναι γεμάτος, προσθέστε χώρο.
• Προστίθεται ένα στοιχείο και το usedSize αυξάνεται κατά 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

Προσθήκη στοιχείου στη θέση θέσης

Εισαγωγή στοιχείου στο δείκτη pos.
Προφυλάξεις:

• Ελέγξτε εάν ο τρέχων πίνακας ακολουθίας είναι γεμάτος, προσθέστε χώρο.
• Είτε η δεδομένη θέση θέσης είναι νόμιμη είτε όχι, θα γίνει εξαίρεση εάν δεν είναι νόμιμη.
• Χρησιμοποιήστε έναν βρόχο από πίσω προς τα εμπρός για να μετακινήσετε τα στοιχεία μετά τη θέση θέσης προς τα πίσω.
• Προστίθεται ένα στοιχείο και το usedSize αυξάνεται κατά 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

Προσδιορίστε εάν περιέχεται ένα στοιχείο

Ελέγξτε εάν τα δεδομένα που δίνονται περιέχονται στον πίνακα ακολουθίας.
Απλώς περάστε το απευθείας, επιστρέψτε το true αν το βρείτε και επιστρέψτε το false αν δεν το βρείτε.

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

Βρείτε τη θέση που αντιστοιχεί σε ένα στοιχείο

Κοιτάξτε το ευρετήριο των δεδομένων σε αυτόν τον πίνακα ακολουθίας.
Απλώς πραγματοποιήστε βρόχο απευθείας και βρείτε τον δείκτη επιστροφής χωρίς να επιστρέψετε -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

Αποκτήστε το στοιχείο στη θέση θέσης

Έξοδος του στοιχείου στη θέση θέσης.
Προφυλάξεις:

• Ελέγξτε εάν το pos είναι νόμιμο

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

Ορίστε το στοιχείο στη θέση pos σε τιμή

Τροποποιήστε το στοιχείο θέσης θέσης.
Προφυλάξεις:

• Ελέγξτε εάν το pos είναι νόμιμο.

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

Διαγράψτε την πρώτη εμφάνιση του κλειδιού λέξης-κλειδιού

Διαγράψτε την πρώτη εμφάνιση του κλειδιού.
Προφυλάξεις:

• Περιηγηθείτε στην αναζήτηση.
• Χρησιμοποιήστε τα στοιχεία μετά το κλειδί που βρέθηκε για να τα καλύψετε ένα προς ένα προς τα εμπρός.
• usedSize μειώνεται κατά 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

Λάβετε μήκος πίνακα ακολουθίας

Η απόκτηση του μήκους του πίνακα ακολουθίας εδώ αναφέρεται στον αριθμό των χρήσιμων δεδομένων, δηλαδή στο usedSize.

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

Εκκαθάριση λίστας ακολουθιών

Ορίστε τα περιεχόμενα του πίνακα ακολουθιών σε άδεια.
Προφυλάξεις:

• Επειδή ο πίνακας πραγματικής ακολουθίας αποθηκεύει γενικά, τα στοιχεία θα οριστούν ως άδεια όταν διασχίζονται ένα προς ένα και θα αντικατασταθούν ορίζοντας τα στο 0 παρακάτω.
• Το UsedSize έχει οριστεί επίσης στο 0.

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

ArrayList σε Java

Η κλάση ArrayList παρέχεται σε Java για να αναπαραστήσει μια διαδοχική λίστα.

υλοποιημένη διεπαφή

Περιγραφή διεπαφής:

1. Η διεπαφή RandomAccess υποδεικνύει υποστήριξη για τυχαία πρόσβαση.
2. Η διεπαφή Cloneable υποδεικνύει υποστήριξη για κλωνοποίηση.
3. Η διεπαφή Serializable υποδεικνύει υποστήριξη για σειριοποίηση.

Μέθοδος κατασκευής

Η Java παρέχει 3 μεθόδους κατασκευής όπως φαίνεται στον πίνακα:

Κοινές μέθοδοι

Οι κοινές μέθοδοι που παρέχονται είναι παρόμοιες με αυτές που εφαρμόσαμε παραπάνω.

Πλεονεκτήματα και μειονεκτήματα των λιστών ακολουθιών

πλεονέκτημα

Τα πλεονεκτήματα των πινάκων ακολουθίας είναι τα εξής:

1. Υποστηρίζεται η τυχαία πρόσβαση.
2. Η αναζήτηση ενός δεδομένου δείκτη είναι γρήγορη.

έλλειψη

1. Εάν δεν υπάρχει αρκετός χώρος, πρέπει να επεκταθεί και θα υπάρξει σπατάλη μνήμης.
2. Η εισαγωγή και η διαγραφή στην κεφαλίδα και στη μέση θα μετακινήσουν τα δεδομένα.

πρακτική

Οι σύνδεσμοι για τις ασκήσεις είναι οι παρακάτω:
τρίγωνο Yang Hui