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

数据结构：线性表之顺序表

news 2026/6/8 1:38:28

线性表

线性表（linear list）是相同类型的n个数据元素的有限序列，并用L命名为线性表，表示为：L={a1，a2，a3，……，an}。
ai是线性表中第i个数据元素，称i为数据元素ai在线性表中的位序（从1开始）。

需要注意的是，位序 i 是数据元素在顺序表中的位置，数组下标 i 则是相对于第一个数据元素的偏移量（从0开始）。
n是表的长度，当n=0时，则为空表。
a1为表头元素（表中第一个数据元素），an为表尾元素（表中最后一个数据元素）。
表中第一个数据元素没有前驱，最后一个元素没有后继。

线性表的两种实现方式

用顺序存储的方式实现就叫顺序表，用链式存储的方式实现就叫链表。
顺序存储：将逻辑上相邻的数据元素存放在一段连续的物理存储单元中，物理存储关系就可以表示数据元素之间的逻辑关系。
链式存储：把逻辑上相邻的梳理元素存储在任意一组物理存储单元中，数据元素之间的逻辑关系由指针表示。

顺序表

静态顺序表

静态顺序表就是用固定大小的静态数组来存储数据，优点是实现简单，缺点是适用场景局限，只适用于确定最多要存的数据个数，否则空间申请多了浪费，少了不够用。

静态顺序表只在确定要存的数据元素个数的时候才适用，适用场景太局限，所以我们一般用的是动态顺序表。

动态顺序表

动态顺序表就是用一个堆上动态申请开辟的内存空间来存储数据，容量不够了可以进行扩容处理。

实现动态顺序表

因为动态顺序表适用场景更广，也更复杂一点，所以这里我们只讲如何实现动态顺序表，这里用C语言来实现。

要实现动态顺序表，就要定义好它的接口函数（初始化、插入、删除等），
这些是它所有定义的接口函数的声明：

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintSqDatatype;//typedef重命名方便类型修改//动态顺序表typedefstructSequeenList{SqDatatype*arr;//用于开辟动态数组intsize;//表中数据元素个数intcapacity;//容量大小}SqList;//将结构体类型struct SequeenList重命名为SqList//方便后续创建顺序表//初始化顺序表voidSqListInit(SqList*ps);//返回顺序表中第i个下标数据元素的值SqDatatypeGetElem(SqList*ps,inti);//在顺序表中查找元素x，找到则返回该数据元素的位置iintLocateElem(SqList*ps,SqDatatype x);//在顺序表第i个下标插入数据元素xvoidSqListInsert(SqList*ps,inti,SqDatatype x);//删除第i个下标的数据元素x，并返回删除的值SqDatatypeSqListDelete(SqList*ps,inti);//获取顺序表中有效元素的个数intSqListSize(SqList*ps);//打印顺序表中的所有数据元素voidSqListPrint(SqList*ps);//判断顺序表是否为空表，是则返回true，不是则返回falseboolEmptySqList(SqList*ps);//头插和尾插voidSqListInsertFront(SqList*ps,SqDatatype x);voidSqListInsertBack(SqList*ps,SqDatatype x);//头删和尾删voidSqListDeleteFront(SqList*ps);voidSqListDeleteBack(SqList*ps);//销毁顺序表voidSqListDestroy(SqList*ps);

下面我们来讲讲如何实现主要的一些接口函数。注：以下位置 i 指的是数组下标。

初始化

初始化顺序表很简单，我们先保证传进来的指针ps的有效性，然后用SqList类型的中顺序表的数据元素类型SqDataType*的指针arr接收开辟的内存空间的起始地址（这里开辟能存放4个数据元素的长度），如果开辟成功则继续往下执行。再给顺序表中的数据元素个数size初始化成0，内存容量capacity初始化成用malloc开辟的内存容量就可以了。

查找

我们需要在顺序表中查找元素x出现的位置i，如果找到则返回下标i，遍历一遍顺序表的数据元素都没找到则返回-1。

插入

我们想在顺序表的任意地方都能插入数据元素，当我们在第i个下标插入数据元素x时，i后面的数据元素都要往后挪一个位置，并且是从后往前开始挪（防止前面的数据元素把后面的覆盖掉）。我这里的下标应该从0开始，我标错了。

为了使得插入这个数据元素后还是一个顺序表（相邻数据元素的物理位置连续），我们判断是否可以插入这个数据元素的条件应该设为要插入数据元素的位置i≤size（数据元素的个数）。如果我们的判定条件设为i＜capacity（顺序表容量大小）。以上图为例，我们插入元素5到位置9的话，这就不再是一个顺序表了（逻辑关系错误，相邻数据元素存放位置不连续）。放了一个元素后size要+1（数据元素个数+1）。

这是在顺序表容量足够大的情况下的。当顺序表容量不够时，我们就需要对其进行扩充。
所以我们在判断是否可以插入前，应该先判断是否需要进行容量扩充（用realloc函数扩充）。

每次只扩充一个显然不合理，但在数据结构中也没有统一的标准，所以这里用realloc重新开辟内存为原来的两倍。

我们知道对于realloc扩容有两种情况，一种是原地往后扩容，另一种是新找一块足够大的空间，然后把数据元素都拷贝过来，再把旧内存释放掉。显然第二种情况耗费的时间更长，但具体是哪种情况我们是不可知也是不可控的，如果想知道可以通过调试观察指针str和指针ps存的是不是同一个地址来判断。

头插和尾插复用该函数就可以实现：

调试看是否成功插入：
插入成功，说明函数功能没有什么问题。

删除

与插入相对的，我们删除一个元素后要保证这个表还是一个顺序表。

这里就是从前往后挪数据元素了。
如图，显而易见，当我们传入的下标位置小于顺序表中已有数据元素的个数并且大于等于0时，才能有效执行删除指令。

同样的，删除一个元素后，size要-1（顺序表中已有数据元素的个数-1）。

头删尾删函数复用该函数就可：