详解C语言之顺序表

什么是顺序表？

顺序表是一种数据结构，它是由一块连续的存储空间表示的线性表，可以通过下标直接寻址访问表中元素。顺序表的插入和删除操作比较困难，但是查找操作比较容易。它是一种静态的数据结构，不能动态改变其大小。

实现顺序表的基本结构

在C语言中，我们可以用数组来实现顺序表的基本结构，如下所示：

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

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

上述代码定义了一个存储整型数据的顺序表，同时定义了它的最大长度和当前长度。

基本操作

初始化操作

定义一个顺序表之后，需要对其进行初始化操作才能使用。初始化操作将顺序表长度设置为0。

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

插入操作

顺序表的插入操作需要将插入位置以后的元素依次后移，再在该位置插入新元素。下面是插入操作的实现代码：

int Insert(SeqList *L, int i, int x) {
    int j;
    if (L->length == MAXSIZE) {  // 当前顺序表已满，无法插入新元素
        return 0;
    }
    if (i < 1 || i > L->length+1) {  // 插入位置i不合法
        return 0;
    }
    for (j = L->length; j >= i; j--) {  // 将插入位置以后的元素依次后移
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = x;  // 在插入位置插入新元素
    L->length++;  // 顺序表长度加1
    return 1;
}

删除操作

顺序表的删除操作需要将删除位置以后的元素依次前移，再将最后一个元素删除。

int Delete(SeqList *L, int i) {
    int j;
    if (L->length == 0) {  // 当前顺序表为空，无法删除元素
        return 0;
    }
    if (i < 1 || i > L->length) {  // 删除位置i不合法
        return 0;
    }
    for (j = i; j < L->length; j++) {  // 将删除位置以后的元素依次前移
        L->data[j-1] = L->data[j];
    }
    L->length--;  // 顺序表长度减1
    return 1;
}

查找操作

顺序表的查找操作首先需要遍历整个顺序表，查找指定元素的位置，如下所示：

int Search(SeqList L, int x) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] == x) {
            return i+1;  // 返回元素在顺序表中的位置
        }
    }
    return 0;  // 未找到指定元素
}

示例

示例1：对已有顺序表按顺序插入元素

SeqList L;
InitList(&L);
int i;
for (i = 1; i <= 5; i++) {
    Insert(&L, i, i);
}

上述代码定义了一个空的顺序表L，并按照顺序插入了5个元素。最终顺序表的内容如下所示：

1   2   3   4   5

示例2：删除指定位置的元素

SeqList L;
InitList(&L);
Insert(&L, 1, 1);
Insert(&L, 2, 2);
Insert(&L, 3, 3);
if (Delete(&L, 2)) {
    printf("删除成功\n");
}

上述代码定义了一个包含3个元素的顺序表L，并删除了第2个位置（即元素2）。最终顺序表的内容如下所示：

1   3

总结

顺序表是一种存储线性表结构的数据结构，它的查找操作比较容易，但是插入和删除操作比较困难。在C语言中，我们可以用数组来实现顺序表的基本结构，并提供了初始化、插入、删除和查找等基本操作函数。