C语言经典顺序表实例分析

1. 引言

顺序表是数据结构中最基础、最常用的线性表实现方式之一。它通过一段连续的存储空间来存储数据元素，具有随机访问、存储密度高等优点。本文将深入分析C语言中顺序表的实现原理，并通过经典实例来展示其应用。

2. 顺序表的基本概念

2.1 顺序表的定义

顺序表（Sequential List）是用一组地址连续的存储单元依次存储线性表中的数据元素。顺序表中的元素在逻辑上相邻，在物理存储上也相邻。

2.2 顺序表的特点

• 随机访问：可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
• 存储密度高：顺序表只存储数据元素，不需要额外的存储空间来存储逻辑关系。
• 插入和删除效率低：在顺序表中插入或删除元素时，需要移动大量元素，时间复杂度为O(n)。

3. 顺序表的C语言实现

3.1 顺序表的结构定义

在C语言中，顺序表通常使用数组来实现。我们可以定义一个结构体来表示顺序表：

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

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

3.2 顺序表的基本操作

3.2.1 初始化顺序表

初始化顺序表时，将顺序表的长度设置为0：

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

3.2.2 插入元素

在顺序表的第i个位置插入元素e：

int InsertList(SeqList *L, int i, int e) {
    if (L->length == MAXSIZE) {
        return 0;  // 顺序表已满，插入失败
    }
    if (i < 1 || i > L->length + 1) {
        return 0;  // 插入位置不合法
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];  // 将第i个位置及之后的元素后移
    }
    L->data[i - 1] = e;  // 插入新元素
    L->length++;         // 顺序表长度加1
    return 1;            // 插入成功
}

3.2.3 删除元素

删除顺序表中第i个位置的元素：

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

3.2.4 查找元素

查找顺序表中值为e的元素的位置：

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

3.2.5 获取元素

获取顺序表中第i个位置的元素：

int GetElem(SeqList *L, int i) {
    if (i < 1 || i > L->length) {
        return -1;  // 位置不合法
    }
    return L->data[i - 1];  // 返回元素值
}

4. 顺序表的经典实例分析

4.1 实例1：顺序表的合并

问题描述：有两个顺序表La和Lb，分别存储了若干有序整数。要求将这两个顺序表合并为一个新的有序顺序表Lc。

解决方案：

void MergeList(SeqList *La, SeqList *Lb, SeqList *Lc) {
    int i = 0, j = 0, k = 0;
    while (i < La->length && j < Lb->length) {
        if (La->data[i] <= Lb->data[j]) {
            Lc->data[k++] = La->data[i++];
        } else {
            Lc->data[k++] = Lb->data[j++];
        }
    }
    while (i < La->length) {
        Lc->data[k++] = La->data[i++];
    }
    while (j < Lb->length) {
        Lc->data[k++] = Lb->data[j++];
    }
    Lc->length = k;
}

分析：该算法的时间复杂度为O(n)，其中n为La和Lb的长度之和。通过逐个比较La和Lb中的元素，将较小的元素插入到Lc中，最终得到一个有序的顺序表Lc。

4.2 实例2：顺序表的逆置

问题描述：给定一个顺序表L，要求将其元素逆置。

解决方案：

void ReverseList(SeqList *L) {
    int temp;
    for (int i = 0; i < L->length / 2; i++) {
        temp = L->data[i];
        L->data[i] = L->data[L->length - i - 1];
        L->data[L->length - i - 1] = temp;
    }
}

分析：该算法的时间复杂度为O(n/2)，即O(n)。通过交换顺序表中对称位置的元素，实现了顺序表的逆置。

4.3 实例3：顺序表的去重

问题描述：给定一个顺序表L，要求删除其中重复的元素，使得每个元素只出现一次。

解决方案：

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

分析：该算法的时间复杂度为O(n)，其中n为顺序表的长度。通过双指针法，遍历顺序表并将不重复的元素保留下来，最终得到一个去重后的顺序表。

5. 顺序表的优缺点总结

5.1 优点

• 随机访问：顺序表支持通过下标直接访问任意位置的元素，访问速度快。
• 存储密度高：顺序表只存储数据元素，不需要额外的存储空间来存储逻辑关系，存储密度高。

5.2 缺点

• 插入和删除效率低：在顺序表中插入或删除元素时，需要移动大量元素，时间复杂度为O(n)。
• 存储空间固定：顺序表的存储空间在初始化时就已经确定，无法动态调整大小。

6. 结语

顺序表作为最基础的数据结构之一，在实际应用中有着广泛的应用。通过本文的分析，我们了解了顺序表的基本概念、C语言实现以及经典实例。掌握顺序表的实现和应用，对于深入理解数据结构和算法具有重要意义。希望本文能为读者提供有价值的参考和帮助。