当前位置：首页 > news >正文

数据结构（2）线性表-顺序表

news 来源：原创 2025/7/5 7:08:41

知道一个算法的好坏怎么去判断以后，就该正式的去学习一些常见的数据结构，当然，这里的数据结构仅仅是初阶，不会挨个一个一个学完，后期慢慢来。

一、数据结构总论

一般按照逻辑结构和存储结构来分类，在初阶的学习时，虽不能全部学完，但基本每个类别都能见到例子。

1.按逻辑结构分类

按照逻辑结构分类，可以分为集合结构（数据元素同属于一个集合，但是并没有任何的关系）、线性结构（数据元素一对一，好像一条线一样连在了一起）、树形结构（数据元素一对多的关系，就好像一个树的主干的根只有一个，但是他身上每一个节点都可能有好几个树枝）、图状/网状结构（这种结构就类似于在天上俯瞰一个城市的公路一样，每条路的十字看做一个数据元素的话，那就是多对多的关系）

2.按存储结构分类

按照存储结构有顺序存储（如数组，数组元素就是在内存中连续的存储）、链式存储（其实在C语言学习结构体的时候我们就已经见过怎样建立一个链表节点，即一个数据域，一个地址，这个地址是指向链式存储的下一个数据元素）、索引存储、哈希存储（根据散列函数的计算而定位数据元素）。

二、线性表

线性表是一类数据结构的总称，这一类数据结构最明显的特点就是逻辑上是线性的，但是物理上不一定是线性的。

也就是说，线性表在使用的时候，在我们的大脑中思考就是连续的、线性的，但实际上在内存中的存储可不一定是顺序存储。

三、顺序表

1.概述

这次学习的顺序表就是属于线性表，符合线性表的特征，即逻辑结构是线性结构，且数据顺序存储（底层实现类似于数组，或者说借助于数组）。

2.顺序表和数组的区别

这个时候就有人要问了，既然你跟我说顺序表借助于数组实现，那为啥不就当成数组呢。它们两个的关系就类似于什么呢：
我相信基本上能跟编程打交道的，你说你自己一点也不玩游戏，我是不信的，甭管玩手机游戏还是电脑游戏，你要玩游戏最基本得有个设备吧，就说手机游戏，你弄个平板玩，正常就搂着玩就行了呗，但是有的人嫌举着累，买个支架，又嫌自己打游戏的时候发热会导致掉帧，卡的不行，又买了一个散热器，手老出汗买个指套，更有甚者玩个手机游戏开加速器。

顺序表和数组基本就是这样的，数组只能存一系列数据，你存着只能取出来用，对里面的数据进行增删改是很麻烦的，顺序表在创建好以后，相当于数组+增加/删除/修改/查找……一系列的辅助工具，帮助你对数据进行维护，数组就没有这个条件。

3.顺序表的声明

①静态顺序表

静态数据表就是用定长数组来存储数据的，当然，并不等同于数组，一般都是这样定义的：

#define定义是为了方便修改静态顺序表的大小，即底层的数组的大小，为什么要将数组的类型由typedef定义一下呢，直接写个int不行吗？

给顺序表的数据的类型取别名也是为了方便修改顺序表所存储的数据类型。

这样看来顺序表也没比数组好到哪去，只不过可以确定有效数据个数而已。

这么看当然看不出来顺序表相对于数组的优点，因为正常情况下，比如用顺序表来存储双11某用户的订单个数，这种玩意肯定是动态的，不能说你就给他7个大小的内存，假如就说成7个订单，那万一双十一买的多了咋办，难道还能让用户少买一点吗？肯定是用户创建的订单决定数据存储的大小，也就是经常用的就是动态顺序表。

②动态顺序表

动态和静态的区别在哪里那，其实举的小例子已经给出了，静态的顺序表存储的数据个数是固定的，你给少了吧就不够用，给多了吧，又给内存浪费了（不要小看内存浪费，一个人浪费1000个字节，人多起来再多的内存都不够用）。

千万不要说，那你说要多大，比如存7个int，我就给你#define N 7，你要几我就定义几，这真就是对程序的内存申请不了解啊，在C语言学习的时候不说别的，编译的时候就给这个顺序表的内存大小固定死了，你把N定义的值改了有什么用，你程序已经写好了，软件里就是这么大，你说改成9，那么软件就不能用了，就得重新把你改好的应用到软件里，你敢想象双十一，特别是双十一的晚上购物平台提交不了订单会造成多大的损失吗，等你改好再上架，黄花菜都凉了。

因此，来看我们动态顺序表的声明（动态就是可以根据你给的数据，去调整申请的内存大小）。