C语言编程简单却重要的数据结构顺序表全面讲解

什么是顺序表？

顺序表是一种线性表，指的是一组有限元素的有限序列，其元素的逻辑顺序与它们在分配到的内存地址上的物理顺序相同或者等价。也就是说，顺序表中的元素按照其在内存中的位置依次存放。

顺序表的实现方式

顺序表的实现方式一般是使用数组，数组中的每一个元素对应着顺序表中的一个元素，位置相对应。

顺序表的优点

• 支持随机访问，时间复杂度为O(1)
• 可以进行排序和查找

实现顺序表的基本操作

1. 初始化

初始化顺序表需要定义一个数组进行存储，同时需要定义一个变量保存当前已经存储的元素数量。

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

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

2. 插入元素

插入元素即在指定位置插入一个新的元素，需要将该位置后面的元素全部后移一位，然后在该位置赋值为新元素。

bool ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return false;
    if (L->length >= MAXSIZE) return false;
    for (int j = L->length; j >= i; j--) L->data[j] = L->data[j - 1];
    L->data[i - 1] = e;
    L->length++;
    return true;
}

3. 删除元素

删除元素即删除指定位置的元素，需要将该位置后面的元素全部前移一位，然后将顺序表的长度减1。

bool ListDelete(SqList *L, int i) {
    if (i < 1 || i > L->length) return false;
    for (int j = i; j < L->length; j++) L->data[j - 1] = L->data[j];
    L->length--;
    return true;
}

4. 查找元素

查找元素即根据元素的值查找该元素在顺序表中的位置。需要遍历整个顺序表，比较每一个元素的值。

int LocateElem(SqList *L, int e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) return i + 1;
    }
    return 0;
}

示例说明

示例一

假设有以下代码：

SqList L;
InitList(&L);
ListInsert(&L, 1, 1);
ListInsert(&L, 2, 2);
ListInsert(&L, 3, 3);
ListInsert(&L, 4, 4);
ListInsert(&L, 5, 5);
ListDelete(&L, 3);
int n = LocateElem(&L, 4);

执行结果为：

1 2 4 5
3

示例二

假设有以下代码：

SqList L;
InitList(&L);
ListInsert(&L, 1, 1);
ListInsert(&L, 2, 2);
ListInsert(&L, 3, 3);
ListInsert(&L, 4, 4);
ListInsert(&L, 5, 5);
int n = LocateElem(&L, 6);

执行结果为：

false

以上代码通过两个示例说明了顺序表的基本操作，包括初始化、插入元素、删除元素、查找元素。希望对理解顺序表的实现有所帮助。