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

Λεπτομερής επεξήγηση και παραδείγματα διαδοχικής αποθήκευσης γραμμικού πίνακα υλοποίησης δομής δεδομένων (C, C#, C)

2024-07-12

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

Κατάλογος άρθρων


Εισαγάγετε την περιγραφή της εικόνας εδώ

Ο γραμμικός πίνακας διαδοχικής αποθήκευσης είναι μια βασική δομή δεδομένων, η οποία αποθηκεύει τα στοιχεία του γραμμικού πίνακα σε ένα σύνολο μονάδων αποθήκευσης με διαδοχικές διευθύνσεις με συγκεκριμένη σειρά. Σε αυτό το ιστολόγιο, θα εισαγάγουμε την υλοποίηση ενός γραμμικού πίνακα διαδοχικής αποθήκευσης λεπτομερώς και θα πάρουμε τρεις γλώσσες προγραμματισμού​​​της C, C# και C++ ως παραδείγματα για να δείξουμε πώς να εφαρμόσουμε έναν γραμμικό πίνακα διαδοχικής αποθήκευσης.

1. Βασικές έννοιες διαδοχικής αποθήκευσης γραμμικών πινάκων

Ο γραμμικός πίνακας διαδοχικής αποθήκευσης είναι μια μέθοδος υλοποίησης γραμμικού πίνακα, η οποία έχει τα ακόλουθα χαρακτηριστικά:

Οι τύποι στοιχείων είναι οι ίδιοι: Τα στοιχεία στον γραμμικό πίνακα διαδοχικής αποθήκευσης είναι του ίδιου τύπου και κάθε στοιχείο καταλαμβάνει συγκεκριμένο χώρο αποθήκευσης.
Τα στοιχεία είναι ταξινομημένα: Τα στοιχεία στη γραμμική λίστα διαδοχικής αποθήκευσης είναι διατεταγμένα με συγκεκριμένη σειρά, συνήθως με μη φθίνουσα σειρά.
Τυχαία πρόσβαση: Οι γραμμικοί πίνακες διαδοχικής αποθήκευσης υποστηρίζουν τυχαία πρόσβαση, δηλαδή, οποιοδήποτε στοιχείο του πίνακα μπορεί να προσπελαστεί απευθείας μέσω του ευρετηρίου.
Δυναμική επέκταση: Οι διαδοχικοί γραμμικοί πίνακες αποθήκευσης μπορούν να επεκτείνουν δυναμικά τον αποθηκευτικό χώρο όπως απαιτείται για να χωρέσουν περισσότερα στοιχεία.

2. Υλοποίηση γραμμικού πίνακα διαδοχικής αποθήκευσης

1. Ορισμός δομής δεδομένων

Αρχικά, πρέπει να ορίσουμε μια δομή δεδομένων για τη διαδοχική αποθήκευση γραμμικών πινάκων. Λαμβάνοντας ως παράδειγμα τη γλώσσα C, μπορείτε να χρησιμοποιήσετε μια δομή (struct) για να ορίσετε:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data; // 指向动态分配的数组
    int size;  // 线性表的当前长度
    int capacity; // 线性表的容量
} SequenceList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2. Αρχικοποίηση

Ο γραμμικός πίνακας αποθηκεύεται στην ακολουθία αρχικοποίησης και η αρχική χωρητικότητα εκχωρείται σε αυτόν. Στη γλώσσα C, μπορούμε να χρησιμοποιήσουμε τη συνάρτηση malloc για να εκχωρήσουμε δυναμικά τη μνήμη:

