一、什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
简单来讲就是用一段物理地址连续的存储单元依次存储数据元素的线性结构，它与数组非常类似，但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小
我们常用的数组有很多的缺点：
而使用顺序表的动态开辟的数组存储就方便很多
二、顺序表的定义
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空 间开多了浪费，开少了不够用。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现动态顺序表。
什么是接口函数？
接口函数是在数据进行操作时进行调用的函数，通过调用数据结构的接口帮助你完成一系列操作
void SLInit(SL* p1);//初始化 void SLDeseroy(SL* p1);//销毁 void SLPrint(SL* p1); void SLCheckCapacity(SL* p1);//扩容 void SLpushback(SL* p1, SLDataType x);//尾插 void SLpushfront(SL* p1, SLDataType x);//头插 void SLpopback(SL* p1);//尾删 void SLpopfront(SL* p1);//头删 //任意位置增删 void SLinsert(SL* p1, int pos, SLDataType x); void SLerase(SL* p1, int pos); //找到返回下标 //没找到返回-1 int SLfind(SL* p1, int pos, SLDataType x);
2.1 创建项目
为了养成模块化好习惯，我们尽量把代码分开来写。首先打开vs2022，在解决方案资源管理器中的 "头文件" 文件夹中创建 SeqList.h 用来存放头文件。在 "源文件" 文件夹中创建 顺序表.cpp 用来实现函数，Test.c 用来测试我们的顺序表：
为了方便后续修改数据类型，我们可以使用 typedef 定义一个新的数据类型，这里我们把它取名为 SLDataType（可以任意）。
我们为了让定义的结构体使用时更方便，我们同样可以使用 typedef 将其定义为 SL
（此时 SL = struct SeqList，后续在使用时可以更加方便）。
2.2 定义顺序表
定义顺序表我们首先需要一个动态内存开辟的空间，当前数据的个数(size)，以及方便扩容的容量大小
typedef int SLDataType; typedef struct Seqlist//顺序表 { SLDataType* a; //动态开辟的数组 int size; //数据个数 int capacity; //容量大小 }SL;
三、顺序表接口功能的实现
3.1 初始化顺序表
首先引入我们自己创建的头文件 #include "SeqList.h" ，我们就可以开始动手实现顺序表初始化函数了。
首先通过 psl 指向 array，将数组为空。因为是初始化，所以将有效数据个数和数组时即能存数据的空间容量一并置为0。
#include "SeqList.h" void SLInit(SL* p1) { p1->a = NULL; p1->size = 0; p1->capacity = 0; }
3.2 销毁顺序表
因为是动态开辟的，所以如果空间不用我们就需要销毁掉。如果不销毁会存在内存泄漏的风险，所以与之对应的我们写一个销毁的接口函数。
void SLDeseroy(SL* p1) { assert(p1); //断言 if (p1->a != NULL) { free(p1->a);//释放动态开辟的空间 p1->a = NULL;//置空 p1->size = 0;//数据个数为0 p1->capacity = 0;//容量大小为0 } }
3.3 扩容
后续我们会插入元素，如果空间不够，则使用realloc函数扩容。
newCapacitv是扩容后的内存空间，tmp是指向这个·新的空间的指针。如果空间为0，则扩容可以放置4个元素的空间，如果空间已满，则在原来的空间基础上，在增加1倍，这样其实依然是有浪费的，后面我们会解决这个问题。
void SLCheckCapacity(SL* p1) { assert(p1); if (p1->size == p1->capacity)//检查容量是否满了，满了就翻倍 { int newCapacity = p1->capacity == 0 ? 4 : p1->capacity * 2;//三目运算符，为空设置为4 SLDataType* tmp = (SLDataType*)realloc(p1->a, sizeof(SLDataType) * newCapacity); if (tmp == NULL)//防止原先地址被覆盖 { perror("realloc fail"); return; } p1->a = tmp; p1->capacity = newCapacity;//更新容量 } }
3.4 打印数据
实现函数后，我们如果想要打印到屏幕上，需要实现打印函数，这样我们每次实现一个功能，测试时，只需调用这个函数就可以了
void SLPrint(SL* p1) { for (int i = 0;i < p1->size;i++) { printf("%d ", p1->a[i]); } printf("\n"); }
3.5 尾插数据
尾插数据，顾名思义就是在顺序表末尾插入数据，在插入数据之前我们应该检查顺序表是否为满。
使用上面的扩容函数
void SLpushback(SL* p1, SLDataType x) { assert(p1); //断言 SLCheckCapacity(p1);//检查容量是否满了 p1->a[p1->size] = x; p1->size++;//有效个数+1 }
3.6 头插数据
顺序表要求数据是连续存储的，且必须是从头开始存储。所以，对于顺序表而言如果要实现头插，就需要把数据往后挪动。不能从前往后挪，如果从前往后挪就挪就会把后面的数据覆盖掉。
思路：首先创建一个 end 变量用来指向要移动的数据，因为指向的是数据的下标，所以是 size 要减 1 。随后进入 while 循环，如果 end >= 0 说明还没有移动完，就会进入循环。循环体内利用下标，进行向后移动操作，移动结束后再 end-- ，进行下一个数据的向后移动。挪动数据成功后，就可以插入了。此时顺序表第一个位置就被腾出来了，就可以在下标0位置插入欲插入的数据 x 了。最后记得 size++ 。
void SLpushfront(SL* p1, SLDataType x) { assert(p1); //断言 SLCheckCapacity(p1);//检查顺序表容量是否已满 int end = p1->size - 1; //从后往前依次向后挪动数据 while (end >= 0) { p1->a[end + 1] = p1->a[end]; end--; } p1->a[0] = x; p1->size++; }
3.7 尾删数据
同理，尾删数据就是删除顺序表中最后一个元素，大部分人所想也许是把最后一个元素置为0或者-1，这是可行的，但如果最后一个数就是0呢？
其实我们这里只需要元素数量减去一个就好了，即size--,这样我们就无法访问最后一个元素了，它便是无效的数据。注意：删除之前要保证顺序表中有数据。
void SLpopback(SL* p1) { assert(p1); //p1->a[p1->size-1] = NULL;//会被覆盖，可以不需要 /*温柔的检查 if (p1->size == 0) { printf("数据已经全部删除了\n"); return; }*/ //暴力的检查 assert(p1->size > 0); p1->size--; }
这里有可能会出现如果内存中一个元素都没有了，size有可能减到-1的位置上，这便是越界了，但size是我们用来统计元素数量的，不可能小于0的，所以这里我们需要断言一下。
3.8 头删数据
思路和头插类似，依次向前挪动，然后数量-1即size--
如果头删多次调用，如何内存中已经没有元素了，size依然在减。所以这里依然会出现越界，所以需要断言。
void SLpopfront(SL* p1) { assert(p1->size > 0); int begin = 1; while (begin < p1->size) { p1->a[begin - 1] = p1->a[begin];//从前往后依次向前挪动 begin++; } p1->size--; }
3.9 任意位置插入数据
与头插类似，从指定位置之后的全部向后挪动
代码思路：
首先添加 pos 位置的限定条件，限定 pos >= 0 并且 pos <= psl->size 从而保证 pos 合法。然后，因为是插入所以免不了要检查增容，直接调用之前写好的检查增容的函数即可。检查完后就可以开始移动了，和头插差不多，我们创建一个变量 end 记录最后一个的下标（psl->size-1），并通过它来指向要移动的数据。最后进入 while 循环，以 end >= pos 作为条件。移动完后，x 的位置就腾出来了，再把 x 插入进去，最后再 size++，就完成了。
void SLinsert(SL* p1, int pos, SLDataType x) { assert(p1); assert(pos >= 0 && pos <= p1->size); SLCheckCapacity(p1); int end = p1->size - 1; //挪动数据 while (end >= pos) { p1->a[end + 1] = p1->a[end];//覆盖 end--; } p1->a[pos] = x; p1->size++; }
3.10 任意位置删除数据
删除指定位置的数据，我们仍然要限制 pos 的位置。限制条件部分和 SeqListInsert 不同的是，因为 psl->size 这个位置没有效数据，所以删除的位置不能是 psl->size！
void SLerase(SL* p1, int pos) { assert(p1->size > 0); assert(pos >= 0 && pos < p1->size); int begin = pos + 1; while (begin < p1->size) { p1->a[begin - 1] = p1->a[begin]; begin++; } p1->size--; }
任意位置删除的函数可以替代头删和尾删
3.11 查找指定数据
根据输入参数，在顺序表中查找指定的值并返回其下标，若未找到则返回-1。
int SLfind(SL* p1, int pos, SLDataType x) { assert(p1); for (int i = 0;i < p1->size;i++) { if (p1->a[i] == x) { return i; } } return -1; }
四、完整代码
4.1 SLDataType.h
#pragma once #include<stdio.h> #include<string> #include<stdlib.h> #include<assert.h> typedef int SLDataType; //单词SL,Date,type typedef struct Seqlist//顺序表 { SLDataType* a; //动态开辟的数组 int size; //数据个数 int capacity; //容量大小 }SL; void SLInit(SL* p1);//初始化 void SLDeseroy(SL* p1);//销毁 void SLPrint(SL* p1); void SLCheckCapacity(SL* p1);//扩容 void SLpushback(SL* p1, SLDataType x);//尾插 void SLpushfront(SL* p1, SLDataType x);//头插 void SLpopback(SL* p1);//尾删 void SLpopfront(SL* p1);//头删 //任意位置增删 void SLinsert(SL* p1, int pos, SLDataType x); void SLerase(SL* p1, int pos); //找到返回下标 //没找到返回-1 int SLfind(SL* p1, int pos, SLDataType x);
4.2 SLDataType.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SLDataType.h" void SLInit(SL* p1) { p1->a = NULL; p1->size = 0; p1->capacity = 0; } void SLDeseroy(SL* p1) { assert(p1); //断言 if (p1->a != NULL) { free(p1->a);//释放动态开辟的空间 p1->a = NULL;//置空 p1->size = 0;//数据个数为0 p1->capacity = 0;//容量大小为0 } } void SLPrint(SL* p1) { for (int i = 0;i < p1->size;i++) { printf("%d ", p1->a[i]); } printf("\n"); } void SLCheckCapacity(SL* p1) { assert(p1); if (p1->size == p1->capacity)//检查容量是否满了，满了就翻倍 { int newCapacity = p1->capacity == 0 ? 4 : p1->capacity * 2;//三目运算符，为空设置为4 SLDataType* tmp = (SLDataType*)realloc(p1->a, sizeof(SLDataType) * newCapacity); if (tmp == NULL)//防止原先地址被覆盖 { perror("realloc fail"); return; } p1->a = tmp; p1->capacity = newCapacity;//更新容量 } } void SLpushback(SL* p1, SLDataType x) { assert(p1); //断言 SLCheckCapacity(p1);//检查容量是否满了 p1->a[p1->size] = x; p1->size++;//有效个数+1 } void SLpushfront(SL* p1, SLDataType x) { assert(p1); //断言 SLCheckCapacity(p1);//检查顺序表容量是否已满 int end = p1->size - 1; //从后往前依次向后挪动数据 while (end >= 0) { p1->a[end + 1] = p1->a[end]; end--; } p1->a[0] = x; p1->size++; } void SLpopback(SL* p1) { assert(p1); //p1->a[p1->size-1] = NULL;//会被覆盖，可以不需要 /*温柔的检查 if (p1->size == 0) { printf("数据已经全部删除了\n"); return; }*/ //暴力的检查 assert(p1->size > 0); p1->size--; } void SLpopfront(SL* p1) { assert(p1->size > 0); int begin = 1; while (begin < p1->size) { p1->a[begin - 1] = p1->a[begin];//从前往后依次向前挪动 begin++; } p1->size--; } void SLinsert(SL* p1, int pos, SLDataType x) { assert(p1); assert(pos >= 0 && pos <= p1->size); SLCheckCapacity(p1); int end = p1->size - 1; //挪动数据 while (end >= pos) { p1->a[end + 1] = p1->a[end];//覆盖 end--; } p1->a[pos] = x; p1->size++; } void SLerase(SL* p1, int pos) { assert(p1->size > 0); assert(pos >= 0 && pos < p1->size); int begin = pos + 1; while (begin < p1->size) { p1->a[begin - 1] = p1->a[begin]; begin++; } p1->size--; } int SLfind(SL* p1, int pos, SLDataType x) { assert(p1); for (int i = 0;i < p1->size;i++) { if (p1->a[i] == x) { return i; } } return -1; }
