⭐️本篇博客我要给大家分享一下顺序表。希望对大家有所帮助。
⭐️ 博主码云gitee链接：码云主页

目录

前言

🌏一、线性表

🌏二、顺序表

         🍯1.概念及接口

        🍯2.接口的实现

        🍍初始化顺序表 

        🍍检查空间，如果满了，进行扩容

        🍍顺序表尾插

        🍍顺序表尾删

        🍍顺序表头插

        🍍顺序表头删

        🍍顺序表查找

        🍍顺序表在pos位置插入x

        🍍顺序表删除pos位置的

        🍍顺序表销毁

        🍍顺序表打印

        🍯3.补充

🌏总结

前言

🌏一、线性表

🍤线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串...
🍤线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

🌏二、顺序表

         🍯1.概念及接口

🍤顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

一般分为：

       🍤 静态顺序表:使用定长数组存储元素。顺序表最大的缺点就是存储空间大小被固定了，空间有限。所以实际上我们不怎么会用这种静态的，所以我们这里不做实现。只实现下面的动态顺序表

//顺序表的静态存储#define N 7typedef int SLDataType;typedef structSeqList{    SLDataType array[N];    //定长数组    size_t size;     //有效数据的个数} SeqList;

       🍤动态顺序表:使用动态开辟的数组存储。更灵活。

//顺序表的动态存储typedef int sLDataType;typedef struct SeqList{    SLDataType*array;    //指向动态开辟的数组    size_t size; //有效数据个数    size_t capicity;    //容量空间的大小} SeqList;

        🍯2.接口的实现

typedef int SLDataType;//以便可以存储不同类型的数据typedef struct SeqList{SLDataType* a;//当前指针int size;//当前大小int capacity;//容量}SL;//初始化顺序表void SeqListInit(SL* ps);//销毁顺序表void SeqListDestory(SL* ps);//尾插void SeqListPushBack(SL* ps, SLDataType x);//尾删void SeqListPopBack(SL* ps);//头插void SeqListPushFront(SL* ps, SLDataType x);//删除void SeqListPopFront(SL* ps);// 顺序表查找int SeqListFind(SL* ps, SLDataType x);//任意位置插入void SeqListInsert(SL* ps, int pos, SLDataType x);//任意位置删除void SeqListErase(SL* ps, int pos);//打印顺序表void SeqListPrint(SL* ps);

        🍍初始化顺序表 

🍤初始指针初始化，容量初始化，当前容量初始化

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

        🍍检查空间，如果满了，进行扩容

🍤检查是否达到最大容量，检查最大容量是否为0，如果为0则给一个整形空间，如果不为0则将原来空间乘2，同时重新创立一个指针开辟新空间来存放重新开辟的空间，如果在原来的指针里开辟的话，如果开辟失败，原指针都会丢失，所以重新建立一个指针，而且如果开辟失败的话结束进程

//检查顺序表容量void CheakCapacity(SL* ps){if (ps->capacity == ps->size){ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;    //判断是否数据一开始是否是0SLDataType* tmp = NULL; //对遥要扩容的目标进行检查tmp = (SLDataType*)realloc(ps->a, ps->capacity*sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n"); //打印错误信息exit(-1);   //结束程序}ps->a = tmp;}}

        🍍顺序表尾插

🍤尾插当然就是在顺序表的尾部进行插入数据，插入数据的同时我们需要考虑到扩容，否则会导致空间不够，当capacity的大小和size的大小相同时，就说明顺序表容量已经满了，所以我们要对顺序表进行扩容操作

void SeqListPushBack(SL* ps, SLDataType x){//检查是否要扩容CheakCapacity(ps);ps->a[ps->size] = x;ps->size++;}

        🍍顺序表尾删

🍤尾删要注意的一点：当顺序表中没有数据时，我们不应该再对顺序表进行删除了

void SeqListPopBack(SL* ps){assert(ps->size > 0);    //当顺序表中没有数据时，我们不应该再对顺序表进行删除了ps->size--;}

        🍍顺序表头插

🍤头插值得我们考虑的点就是要对顺序表进行扩容，上面我们也提到了CheckCapacity这个函数，所以这里我们也要用到他，用他来检查顺序表容量。

void SeqListPushFront(SL* ps, SLDataType x){CheakCapacity(ps);int end = 0;for (end = ps->size - 1; end >= 0; end--){ps->a[end + 1] = ps->a[end];}ps->a[0] = x;ps->size++;}

        🍍顺序表头删

🍤头删也要注意顺序表中是否还有数据，如果没有就不进行删除操作，否则会导致程序崩溃，防止会越界访问。

void SeqListPopFront(SL* ps){assert(ps->size > 0);int start = 0;for (start = 0; start size - 1; start++){ps->a[start] = ps->a[start + 1];}ps->size--;}

        🍍顺序表查找

🍤如果找到了当前指针，则返回下标，如果没有找到则返回-1

// 顺序表查找int SeqListFind(SL* ps, SLDataType x){int i = 0;for (i = 0; i size; i++){if (ps->a[i] == x){return i;}}return -1;}

        🍍顺序表在pos位置插入x

🍤断言判断pos的值和ps的值是否合法，再检查现有空间是否足够，向后挪动数据

//任意位置插入void SeqListInsert(SL* ps, int pos, SLDataType x){assert(pos >= 0 && pos size);     assert(ps);CheakCapacity(ps);int end = 0;for (end = ps->size - 1; end >= pos; end--){ps->a[end + 1] = ps->a[end];}ps->a[pos] = x;ps->size++;}

        🍍顺序表删除pos位置的

🍤与插入相同

void SeqListErase(SL* ps, int pos){assert(pos >= 0 && pos size);assert(ps->size > 0);int start = 0;for (start = pos; start size - 1; start++){ps->a[start] = ps->a[start + 1];}ps->size--;}

        🍍顺序表销毁

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

        🍍顺序表打印

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

        🍯3.补充

🍤优点：

        连续物理空间，方便下标随机访问

🍤缺点：

        空间不足时要扩容，扩容有性能消耗(realloc如果异地扩容要开辟新空间)

        头部或中间插入删除数据，需要挪动数据，效率较低

        存在一定空间占用（浪费空间），不能按需申请所需的空间

🌏总结

🍤realloc两种扩容：

        原地扩容：在原来空间后面增加空间

        异地扩容：重新找一个空间开辟好

中评网简体版