顺序表
前言
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。本章我们将用C语言来实现一个顺序表。
一、顺序表结构
//顺序表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
我们首先定义一个顺序表结构，在这里即是这个SeqList的结构体并将其typedef重命名为SL，便于后面书写的简便性。在这个顺序表结构中，我们需要定义一个指针来存储数据，一个整形变量来存储有效数据个数，一个整形变量来存储当前空间容量。需要注意的是，为了方便我们以后更改顺序表的类型，我们可以在这里将类型进行typedef，即typedef int SLDataType，将int重命名为SLDataType，这样以后我们只用在这里更改类型即可更改顺序表的存储的数据类型。#define INIT_CAPACITY 4可以定义初始化的时候的初始化容量，不过这个意义没有那么大，可以根据个人看是否使用。
二、顺序表实现
1.初始化和销毁
//初始化和销毁
//初始化
void SLInit(SL* ps)
{
assert(ps);
SLDataType* new = (SLDataType*)malloc(10 * sizeof(SLDataType));
if (new == NULL)
{
perror("SLInit");
exit(-1);
}
ps->a = new;
ps->capacity = 10;
ps->size = 0;
}
//销毁
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
}
这两个函数实现顺序表的初始化和销毁。在这里我们利用malloc函数对结构体中的指针进行初始化，将顺序表的容量初始化为10，当前大小设置为0。销毁时利用free函数进行销毁，然后在这里可以养成一个好习惯，在使用free函数释放空间后将该指针设置为空指针，避免野指针等问题。需要说明一下的是，我们在每个函数的开头都加了一句assert断言，这样是为了避免传入空指针而导致空指针的解引用问题。
2.打印和扩容
//打印
void SLPrint(SL* ps)
{
assert(ps);
SLDataType* cur = ps->a;
int n = ps->size;
while (n--)
{
printf("%d ", *cur);
cur++;
}
printf("\n");
}
//扩容
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
SLDataType* new = (SLDataType*)realloc(ps->a, (ps->capacity) * 2);
if (new == NULL)
{
perror("SLCheckCapacity");
exit(-1);
}
ps->a = new;
ps->capacity = (ps->capacity) * 2;
}
}
这两个函数实现顺序表的打印和扩容操作。打印即是利用一个while循环遍历整个顺序表进行打印。扩容这里准确来说是一个检查并扩容的函数，当容量capacity等于大小size时，我们就进行扩容操作，利用realloc函数进行扩容，我们在这里采用2倍扩，即扩容为原来容量的2倍。
3.插入和删除
尾插函数，先调用SLCheckCapacity函数检查是否需要扩容，然后进行扩容操作。
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->a[ps->size] = x;
(ps->size)++;
}
尾删函数，直接对大小size减1即可。不过我们在所有删除函数的逻辑前面也应该加一句assert(ps->size > 0);的断言，这样可以避免当顺序表为空时仍在删除的错误操作。
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size > 0);
(ps->size)--;
}
头插函数，也是先调用SLCheckCapacity函数检查是否需要扩容，不过在这里我们需要先对顺序表的数据进行后移，这里可以利用一个while循环完成后移操作，不过在这里我们就应该知道对于顺序表来说头插是比较麻烦，消耗是比较大的，所以我们日常的使用中也应该尽量避免使用顺序表的头插。
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
int n = ps->size;
while (n > 0)
{
ps->a[n] = ps->a[n - 1];
n--;
}
ps->a[0] = x;
(ps->size)++;
}
头删函数，和头插函数类型，我们需要对数据进行前移，这里我们通过一个for循环进行数据的前移，因为也要移动数据，所以也是消耗比较大的，我们在平常也应尽量避免使用顺序表的头删。
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size > 0);
int i = 0;
for (i = 0; i < (ps->size)-1; i++)
{
ps->a[i] = ps->a[i + 1];
}
(ps->size)--;
}
在指定位置插入数据函数，其实和头插也类似，只是后移的起始位置从索引为0的位置变为索引为i的位置。
//指定位置之前插入/删除数据
//插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
int i = 0;
for (i = ps->size; i >= pos; i--)
{
ps->a[i] = ps->a[i - 1];
}
ps->a[i] = x;
(ps->size)++;
}
在指定位置删除数据函数，同理也是和头删类似。
//删除
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(ps->size > 0);
int i = 0;
for (i = pos - 1; i < (ps->size)-1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->a[i] = 0;
(ps->size)--;
}
特别说明一下，我们在这里知道指定位置插入/删除其实就和头插/头删类似，所以如果想简化代码，我们可以在这里采用复用的思想。比如头插函数就直接调用在指定位置插入的函数，然后把位置设置成头部即可，同理头删也类似。这种复用的思想还是非常有用的，我们在实现顺序表这种简单的数据结构的时候可能体现得不明显，但到后面这会是一个非常有用的思想，毕竟没人想干重复的活。
4.查找
查找函数，即对顺序表进行遍历，然后返回查找元素在顺序表中对应的位置。这里不是返回元素的索引值，而是返回在顺序表中的第几个位置，所以返回的为值为i+1。不过这里也可以改成返回索引值，不过这样的话当未找到目标元素的时候就不能返回0，得返回-1之类的值。
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i + 1;
}
}
return 0;
}
5.测试
进行测试的main函数，用来测试我们写的顺序表逻辑是否存在问题。
int main()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopBack(&s);
SLPrint(&s);
SLPushFront(&s, 1);
SLPushFront(&s, 2);
SLPushFront(&s, 3);
SLPushFront(&s, 4);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLInsert(&s, 3, 5);
SLPrint(&s);
SLErase(&s, 4);
SLPrint(&s);
int n = SLFind(&s, 5);
printf("%d\n", n);
SLDestroy(&s);
return 0;
}
三、优点和缺点
优点
随机访问：顺序表的一个显著优势在于能够快速地通过索引访问到任何一个元素。这意味着如果你知道元素的位置，你可以直接通过该位置（即索引）访问到元素，而无需从头开始遍历整个列表。这种访问方式的时间复杂度为O(1)。
高效的尾部操作：在顺序表的尾部添加或删除元素通常是非常高效的，因为这只需要改变少数几个数据（如更新最后一个元素的位置或计数器），而不需要移动其他元素。这种操作的时间复杂度同样为O(1)。
CPU缓存利用率高：由于顺序表中的元素是连续存储的，这有助于提高CPU缓存的命中率，从而加快访问速度。
缺点
插入和删除效率低：如果要在顺序表的头部或中间位置插入或删除元素，则可能需要移动大量的元素以保持顺序表的连续性。这样的操作时间复杂度为O(n)，其中n是顺序表的长度。
空间扩展性差：顺序表在创建时需要预先分配一定的空间大小。当顺序表已满时，需要重新分配更大的空间，并将原有数据复制过去。这个过程不仅消耗时间，还可能导致内存碎片化和空间浪费。
总结
本章的顺序表的实现到这里就完成了，顺序表的实现难度还是比较低的，毕竟只是作为数据结构的入门结构，但我觉得还是值得我们去花一些时间来亲手实现它，我相信这不仅能让我们对顺序表有更深刻的印象，还能帮助我们更好地理解后面的一些更难的数据结构。
如需源码，可在我的gitee上找到，下面是链接。
顺序表源码
如对您有所帮助，可以来个三连，感谢大家的支持。
每文推荐
伍佰–泪桥
陈泫孝–静悄悄
A-Lin–幸福了 然后呢
学技术学累了时可以听歌放松一下。
标签：ps,顺序,实现,C语言,assert,int,SLDataType,size From： https://blog.csdn.net/2401_86557724/article/details/142001151