慕课堂顺序表练习从基础到进阶掌握数据结构核心技能

引言

顺序表（Sequential List）是数据结构中最基础、最核心的线性结构之一。它使用连续的内存空间来存储数据元素，通过数组实现，支持随机访问，是学习数据结构的入门必经之路。在慕课堂的练习体系中，从基础到进阶的顺序表练习，旨在帮助学习者深入理解线性表的逻辑结构、物理结构、基本操作及其性能分析，从而掌握数据结构的核心技能。本文将系统地介绍顺序表的基础知识、核心操作、进阶应用，并通过详尽的代码示例和实际问题分析，帮助读者从理论到实践全面掌握顺序表。

一、顺序表基础：概念与初始化

1.1 顺序表的定义与特点

顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。其特点是：

• 随机访问：通过下标可以直接访问任意位置的元素，时间复杂度为 O(1)。
• 存储密度高：只存储数据本身，无需额外指针。
• 插入和删除效率低：需要移动大量元素，平均时间复杂度为 O(n)。

1.2 顺序表的初始化

在C语言中，顺序表通常用结构体表示，包含一个数组和一个记录当前元素个数的变量。以下是初始化顺序表的示例代码：

#include <stdio.h>
#include <stdlib.h>

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

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

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

int main() {
    SeqList L;
    initSeqList(&L);
    printf("顺序表初始化成功，当前长度：%d\n", L.length);
    return 0;
}

代码说明：

• 定义了一个结构体 SeqList，包含一个固定大小的数组 data 和一个整型变量 length。
• initSeqList 函数将顺序表的长度初始化为0，表示空表。
• 在 main 函数中创建顺序表实例并调用初始化函数。

1.3 动态顺序表

为了更灵活地管理内存，可以使用动态数组实现顺序表。以下是动态顺序表的初始化示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;      // 指向动态数组的指针
    int capacity;   // 当前容量
    int length;     // 当前长度
} DynamicSeqList;

// 初始化动态顺序表
void initDynamicSeqList(DynamicSeqList *L, int capacity) {
    L->data = (int *)malloc(capacity * sizeof(int));
    if (L->data == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    L->capacity = capacity;
    L->length = 0;
}

// 释放动态顺序表内存
void freeDynamicSeqList(DynamicSeqList *L) {
    if (L->data != NULL) {
        free(L->data);
        L->data = NULL;
    }
    L->capacity = 0;
    L->length = 0;
}

int main() {
    DynamicSeqList L;
    initDynamicSeqList(&L, 10);
    printf("动态顺序表初始化成功，容量：%d，长度：%d\n", L.capacity, L.length);
    freeDynamicSeqList(&L);
    return 0;
}

代码说明：

• 动态顺序表使用指针 data 指向动态分配的内存，容量可扩展。
• initDynamicSeqList 函数分配指定容量的内存，并初始化长度和容量。
• freeDynamicSeqList 函数释放内存，避免内存泄漏。

二、顺序表核心操作：插入、删除与查找

2.1 插入操作

在顺序表的第 i 个位置插入元素 e，需要将第 i 到第 n 个元素向后移动一位，然后插入新元素。时间复杂度为 O(n)。

示例代码：

// 在顺序表L的第i个位置插入元素e，i从1开始计数
int insertSeqList(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        printf("插入位置无效！\n");
        return 0;
    }
    if (L->length >= MAX_SIZE) {
        printf("顺序表已满，无法插入！\n");
        return 0;
    }
    // 从后向前移动元素
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;  // 插入新元素
    L->length++;         // 长度加1
    return 1;
}

