数据结构：顺序表（Sequence List）及其实现

什么是顺序表？

顺序表是一种最简单的数据结构，它就像一排连续的小房子，每个房子里都住着一个数据元素。这些房子是按顺序排列的，每个房子都有一个门牌号（下标），我们可以通过门牌号快速找到对应的数据。

顺序表的核心特点是：数据在内存中是连续存储的。正因为数据是连续的，所以我们可以通过下标快速访问任意位置的元素。

顺序表的原理

顺序表的底层通常是用数组实现的。数组是一块连续的内存空间，每个元素都紧挨着存储。比如，我们定义一个数组 int arr[10]，它就在内存中占用了 10 个连续的整数空间。

顺序表的优点：

1. 访问速度快：通过下标可以直接访问元素，时间复杂度是 O(1)。

2. 实现简单：用数组就能实现，代码容易理解。

顺序表的缺点：

1. 插入和删除慢：如果要在中间插入或删除元素，需要移动大量数据，时间复杂度是 O(n)。

2. 大小固定：数组的大小是固定的，如果数据量超过数组容量，需要重新分配更大的空间。

3. 顺序表的基本操作

   顺序表的基本操作包括：增、删、查、改。下面我们用大白话解释这些操作。

4. 增加元素：

   • 在顺序表的末尾添加一个元素很简单，直接放到最后一个空位就行。

   • 如果要在中间插入元素，就需要把后面的元素都往后挪，腾出位置。

5. 删除元素：

   • 删除末尾元素很简单，直接丢掉就行。

   • 如果删除中间的元素，就需要把后面的元素都往前挪，填补空缺。

6. 查找元素：

   • 通过下标可以直接找到元素，速度很快。

   • 如果要根据值查找元素，需要从头到尾遍历，直到找到目标。

7. 修改元素：

   • 通过下标找到元素后，直接修改它的值就行。

C 语言实现顺序表

下面是一个简单的顺序表实现代码，包含初始化、插入、删除、查找和打印功能。

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

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

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

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

// 插入元素
int InsertList(SeqList *list, int index, int value) {
    if (index < 0 || index > list->length || list->length == MAX_SIZE) {
        return -1;  // 插入位置不合法或顺序表已满
    }
    // 将插入位置后的元素往后挪
    for (int i = list->length; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;  // 插入新元素
    list->length++;             // 长度加 1
    return 0;
}

// 删除元素
int DeleteList(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        return -1;  // 删除位置不合法
    }
    // 将删除位置后的元素往前挪
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;  // 长度减 1
    return 0;
}

// 查找元素
int FindList(SeqList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i;  // 返回元素的下标
        }
    }
    return -1;  // 未找到
}

// 打印顺序表
void PrintList(SeqList *list) {
    printf("顺序表内容：");
    for (int i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

int main() {
    SeqList list;
    InitList(&list);  // 初始化顺序表

    // 插入元素
    InsertList(&list, 0, 10);  // 在第 0 个位置插入 10
    InsertList(&list, 1, 20);  // 在第 1 个位置插入 20
    InsertList(&list, 2, 30);  // 在第 2 个位置插入 30
    PrintList(&list);          // 打印顺序表

    // 删除元素
    DeleteList(&list, 1);  // 删除第 1 个位置的元素
    PrintList(&list);      // 打印顺序表

    // 查找元素
    int index = FindList(&list, 30);
    if (index != -1) {
        printf("元素 30 的下标是：%d\n", index);
    } else {
        printf("未找到元素 30\n");
    }

    return 0;
}

顺序表的使用场景

1. 数据量固定且需要快速访问：比如存储一周的温度数据，数据量固定，且需要快速访问某一天的温度。

2. 简单的数据存储：比如存储学生的成绩列表，数据量不大，且不需要频繁插入和删除。

3. 作为其他数据结构的基础：顺序表是很多高级数据结构（如栈、队列）的基础。

下面是一个顺序表的示意图：

下标： 0    1    2    3    4
数据：[10, 20, 30, 40, 50]
长度：5

• 每个格子代表一个数据元素，下标从 0 开始。

• 数据是连续存储的，就像一排小房子。

顺序表与数组的区别

顺序表和数组看起来很相似，但它们之间有一些关键的区别。为了更好地理解，我们可以把顺序表看作是一个“高级版”的数组，它在数组的基础上增加了一些功能和灵活性。

1. 数组是什么？

数组是一种最基本的数据结构，它是一块连续的内存空间，用来存储相同类型的数据。比如：

int arr[5] = {10, 20, 30, 40, 50};

数组的特点是：

• 大小固定：数组一旦定义，大小就不能改变了。

• 直接访问：通过下标可以快速访问任意位置的元素。

• 功能单一：数组只负责存储数据，没有额外的功能（比如动态扩容）。

2. 顺序表是什么？

顺序表是基于数组实现的，但它比数组更“智能”。顺序表不仅用数组存储数据，还记录了当前存储的元素个数（长度），并提供了一些常用的操作（比如插入、删除、查找等）。

顺序表的特点是：

• 动态管理：顺序表可以动态管理数据，比如插入、删除元素。

• 长度可变：顺序表的长度可以根据需要变化（虽然底层数组大小固定，但可以通过重新分配数组实现扩容）。

• 功能丰富：顺序表封装了常用的操作，使用起来更方便。

3. 顺序表和数组的区别

4. 代码对比

数组的用法：

int arr[5] = {10, 20, 30, 40, 50};  // 定义一个数组
arr[2] = 100;  // 修改第 3 个元素
printf("%d\n", arr[2]);  // 访问第 3 个元素

顺序表的用法：

// 定义顺序表
typedef struct {
    int data[100];  // 底层数组
    int length;     // 当前长度
} SeqList;

// 插入元素
void InsertList(SeqList *list, int index, int value) {
    // 插入逻辑（需要移动元素）
}

// 删除元素
void DeleteList(SeqList *list, int index) {
    // 删除逻辑（需要移动元素）
}

// 使用顺序表
SeqList list;
list.length = 0;  // 初始化长度
InsertList(&list, 0, 10);  // 插入元素
DeleteList(&list, 0);      // 删除元素

从代码中可以看出，顺序表比数组更“高级”，它封装了更多的功能，使用起来更方便。

5. 使用场景对比

数组的使用场景：

• 数据量固定，比如存储一周的天数（7 天）。

• 只需要简单的存储和访问，不需要频繁插入和删除。

顺序表的使用场景：

• 数据量不确定，比如存储用户输入的数据。

• 需要频繁插入、删除、查找等操作。

6. 图片对比

数组示意图：

下标： 0    1    2    3    4
数据：[10, 20, 30, 40, 50]

• 数组的大小固定为 5，无法动态扩展。

顺序表示意图：

下标： 0    1    2    3    4    5    6    7
数据：[10, 20, 30, 40, 50,  _,  _,  _]
长度：5

• 顺序表的底层数组大小可以更大（比如 8），但只使用了前 5 个位置。

• 可以通过插入操作动态增加数据。

总结

• 数组是最基础的数据结构，适合数据量固定、操作简单的场景。

• 顺序表是基于数组实现的“高级版”，适合数据量变化、操作复杂的场景。

顺序表是一种简单而实用的数据结构，适合数据量固定且需要快速访问的场景。它的实现简单，但插入和删除操作效率较低。通过学习顺序表，我们可以更好地理解更复杂的数据结构。希望这篇文章能帮你轻松掌握顺序表！

版权声明：本文为原创文章，转载请注明出处。