线性表
数据的逻辑结构分为线性结构和非线性结构，这里的线性结构就是我们所说的线性表(linear list)，那么线性表的定义是什么呢？
线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串......
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
一.线性表的数组结构——顺序表
顺序表我们可以理解成一个结构体的数组，它在内存中的存储的物理地址是连续的，存储数据时依次存储。一般可分为静态顺序表（使用定长数组）和动态顺序表（使用动态开辟数组）。
1.静态顺序表结构
//静态顺序表 typedef int SLDataType; #define N 10//容量 typedef struct SeqListStatic { SLDataType data[N];//保存数据 size_t size;//存入的数据个数 }SListS;
2.动态顺序表结构
//动态顺序表 typedef struct SeqList { SLDataType* a;//指向动态开辟的的数组 size_t size;//顺序表内存放数据的个数 size_t capacity; //顺序表容量 }SeqList;
3.接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。下面实现的接口大多数都是要对结构进行修改，所以我们传参的时候，都传结构体指针
（1）初始化
初始状态时，表内没有数据，我们把动态开辟的数组类型a置空，此时容量与数据个数都为0。
void SeqListInit(SeqList* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->size = 0; }
（2）销毁
有初始化就会有销毁，顺序表的空间是动态开辟来的，那么不用的时候我们要释放这些空间，，首先将空间free，然后将指针置空，最后将容量与数据个数置为0。
void SeqListDestroy(SeqList* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }
（3）打印
为了便于我们观察顺序表内存放的内容，我们实现一个打印接口，将顺序表内的内容打印出来。由于顺序表内存放书数据的形式是数组，因此我们定义一个遍历的变量i，表示数组下标，该表内共存放size个数据。
void SeqListPrint(const SeqList* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
（4）插入数据
插入数据的时候，会有一个风险，当容量不够时，直接插入会导致越界，因此，在插入数据之前，应该先检查顺序表容量，如果不够，我们应该动态增容
void SLCheckCapacity(SeqList* ps) { if (ps->capacity == ps->size) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//判断表内容量是否为空 SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//增加容量 if (tmp == NULL) { perror("realloc fail:"); return; } ps->a = tmp; ps->capacity = newCapacity; } }
我们检查capacity与size是否相等，由于capacity只能大于或者等于size，所以当size==capacity的时候，就证明顺序表已经满了，我们需要增容了。增容的大小可以随意 ，但是二倍是最合适的，增容过多会导致空间浪费，过少会导致增容次数变多，使效率下降。但是在初始化的时候，我们将capacity内的值置为0，所以直接*2显然是不合适的，因此，需要加一个判断，这里我们使用三目操作符" ? :"，如果capacity为0，那么首先开辟4个元素大小的空间，否则将空间扩大到原来的二倍。
1.尾插
首先使用assert判断指针的有效性，然后检查容量，不够则扩容，然后将数据放在size下标的位置，然后size自增1。
void SeqListPushBack(SeqList* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; }
2.头插
尾插的时候，是在数据的最后面插入，因此不需要挪动数据，但是头插我们需要将前面的所有数组向后挪动一位，然后在最开始的位置插入一个数据。 挪动数据的方式也是有讲究的，对于当前这种情况，我们应该让数据从后往前挪动，否则其他数据会被覆盖，导致数据丢失。
void SeqListPushFront(SeqList* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= 0)//挪动数据 { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }
3.在任意位置插入
在任意位置插入时，我们不仅要考虑传入的指针ps是否有效，对于传入的位置pos也是需要判断是否合法的，pos只能在有数据的位置或者是最后一个数据的下一个位置，所以pos <= ps->size；要在顺序表内随机的地方插入数据，那么就要把该位置之后的所有数据向后挪动一位， 挪动完成之后，在pos位置存入数据。
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x) { assert(ps); assert(pos <= ps->size); SLCheckCapacity(ps); size_t end = ps->size; while (end > pos)//挪动数据 { ps->a[end] = ps->a[end - 1]; end--; } ps->a[pos] = x; ps->size++; }
（5）删除数据
1.尾删
尾删数据的时候，会导致有位置被空出来，这时候，我们要考虑的问题就是，是否要缩容，首先结论是不需要。缩容是有代价的，会使效率变低，并且以后要插入数据的时候，还需要重新扩容，现在的硬件技术发达，对于空间的需求没有那么紧张，因此，综合考虑我们不进行缩容操作。由于我们访问顺序表内元素的方式是通过数组下标，即size，所以直接对size自减就可以啦。
void SeqListPopBack(SeqList* ps) { assert(ps); if (ps->size > 0) ps->size--; else return; }
2.头删
在顺序表的头的位置删除数据，需要保持结构不变，所以需要将后面的数据向前挪动，由于第一个数据是需要被删除的，不需要保留，所以从前向后挪动就行，当数据挪动完成，将size自减，即可完成头删操作。
void SeqListPopFront(SeqList* ps) { assert(ps); assert(ps->size > 0); int begin = 0; while (begin < ps->size - 1)//挪动数据 { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }
3.在任意位置删除
在任意位置删除时，我们不仅要考虑传入的指针ps是否有效，对于传入的位置pos也是需要判断是否合法的，pos只能在有数据的位置，所以pos < ps->size；要在顺序表内随机的地方删除数据，那么就要把该位置之后的所有数据向前挪动一位， 挪动完成之后，size自减。
void SeqListErase(SeqList* ps, size_t pos) { assert(ps); assert(ps->size > pos); size_t begin = pos; while (begin <= ps->size) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }
注：对于增删数据，我们实现的6个接口，其实是可以复用的，对于插入数据，我们使用SeqListInsert函数，传入pos为0的时候就是头插，传入pos为ps->size的时候就是尾插，同样的对于删除数据，使用SeqListErase，传入pos为0就是头删，为ps->size-1就是尾删。
（6）查找数据
查找数据，首先要检验传入指针的有效性，然后检查表内是否存在数据，如果传入空表，继续执行查找操作是不合适的，然后我们要遍历顺序表，并判断每个元素存放的值是否与我们要查找的值相同。找到了就返回下标位置，否则就返回-1。
int SeqListFind(SeqList* ps, SLDataType x) { assert(ps); if (ps->size <= 0) return -1; else { for (int i = 0; i < ps->size; i++) { if (x == ps->a[i]) return i; } } return -1; }
（7）修改数据
增删查改是所有数据结构需要实现的接口，但是对于修改数据这个接口，它和查找数据是类似的，这里就不进行过多赘述。
