C语言顺序表的概念及结构是什么

1. 顺序表的概念

顺序表（Sequential List）是线性表的一种存储结构，它使用一段连续的存储单元依次存储线性表中的数据元素。顺序表的特点是逻辑上相邻的元素在物理存储位置上也相邻，因此可以通过元素的存储位置直接访问元素。

顺序表通常使用数组来实现，数组的下标对应元素的逻辑位置，数组的元素对应线性表中的数据元素。由于数组的存储空间是连续的，因此顺序表的插入、删除等操作可能需要移动大量元素，效率较低。

2. 顺序表的结构

在C语言中，顺序表通常使用结构体来表示。结构体中包含两个主要部分：数据元素数组和当前顺序表的长度。

#define MAXSIZE 100  // 定义顺序表的最大长度

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

2.1 数据元素数组

data数组用于存储顺序表中的数据元素。数组的大小通常定义为顺序表的最大长度MAXSIZE，这样可以确保顺序表在插入元素时不会超出数组的边界。

2.2 当前顺序表的长度

length表示当前顺序表中实际存储的元素个数。length的值总是小于或等于MAXSIZE。当length等于MAXSIZE时，顺序表已满，无法再插入新元素。

3. 顺序表的基本操作

顺序表的基本操作包括初始化、插入、删除、查找等。下面简要介绍这些操作的实现。

3.1 初始化顺序表

初始化顺序表时，将length设置为0，表示顺序表为空。

void InitList(SeqList *L) {
    L->length = 0;
}

3.2 插入元素

在顺序表的第i个位置插入元素e。插入操作需要将第i个位置及其后的元素依次后移，然后将e放入第i个位置。

int InsertList(SeqList *L, int i, int e) {
    if (L->length >= MAXSIZE) {
        return 0;  // 顺序表已满，插入失败
    }
    if (i < 1 || i > L->length + 1) {
        return 0;  // 插入位置不合法
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;  // 插入成功
}

3.3 删除元素

删除顺序表中第i个位置的元素。删除操作需要将第i+1个位置及其后的元素依次前移。

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

3.4 查找元素

查找顺序表中值为e的元素，并返回其位置。如果未找到，返回-1。

int LocateElem(SeqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;  // 返回元素的位置
        }
    }
    return -1;  // 未找到
}

4. 顺序表的优缺点

4.1 优点

• 随机访问：由于顺序表使用数组存储，可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
• 存储密度高：顺序表只存储数据元素，不需要额外的存储空间来维护元素之间的关系。

4.2 缺点

• 插入和删除效率低：在顺序表中插入或删除元素时，可能需要移动大量元素，时间复杂度为O(n)。
• 存储空间固定：顺序表的存储空间在初始化时就已确定，无法动态扩展。

5. 总结

顺序表是线性表的一种简单且常用的存储结构，适用于元素数量固定且需要频繁随机访问的场景。然而，由于插入和删除操作的效率较低，顺序表在处理动态数据时可能不太适用。在实际应用中，应根据具体需求选择合适的存储结构。