void initSequenceList(SequenceList *list, int capacity) {
    list->data = (int *)malloc(capacity * sizeof(int));
    if (list->data == NULL) {
        exit(-1); // 内存分配失败，退出程序
    }
    list->size = 0;
    list->capacity = capacity;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3. Προσθέστε στοιχεία

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

void appendSequenceList(SequenceList *list, int value) {
    if (list->size == list->capacity) {
        // 扩展容量
        int newCapacity = list->capacity * 2;
        int *newData = (int *)malloc(newCapacity * sizeof(int));
        if (newData == NULL) {
            exit(-1); // 内存分配失败，退出程序
        }
        for (int i = 0; i < list->size; i++) {
            newData[i] = list->data[i];
        }
        free(list->data);
        list->data = newData;
        list->capacity = newCapacity;
    }
    list->data[list->size++] = value;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

4. Στοιχεία πρόσβασης

Πρόσβαση σε καθορισμένα στοιχεία σε μια γραμμική λίστα που αποθηκεύεται διαδοχικά:

int getSequenceList(const SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return -1; // 索引无效，返回-1
    }
    return list->data[index];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

5. Τροποποίηση στοιχείων

Τροποποιήστε τα καθορισμένα στοιχεία στη γραμμική λίστα διαδοχικής αποθήκευσης:

void setSequenceList(SequenceList *list, int index, int value) {
    if (index < 0 || index >= list->size) {
        return; // 索引无效，不进行操作
    }
    list->data[index] = value;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

6. Διαγραφή στοιχείων

Διαγράψτε καθορισμένα στοιχεία σε μια διαδοχικά αποθηκευμένη γραμμική λίστα:

void removeSequenceList(SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return; // 索引无效，不进行操作
    }
    for (int i = index + 1; i < list->size; i++) {
        list->data[i - 1] = list->data[i];
    }
    list->size--;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

7. Καταστρέψτε

Καταστρέψτε τον γραμμικό πίνακα διαδοχικής αποθήκευσης και απελευθερώστε την εκχωρημένη μνήμη:

void destroySequenceList(SequenceList *list) {
    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

3. Παράδειγμα

Παρακάτω χρησιμοποιούμε τρεις γλώσσες προγραμματισμού, C, C# και C++, για την υλοποίηση ενός γραμμικού πίνακα διαδοχικής αποθήκευσης και την προσθήκη, διαγραφή, πρόσβαση και εκτύπωση στοιχείων στον γραμμικό πίνακα.

Παράδειγμα γλώσσας Γ

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} SequenceList;

void initSequenceList(SequenceList *list, int capacity) {
    list->data = (int *)malloc(capacity * sizeof(int));
    if (list->data == NULL) {
        exit(-1);
    }
    list->size = 0;
    list->capacity = capacity;
}

void appendSequenceList(SequenceList *list, int value) {
    if (list->size == list->capacity) {
        int newCapacity = list->capacity * 2;
        int *newData = (int *)malloc(newCapacity * sizeof(int));
        if (newData == NULL) {
            exit(-1);
        }
        for (int i = 0; i < list->size; i++) {
            newData[i] = list->data[i];
        }
        free(list->data);
        list->data = newData;
        list->capacity = newCapacity;
    }
    list->data[list->size++] = value;
}

int getSequenceList(const SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return -1;
    }
    return list->data[index];
}

void setSequenceList(SequenceList *list, int index, int value) {
    if (index < 0 || index >= list->size) {
        return;
    }
    list->data[index] = value;
}

void removeSequenceList(SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return;
    }
    for (int i = index + 1; i < list->size; i++) {
        list->data[i - 1] = list->data[i];
    }
    list->size--;
}

void destroySequenceList(SequenceList *list) {
    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

int main() {
    SequenceList list;
    initSequenceList(&list, 10);
    appendSequenceList(&list, 1);
    appendSequenceList(&list, 2);
    appendSequenceList(&list, 3);
    printf("Get element at index 1: %dn", getSequenceList(&list, 1));
    setSequenceList(&list, 1, 4);
    printf("Get element at index 1 after modification: %dn", getSequenceList(&list, 1));
    removeSequenceList(&list, 0);
    printf("Get element at index 0 after removal: %dn", getSequenceList(&list, 0));
    destroySequenceList(&list);
    return 0;
}

  • 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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

Παράδειγμα γλώσσας C#

using System;

public class SequenceList
{
    private int[] data;
    private int size;
    private int capacity;

    public SequenceList(int capacity)
    {
        this.data = new int[capacity];
        this.size = 0;
        this.capacity = capacity;
    }

    public void Append(int value)
    {
        if (size == capacity)
        {
            int newCapacity = capacity * 2;
            int[] newData = new int[newCapacity];
            for (int i = 0; i < size; i++)
            {
                newData[i] = data[i];
            }
            data = newData;
            capacity = newCapacity;
        }
        data[size++] = value;
    }

    public int Get(int index)
    {
        if (index < 0 || index >= size)
        {
            return -1;
        }
        return data[index];
    }

    public void Set(int index, int value)
    {
        if (index < 0 || index >= size)
        {
            return;
        }
        data[index] = value;
    }

    public void RemoveAt(int index)
    {
        if (index < 0 || index >= size)
        {
            return;
        }
        for (int i = index + 1; i < size; i++)
        {
            data[i - 1] = data[i];
        }
        size--;
    }

    public void Clear()
    {
        size = 0;
    }
}

class Program
{
    static void Main(string[] args)
    {
        SequenceList list = new SequenceList(10);
        list.Append(1);
        list.Append(2);
        list.Append(3);
        Console.WriteLine("Get element at index 1: " + list.Get(1));
        list.Set(1, 4);
        Console.WriteLine("Get element at index 1 after modification: " + list.Get(1));
        list.RemoveAt(0);
        Console.WriteLine("Get element at index 0 after removal: " + list.Get(0));
        list.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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

Παράδειγμα γλώσσας C++

#include <iostream>

class SequenceList {
private:
    int *data;
    int size;
    int capacity;

public:
    SequenceList(int capacity) {
        data = new int[capacity];
        size = 0;
        capacity = capacity;
    }

    void Append(int value) {
        if (size == capacity) {
            int newCapacity = capacity * 2;
            int *newData = new int[newCapacity];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
            capacity = newCapacity;
        }
        data[size++] = value;
    }

    int Get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        return data[index];
    }

    void Set(int index, int value) {
        if (index < 0 || index >= size) {
            return;
        }
        data[index] = value;
    }

    void RemoveAt(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
    }

    void Clear() {
        size = 0;
    }
};

int main() {
    SequenceList list(10);
    list.Append(1);
    list.Append(2);
    list.Append(3);
    std::cout << "Get element at index 1: " << list.Get(1) << std::endl;
    list.Set(1, 4);
    std::cout << "Get element at index 1 after modification: " << list.Get(1) << std::endl;
    list.RemoveAt(0);
    std::cout << "Get element at index 0 after removal: " << list.Get(0) << std::endl;
    list.Clear();
    return 0;
}

  • 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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71

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

Προσωπικό προφίλ

Έχει αφοσιωθεί στην έρευνα της τεχνολογίας για περισσότερα από 30 χρόνια και είναι ικανός σε διάφορες γλώσσες όπως java, linux, javascript, php, css κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα σταθμός τεκμηρίωσης προγραμματιστή για να μοιραστείτε ορισμένα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο