Compartir tecnología

Explicación detallada y ejemplos de implementación de tablas lineales de almacenamiento secuencial de la estructura de datos (C, C#, C)

2024-07-12

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

Directorio de artículos


Insertar descripción de la imagen aquí

La tabla lineal de almacenamiento secuencial es una estructura de datos básica que almacena los elementos de la tabla lineal en un conjunto de unidades de almacenamiento con direcciones consecutivas en un orden determinado. En este blog, presentaremos en detalle la implementación de una tabla lineal de almacenamiento secuencial y tomaremos tres lenguajes de programación de C, C# y C++ como ejemplos para mostrar cómo implementar una tabla lineal de almacenamiento secuencial.

1. Conceptos básicos de almacenamiento secuencial de tablas lineales.

La tabla lineal de almacenamiento secuencial es un método de implementación de tabla lineal, que tiene las siguientes características:

Los tipos de elementos son los mismos: los elementos de la tabla lineal de almacenamiento secuencial son del mismo tipo y cada elemento ocupa un determinado espacio de almacenamiento.
Los elementos están ordenados: los elementos en la lista lineal de almacenamiento secuencial están ordenados en un orden determinado, generalmente en orden no decreciente.
Acceso aleatorio: las tablas lineales de almacenamiento secuencial admiten el acceso aleatorio, es decir, se puede acceder directamente a cualquier elemento de la tabla a través del índice.
Expansión dinámica: las mesas lineales de almacenamiento secuencial pueden expandir dinámicamente el espacio de almacenamiento según sea necesario para acomodar más elementos.

2. Implementación de tabla lineal de almacenamiento secuencial.

1. Definición de estructura de datos

Primero, necesitamos definir una estructura de datos para el almacenamiento secuencial de tablas lineales. Tomando el lenguaje C como ejemplo, puede usar una estructura (struct) para definir:

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

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

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

2. Inicialización

La tabla lineal se almacena en la secuencia de inicialización y se le asigna capacidad inicial. En lenguaje C, podemos usar la función malloc para asignar memoria dinámicamente:

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. Agregar elementos

Agregue elementos a una lista lineal almacenada secuencialmente. Si la capacidad actual no es suficiente para acomodar los nuevos elementos, primero debe ampliar la capacidad:

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. Elementos de acceso

Acceda a elementos especificados en una lista lineal almacenada secuencialmente:

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. Modificar elementos

Modifique los elementos especificados en la lista lineal de almacenamiento secuencial:

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. Eliminar elementos

Eliminar elementos especificados en una lista lineal almacenada secuencialmente:

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. destruir

Destruya la tabla lineal de almacenamiento secuencial y libere la memoria asignada:

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

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

3. Ejemplo

A continuación utilizamos tres lenguajes de programación, C, C# y C++, para implementar una tabla lineal de almacenamiento secuencial y agregar, eliminar, acceder e imprimir elementos en la tabla lineal.

ejemplo de lenguaje 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

Ejemplo de lenguaje 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

Ejemplo de lenguaje 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

En estos tres ejemplos, definimos una clase de lista lineal de almacenamiento secuencial y proporcionamos una serie de operaciones básicas como agregar, eliminar, acceder e imprimir elementos. Con estos ejemplos podrás aprender a implementar tablas lineales de almacenamiento secuencial en diferentes lenguajes de programación.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo