C语言线性表之顺序表

顺序表（Sequential List），也称为数组，是一种基本的线性表数据结构，其中元素在内存中按顺序存储，可以通过索引访问。在 C 语言中，数组是顺序表的一种实现。以下是一个简单的顺序表的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100  // 顺序表的最大容量

// 定义顺序表结构
typedef struct {
    int data[MAX_SIZE];
    int length;
} SeqList;

// 初始化顺序表
void initSeqList(SeqList *list) {
    list->length = 0;
}

// 判断顺序表是否为空
bool isEmpty(SeqList *list) {
    return list->length == 0;
}

// 判断顺序表是否已满
bool isFull(SeqList *list) {
    return list->length == MAX_SIZE;
}

// 在指定位置插入元素
bool insert(SeqList *list, int index, int value) {
    if (index < 0 || index > list->length || isFull(list)) {
        return false;
    }
    
    for (int i = list->length; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    
    list->data[index] = value;
    list->length++;
    
    return true;
}

// 删除指定位置的元素
bool removeAt(SeqList *list, int index) {
    if (index < 0 || index >= list->length || isEmpty(list)) {
        return false;
    }
    
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    
    list->length--;
    
    return true;
}

// 获取指定位置的元素
bool get(SeqList *list, int index, int *value) {
    if (index < 0 || index >= list->length) {
        return false;
    }
    
    *value = list->data[index];
    
    return true;
}

int main() {
    SeqList list;
    initSeqList(&list);
    
    insert(&list, 0, 10);
    insert(&list, 1, 20);
    insert(&list, 1, 15);
    
    int value;
    if (get(&list, 1, &value)) {
        printf("索引 1 处的元素：%d\\n", value);
    }
    
    removeAt(&list, 0);
    
    printf("顺序表内容：");
    for (int i = 0; i < list.length; i++) {
        printf("%d ", list.data[i]);
    }
    printf("\\n");
    
    return 0;
}

在这段代码中，SeqList 结构表示顺序表，其中 data 数组用于存储元素，length 表示当前顺序表的长度。initSeqList 函数用于初始化顺序表，isEmpty 和 isFull 函数分别判断顺序表是否为空和已满，insert 函数在指定位置插入元素，removeAt 函数删除指定位置的元素，get 函数获取指定位置的元素。

顺序表在内存中是连续存储的，访问元素的时间复杂度为 O(1)，但插入和删除操作可能需要移动大量元素，时间复杂度为 O(n)。在实际应用中，顺序表适用于需要频繁随机访问元素的场景。