重点和易错点都用彩笔标记出来了，放心食用！！
数据结构分为线性表和非线性表，今天我们要学习的顺序表就是线性表中的一个小类。那么，何为线性表，线性表是指n个具有相同性质的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列、字符串等等。注意，线性表的物理结构不一定是线性的，它在逻辑结构上一定是线性的（这个很好理解，等我们学完顺序表和单链表这对黄金搭档，就明白这句话的含义了）
今天我们重点讲解顺序表，顺序表是线性表，顺序表在逻辑结构和物理结构上都是线性的。
顺序表（SeqList）：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（连续存储数据，不能跳跃）。
一般我们用数组存储顺序表，在数组上完成数据的增删查改。
顺序表分为两种类型：
//静态顺序表
#define N 7
typedef int SLDateType;
typedef struct SeqList
{
SLDateType array[N]; //定长数组
size_t size; //有效数据长度，size_t是无符号整形
}SeqList;
//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* array; //指向动态开辟的数组
size_t size; //数据中存储的数据
size_t capacity; //数组的容量
}SeqList;我建议用动态顺序表，比起静态顺序表，动态的更加好调整顺序表的大小。接下来，我也会以动态顺序表为例，介绍如何实现动态顺序表的增删查改。
我们要实现以下功能
//顺序表初始化
void SeqListInit(SeqList* psl); //psl p指针，sl顺序表
//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);这里提一嘴，我建议在每写一个功能就测试一下，千万不要把大部分功能写完再统一测试，那样你的Bug可能会99+（别问我为什么知道）。
//打印顺序表
void SeqListPrint(SeqList* psl)
{
assert(psl);
for(int i=0;i<psl->size;i++)
{
printf("%d ", psl->array[i]);
}
printf('\n');
}链表初始化没什么好说的，我直接上代码了。
void SeqListInit(SeqList*psl)
{
assert(psl); //断言psl是不是空指针
psl->array=NULL;
psl->size=psl->capacity=0;
}思路讲解：
//检查容量，增容
void CheckCapacity(SeqList* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);
//这里用realloc非常好
SLDateType* tmp = (SLDateType*)realloc(psl->array, psl->capacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc：");
return;
}
psl->array = tmp;
psl->capacity = newcapacity;
}
}这里就需要注意在尾插前检查容量，并且不要忘记psl->size++。
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{
assert(psl);
CheckCapacity(psl);
psl->array[psl->size] = x;
//别忘记让psl->size+1
psl->size++;
}注意：不管是进行头删还是进行尾删，我们都要检查psl->size是否大于0，我也提供了两种检查的方式，选其一即可。
//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
assert(psl);
//千万不要忘记检查psl->size是否大于0
//检查方式一：温柔的检查
/*if (psl->size == 0)
return;*/
//检查方式二：暴力的检查
assert(psl->size>0);
psl->size--;
}这个也没什么好说的，直接上代码。
void SeqListPushFront(SeqList*psl, SLDateType x)
{
assert(psl);
CheckCapacity(psl);
for (int i = psl->size;i>0; i++)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[0] = x;
psl->size++;
}删除数据不要忘记暴力检查psl->size。
//顺序表头删
void SeqListPopFront(SeqList*psl)
{
assert(psl);
//暴力检查
assert(psl->size);
for (int i = 0; i < psl->size - 1; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}找到了，返回值为数组下标；未找到，返回值为-1。
//顺序表查找(返回下标,找不到就返回-1)
int SeqListFind(SeqList* psl, SLDateType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->array[i] == x)
{
return i;
}
}
return -1;
}这个功能在实现的过程中一不小心就出问题，注意注意！！！！
//顺序表在pos位置插入x（pos为下标值）
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
assert(psl);
assert(pos<=psl->size);//注意：pos是可以等于psl->size，此时就相当于尾插
CheckCapacity(psl);
//写法一：
for (int i = psl->size-1; i >= pos; i--)
{
psl->array[i + 1] = psl->array[i];
}
//写法二：
size_t end=psl->size-1;
while(end)
{
psl->array[end+1]=psl->array[end];
end--;
}
psl->array[pos] = x;
psl->size++;
}当在下标为0的位置上插入一个数据时，i从psl->size-1到0，i进行i--操作，此时i=-1，再执行i>=pos操作，此时会停止循环吗？答案是不会，大家可以去调试，确实不会让循环停下。
那为什么呢？因为pos为size_t的类型，size_t为无符号整形-，当int（有符号整形）和size_t（无符号整形）比较大小时，int型的数据会发生算数转换，转换成unsigned int型，此时为负数的i就变成了很大的数字，自然而然比0大，因此会进入死循环。
那怎么解决呢？
针对写法一的解决办法：
for (int i = psl->size; i > pos; i--)
{
psl->array[i] = psl->array[i-1];
}
此时，避免了i==0的情况，保证i始终大于0，这样i--就不会出现问题了。
针对写法二的解决方法：
size_t end=psl->size;
while(end)
{
psl->array[end]=psl->array[end-1];
end--;
}有人肯定会不理解，为什么非让pos为size_t类型，如果让pos变成int型，只需要保证pos大于等于0就可以了，size_t显得好像更麻烦一些。其实，我们把pos写成size_t是因为库也是这样写的，我们严格根据库的声明来实现，以后当我们涉及到的问题更加复杂时，用size_t做接口肯定比int更好。
这里注意好循环时i的上下限就可以了。
//顺序表删除pos的位置
void SeqListErase(SeqList*psl, size_t pos)
{
assert(psl);
assert(pos < psl->size);
for (int i = pos;i<psl->size-1;i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}//修改顺序表的值
void SeqListModify(SeqList*psl, size_t pos,SLDateType x)
{
assert(psl);
assert(pos < psl->size);
psl->array[pos] = x;
}//销毁顺序表
void SeqListDestory(SeqList*psl)
{
assert(psl);
free(psl->array);
psl->array = NULL;
psl->size = psl->capacity = 0;
}#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
静态版本
//#define N 7
//typedef struct SeqList
//{
// SLDateType array[N]; //静态数组
// size_t size; //有效数据个数
//}SeqList;
//动态版本
typedef struct SeqList
{
SLDateType* array; //指向动态开辟的数组
size_t size; //有效数据个数
size_t capacity; //容量空间的大小
}SeqList;
//基本增删查改接口
//顺序表初始化
void SeqListInit(SeqList* psl); //psl p指针，sl顺序表
//检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);
#include"SeqList.h"
//打印顺序表
void PrintSL(const SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->array[i]);
}
printf("\n");
}
//初始化顺序表
void SeqListInit(SeqList* psl)
{
assert(psl);
psl->array = NULL;
psl->size = psl->capacity = 0;
}
//检查容量，增容
void CheckCapacity(SeqList* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);
//这里用realloc非常好，当realloc的第一个参数为0时，其效果等同于malloc
//用realloc可以完美实现最初开辟空间和增容的功能
//一定要注意：是newcapacity，而不是psl->capacity
SLDateType* tmp = (SLDateType*)realloc(psl->array, newcapacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc：");
return;
}
psl->array = tmp;
psl->capacity = newcapacity;
}
}
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{
assert(psl);
CheckCapacity(psl);
psl->array[psl->size] = x;
//也可以用SeqListInsert（psl，psl->size,x),但经常用上面的方法，可读性更强
//可别忘了让psl->size加1
psl->size++;
}
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x)
{
assert(psl);
CheckCapacity(psl);
for (int i = psl->size; i > 0; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[0] = x;
//也可以用SeqListInsert（psl，0,x),但经常用上面的方法，可读性更强
psl->size++;
}
//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
assert(psl);
//千万不要忘记检查size是否大于0
//温柔地检查SL中的size是否大于0
/*if (psl->size == 0)
{
return;
}*/
//暴力的检查
assert(psl->size > 0);
psl->size--;
}
//顺序表头删
void SeqListPopFront(SeqList* psl)
{
assert(psl);
assert(psl->size > 0);
for (int i = 0; i < (psl->size - 1); i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->array[i] == x)
{
return i;
}
}
return -1;
}
//顺序表在pos位置插入x（pos指的是下标）
void SeqListInsert(SeqList* psl,size_t pos,SLDateType x)
{
assert(psl);
CheckCapacity(psl);
assert(pos <= psl->size);//size_t是无符号整形，所以不需要担心pos小于0
//而pos等于psl->size，此时就不是插在中间了，而是尾插了。
//易错：pos=0
for (int i = psl->size; i >pos; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[pos] = x;
psl->size++;
}
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos<psl->size);
for (int i = pos; i < psl->size; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}
//顺序表销毁
void SeqListDestory(SeqList* psl)
{
assert(psl);
free(psl->array);
psl->array = NULL;
psl->capacity = psl->size = 0;
}
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x)
{
assert(psl);
assert(psl < psl->size);
psl->array[pos] = x;
}test.c可以自己写，记得引用头文件就可以。
#include"SeqList.h"
int main()
{
SeqList SL;
SeqListInit(&SL);
SeqListPushBack(&SL, 5);
SeqListPushBack(&SL, 2);
SeqListPushFront(&SL, 0);
PrintSL(&SL);
SeqListInsert(&SL, 2, 3);
PrintSL(&SL);
SeqListInsert(&SL, 2, 3);
PrintSL(&SL);
return 0;
}这是数据结构第二篇文章了，数据结构有些小难♂，但别担心，快关注我跟我一起坚持学习吧！(*^▽^*)
如果喜欢我的文章就给我点个赞再走吧！下次见！拜拜 ┏(＾0＾)┛