主页 > 软件开发 >

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

软件开发
2025-09-03 11:33:02

什么是顺序表？

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

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

顺序表的原理

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

顺序表的优点：

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

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

顺序表的缺点：

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

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

顺序表的基本操作

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

增加元素：

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

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

删除元素：

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

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

查找元素：

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

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

修改元素：

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

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; } 顺序表的使用场景

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

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

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

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

下标： 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，无法动态扩展。