一、线性表
是什么线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列； 线性表是一种在实际中广泛使 用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…
线性表的结构
线性表在逻辑上是线性结构，也就说是连续的一条直线；但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
1、什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
简单来说，顺序表就是数组，只是要求数组里面的元素必须连续存储而已。
2、顺序表的分类
顺序一般分为两类：静态顺序表和动态顺序表。
静态顺序表：采用定长数组来存储元素。
#define MAX 1000 //数组的最大长度 typedef int SLDtataType; //重命名数据类型 typedef struct SeqList { SLDtataType data[MAX]; //使用定长数组来存储数据 size_t size; //有效数据的个数 }SL;
动态顺序表：使用动态开辟的数据来存储元素。
typedef int SLDataType; //将数据类型重命名为SLDataType typedef struct SeqList { SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间 size_t size; //记录当前有效数据的个数 size_t capacity; //记录当前容量，不够就增容 }SL;
两种顺序表的对比：相较于动态顺序表，静态顺序表存在很大的缺陷，那就是空间问题：当我们数据量很大时给定的空间可能不够用，但我们数据量比较小时，给定的空间又可能过大，造成空间浪费，即静态顺序表只适用于确定知道需要存多少数据的场景；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，而静态顺序表很少使用。下面我们用C语言来模拟实现一个动态的顺序表。
三、动态顺序表的实现
1、结构的定义
#define DEF_SIZE 5 //初始容量 #define CRE_SIZE 2 //一次扩容的倍数 typedef int SLDataType; //将数据类型重命名为SLDataType typedef struct SeqList { SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间 size_t size; //记录当前有效数据的个数 size_t capacity; //记录当前容量，不够就增容 }SL;
如上：我们将要管理的数据类型重命名为SLDateType，这样以后当我们要用此顺序表管理其他数据类型时，我们就只需要改动这一个地方。
其次，相较于静态顺序表，我们的结构体多了一个参数 – capacity，我们用它来记录顺序表当前的容量，当当前的有效数据个数size与它相等时，我们就进行扩容；由于数据个数和顺序表的容量都不可能小于0，所以我们将其定义为size_t的。
最后就是关于初始容量和每次扩增倍数的问题，这里把初始容量设定为5，然后把扩增倍数设定为2，即我们的顺序表每次扩容两倍。
2、顺序表的初始化
在初始化函数中，我们把size和capacity都置为相应大小，并且为data指针动态开辟一块空间，用于存储数据。
//初始化顺序表 void SeqListInit(SL* psl) { assert(psl); //断言：防止psl为空 psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType)); //开辟默认大小的空间并初始化 if (psl == NULL) //判空 { perror("calloc fail"); //打印错误信息 return; } psl->size = 0; psl->capacity = DEF_SIZE; }
3、检查容量
在检查容量的函数中，当我们结构体中的size和capacity相等时，我们就扩容，在扩容时我们要注意不要直接用data指针来接收realloc函数的返回值，避免扩容失败导致data指针找不到之前管理的空间，从而造成内存泄漏。
//检查容量（增容） void CheckCapacity(SL* psl) { assert(psl); //断言：防止psl为空 if (psl->size == psl->capacity) //当数据个数和容量相等时扩容 { //将realloc的返回值交由一个临时变量保存，防止扩容失败丢失原来空间的地址 SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType)); if (ptr == NULL) //判空 { perror("realloc fail"); return; } psl->data = ptr; psl->capacity *= CRE_SIZE; //增加容量 } }
4、在头部插入数据
在头部插入数据时，我们需要先将顺序表中的数据整体向后挪动一位，然后在顺序表的开头插入；在插入完成后记得要让size++。
//在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x) { assert(psl); //判空 CheckCapacity(psl); //检查容量 int i = 0; for (i = psl->size - 1; i >= 0; i--) { psl->data[i + 1] = psl->data[i]; //将数据整体向后移 } psl->data[0] = x; //插入数据 psl->size++; }
5、在尾部插入数据
在尾部插入数据很简单，直接插入就行。
//在尾部插入数据 void SeqListPushBack(SL* psl, SLDataType x) { assert(psl); //判空 CheckCapacity(psl); //检查容量 psl->data[psl->size] = x; //插入数据 psl->size++; }
6、在指定位置插入数据
在此函数中，我们需要先将pos及其之后的元素整体向后挪动一位，然后再在pos处插入数据。
//在任意位置插入数据 void SeqListInsert(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos <= psl->size); //断言 因为可能会在尾部插入数据，所以pos可以等于size CheckCapacity(psl); //检查容量 size_t end = psl->size; while (end > pos) //把pos及以后的数据向后挪动一位 { psl->data[end] = psl->data[end - 1]; --end; } psl->data[pos] = x; //插入数据 ++psl->size; }
由于尾插和头插也可以通过调用 SeqListInsret 函数实现，所以我们可以对头插和尾插函数进行改造，以此来简化代码：
在头部插入数据
//在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x) { assert(psl); SeqListInsert(psl, 0, x); //相当于在0位置处插入数据 }
在尾部插入数据
//在尾部删除数据 void SeqListPopBack(SL* psl) { assert(psl); SeqListErase(psl, psl->size - 1); //相当于在size-1处插入数据（数组下标从0开始） }
7、在尾部删除数据
删除尾部的数据很简单，我们只需要将size–即可，并不需要对其进行改动，因为我们下一次插入数据时会直接将原来空间中的数据覆盖掉。
//在尾部删除数据 void SeqListPopBack(SL* psl) { assert(psl); assert(psl->size); psl->size--; //如果尾部有数据，直接让size--即可 }
8、在头部删除数据
在头部删除数据，我们只需要将顺序表中的数据整体向前挪动一位，然后将size–即可。
//在头部删除数据 void SeqListPopFront(SL* psl) { assert(psl); assert(psl->size); size_t i = 0; for (i = 0; i < psl->size - 1; i++) { psl->data[i] = psl->data[i + 1]; //让表中的数据依次往前移 } psl->size--; }
9、删除指定位置的数据
删除指定位置数据，我们需要将pos后面的数据整体向前挪动一位，然后让size–。
//删除指定位置的数据 void SeqListErase(SL* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t i = 0; for (i = pos; i < psl->size - 1; i++) { psl->data[i] = psl->data[i + 1]; } psl->size--; }
和上面的插入数据一样，我们也可以通过调用 SeqListErase 函数来实现数据的头删和尾删。
在头部删除数据
//在头部删除数据 void SeqListPopFront(SL* psl) { assert(psl); SeqListErase(psl, 0); //相当于删除0下标处的数据 }
在尾部删除数据
//在尾部删除数据 void SeqListPopBack(SL* psl) { assert(psl); SeqListErase(psl, psl->size - 1); //相当于删除size-1下标处的数据 }
面试题：删除数据是否要缩容？
我们知道，插入数据空间不够时我们要增容，那么删除数据达到一定的数量后我们是否要缩容呢？答案是不用缩容。原因如下：
第一：我们缩容之后插入数据又需要重新增容，而增容是有代价的，会降低程序的效率。我们知道 realloc 函数扩容分为两种情况，一种是原地扩，即当原来的空间后面有足够的空闲空间时，操作系统会直接将那一块空间交由我们使用，这种情况对效率影响不大；另一种是异地扩，即当原来空间后面没有足够的的空间开辟时，操作系统会在另外空间足够的地方为我们开辟一块新的空间，这时操作系统需要先将我们原来空间中的数据拷贝到新空间中，再将原来的空间释放掉，这种情况对效率的影响就比较大了。
第二：缩容也是有代价的。其实缩容和扩容的过程是一样的，都分为原地和异地，会对程序效率造成影响。
第三：顺序表申请的是一块连续的空间，而free函数数并不能释放连续空间的一部分，只能全部一起释放，所以这里即使想释放也是做不到的。
所以综合前面三个因素考虑，顺序表删除数据不会缩容；这是我们典型的以空间换时间的做法。
10、查找数据
当我们找到该元素时，我们返回元素的下标；当该元素不存在时，我们返回一个无意义的值。（如-1）
//查找数据 int SeqListFind(const SL* psl, SLDataType x) { assert(psl); int i = 0; for (i = 0; i < (int)psl->size; i++) { if (psl->data[i] == x) return i; //找到元素所在返回下标 } return -1; //找不到返回-1（一个无效下标） }
11、修改指定位置的数据
//修改指定位置的数据 void SeqListModify(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos < psl->size); //断言 psl->data[pos] = x; //修改数据 }
12、打印顺序表中的数据
//打印顺序表中的数据 void SeqListPrint(const SL* psl) { assert(psl); //判空 size_t i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->data[i]); } printf("\n"); }
13、顺序表的销毁
在销毁顺序表的时候我们一定要记得将前面动态开辟的空间释放掉，防止内存泄漏。
//销毁顺序表 void SeqListDestory(SL* psl) { assert(psl); //断言：防止psl为空 free(psl->data); //释放（避免内存泄漏） psl->data = NULL; //置空（避免野指针） psl->size = 0; psl->capacity = 0; }
