Teknologian jakaminen

Yksityiskohtainen selitys ja esimerkkejä tietorakenteen peräkkäisen varastoinnin lineaaritaulukon toteutuksesta (C, C#, C)

2024-07-12

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

Artikkelihakemisto


Lisää kuvan kuvaus tähän

Sekvenssitallennuslineaaritaulukko on perustietorakenne, joka tallentaa lineaarisen taulukon elementit joukkoon tallennusyksiköitä, joissa on peräkkäiset osoitteet tietyssä järjestyksessä. Tässä blogissa esittelemme peräkkäisen tallennuslineaaritaulukon toteutuksen yksityiskohtaisesti ja otamme kolme ohjelmointikieltä C, C# ja C++ esimerkkeinä osoittamaan, kuinka peräkkäinen varastointilineaaritaulukko toteutetaan.

1. Lineaaristen taulukoiden peräkkäisen tallennuksen peruskäsitteet

Sekvenssimuistin lineaarinen taulukko on lineaarisen taulukon toteutusmenetelmä, jolla on seuraavat ominaisuudet:

Elementtityypit ovat samat: Jaksottaisen varastointitaulukon elementit ovat samaa tyyppiä, ja jokainen elementti vie tietyn tallennustilan.
Elementit on järjestetty: Elementit peräkkäisessä varastointilistassa on järjestetty tiettyyn järjestykseen, yleensä ei-laskevaan järjestykseen.
Random access: Sekventiaaliset lineaariset taulukot tukevat satunnaiskäyttöä, eli mitä tahansa taulukon elementtiä voidaan käyttää suoraan indeksin kautta.
Dynaaminen laajennus: Jaksottaiset lineaariset varastotaulukot voivat laajentaa tallennustilaa dynaamisesti tarpeen mukaan, jotta siihen mahtuu enemmän elementtejä.

2. Toteutus peräkkäinen varastointi lineaarista taulukkoa

1. Tietorakenteen määritelmä

Ensinnäkin meidän on määriteltävä tietorakenne lineaaristen taulukoiden peräkkäistä tallennusta varten. C-kielen esimerkkinä voidaan käyttää rakennetta (struct) määrittääksesi:

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

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

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

2. Alustus

Lineaarinen taulukko tallennetaan alustussekvenssiin ja sille varataan alkukapasiteetti. C-kielessä voimme käyttää malloc-funktiota muistin dynaamiseen varaamiseen:

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. Lisää elementtejä

Lisää elementtejä peräkkäin tallennettuun lineaariseen luetteloon. Jos nykyinen kapasiteetti ei riitä uusien elementtien vastaanottamiseen, sinun on ensin laajennettava kapasiteettia:

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. Pääsyelementit

Käytä määritettyjä elementtejä peräkkäin tallennetussa lineaarisessa luettelossa:

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. Muokkaa elementtejä

Muokkaa määritettyjä elementtejä peräkkäisessä tallennuslistassa:

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. Poista elementtejä

Poista määritetyt elementit peräkkäin tallennetusta lineaarisesta luettelosta:

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

Tuhoa peräkkäinen tallennuslineaarinen taulukko ja vapauta varattu muisti:

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

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

3. Esimerkki

Alla käytämme kolmea ohjelmointikieltä, C, C# ja C++, toteuttamaan peräkkäisen varastointilineaaritaulukon sekä lisäämään, poistamaan, käyttämään ja tulostamaan elementtejä lineaariseen taulukkoon.

C-kielen esimerkki

#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#-kieli esimerkki

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++-kieliesimerkki

#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

Näissä kolmessa esimerkissä määritämme peräkkäisen muistin lineaarisen luetteloluokan ja tarjoamme joukon perustoimintoja, kuten elementtien lisäämistä, poistamista, käyttämistä ja tulostamista. Näiden esimerkkien avulla opit toteuttamaan peräkkäisiä lineaarisia tallennustaulukoita eri ohjelmointikielillä.

henkilökohtainen profiili

Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin tässä Kehittäjän dokumentaatioasema, jossa voit ja teknologian kehittämisen ongelman myöhempää käyttöä varten

yhteystietoni

Mail