C语言实现动态顺序表的实现代码

让我来为大家详细讲解一下如何使用C语言实现动态顺序表的实现代码。

1. 动态顺序表的概述

动态顺序表是一种线性表，它基于数组实现。动态顺序表可以自动扩充或缩小其容量以存储数据。动态顺序表中元素的位置是按照它们在数组中的位置来确定的。它们在内存中是连续存储的，因此它们可以通过下标快速访问。

2. 动态顺序表的实现

我们使用C语言的方法来实现动态顺序表。首先，我们需要定义一些数据结构来表示动态顺序表。我们定义一个叫做SeqList的结构体表示动态顺序表：

#define DEFAULT_CAPACITY 10

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

其中：

data：表示存储数据的数组。
capacity：表示当前动态顺序表的容量。
size：表示当前动态顺序表中的元素数量。

我们使用malloc函数来为data分配内存。

SeqList* SeqList_Create() {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    list->data = (int*)malloc(DEFAULT_CAPACITY * sizeof(int));
    list->capacity = DEFAULT_CAPACITY;
    list->size = 0;
    return list;
}

为了保证动态顺序表有足够的存储空间存储元素，我们需要扩充它的容量。

int SeqList_Expand(SeqList* list) {
    int* oldData = list->data;
    int oldCapacity = list->capacity;
    int newCapacity = oldCapacity * 2;
    list->data = (int*)malloc(newCapacity * sizeof(int));
    if (list->data == NULL) {
        list->data = oldData;
        list->capacity = oldCapacity;
        return 0;
    }
    int i;
    for (i = 0; i < oldCapacity; i++) {
        list->data[i] = oldData[i];
    }
    list->capacity = newCapacity;
    free(oldData);
    return 1;
}

我们还需要实现插入元素、删除元素和访问元素等操作：

int SeqList_Insert(SeqList* list, int pos, int value) {
    if (pos < 0 || pos > list->size) {
        return 0;
    }
    if (list->size >= list->capacity) {
        if (!SeqList_Expand(list)) {
            return 0;
        }
    }
    int i;
    for (i = list->size; i > pos; i--) {
        list->data[i] = list->data[i-1];
    }
    list->data[pos] = value;
    list->size++;
    return 1;
}

int SeqList_Delete(SeqList* list, int pos) {
    if (pos < 0 || pos >= list->size) {
        return 0;
    }
    int i;
    for (i = pos; i < list->size-1; i++) {
        list->data[i] = list->data[i+1];
    }
    list->size--;
    return 1;
}

int SeqList_Get(SeqList* list, int pos, int* value) {
    if (pos < 0 || pos >= list->size) {
        return 0;
    }
    *value = list->data[pos];
    return 1;
}

完整的实现代码如下：

#include <stdlib.h>

#define DEFAULT_CAPACITY 10

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

SeqList* SeqList_Create() {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    list->data = (int*)malloc(DEFAULT_CAPACITY * sizeof(int));
    list->capacity = DEFAULT_CAPACITY;
    list->size = 0;
    return list;
}

int SeqList_Expand(SeqList* list) {
    int* oldData = list->data;
    int oldCapacity = list->capacity;
    int newCapacity = oldCapacity * 2;
    list->data = (int*)malloc(newCapacity * sizeof(int));
    if (list->data == NULL) {
        list->data = oldData;
        list->capacity = oldCapacity;
        return 0;
    }
    int i;
    for (i = 0; i < oldCapacity; i++) {
        list->data[i] = oldData[i];
    }
    list->capacity = newCapacity;
    free(oldData);
    return 1;
}

int SeqList_Insert(SeqList* list, int pos, int value) {
    if (pos < 0 || pos > list->size) {
        return 0;
    }
    if (list->size >= list->capacity) {
        if (!SeqList_Expand(list)) {
            return 0;
        }
    }
    int i;
    for (i = list->size; i > pos; i--) {
        list->data[i] = list->data[i-1];
    }
    list->data[pos] = value;
    list->size++;
    return 1;
}

int SeqList_Delete(SeqList* list, int pos) {
    if (pos < 0 || pos >= list->size) {
        return 0;
    }
    int i;
    for (i = pos; i < list->size-1; i++) {
        list->data[i] = list->data[i+1];
    }
    list->size--;
    return 1;
}

int SeqList_Get(SeqList* list, int pos, int* value) {
    if (pos < 0 || pos >= list->size) {
        return 0;
    }
    *value = list->data[pos];
    return 1;
}

3. 示例说明

示例1：插入元素

以下是插入元素的示例代码：

#include <stdio.h>

int main() {
    SeqList* list = SeqList_Create();
    SeqList_Insert(list, 0, 1);
    SeqList_Insert(list, 0, 2);
    SeqList_Insert(list, 1, 3);
    int i, value;
    for (i = 0; i < list->size; i++) {
        SeqList_Get(list, i, &value);
        printf("%d ", value);
    }
    printf("\n");
    SeqList_Delete(list, 1);
    for (i = 0; i < list->size; i++) {
        SeqList_Get(list, i, &value);
        printf("%d ", value);
    }
    printf("\n");
    return 0;
}

输出结果为：

2 3 1
2 1

在这个示例中，我们创建了一个动态顺序表，并向其中插入了三个元素。然后，我们遍历动态顺序表中的所有元素并打印它们。接着，我们删除了第一个插入的元素，并再次遍历动态顺序表中的所有元素并打印它们。

示例2：访问元素

以下是访问元素的示例代码：

#include <stdio.h>

int main() {
    SeqList* list = SeqList_Create();
    SeqList_Insert(list, 0, 1);
    SeqList_Insert(list, 0, 2);
    SeqList_Insert(list, 1, 3);
    int value;
    SeqList_Get(list, 1, &value);
    printf("%d\n", value);
    return 0;
}