数据结构之顺序存储线性表实现详解与示例（C，C#，C++）

07-12 1656阅读

文章目录

  • 一、顺序存储线性表的基本概念
  • 二、顺序存储线性表的实现
    • 1、数据结构定义
    • 2、初始化
    • 3、添加元素
    • 4、访问元素
    • 5、修改元素
    • 6、删除元素
    • 7、销毁
    • 三、示例
      • C语言示例
      • C#语言示例
      • C++语言示例

        数据结构之顺序存储线性表实现详解与示例（C，C#，C++）

        顺序存储线性表是一种基本的数据结构，它将线性表的元素按照一定的顺序存放在一组地址连续的存储单元中。在这篇博客中，我们将详细介绍顺序存储线性表的实现，并以C、C#和C++三种编程语言为例，展示如何实现一个顺序存储线性表。

        一、顺序存储线性表的基本概念

        顺序存储线性表是一种线性表的实现方式，它具有以下特点：

        元素类型相同：顺序存储线性表中的元素类型相同，每个元素占用一定的存储空间。

        元素有序：顺序存储线性表中的元素按照一定的顺序排列，通常为非递减顺序。

        随机访问：顺序存储线性表支持随机访问，即可以通过索引直接访问表中的任意元素。

        动态扩展：顺序存储线性表可以根据需要动态地扩展存储空间，以容纳更多元素。

        二、顺序存储线性表的实现

        1、数据结构定义

        首先，我们需要为顺序存储线性表定义一个数据结构。以C语言为例，可以使用结构体（struct）来定义：

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

        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;
}

        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 size; i++) {
            newData[i] = list->data[i];
        }
        free(list->data);
        list->data = newData;
        list->capacity = newCapacity;
    }
    list->data[list->size++] = value;
}

        4、访问元素

        访问顺序存储线性表中的指定元素：

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

        5、修改元素

        修改顺序存储线性表中的指定元素：

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

        6、删除元素

        删除顺序存储线性表中的指定元素：

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

        7、销毁

        销毁顺序存储线性表，释放分配的内存：

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

        三、示例

        下面我们使用C、C#和C++三种编程语言，分别实现一个顺序存储线性表，并添加、删除、访问和打印线性表中的元素。

        C语言示例

        #include 
#include 
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 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 = list->size) {
        return -1;
    }
    return list->data[index];
}
void setSequenceList(SequenceList *list, int index, int value) {
    if (index = list->size) {
        return;
    }
    list->data[index] = value;
}
void removeSequenceList(SequenceList *list, int index) {
    if (index = list->size) {
        return;
    }
    for (int i = index + 1; i 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: %d\n", getSequenceList(&list, 1));
    setSequenceList(&list, 1, 4);
    printf("Get element at index 1 after modification: %d\n", getSequenceList(&list, 1));
    removeSequenceList(&list, 0);
    printf("Get element at index 0 after removal: %d\n", getSequenceList(&list, 0));
    destroySequenceList(&list);
    return 0;
}

        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)
        {
            return -1;
        }
        return data[index];
    }
    public void Set(int index, int value)
    {
        if (index = size)
        {
            return;
        }
        data[index] = value;
    }
    public void RemoveAt(int index)
    {
        if (index = size)
        {
            return;
        }
        for (int i = index + 1; i  

        C++语言示例
         

        #include 
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) {
            return -1;
        }
        return data[index];
    }
    void Set(int index, int value) {
        if (index = size) {
            return;
        }
        data[index] = value;
    }
    void RemoveAt(int index) {
        if (index = size) {
            return;
        }
        for (int i = index + 1; i
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]