【408考点之数据结构】线性表的顺序表示

线性表的顺序表示

顺序表的定义

顺序表是一种线性表的顺序存储结构。它将线性表中的数据元素按照其逻辑顺序依次存储在一块连续的存储空间中。顺序表通过数组来实现，数组中的每个元素对应于线性表的一个数据元素。顺序表的主要特点是支持随机访问，但在插入和删除操作时可能需要移动大量元素。

顺序表的特点

1. 存储结构：顺序表使用一块连续的存储空间，通常是数组。
2. 随机访问：由于存储空间连续，顺序表支持O(1)的随机访问，即可以通过元素的下标直接访问元素。
3. 插入和删除操作：在顺序表中进行插入和删除操作时，可能需要移动大量元素，操作效率较低，特别是在表头或表中间进行插入或删除时。
4. 存储空间分配：顺序表的存储空间是在创建时一次性分配的，表的长度需要提前确定，若需要扩展存储空间则需要重新分配内存，成本较高。

顺序表的基本操作

以下是顺序表的基本操作，包括初始化、插入元素和删除元素的C语言实现。

定义顺序表结构：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE]; // 存储元素的数组
    int length;         // 顺序表的当前长度
} SeqList;

// 初始化顺序表
void initList(SeqList *L) {
    L->length = 0; // 初始化长度为0
}

插入元素：

int insertElement(SeqList *L, int pos, int elem) {
    if (pos < 0 || pos > L->length || L->length >= MAX_SIZE) return -1; // 插入位置不合法或表已满
    for (int i = L->length; i > pos; i--) {
        L->data[i] = L->data[i - 1]; // 将元素后移
    }
    L->data[pos] = elem; // 插入元素
    L->length++;
    return 0; // 插入成功
}

删除元素：

int deleteElement(SeqList *L, int pos) {
    if (pos < 0 || pos >= L->length) return -1; // 删除位置不合法
    for (int i = pos; i < L->length - 1; i++) {
        L->data[i] = L->data[i + 1]; // 将元素前移
    }
    L->length--;
    return 0; // 删除成功
}

通过理解顺序表的定义和特点，以及顺序表的基本操作实现，我们可以更好地应用这种数据结构来解决实际问题。顺序表适用于需要快速随机访问的场景，但在频繁插入和删除操作的场合，其效率可能不如链式存储结构。选择适合的存储结构，对于优化程序性能至关重要。