1.线性表
（1）.线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串...
（2）.线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不是一定是连续的，线性表在物理上存储的，通常以数组和链表结构的形式存储。
文章来源地址https://www.toymoban.com/news/detail-645835.html
文章来源：https://www.toymoban.com/news/detail-645835.html
目录
1.线性表
2.顺序表
顺序表的初始化：
顺序表的扩容：
顺序表的尾插：
顺序表的头插：
顺序表的尾删：
顺序表的头删：
顺序表的最后处理：
顺序表的指定位置插入：
顺序表的指定位置删除：
2.顺序表
顺序表是用一段物理连续的存储单元依次存储数据元素的线性结构，一般情况下采用的数组存储。在数组上完成数据的增删查改。
在这里，我将给大家讲动态顺序表是怎么实现的。
（1）.我先定义了一个结构体，因为顺序表是具有相同特性的数据元素的有限列表。所以我用SeqListDateType来typedef 了，这样我们如果是double 或者float这样的类型的话，我们就只用改变宏这里一处。
（2）.因为是动态的，所以我就用指针，size就代表了顺序表中有多少个元素，capacity代表了是有多少的空间。
#define SeqListDateType int
typedef struct SeqList
{
SeqListDateType* arr;
int size;
int capacity;
}SeqList;
顺序表的初始化：
第一个函数就是度顺序表的初始化，这里我是直接把ps->arr置位了NULL，size和capacity一开始是0。
void SeqListInit(SeqList* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}顺序表的扩容：
因为我们是实现动态的顺序表，所以我们要处理一下，当size和capacity相等的时候，有2种情况，一种情况：一开始为0的时候，第二种情况：当空间不够的时候
这里，我用三目来实现了，如果是一开始我就给了4个int大小的空间，如果是第二种情况的话我就用扩二倍的思想来处理。
void SeqListCheckCapacity(SeqList* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SeqListDateType* tmp = (SeqListDateType*)realloc(ps->arr, newcapacity*sizeof(SeqListDateType)*2);
if (tmp == NULL)
{
perror("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->arr = tmp;
}
}顺序表的尾插：
一开始，我们开辟了4个int大小的空间，所以size一开始是0，然后就插入，然后size++就可以实现了，不过在我们插入的时候我们要考虑扩容的问题，如果空间满了，是要扩容的。
void SeqListPushBack(SeqList* ps, int x)
{
assert(ps);
SeqListCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
//SeqListInsert(ps, ps->size,x);
}
顺序表的头插：
思路：可以用迭代的思路走，但我们想一想，如果是从前面迭代的话，就会形成对数据的覆盖，所以要从后面迭代走。
我定义了end指向了4的位置，然后4要到后面的位置去，然后end--，这样当我们迭代完，顺序表0的位置就空了出来，直接把数据插入进去就可以了。
void SeqListPushFront(SeqList* ps,int x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >=0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[0] = x;
ps->size++;
//SeqListInsert(ps,0,x);
}
顺序表的尾删：
顺序表尾删更简单，直接让size--就可以实现了。因为，我们打印的数据就是size范围内的数据，size减了过后就没有这个数据了。
void SeqListPopBack(SeqList* ps)
{
assert(ps);
ps->size--;
//SeqListErqse(ps, ps->size-1);
}
顺序表的头删：
思路：先定义一个begin来指向第一个位置，我们迭代让后面的数据覆盖掉前面的数据就可以了。最后size--就实现了顺序表的头删。
void SeqListPopFront(SeqList* ps)
{
assert(ps);
int begin = 0;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin+1];
++begin;
}
ps->size--;
//SeqListErqse(ps, 0);
}
顺序表的最后处理：
我们直接free掉动态开辟的空间就可以了，然后把size和capacity置为0.
void SeqListDestory(SeqList* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}我们想一个问题，如果是在面试中，给了我们10分钟来实现顺序表，如果这样处理时间是不是可能不够呢？？所以，我给大家带来另外2个函数，这样我们就可以复用这2个函数对顺序表的头插、尾插..就可以直接复用，大大节约了时间。话不多说，直接放码！！！
顺序表的指定位置插入：
思路：假设pos=2，我定义了end来指向最后一个元素，只需要将最后一个元素往后移动一位，然后end--，这样就迭代了起来，最终就可以把pos的位置空出来，然后在pos位置插入想要的元素。
void SeqListInsert(SeqList* ps, int pos, int x)
{
assert(pos <= ps->size && pos>=0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->arr[end+1] = ps->arr[end];
end--;
}
ps->arr[pos] = x;
ps->size++;
}顺序表的指定位置删除：
思路：删除的话，其实也是一个覆盖的过程，将pos+1的位置覆盖掉pos的位置，然后迭代，临界位置就是size-1的时候，最后size--就实现了对指定位置的删除。
void SeqListErase(SeqList* ps, int pos)
{
assert(pos >=0 && pos <= ps->size-1);
int begin = pos+1;
while (begin <= ps->size-1)
{
ps->arr[begin-1] = ps->arr[begin];
begin++;
}
ps->size--;
}
这样，就可以用这两个元素来复用了！
尾插：尾插其实就是对顺序表最后的位置插入元素（注意，在最后一个位置插入的时候size已经++了，所以是ps->size）SeqListInsert(ps, ps->size,x);头插：头插就是对0的位置插入元素
SeqListInsert(ps,0,x);尾删：尾删也是和尾插一样的，对最后的位置删除
SeqListErase(ps, ps->size-1);头删：头删是对0的位置开始删除
SeqListErase(ps, 0);
到了这里，关于数据结构——顺序表（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
