前言
本篇博客我们来总结下线性表中的顺序表有关知识，并通过C语言代码实现出一个顺序表
个人主页：小张同学zkf
若有问题 评论区见
感兴趣就关注一下吧
目录
1.顺序表的概念与结构
什么是顺序表那
在了解顺序表之前，我们可以先了解线性表
1.1线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。简单来说是具有相同特性的数据结构的集合， 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑结构上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 肯定又有人有疑问了，什么是物理结构，什么又是逻辑结构？
1.1.1物理结构
物理结构就是数据在内存中存储的结构，比如数组，数组中这一块块空间地址就是物理地址，这种在内存中存储的方式就是物理的。
对于线性表而言物理结构可以连续的，也可以不连续
1.1.2逻辑结构
逻辑结构是我们想象出来的结构，是一种抽象式结构，对与线性表来说，它的逻辑结构我们就把它想象成像直线一样的线性结构，所以线性表的逻辑结构就是线性结构。那线性表的逻辑结构就一定是连续的，我们举个生活中的例子，比如：你排队去商店买书在门口排队
那这支队伍竖着来看是不是就是线性表的线性结构，虽然可能这只队伍在排队时排的没那么齐，但线性结构是想象出来的，我们可以把它抽象成一条直线。
1.2顺序表的特性
我们知道了物理结构与逻辑结构，以及线性表在物理结构不一定连续，在逻辑结构一定连续，那我们重新分析什么是顺序表，那它的特性我们无疑也可以从物理结构与逻辑结构两方面来分析
首先，顺序表是线性表的一种，那它的逻辑结构一定是连续的。这一点无疑是肯定的，既然你是属于线性表里的一种，那线性表在逻辑结构上规定是连续的，所以顺序表在逻辑结构上也必须连续
关键是在物理结构上，顺序表是不是连续的
我们先要明白顺序表底层就是数组，既然数组在物理结构上是连续的，那顺序表在物理结构上就是连续的
总结来看，顺序表在物理结构上是连续的，在逻辑结构上也是连续的
1.2.1顺序表与数组的区别
有人可能有疑问，既然顺序表的底层是数组，那它和数组有什么区别那
其实顺序表是对数组的封装，实现了常用的增删改查等接口，赋予了数组很多功能，成为了一个数句结构
我们可以想象一下，要是对一个数组实施插入或删除，那我们是不是要知道这个数组元素个数，修改时要知道数组的下标，那这样找来找去是不是很麻烦。
但反观顺序表就不一样了，它提供了很多现成的方法，开箱即用，所以就变成了一个特别厉害的数据结构
我们假设一个生活中的例子
比如我们去饭店吃饭，我们要是去一般的饭店点了一道菜，就叫炒土豆丝，味道感觉一般；
我们要是去豪华饭店吃饭，点了一道菜就叫豪华金丝吧，这个味道就特别好，他们的原料都是土豆，但你发现效果就不一样
额，饿了，哈哈开玩笑开玩笑
我们言归正传，那数组和顺序表是不是就像我刚刚举例的炒土豆丝和豪华金丝的关系
顺序表底层是数组，但是给了数组更多的功能，更加灵活方便
1.3顺序表的分类
顺序表分为动态顺序表与静态顺序表
我们先看静态顺序表
这就是一个顺序表结构，只不是静态，何来静态一说，我们来看它里面的成员，数组给定好100个空间，那这个空间就固定死了，所以是静态顺序表，而这个size就是表示当前在顺序表里有效数据的个数
我们再来看动态顺序表
动态顺序表第一个成员是指向数组的首元素指针，那这个空间可以用动态函数malloc 或calloc来开辟，size依旧是有效数据个数，而capacity是空间个数（能容纳的元素总个数）
哪一种顺序表更好呢
我觉得动态顺序表，更方便，它可以动态增容
2.动态顺序表的代码实现
那如何用C语言代码实现一个动态顺序表那
首先我们要知道，在打一个项目时，我们要有个头文件和源文件，头文件用来声明顺序表的方法，源文件用来实现顺序表的方法
我们可以近似把头文件当做目录，源文件当做从目录找到的内容
我们还需要再创个源文件，这个源文件是检测我打出来的顺序表是否正确
所以一共要有三个文件，一个头文件，两个源文件
那我们就正式开启写代码
首先在顺序表.h的文件里，把顺序表这个结构体先定义下来，定义完后，可以用typedef改名，
然后，我们要想这个数组里必须是int型的吗，不一定，那我就用typedef提前把int重类型一下，这样我们就可以不仅仅停留在int,若想改成其他类型，直接在typedef后将int改成你想在顺序表放的类型就可以了
然后我们要想在头文件里声明些什么函数那，根据顺序标的功能，最起码要增删查的功能吧，若空间不够也要有扩容功能的函数吧。也要有初始化函数和用于将动态内存开辟的空间归还给操作系统的销毁空间的函数，那我们可以总结一下
1.初始化函数
2.插入函数
3.扩容函数
分为头插入函数和尾插入函数
4.删除函数
分为头删除和尾删除函数
5.查找函数
6.在指定位置前插入函数
7.在指定位置处删除函数
8.销毁空间函数
9.打印顺序表
所以.h里面有这些代码
#define INIT_CAPACITY 4 typedef int SLDataType; // 动态顺序表 — 按需申请 typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL; //初始化和销毁 void SLInit(SL* ps); void SLDestroy(SL* ps); void SLPrint(SL* ps); //扩容 void SLCheckCapacity(SL* ps); //头部插⼊删除 / 尾部插⼊删除 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); //指定位置之前插⼊/删除数据 void SLInsert(SL* ps, int pos, SLDataType x);void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x);
接下来我们在顺序表.c文件中来一个一个函数定义，记得包含头文件
首先是初始化定义
将arr指针置空，size和capacity都等于0
注意：我们要传结构体时是传址调用！！！前面C语言结构体总结过
接着我们再定义销毁函数，释放空间
如果arr非空，我们要free掉它，否则内存泄漏，然后再置空，用完之后，再将size和capacity赋值成0
我们接下来定义打印顺序表
打印就很简单，直接for循环将数组里的元素都打印出来就行了，代码为
void SLPrint(SL* s)
{
for (int i = 0; i < s->size; i++)
{
printf(“%d “, s->arr[i]);
}
printf(“\n”);
}
在插入之前我们要想咱们现在初始化容量数为0，得扩容呀，那我们就扩容定义
如何来扩容那，我们一般规定扩容到原空间的两倍，扩容用到的函数是realloc函数，但刚开始是0，我们可以用三目操作符来判断如果空间为0，我们要给它4个空间数，若不是0，直接capacity乘2，接着再使用新的容量数乘每个类型的字节数放到realloc里就是开辟了新的空间
但我们要注意新开辟空间可能开辟失败，我们可以临时创个指针进行判断，最后再赋值给顺序表里的数组就行了，记得也要让容量数赋值成新的容量数
扩容完，我们就来插入，我们来定义头插入函数，我们想想头插入是怎么插的
我们画图可以得知，头插入现将数组整体后移一个空间，前面空出的空间方便新的元素插入
我们要注意，在后移的过程中，我们如果把1复制给第二个空间，那第二个空间的2是不是被覆盖了，数据就篡改了，所以我们要从后往前移，先把最后一个数放在后面的空间，再继续把倒数第二个空间的数放在倒数第一个空间里以此类推，就正好前面多出来一个空间，也没有出现数据覆盖
所以这个函数我们可以这么写
注意我们在将顺序表指针传进来之前，我们先要进行assert断言来判断这个指针是否为空，然后我们调用扩容函数，来判断是不是空间已满需要扩容再添加，这些都结束了，我们再进行后移是从后开始进行，在这里，我们要考虑i边界的问题，i最低取值为1，如果取值为零，那i-1就为-1，数组下标下限为0，所以出错了，所以i>0，移完再将新元素放到首空间。别忘了有效个数增加了，要加一
我们再来定义尾插入
我们在尾插时，我们想一下，在没插之前，size是不是记录当前元素个数，那它是不是就是新元素的下标，用完之后再加一
那插入之前还是先断言，再查容，再直接尾差就行，用完size再加1
我们插入完了，如何删除那，也有头删和尾删
我们先看尾删
尾删其实很简单，就是直接size减一，有效个数不包含最后一个就行了
我们要注意：在删之前我们要确定空间里有有效元素，否则你删什么，空间没数据你删不了呀，对不对，所以我们不仅要指针断言，还要把size断言一下，确保size不是0
再来看头删，头删是不是就是把首元素删除，然后整体向前挪动一位
向前移的时候我们也要考虑是否会重叠，如果按之前的方法从后往前移肯定重叠，如果是从前往后移，第一个空出来的空间放删完之后的第一个元素，第二个空间放删完之后的第二个元素，以此类推，是不是没有重叠，所从前往后移
依旧判断空指针和size是否为0，从前往后移，所以i从0开始进行++,这个边界最大值是多少那，如果i的最大值为最大下标数size-1，那i+1是不是就大于了最大下标数越界了，所以i要小于size-1,删完记得size–
我们再来看看在指定位置之前插入函数的定义
那我们这个函数是不是有三个参数，一个是指针，一个是指定位置的下标pos，一个是要插的元素
插入的时候我们要考虑指针是不是为空，这个下标是不是在这个数组下标的合法范围内。注意这里可以等于size,pos等于size相当于尾插嘛。
然后查容，需不需要扩容
那我们画图可以看出，这个是不是就是把从指定下标开始整体后移，那这个就可以和之前的头插想法联系起来，所以代码为
也就是说头插入for循环，i的最小值要大于0，而这里最小值要大于pos,插完记得size++
我们再来看从指定位置删除元素
依旧是俩断言，指针和下标合法，但这里就不能等于size，因为是删除，pos最大也只能为size-1
我们画图可知，删除后相当于后面元素整体前移，那类似于前面的头删，所以代码为
这里for循环也就和头删的for循环i的初始化不一样，剩下都没变，边界依旧是size-1，删完记得size–
我们最后定义一个查找函数，这个就是查找顺序表某一元素，两个参数，一个是指针，一个是你要查找的元素，那岂不是很简单，就是for循环从0直接到最大下标，if判断，若相等函数返回对应的下标个数，若直到最后都不相等，那就返回-1。
定义完函数，另一个.c源文件就可以来检测我们顺序表了。
我们可以自己定义一个顺序表变量，将地址带进每一个函数，通过函数调用，进行检测所打代码是否正确
记得也要包含头文件
#include”SeqList.h”
void SLTest01()
{
SL sl;
SLInit(&sl);
//ɾIJ
//β
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//SLPushFront(&sl, 5);
//SLPushFront(&sl, 6);
//βɾ
SLPopBack(&sl);
SLPrint(sl);//1 2 3
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
//………..
SLDestroy(&sl);
}
int main()
{
SLTest01();
return 0;
}
3.以下是动态顺序表的所有代码
头文件.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构
//#define N 100
//
静态顺序表
//struct SeqList
//{
// int arr[N];
// int size;//有效数据个数
//};
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间大小
}SL;
//typedef struct SeqList SL;
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);函数定义.c
#include"SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
if (ps->arr) //等价于 if(ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
//插入数据之前先看空间够不够
if (ps->capacity == ps->size)
{
//申请空间
//malloc calloc realloc int arr[100] --->增容realloc
//三目表达式
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);//直接退出程序，不再继续执行
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
温柔的解决方式
//if (ps == NULL)
//{
// return;
//}
assert(ps); //等价与assert(ps != NULL)
//ps->arr[ps->size] = x;
//++ps->size;
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
//头插
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];//arr[1] = arr[0]
}
ps->arr[0] = x;
ps->size++;
}
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
//ps->arr[ps->size - 1] = -1;
--ps->size;
}
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//数据整体往前挪动一位
for (int i = 0; i < ps->size-1 ; i++)
{
ps->arr[i] = ps->arr[i + 1]; //arr[size-2] = arr[size-1]
}
ps->size--;
}检测顺序表.c
#include"SeqList.h"
void SLTest01()
{
SL sl;
SLInit(&sl);
//ɾIJ
//β
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//SLPushFront(&sl, 5);
//SLPushFront(&sl, 6);
//βɾ
SLPopBack(&sl);
SLPrint(sl);//1 2 3
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
//...........
SLDestroy(&sl);
}
int main()
{
SLTest01();
return 0;
}结束语
本篇博客虽然内容多，但十分简单，没有什么难点，但也要注意细节，这里要多留意掌握这篇博客，顺序表知识总结就结束了
OK，感谢观看！！！！
版权声明：本文为博主作者：小张同学zkf原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/m0_74091744/article/details/137400282
