数据结构 C语言 顺序表

在C语言中，顺序表是一种基础的数据结构，它将元素按照线性的方式存储在一个连续的内存空间中。顺序表的特点包括：

1. **动态性和固定大小**：顺序表通常用于动态分配内存，可以预先设定长度，一旦创建就不能自动调整大小，需要手动扩容或缩容。

2. **随机访问**：通过索引可以直接访问任意位置的元素，因为所有元素都在一连串的内存地址中。

3. **插入和删除**：在列表头部和尾部添加或删除元素效率较高，但中间位置的操作由于需要移动其他元素，时间复杂度较高，通常是O(n)。

4. **数组表示**：在C语言中，最常见的是使用数组来实现顺序表，数组名和数组下标对应，元素的位置通过下标计算得出。

以下是创建和操作顺序表的一个简单示例：

#include <stdio.h>

typedef struct {
    int* data; // 存储数据的指针
    int size;  // 当前元素个数
    int capacity; // 初始或预设的最大容量
} List;

// 初始化顺序表
List* init_list(int cap) {
    List* list = (List*)malloc(sizeof(List));
    list->data = (int*)malloc(cap * sizeof(int));
    list->size = 0;
    list->capacity = cap;
    return list;
}

// 插入元素
void insert(List* list, int index, int value) {
    if (index > list->size || index < 0) {
        printf("Invalid index.\n");
        return;
    }
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->data = (int*)realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[index] = value;
    list->size++;
}

// 删除元素
void delete(List* list, int index) {
    if (index >= list->size) {
        printf("Index out of range.\n");
        return;
    }
    for (int i = index; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    free(list->data[index]);
    list->size--;
}

// 打印列表
void print_list(List* list) {
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 示例
int main() {
    List* list = init_list(5);
    // ...其他操作...
    print_list(list); // 输出当前列表内容
    return 0;
}