“路虽远，行则将至”
❤️主页：
小赛毛
顺序表·目录
1.线性表
线性表
（
linear list
）
是
n
个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串
…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.
顺序表
概念及结构
顺序表与数组的区别：顺序表的存储一定是连续的
顺序表是用一段
物理地址连续
的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
顺序表一般可以分为：
静态顺序表：使用定长数组存储元素
。
空间在一开始的时候就已经开好，是定长数组。
一般情况下，我们不使用静态的，因为把握不住到底开辟多大的空间，你把握不住啊，兄弟哈哈哈
动态顺序表：使用动态开辟的数组存储。
存储数据的数组空间是根据需求动态开辟的。
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致
N
定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size; //存储有效数据个数
int capacity; //空间大小
}SL;
在调用接口函数的时候，这里我们需要注意的是：
形参是实参的拷贝，形参的改变不会影响实参。
在顺序表进行插入操作的时候，有时候空间需要扩容：
//满了要扩容 if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType))); if (tmp == NULL) { perror("realloc failed"); exit(-1); } }
我们这里来举个例子：
int main() { //SL sl; //SLInit(&sl); int* p1 = (int*)malloc(12); int* p2 = realloc(p1, 20); printf("%p,%p\n", p1, p2); return 0; }
很显然上面展示的是
原地扩容
，那我们接下来试一个大一点的：int main() { //SL sl; //SLInit(&sl); int* p1 = (int*)malloc(12); int* p2 = realloc(p1, 200); printf("%p,%p\n", p1, p2); return 0; }
很显然是
异地扩容
。
在进行尾删操作的时候，我们要进行检测，这个时候呢分为两种方式：
void SLPopBack(SL* ps)
{
// 温柔的检查
//if (ps->size == 0)
//return;
// 暴力的检查
assert(ps->size > 0);
//ps->a[ps->size - 1] = 0;
ps->size--;
}头插：
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
ps：头插挪动数据的时候是从后往前挪
头删：
void SLPopFront(SL* ps)
{
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}SLInsert：在pos位置前插入
//在pos位置插入x void SLInsert(SL* ps, int pos, SLDataType x) { assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; }此接口可以搭配SLFind接口使用
int SLFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; }ps：
int x; scanf("%d", &x); int pos = SLFind(&sl, x); if (pos != -1) { SLInsert(&sl, pos, x * 10); } SLPrint(&sl); SLDestroy(&sl);
SLErase:
//删除pos位置的值 void SLErase(SL* ps, int pos) { assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }同理，这里也可以搭配SLFind使用：
int x; scanf("%d", &x); int pos = SLFind(&sl, x); if (pos != -1) { SLErase(&sl, pos, x * 10); } SLPrint(&sl); SLDestroy(&sl);