首先我要知道数据结构中的线性表：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
1.顺序表概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表分为静态与动态两种，日常使用上，动态顺序表比静态顺序表要使用的多些。静态顺序表实现起来也更加简单些，使用定长数组存储元素，然后对数据进行增删查改的操作。动态顺序表则更加灵活，可以对空间大小进行调节，容量不够可以扩容。
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。
2.动态顺序表实现
2.1.所需要用到的接口：
typedef int SLDatatype; typedef struct SeqList { SLDatatype* array; int size;//有效数据个数 int capacity;//空间大小 }SL; //增删查改 void SLInit(SL* ps);//初始化 void SLdestroy(SL* ps);//销毁 //打印 void SLprint(SL* ps); //检查空间 void Inspect(SL* ps); //尾插尾删 void SLpushBack(SL* ps, SLDatatype x); void SLpopback(SL* ps); //头插头删 void SLpushFront(SL*ps, SLDatatype x); void SLpopFront(SL*ps); //查找数据下标 int SLFind(SL* ps, SLDatatype x); //在pox位置插入x void SLInsert(SL* ps, int pox,SLDatatype x); //删除pox位置的值 void SLErase(SL* ps, int pox); //修改pox位置的值 void SLModify(SL* ps, int pox, SLDatatype x);
2.2初始化
对顺序表进行初始化，使表的开始大小可以存储4个有效元素
void SLInit(SL* ps) { assert(ps); ps->array = (SLDatatype*)malloc(sizeof(SLDatatype) * 4); if (ps->array == NULL) { perror("malloc failde"); exit(-1); } ps->size = 0; ps->capacity = 4; }
2.3空间检查
若是表中的元素个数已满，则进行扩容，扩容的后大小是原顺序表的2倍
void Inspect(SL* ps) { assert(ps); if (ps->size == ps->capacity) { SLDatatype* tmp = (SLDatatype*)realloc(ps->array, ps->capacity * 2 * sizeof(SLDatatype)); if (tmp == NULL) { perror("realloc failed"); exit(-1); } ps->array = tmp; ps->capacity *= 2; } }
2.4打印
打印顺序表中所有的元素
void SLprint(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->array[i]); } printf("\n"); }
2.5尾插
在顺序表的末尾插入元素
void SLpushBack(SL* ps, SLDatatype x) { assert(ps); Inspect(ps); ps->array[ps->size] = x; ps->size++; }
2.6尾删
将顺序表最后一个元素删除
void SLpopback(SL* ps) { assert(ps); assert(ps->size > 0); ps->size--; }
2.7头插
在顺序表的头部，表中首元素的前面插入新的元素，这时就需要将旧数据都往后挪一位
void SLpushFront(SL* ps, SLDatatype x) { assert(ps); Inspect(ps); int len = ps->size - 1; while (len >= 0) { ps->array[len + 1] = ps->array[len]; len--; } ps->array[0] = x; ps->size++; }
2.8头删
将头部的首元素删除
//头删 void SLpopFront(SL* ps) { assert(ps); int left = 1; while (left < ps->size) { ps->array[left - 1] = ps->array[left]; left++; } ps->size--; }
2.9查找数据下标
这一步是为了在指定的位置进行增删改查
int SLFind(SL* ps, SLDatatype x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->array[i] == x) { return i; } } return -1; }
2.10在指定位置插入元素
查找到要插入的位置下标，将元素插入
void SLInsert(SL* ps, int pox, SLDatatype x) { assert(ps); assert(pox >= 0 && pox <= ps->size); Inspect(ps); int end = ps->size - 1; while (end >= pox) { ps->array[end + 1] = ps->array[end]; end--; } ps->array[pox] = x; ps->size++; }
2.11删除指定位置的元素
查找到要删除的位置下标，将元素删除
void SLErase(SL* ps, int pox) { assert(ps); assert(pox >= 0 && pox < ps->size); int begin = pox + 1; while (begin < ps->size) { ps->array[begin - 1] = ps->array[begin]; begin++; } ps->size--; }
2.12删除指定位置的值
查找到要修改的值的位置下标，将旧的元素改为新的值
void SLModify(SL* ps, int pox, SLDatatype x) { assert(ps); assert(pox >= 0 && pox < ps->size); ps->array[pox] = x; }
2.13顺序表的销毁
顺序表使用完后，可以进行释放空间的操作
void SLdestroy(SL* ps) { assert(ps); free(ps->array); ps->array = NULL; ps->size = ps->capacity = 0; }
这里就要提一下出顺序表的劣势了：
中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
这就引申出一个问题，那有没有更好的数据结构呢？能够避开这些缺点？
答案是有的，这就是链表，下期来讲解链表都有哪些好处，以及链表如何来实现。
本期的内容就到此为止结束啦，感谢小伙伴们的阅读。