// 测试插入操作
int main() {
    SeqList L;
    initSeqList(&L);
    // 插入元素
    insertSeqList(&L, 1, 10);  // 插入第一个元素
    insertSeqList(&L, 2, 20);  // 插入第二个元素
    insertSeqList(&L, 1, 5);   // 在第一个位置插入5
    printf("插入后顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

插入后顺序表内容：5 10 20

代码说明：

• 检查插入位置是否有效（1 到 length+1）。
• 检查顺序表是否已满。
• 从后向前移动元素，为新元素腾出空间。
• 插入新元素并更新长度。

2.2 删除操作

删除顺序表的第 i 个元素，需要将第 i+1 到第 n 个元素向前移动一位。时间复杂度为 O(n)。

示例代码：

// 删除顺序表L的第i个元素，i从1开始计数
int deleteSeqList(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) {
        printf("删除位置无效！\n");
        return 0;
    }
    *e = L->data[i - 1];  // 保存被删除的元素
    // 从前向后移动元素
    for (int j = i - 1; j < L->length - 1; j++) {
        L->data[j] = L->data[j + 1];
    }
    L->length--;  // 长度减1
    return 1;
}

// 测试删除操作
int main() {
    SeqList L;
    initSeqList(&L);
    // 插入一些元素
    insertSeqList(&L, 1, 10);
    insertSeqList(&L, 2, 20);
    insertSeqList(&L, 3, 30);
    printf("删除前顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    
    int deleted;
    deleteSeqList(&L, 2, &deleted);  // 删除第二个元素
    printf("删除的元素：%d\n", deleted);
    printf("删除后顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

删除前顺序表内容：10 20 30
删除的元素：20
删除后顺序表内容：10 30

代码说明：

• 检查删除位置是否有效（1 到 length）。
• 保存被删除的元素到指针参数 e。
• 从前向后移动元素，覆盖被删除的位置。
• 更新长度。

2.3 查找操作

顺序表的查找通常指按值查找，返回第一个匹配元素的位置。时间复杂度为 O(n)。

示例代码：

// 在顺序表L中查找值为e的元素，返回位置（从1开始），未找到返回0
int locateSeqList(SeqList *L, int e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) {
            return i + 1;  // 位置从1开始
        }
    }
    return 0;  // 未找到
}

// 测试查找操作
int main() {
    SeqList L;
    initSeqList(&L);
    insertSeqList(&L, 1, 10);
    insertSeqList(&L, 2, 20);
    insertSeqList(&L, 3, 30);
    
    int pos = locateSeqList(&L, 20);
    if (pos != 0) {
        printf("值20在顺序表中的位置：%d\n", pos);
    } else {
        printf("值20未找到！\n");
    }
    return 0;
}

输出结果：

值20在顺序表中的位置：2

代码说明：

• 遍历顺序表，比较每个元素与目标值。
• 找到则返回位置（从1开始），否则返回0。

三、顺序表进阶：动态扩容与性能优化

3.1 动态扩容

动态顺序表在容量不足时需要扩容。常见的策略是倍增扩容（容量翻倍），以减少频繁扩容的开销。

示例代码：

// 动态顺序表扩容函数
int resizeDynamicSeqList(DynamicSeqList *L, int new_capacity) {
    int *new_data = (int *)realloc(L->data, new_capacity * sizeof(int));
    if (new_data == NULL) {
        printf("扩容失败！\n");
        return 0;
    }
    L->data = new_data;
    L->capacity = new_capacity;
    return 1;
}

// 在动态顺序表中插入元素
int insertDynamicSeqList(DynamicSeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        printf("插入位置无效！\n");
        return 0;
    }
    // 检查容量，不足则扩容
    if (L->length >= L->capacity) {
        int new_capacity = L->capacity * 2;  // 倍增策略
        if (!resizeDynamicSeqList(L, new_capacity)) {
            return 0;
        }
    }
    // 移动元素并插入
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

// 测试动态扩容
int main() {
    DynamicSeqList L;
    initDynamicSeqList(&L, 2);  // 初始容量为2
    
    // 插入元素，触发扩容
    insertDynamicSeqList(&L, 1, 10);
    insertDynamicSeqList(&L, 2, 20);
    insertDynamicSeqList(&L, 3, 30);  // 此时容量不足，触发扩容
    
    printf("插入后容量：%d，长度：%d\n", L.capacity, L.length);
    printf("顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    
    freeDynamicSeqList(&L);
    return 0;
}

输出结果：

插入后容量：4，长度：3
顺序表内容：10 20 30

代码说明：

• 当长度达到容量时，使用 realloc 扩容到原容量的两倍。
• 倍增策略使得扩容操作的均摊时间复杂度为 O(1)。

3.2 性能优化：减少元素移动

在插入和删除操作中，元素移动是主要开销。可以通过以下方式优化：

• 批量操作：一次性插入或删除多个元素，减少移动次数。
• 使用哨兵：在特定场景下使用哨兵简化边界判断。

示例：批量插入

// 批量插入：将数组arr中的元素插入到顺序表L的第i个位置
int batchInsertSeqList(SeqList *L, int i, int arr[], int n) {
    if (i < 1 || i > L->length + 1) {
        printf("插入位置无效！\n");
        return 0;
    }
    if (L->length + n > MAX_SIZE) {
        printf("顺序表空间不足！\n");
        return 0;
    }
    // 移动元素
    for (int j = L->length - 1; j >= i - 1; j--) {
        L->data[j + n] = L->data[j];
    }
    // 插入新元素
    for (int k = 0; k < n; k++) {
        L->data[i - 1 + k] = arr[k];
    }
    L->length += n;
    return 1;
}

// 测试批量插入
int main() {
    SeqList L;
    initSeqList(&L);
    int arr[] = {10, 20, 30};
    batchInsertSeqList(&L, 1, arr, 3);
    printf("批量插入后顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

批量插入后顺序表内容：10 20 30

代码说明：

• 批量插入时，先一次性移动所有元素，然后插入多个元素。
• 减少了循环次数，提高了效率。

四、顺序表应用：实际问题与解决方案

4.1 问题：合并两个有序顺序表

给定两个有序顺序表，合并成一个新的有序顺序表。

示例代码：

// 合并两个有序顺序表L1和L2到L3
void mergeSeqList(SeqList *L1, SeqList *L2, SeqList *L3) {
    int i = 0, j = 0, k = 0;
    while (i < L1->length && j < L2->length) {
        if (L1->data[i] <= L2->data[j]) {
            L3->data[k++] = L1->data[i++];
        } else {
            L3->data[k++] = L2->data[j++];
        }
    }
    // 处理剩余元素
    while (i < L1->length) {
        L3->data[k++] = L1->data[i++];
    }
    while (j < L2->length) {
        L3->data[k++] = L2->data[j++];
    }
    L3->length = k;
}

// 测试合并操作
int main() {
    SeqList L1, L2, L3;
    initSeqList(&L1);
    initSeqList(&L2);
    initSeqList(&L3);
    
    // 插入有序数据
    insertSeqList(&L1, 1, 10);
    insertSeqList(&L1, 2, 30);
    insertSeqList(&L1, 3, 50);
    
    insertSeqList(&L2, 1, 20);
    insertSeqList(&L2, 2, 40);
    insertSeqList(&L2, 3, 60);
    
    mergeSeqList(&L1, &L2, &L3);
    
    printf("合并后顺序表内容：");
    for (int i = 0; i < L3.length; i++) {
        printf("%d ", L3.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

合并后顺序表内容：10 20 30 40 50 60

代码说明：

• 使用双指针法，比较两个顺序表的元素，依次放入新顺序表。
• 时间复杂度为 O(m+n)，其中 m 和 n 是两个顺序表的长度。

4.2 问题：顺序表去重

给定一个顺序表，去除重复元素，保持元素顺序不变。

示例代码：

// 去除顺序表中的重复元素
void removeDuplicates(SeqList *L) {
    if (L->length <= 1) return;
    int k = 1;  // 新顺序表的长度
    for (int i = 1; i < L->length; i++) {
        int j;
        for (j = 0; j < k; j++) {
            if (L->data[i] == L->data[j]) {
                break;
            }
        }
        if (j == k) {  // 未找到重复
            L->data[k] = L->data[i];
            k++;
        }
    }
    L->length = k;
}

// 测试去重操作
int main() {
    SeqList L;
    initSeqList(&L);
    insertSeqList(&L, 1, 10);
    insertSeqList(&L, 2, 20);
    insertSeqList(&L, 3, 10);
    insertSeqList(&L, 4, 30);
    insertSeqList(&L, 5, 20);
    
    printf("去重前顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    
    removeDuplicates(&L);
    
    printf("去重后顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

去重前顺序表内容：10 20 10 30 20
去重后顺序表内容：10 20 30

代码说明：

• 使用双指针法，k 指向新顺序表的末尾，i 遍历原顺序表。
• 对于每个元素，检查是否在新顺序表中已存在，若不存在则加入。
• 时间复杂度为 O(n²)，对于大数据集效率较低，但逻辑简单。

五、顺序表的高级应用：与算法结合

5.1 顺序表在排序算法中的应用

顺序表是许多排序算法的基础，如冒泡排序、插入排序、快速排序等。

示例：顺序表的插入排序

// 对顺序表进行插入排序
void insertionSort(SeqList *L) {
    for (int i = 1; i < L->length; i++) {
        int key = L->data[i];
        int j = i - 1;
        // 将大于key的元素向后移动
        while (j >= 0 && L->data[j] > key) {
            L->data[j + 1] = L->data[j];
            j--;
        }
        L->data[j + 1] = key;
    }
}

// 测试插入排序
int main() {
    SeqList L;
    initSeqList(&L);
    insertSeqList(&L, 1, 50);
    insertSeqList(&L, 2, 20);
    insertSeqList(&L, 3, 40);
    insertSeqList(&L, 4, 10);
    insertSeqList(&L, 5, 30);
    
    printf("排序前顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    
    insertionSort(&L);
    
    printf("排序后顺序表内容：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

排序前顺序表内容：50 20 40 10 30
排序后顺序表内容：10 20 30 40 50

代码说明：

• 插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 时间复杂度为 O(n²)，但对小规模数据或基本有序的数据效率较高。

5.2 顺序表在查找算法中的应用

顺序表支持二分查找，前提是顺序表有序。

示例：顺序表的二分查找

// 对有序顺序表进行二分查找，返回位置（从1开始），未找到返回0
int binarySearch(SeqList *L, int e) {
    int low = 0, high = L->length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (L->data[mid] == e) {
            return mid + 1;  // 位置从1开始
        } else if (L->data[mid] < e) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return 0;
}

// 测试二分查找
int main() {
    SeqList L;
    initSeqList(&L);
    // 插入有序数据
    insertSeqList(&L, 1, 10);
    insertSeqList(&L, 2, 20);
    insertSeqList(&L, 3, 30);
    insertSeqList(&L, 4, 40);
    insertSeqList(&L, 5, 50);
    
    int pos = binarySearch(&L, 30);
    if (pos != 0) {
        printf("值30在顺序表中的位置：%d\n", pos);
    } else {
        printf("值30未找到！\n");
    }
    return 0;
}

输出结果：

值30在顺序表中的位置：3

代码说明：

• 二分查找每次将搜索范围减半，时间复杂度为 O(log n)。
• 要求顺序表必须有序，否则无法使用。

六、顺序表的局限性及改进方向

6.1 顺序表的局限性

• 插入和删除效率低：需要移动大量元素，不适合频繁插入和删除的场景。
• 容量固定：静态顺序表容量固定，容易溢出或浪费空间。
• 内存连续性要求：需要连续的内存空间，可能难以分配大块内存。

6.2 改进方向：链表

当顺序表的插入和删除操作频繁时，可以考虑使用链表。链表通过指针链接元素，插入和删除只需修改指针，时间复杂度为 O(1)，但牺牲了随机访问能力。

示例：单链表的插入操作

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 在单链表的第i个位置插入元素e
int insertLinkedList(Node **head, int i, int e) {
    if (i < 1) {
        printf("插入位置无效！\n");
        return 0;
    }
    Node *new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("内存分配失败！\n");
        return 0;
    }
    new_node->data = e;
    
    if (i == 1) {
        new_node->next = *head;
        *head = new_node;
        return 1;
    }
    
    Node *p = *head;
    int j = 1;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL) {
        printf("插入位置超出链表长度！\n");
        free(new_node);
        return 0;
    }
    
    new_node->next = p->next;
    p->next = new_node;
    return 1;
}

代码说明：

• 链表插入只需修改指针，无需移动元素。
• 适合频繁插入和删除的场景，但访问元素需要遍历，时间复杂度为 O(n)。

七、总结

通过慕课堂的顺序表练习，从基础到进阶，我们系统地掌握了顺序表的核心技能：

1. 基础操作：初始化、插入、删除、查找，理解顺序表的逻辑结构和物理结构。
2. 进阶技能：动态扩容、性能优化、批量操作，提升顺序表的实用性和效率。
3. 实际应用：合并有序表、去重、排序和查找算法，将顺序表与算法结合解决实际问题。
4. 局限性分析：认识到顺序表的不足，并了解链表作为替代方案的优势。

顺序表作为数据结构的基石，其原理和操作是学习更复杂数据结构（如栈、队列、树、图）的基础。通过不断练习和实践，可以深入理解数据结构的核心思想，为后续学习打下坚实基础。建议读者在慕课堂中完成相关练习，结合代码实现，加深理解，逐步掌握数据结构的核心技能。