Partage de technologie

Explication détaillée et exemples d'implémentation de table linéaire de stockage séquentiel de la structure de données (C, C#, C)

2024-07-12

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

Annuaire d'articles


Insérer la description de l'image ici

La table linéaire de stockage séquentiel est une structure de données de base qui stocke les éléments de la table linéaire dans un ensemble d'unités de stockage avec des adresses consécutives dans un certain ordre. Dans ce blog, nous présenterons en détail l'implémentation d'une table linéaire de stockage séquentiel et prendrons trois langages de programmation​​C, C# et C++ comme exemples pour montrer comment implémenter une table linéaire de stockage séquentiel.

1. Concepts de base du stockage séquentiel des tableaux linéaires

La table linéaire à stockage séquentiel est une méthode de mise en œuvre de table linéaire, qui présente les caractéristiques suivantes :

Les types d'éléments sont les mêmes : les éléments de la table linéaire de stockage séquentiel sont du même type et chaque élément occupe un certain espace de stockage.
Les éléments sont ordonnés : les éléments de la liste linéaire de stockage séquentiel sont disposés dans un certain ordre, généralement dans un ordre non décroissant.
Accès aléatoire : les tables linéaires de stockage séquentiel prennent en charge l'accès aléatoire, c'est-à-dire que n'importe quel élément de la table est directement accessible via l'index.
Expansion dynamique : les tables linéaires de stockage séquentiel peuvent étendre dynamiquement l'espace de stockage selon les besoins pour accueillir plus d'éléments.

2. Mise en œuvre d'une table linéaire de stockage séquentiel

1. Définition de la structure des données

Tout d’abord, nous devons définir une structure de données pour le stockage séquentiel des tableaux linéaires. En prenant le langage C comme exemple, vous pouvez utiliser une structure (struct) pour définir :

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

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

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

2. Initialisation

La table linéaire est stockée dans la séquence d'initialisation et une capacité initiale lui est allouée. En langage C, nous pouvons utiliser la fonction malloc pour allouer dynamiquement de la mémoire :

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. Ajouter des éléments

Ajoutez des éléments à une liste linéaire stockée séquentiellement. Si la capacité actuelle n’est pas suffisante pour accueillir les nouveaux éléments, vous devez d’abord augmenter la capacité :

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. Accéder aux éléments

Accédez aux éléments spécifiés dans une liste linéaire stockée séquentiellement :

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. Modifier les éléments

Modifiez les éléments spécifiés dans la liste linéaire de stockage séquentiel :

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. Supprimer des éléments

Supprimez les éléments spécifiés dans une liste linéaire stockée séquentiellement :

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. Détruire

Détruisez la table linéaire de stockage séquentiel et libérez la mémoire allouée :

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

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

3. Exemple

Ci-dessous, nous utilisons trois langages de programmation, C, C# et C++, pour implémenter une table linéaire de stockage séquentiel et ajouter, supprimer, accéder et imprimer des éléments dans la table linéaire.

Exemple de langage 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

Exemple de langage 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

Exemple de langage 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

Dans ces trois exemples, nous définissons une classe de liste linéaire de stockage séquentiel et fournissons une série d'opérations de base telles que l'ajout, la suppression, l'accès et l'impression d'éléments. Avec ces exemples, vous pouvez apprendre à implémenter des tables linéaires de stockage séquentiel dans différents langages de programmation.

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail