C语言顺序表如何实现

顺序表是线性表的一种存储结构，它使用一段连续的存储单元依次存储线性表中的数据元素。顺序表的特点是逻辑上相邻的元素在物理存储上也相邻，因此可以通过下标直接访问元素，具有随机访问的特性。本文将介绍如何使用C语言实现顺序表。

1. 顺序表的定义

顺序表通常使用数组来实现。数组的大小决定了顺序表的最大容量，而顺序表的实际长度则通过一个变量来记录。顺序表的结构定义如下：

#define MAX_SIZE 100  // 定义顺序表的最大容量

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

• data：用于存储数据元素的数组，数组的大小为MAX_SIZE。
• length：表示当前顺序表中实际存储的元素个数。

2. 顺序表的初始化

顺序表的初始化操作是将顺序表的长度设置为0，表示顺序表为空。

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

3. 顺序表的插入操作

顺序表的插入操作是指在顺序表的指定位置插入一个元素。插入操作需要将插入位置及其后面的元素依次向后移动，为新元素腾出空间。

int InsertList(SeqList *L, int pos, int value) {
    if (pos < 1 || pos > L->length + 1) {
        return 0;  // 插入位置不合法
    }
    if (L->length >= MAX_SIZE) {
        return 0;  // 顺序表已满，无法插入
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];  // 将插入位置及其后面的元素后移
    }
    L->data[pos - 1] = value;  // 插入新元素
    L->length++;  // 顺序表长度加1
    return 1;  // 插入成功
}

• pos：插入的位置，从1开始计数。
• value：要插入的元素值。
• 返回值：插入成功返回1，失败返回0。

4. 顺序表的删除操作

顺序表的删除操作是指删除顺序表中指定位置的元素。删除操作需要将删除位置后面的元素依次向前移动，填补删除后的空缺。

int DeleteList(SeqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        return 0;  // 删除位置不合法
    }
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];  // 将删除位置后面的元素前移
    }
    L->length--;  // 顺序表长度减1
    return 1;  // 删除成功
}

• pos：删除的位置，从1开始计数。
• 返回值：删除成功返回1，失败返回0。

5. 顺序表的查找操作

顺序表的查找操作是指在顺序表中查找指定元素的位置。由于顺序表支持随机访问，查找操作可以通过遍历数组来实现。

int FindList(SeqList *L, int value) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == value) {
            return i + 1;  // 返回元素的位置（从1开始计数）
        }
    }
    return 0;  // 未找到元素
}

• value：要查找的元素值。
• 返回值：找到元素返回其位置（从1开始计数），未找到返回0。

6. 顺序表的遍历操作

顺序表的遍历操作是指依次访问顺序表中的每个元素。遍历操作可以通过循环遍历数组来实现。

void TraverseList(SeqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);  // 输出顺序表中的元素
    }
    printf("\n");
}

7. 顺序表的完整示例

下面是一个完整的顺序表操作示例，包括初始化、插入、删除、查找和遍历操作。

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;
} SeqList;

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

int InsertList(SeqList *L, int pos, int value) {
    if (pos < 1 || pos > L->length + 1) {
        return 0;
    }
    if (L->length >= MAX_SIZE) {
        return 0;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = value;
    L->length++;
    return 1;
}

int DeleteList(SeqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        return 0;
    }
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return 1;
}

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

void TraverseList(SeqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    SeqList L;
    InitList(&L);

    InsertList(&L, 1, 10);
    InsertList(&L, 2, 20);
    InsertList(&L, 3, 30);
    TraverseList(&L);  // 输出: 10 20 30

    DeleteList(&L, 2);
    TraverseList(&L);  // 输出: 10 30

    int pos = FindList(&L, 30);
    if (pos) {
        printf("元素30的位置是: %d\n", pos);  // 输出: 元素30的位置是: 2
    } else {
        printf("未找到元素30\n");
    }

    return 0;
}

8. 总结

顺序表是一种简单且高效的线性表存储结构，适用于元素数量固定或变化不大的场景。通过数组实现顺序表，可以方便地进行插入、删除、查找和遍历操作。然而，顺序表的插入和删除操作需要移动大量元素，时间复杂度为O(n)，因此在元素频繁变动的场景下，顺序表的效率较低。此时，可以考虑使用链表等其他数据结构。