重生之我在异世界学编程之算法与数据结构：深入静态顺序表篇-正文

一、顺序表的概念及结构

1. 顺序表的定义

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素的线性表。其特点是逻辑上相邻的元素在物理位置上也相邻。顺序表一般使用数组来实现。

2. 顺序表的结构

顺序表的基本结构包括一个用于存储数据元素的数组和一个表示当前顺序表长度的变量（通常称为“长度”或“size”）。此外，为了操作的方便和高效，有时还需要设置一个“最大容量”（通常称为“capacity”）来表示顺序表可以容纳的最大元素个数。

如下所示：

#define MAXSIZE 100  // 定义顺序表的最大容量
typedef int ElemType; // 定义顺序表中存储的数据类型

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

在上述结构中，data是一个一维数组，用于存放顺序表中的元素；length是一个整型变量，用于记录顺序表中当前所含元素的个数。

3. 顺序表的初始化

顺序表的初始化操作主要是设置其长度为0，并可以根据需要为其分配存储空间（如果采用动态分配的话）。

以下是一个简单的初始化函数示例：

void InitList(SqList *L) {
    L->length = 0; // 将顺序表的长度初始化为0
}

注意：

这里我们假设顺序表的存储空间已经通过定义结构体时分配的数组来实现了，因此不需要额外的内存分配操作。如果需要动态分配存储空间，则需要在初始化函数中调用相应的内存分配函数（如malloc）来为data数组分配内存。

二、顺序表的基本操作（静态）

1. 插入操作

在顺序表中插入一个新元素时，需要找到插入位置，然后将该位置及其后的所有元素都向后移动一位，最后将新元素放入指定位置。插入操作的时间复杂度为O(n)，其中n是顺序表的长度。

以下是插入操作的实现代码：

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

bool ListInsert(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length + 1) {
        return false; // 插入位置不合法
    }
    if (L->length >= MAXSIZE) {
        return false; // 顺序表已满，无法插入新元素
    }
    for (int k = L->length - 1; k >= i - 1; k--) {
        L->data[k + 1] = L->data[k]; // 将插入位置及其后的元素后移一位
    }
    L->data[i - 1] = e; // 在指定位置插入新元素
    L->length++; // 顺序表长度加1
    return true;
}

在上述代码中，我们首先检查插入位置是否合法以及顺序表是否已经满员。然后，从顺序表的末尾开始向前遍历，将插入位置及其后的所有元素都向后移动一位。最后，在指定位置插入新元素，并将顺序表的长度加1。

2. 删除操作

在顺序表中删除一个元素时，需要找到要删除的元素的位置，然后将该位置之后的所有元素都向前移动一位。删除操作的时间复杂度也为O(n)。

以下是删除操作的实现代码：

bool ListDelete(SqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length) {
        return false; // 删除位置不合法
    }
    *e = L->data[i - 1]; // 保存被删除的元素的值
    for (int k = i; k < L->length; k++) {
        L->data[k - 1] = L->data[k]; // 将删除位置之后的元素前移一位
    }
    L->length--; // 顺序表长度减1
    return true;
}

在上述代码中，我们首先检查删除位置是否合法。然后，将要删除的元素的值保存到参数e指向的变量中。接着，从删除位置开始向后遍历，将删除位置之后的所有元素都向前移动一位。最后，将顺序表的长度减1。

3. 查找操作

在顺序表中查找一个元素时，需要从头到尾依次比较每个元素与目标值的大小关系，直到找到目标值或者遍历完整个顺序表为止。查找操作的时间复杂度为O(n)。

以下是按值查找操作的实现代码：

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; // 返回查找到的元素的位序（从1开始计数）
        }
    }
    return 0; // 未找到目标元素，返回0或其他特殊标记值
}

在上述代码中，我们使用了一个循环来遍历顺序表中的每个元素，并将其与目标值进行比较。如果找到了目标值，则返回其在顺序表中的位序（从1开始计数）；否则，返回0或其他特殊标记值来表示未找到目标元素。

另外，还可以根据元素的位序来查找对应的元素值。这种操作的时间复杂度也是O(1)（因为可以直接通过下标访问），但前提是已知元素的位序且该位序在顺序表的范围内内有效。

4. 更新操作

更新操作是指修改顺序表中某个位置的元素的值。由于顺序表是基于数组的实现的，因此可以通过直接访问数组的下标来快速定位并修改指定位置的元素的值。更新操作的时间复杂度为O(1)。

以下是更新操作的实现代码：

bool ListUpdate(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length) {
        return false; // 修改位置不合法
    }
    L->data[i - 1] = e; // 修改指定位置的元素的值
    return true;
}

在上述代码中，我们首先检查修改位置是否合法。然后，直接通过下标访问并修改指定位置的元素的值。

5. 获取元素操作

获取元素操作是指获取顺序表中某个位置的元素的值。与更新操作类似，由于顺序表是基于数组的实现的，因此可以通过直接访问数组的下标来快速获取指定位置的元素的值。获取元素操作的时间复杂度也为O(1)。

以下是获取元素操作的实现代码：

bool GetElem(SqList L, int i, ElemType *e) {
    if (i < 1 || i > L.length) {
        return false; // 获取位置不合法
    }
    *e = L.data[i - 1]; // 获取指定位置的元素的值
    return true;
}

在上述代码中，我们首先检查获取位置是否合法。然后，直接通过下标访问并获取指定位置的元素的值，并将其保存到参数e指向的变量中。

6. 遍历操作

遍历操作是指依次访问顺序表中的每个元素，并对它们进行某种处理（如打印输出）。遍历操作可以使用循环语句来实现，时间复杂度为O(n)。

以下是遍历操作的实现代码：

void TraverseList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]); // 打印输出每个元素的值（假设元素类型为整型）
    }
    printf("
");
}

在上述代码中，我们使用了一个循环来遍历顺序表中的每个元素，并使用printf函数将其打印输出。当然，在实际应用中，对元素的处理方式可能更加复杂多样。

7. 求顺序表的长度

求顺序表的长度操作是指获取顺序表中当前所含元素的个数。由于顺序表的长度是通过一个整型变量来记录的，因此该操作的时间复杂度为O(1)。

以下是求顺序表长度的实现代码：

int ListLength(SqList L) {
    return L.length; // 返回顺序表的长度
}

在上述代码中，我们直接返回了顺序表的长度变量的值。

8. 判断顺序表是否为空

判断顺序表是否为空操作是指检查顺序表中是否包含任何元素。这可以通过比较顺序表的长度与0的大小关系来实现，时间复杂度为O(1)。

以下是判断顺序表是否为空的实现代码：

bool IsEmpty(SqList L) {
    return L.length == 0; // 如果顺序表的长度为0，则表示为空表
}

在上述代码中，我们比较了顺序表的长度与0的大小关系，并根据结果返回一个布尔值来表示顺序表是否为空。

秒客网