网站导航
> 技术文档 > 【数据结构】数据结构入门：顺序表详解与实践指南

【数据结构】数据结构入门：顺序表详解与实践指南

网友: 技术文档 2025-09-02 19:03:19

【数据结构】数据结构入门：顺序表详解与实践指南

数据结构入门：顺序表详解与实践指南

✨前言：数据结构作为计算机科学的核心基础，是每位程序员必须掌握的技能。顺序表作为最简单、最基础的数据结构之一，不仅能够帮助我们理解数据的存储与组织方式，更是后续学习更复杂数据结构的重要基石。本文将全面介绍顺序表的相关概念，并通过C语言实现一个完整的动态顺序表，为读者打下坚实的数据结构基础。
📖专栏：【数据结构】

目录

  • 数据结构入门：顺序表详解与实践指南
    • 一、数据结构相关概念
      • 1.1、什么是数据结构？
      • 1.2、为什么需要数据结构？
    • 二、顺序表
      • 2.1、顺序表的概念及结构
      • 2.2、顺序表分类
      • 2.3、动态顺序表的实现
    • 总结

一、数据结构相关概念

考虑到大家可能都是未学习过数据结构，所以我会在对数据结构进行相对应的解释。

1.1、什么是数据结构？

数据结构是由“数据”和“结构”两词组合而来。
什么是数据？
常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据。
什么是结构？
当我们想要使用大量使用同⼀类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在⼀起，结构也可以理解为组织数据的方式。
比如：想要找到草原上名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来。
【数据结构】数据结构入门：顺序表详解与实践指南
概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么方式构成，以及数据元素之间呈现的结构。
总结：
1）能够存储数据（如顺序表、链表等结构）
2）存储的数据能够方便查找

1.2、为什么需要数据结构？

【数据结构】数据结构入门：顺序表详解与实践指南
如图中所示，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。
最基础的数据结构：数组。
【数据结构】数据结构入门：顺序表详解与实践指南
那我们就要思考：有了数组，为什么还要学习其他的数据结构？
假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：

求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是否要判断数组是否满了，满了还能继续插入吗）…

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。
结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现，所以就有了其它的数据结构。

二、顺序表

2.1、顺序表的概念及结构

线性表是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合。
对于逻辑结构和物理结构的理解：逻辑结构是\"怎么看\"，物理结构是\"怎么存\"。
对于顺序表，它再逻辑结构和物理结构上都是连续的。

2.2、顺序表分类

  • 顺序表和数组的区别

    • 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

  • 顺序表分类

    • 静态顺序表

    概念：使用定长数组存储元素
    【数据结构】数据结构入门：顺序表详解与实践指南
    静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

    • 动态顺序表

    【数据结构】数据结构入门：顺序表详解与实践指南
    优点在于可以根据使用者的情况进行扩容。

我们主要来进行动态顺序表的实现，动态只要会使用，静态的就很简单了。

2.3、动态顺序表的实现

首先，我们应有三个模块，分别用来实现不同的功能：
【数据结构】数据结构入门：顺序表详解与实践指南
SeqList.h中代码：

#include#include#include//元素类型typedef int SLDataType;//动态顺序表定义typedef struct SeqList{SLDataType* arr;int size;//有效数据个数int capacity;//空间容量}SL;//顺序表操作//顺序表的初始化void SLInit(SL* ps);//顺序表的销毁void SLDestroy(SL* ps);//打印void SLPrint(SL* ps);//扩容void SLCheckCapacity(SL* ps);//头部插入void SLPushFront(SL* ps, SLDataType x);//尾部插入void SLPushBack(SL* ps, SLDataType x);//头部删除 void SLPopFront(SL* ps);//尾部删除void SLPopBack(SL* ps);//指定位置之前插入数据void SLInsert(SL* ps, int pos, SLDataType x);//指定位置之前删除数据void SLErase(SL* ps, int pos);//查找int SLFind(SL* ps, SLDataType x);

SeqList.c中代码实现：

#include\"SeqList.h\"

顺序表的初始化

void SLInit(SL* ps){ps->arr = NULL;ps->size = ps->capacity = 0;}

顺序表的销毁

void SLDestroy(SL* ps){free(ps->arr );ps->arr = NULL;ps->size = ps->capacity = 0;}

顺序表的打印

void SLPrint(SL* ps){for (int i = 0; i < ps->size; i++){printf(\"%d \", ps->arr[i]);}printf(\"\\n\");}

扩容

#define INIT_CAPACITY 4 //初始容量void SLCheckCapacity(SL* ps){assert(ps);//判断容量够不够int newcapacity = 0;if (ps->capacity == ps->size){newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->arr ,sizeof(SLDataType) * newcapacity);if (!tmp ){perror(\"realloc\");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}}

头部插入

void SLPushFront(SL* ps, SLDataType x){assert(ps);//检查容量SLCheckCapacity(ps);//移动元素for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;}

尾插

void SLPushBack(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;}

头部删除

void SLPopFront(SL* ps){assert(ps);assert(ps->arr);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;}

尾部删除

void SLPopBack(SL* ps){assert(ps);//if (!ps->size)//return;assert(ps->arr);ps->size--;}

指定位置之前插入数据

void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i>pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;}

删除指定位置数据

void SLErase(SL* ps, int pos){assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size; i++){ps->arr[i - 1] = ps->arr[i];//ps->arr[size-2] = ps->arr[size-1]}ps->size--;}

查找

int SLFind(SL* ps, SLDataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;}

test.c中主要是我们用于测试，用来判断代码实现正确与否，读者自行使用。

总结

顺序表作为数据结构的入门内容，虽然简单但却非常重要。通过本文的学习，我们不仅理解了顺序表的基本概念和实现原理，还掌握了用C语言实现动态顺序表的完整过程。在这里建议亲自动手实现一遍代码，这将大大加深对顺序表的理解。
在后续文章中，我们将继续探讨链表、栈、队列等更复杂的数据结构，敬请期待！

网络标签：

相关问题