C++ 数据结构：超详细讲解顺序表

什么是顺序表

顺序表是一种线性结构，它用一段地址连续的存储单元依次存储线性表中的各个元素。

顺序表的结构

顺序表由两部分组成，分别是元素存储区和表长度信息。元素存储区通常用数组实现，表长度信息记录表中元素的个数。

顺序表的操作

常见的顺序表操作包括：

• 初始化操作
• 插入操作
• 删除操作
• 查找操作
• 遍历操作

初始化顺序表

初始化顺序表需要定义一个数组和一个整型变量来存储表内数据和表长：

#define MAXSIZE 100
typedef struct{
    int elem[MAXSIZE];
    int length;
}SqList;

其中，MAXSIZE 代表数组最大长度，elem 数组用于存放元素，length 表示顺序表的元素个数。

初始化操作可以用以下代码实现：

void initList(SqList &L){
    L.length = 0;
    memset(L.elem, 0, sizeof(L.elem));
}

插入操作

在顺序表中插入一个元素，需要将该元素插入到数组的指定位置。

bool insert(SqList &L, int index, int value) {
    // 检查插入位置是否合法
    if (index < 1 || index > L.length + 1) {
        return false;
    }
    // 将插入位置之后的元素后移
    for (int i = L.length; i >= index; i--) {
        L.elem[i] = L.elem[i - 1];
    }
    // 插入元素
    L.elem[index - 1] = value;
    L.length += 1;
    return true;
}

删除操作

删除顺序表中的一个元素，需要将该位置之后的所有元素向前移动。

bool deleteElement(SqList &L, int index, int &value) {
    if (index < 1 || index > L.length) {
        return false;
    }
    // 取出要删除的元素
    value = L.elem[index - 1];
    // 将该元素之后的所有元素向前移动
    for (int i = index - 1; i < L.length - 1; i++) {
        L.elem[i] = L.elem[i + 1];
    }
    L.length -= 1;
    return true;
}

查找操作

查找顺序表中一个元素的位置，可以使用以下代码实现：

int searchElement(SqList L, int value) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == value) {
            return i + 1;
        }
    }
    return 0;
}

遍历操作

遍历顺序表中的所有元素，可以使用以下代码实现：

void traverseList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        cout << L.elem[i] << " ";
    }
    cout << endl;
}

示例说明

示例1：插入一个元素

在顺序表中第二个位置上插入元素 3。

SqList L;
initList(L);
L.elem[0] = 1;
L.elem[1] = 2;
L.length = 2;

insert(L, 2, 3);
traverseList(L);

输出结果：

1 3 2

示例2：删除一个元素

删除顺序表中第二个位置上的元素，并输出删除的元素值。

SqList L;
initList(L);
L.elem[0] = 1;
L.elem[1] = 2;
L.elem[2] = 3;
L.length = 3;

int value;
deleteElement(L, 2, value);
cout << value << endl;
traverseList(L);

输出结果：

2
1 3

总结

顺序表是一种常用的线性结构，实现起来也比较容易。可以使用数组来存放顺序表中的元素，通过数组下标来访问和操作元素。