前言
在了解顺序表之前，我们要先了解一下什么是线性表？
线性表是n个具有相同特性的数据元素的有序数列，在实际应用广泛的线性表有顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性结构，也就是说是连续的一条直线，但是它在物理结构上不一定是连续的，线性表在物理结构上通常是以数组和链表的形式进行存储的。
顺序表：
链表
本篇文章我们先来了解以下顺序表。
一、顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
顺序表实质上就是数组。
二、顺序表的分类
1.静态顺序表
静态顺序表：使用定长数组存储数据，顺序表定义之后，它的大小就不能改变了。
先来一串代码带大家看看怎么声明一个静态顺序表：
#define N 10//定义数组的大小（元素的个数） typedef int SLDataType;//顺序表中存储的数据的类型 //静态顺序表 typedef struct SeqList { SLDataType a[N];//放数据的数组 SLDataType size;//有效数据的个数 }SeqList;//重定义结构体类型的名称
2.动态顺序表
由静态顺序表的定义可以看出：静态顺序表的定长数组的空间大小由N决定，N如果定大了，空间开多了浪费；如果N定小了，空间开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小
动态顺序表：使用动态开辟的数组存储数据，它的大小是可以改变的。
动态顺序表的声明：
typedef int SLDateType;//顺序表的数据类型 typedef struct SeqList { SLDataType* a;//指向动态开辟的数组 int size;//有效数据数 int capacity;//容量空间大小 }SeqList;
三、动态顺序表的接口
我们所调用的函数也叫做接口，是用来实现某一项具体的功能的。
要实现一个动态顺序表需要的接口有以下几个：
void SeqListInit(SeqList* ps);//顺序表的初始化 void SeqListDestory(SeqList* ps);//销毁顺序表（避免内存泄漏） void Capacity(SeqList* ps);//检查容量 void SLPrint(const SeqList* ps);//打印顺序表的数据（方便观察） //对数据进行管理——增删查改 //头插和尾插，头删和尾删 void SLPushFront(SeqList* ps, SLDataType x);//头插 void SLPushBack(SeqList* ps, SLDataType x);//尾插 void SLPopFront(SeqList* ps);//头删 void SLPopBack(SeqList* ps);//尾删 //在顺序表中进行查找 int SeqListFind(SeqList* ps, SLDataType x);//查找某个数据 // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//在pos所指向的数据位置插入数据 // 顺序表删除pos位置的值 void SeqListErase(SeqList*ps, size_t pos);//删除pos所指向的数据 //顺序表中修改pos位置处的值 void SeqListModify(SeqList*ps, size_t pos, SLDataType x);//修改pos所指向的数据
四、接口的实现
1.初始化顺序表
//初始化顺序表 void SeqListInit(SeqList* ps) { assert(ps); ps->a = NULL;//初始化地址 ps->size = 0; ps->capacity = 0;//初始化数据个数和容量大小 }
关于在程序中检查错误的方式：
①温柔的检查： 如果出现错误，程序就不继续执行 If(ps->size==0) { //……代码
return;//或者exit(-1);因为一般情况下，我们运行程序成功就返回0，则运行失败就返回-1. }
②暴力的检查（推荐用这种）： 使用断言，如果发生错误，程序会报警告 assert()函数
2.销毁顺序表
//销毁顺序表 void SeqListDestory(SeqList* ps) { assert(ps); free(ps->a);//释放动态空间 ps->a = NULL; ps->capacity = ps->size = 0;//将数据个数和容量大小置为0 }
3.检查顺序表容量
//检查容量 void SLCheckCapacity(SeqList* ps) { if (ps->capacity == ps->size) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* temp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType)); if (temp == NULL) { perror("realloc fail");//如果realloc开辟空间失败就会报错 return; } ps->a = temp; ps->capacity = newcapacity; } }
注意：
1.不能直接将返回的指针传给ps，避免因为空间开辟失败导致将空指针传给ps，使得ps丢掉原先的地址。
2.realloc在开辟动态内存空间时，如果传给它的是一个空指针，那么他就会开辟一个新的内存空间，用法类似malloc。
4.打印顺序表
//打印顺序表的数据（方便观察） void SLPrint(const SeqList* ps) { int i = 0; for (i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); }
5.头插
//头插 void SLPushFront(SeqList* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); int end = 0; for (end = ps->size; end > 0; end--) { ps->a[end] = ps->a[end - 1]; } ps->a[0] = x; ps->size++; }
当然，头插也可以直接调用函数SeqListInsert()
SeqListInsert(ps, 0, x);
6.尾插
//尾插 void SLPushBack(SeqList*ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; }
尾插也可以直接用函数SeqListInsert()
SeqListInsert(ps, ps->size, x);
7.头删
//头删 void SLPopFront(SeqList* ps) { assert(ps); assert(ps->size);//如果顺序表中没有数据了，继续进行头删就会报错 int begin = 0; for (begin = 0; begin < ps->size-1; ++begin) { ps->a[begin] = ps->a[begin + 1];//用后一个元素覆盖前一个元素，相当于头删第一个元素 } ps->size--; }
可以借用函数SeqListErase实现头删
SeqListErase(ps, 0);
