一、顺序表的基本概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为静态顺序表和动态顺序表，本文章主要说明动态顺序表的实现。
二、顺序表的的定义和初始化
1.顺序表的定义
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size; //有效数据
int capacity; //capacity表示空间的容量
}SL; 注：typedef int SLDataType; 这个语句中，将int类型重命名为SLDataType。通过这个typedef声明，可以在代码中使用SLDataType来代替int类型。在后续的代码中，将直接使用SLDataType来声明变量，而不必再使用int类型。
这里命名了一个名为SeqList的顺序表，其中size表示此顺序表内的数据个数，capacity表示此顺序表所能容纳的数据个数。
2.顺序表的初始化
void SLInit(SL* psl)
{
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
} 三、顺序表的接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表
顺序表的接口如下：
// 顺序表初始化 void SeqListInit(SeqList* psl); // 检查空间，如果满了，进行增容 void CheckCapacity(SeqList* psl); // 顺序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x); // 顺序表尾删 void SeqListPopBack(SeqList* psl); // 顺序表头插 void SeqListPushFront(SeqList* psl, SLDataType x); // 顺序表头删 void SeqListPopFront(SeqList* psl); // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* psl, size_t pos); // 顺序表销毁 void SeqListDestory(SeqList* psl); // 顺序表打印 void SeqListPrint(SeqList* psl);
1.顺序表扩容
void SLCheckCapacity(SL* psl)
{
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
} 在顺序表当中，我们会插入元素，如果psl->size == psl->capacity（即顺序表中的元素个数与此顺序表所能容纳的数据个数相等），表示此顺序表已经满了，则需要使用realloc函数扩容。
2.顺序表尾插
void SLPushBack(SL* psl, SLDataType x)
{
SLCheckCapacity(psl); //检查顺序表空间容量
psl->a[psl->size] = x;
psl->size++;
} 3.顺序表头插
顺序表的要求是数据存储的时候必须是连续的，而且必须从头开始存储。所以顺序表在进行头插时，就需要从最后一个数据起，依次往后挪动。
问：如何确定顺序表中的最后一个元素？
创建一个end变量来指向要挪动的数据，由于end指向的是数据的下标，所以end=size-1。进入while循环，将顺序表中的所有元素依次向后移动一个位置，为新元素腾出插入位置。循环体结束后，就可以在下标为0的位置上插入新的元素。此时顺序表内元素加了一个，要记得size++。
void SLPushFront(SL* psl, SLDataType x)
{
SLCheckCapacity(psl);
// 挪动数据
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
} 4.顺序表尾删
尾删即删除顺序表中的最后一个元素，只需要将元素的数量减去一个就可以了，即size--， 这样最后一个元素就是无效数据，无法访问了，那么就相当于删除了最后一个元素。
void SLPopBack(SL* psl)
{
assert(psl->size > 0);
psl->size--;
} 当顺序表中一个元素都没有时，size就会减到-1这个位置上，从而出现越界，但由于size是用来表示顺序表中的元素个数的，不可能小于0，所以这里需要断言。
越界通常指的是访问数组、链表等数据结构时，访问了超出其有效范围的位置。这种操作可能会导致程序运行出错或产生意料之外的结果。
在数组中，越界通常指的是访问数组索引小于0或大于等于数组长度的位置。例如，对于一个长度为n的数组，如果访问了数组索引为n或大于n的位置，就会发生越界。
越界访问可能会导致程序崩溃、内存错误、数据损坏等问题，所以在编程时应该格外注意边界条件的处理，避免越界访问的发生。
5.顺序表头删
头删只需要依次向前挪动数据即可。
void SLPopFront(SL* psl)
{
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
} 6.顺序表查找
int SLFind(SL* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i <= psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
return -1;
}
} 7.任意位置插入
pos是元素的下标，所以要限定pos的范围pos >= 0 && pos <= psl->size，以保证pos的值合法。
创建变量end指向顺序表中最后一个元素的下标，并通过ned指向需要挪动的数据。因为需要把pos下标之后的数据往后挪动（包括pos下标的元素),所以while循环中以end>=pos作为判断条件，数据挪动之后，便可以把插入数据x在pos这个位置上。最后size++。
// 注意pos是下标
// size是数据个数，看做下标的话，他是最后一个数据的下一个位置
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
8.删除任意位置的元素
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
} 9.顺序表销毁
顺序表需要销毁的主要原因有以下几点：
1. 节约内存空间：当顺序表不再需要使用时，及时销毁顺序表可以释放占用的内存空间，避免内存泄漏问题，提高内存利用率。
2. 避免资源浪费：顺序表在不使用的情况下占用计算机资源，包括内存和其他系统资源，及时销毁可以避免资源的浪费。
3. 防止数据泄露：如果顺序表中存储了敏感或重要数据，在不再需要使用这些数据时，销毁顺序表可以有效防止数据泄露的风险。
4. 提高程序性能：当顺序表不再需要使用时，销毁顺序表可以减少系统资源的占用，提高程序的性能和响应速度。
所以呢，及时销毁顺序表是一种良好的编程习惯，能够有效管理内存和资源，保护数据安全，提高程序性能。
void SLDestroy(SL* psl)
{
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
} 10.顺序表打印
实现函数后，我们想要打印出顺序表的元素，就需要一个打印函数，在实现其他功能时，我们需要进行简单测试，就可以调用此函数。
void SLPrint(SL* psl)
{
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
} 四、代码总览
1.SeqList.h
#include#include #include typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; //有效数据 int capacity; //空间容量 }SL; void SLInit(SL* ps1); //初始化顺序表 void SLDestroy(SL* ps1);//销毁 void SLPrint(SL* ps1); //打印 void SLCheckCapacity(SL* ps1); //扩容 // 头尾插入删除 void SLPushBack(SL* ps1, SLDataType x); void SLPushFront(SL* ps1, SLDataType x); void SLPopBack(SL* ps1); void SLPopFront(SL* ps1); //在任意下标位置的插入删除 void SLInsert(SL* psl, int pos, SLDataType x); void SLErase(SL* psl, int pos); //查找 int SLFind(SL* psl, SLDataType x);
2.SeqList.c
#include"SeqList.h"
//初始化
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
//销毁
void SLDestroy(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}
//打印
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
//扩容
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
//头插
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
// 挪动数据
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
//尾删
void SLPopBack(SL* psl)
{
assert(psl->size > 0);
psl->size--;
}
//头删
void SLPopFront(SL* psl)
{
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
int SLFind(SL* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i <= psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
return -1;
}
}
// 注意pos是下标
// size是数据个数，看做下标的话，他是最后一个数据的下一个位置
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}