1.线性表

线性表*（linear list）*是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储元素。

2.动态顺序表：使用动态开辟的数组存储。

3.接口的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef int SLDataType;
#define INIT_CAPACITY 2
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义SeqList ：
typedef struct
{
  SLDataType* a;
  int size;
  int capacity;
}SeqList;
//初始化SeqList
void SeqListInit(SeqList* pa);
//销毁SeqList
void SeqListDestory(SeqList* pa);
//打印SeqList
void SeqListPrint(SeqList* pa);
//扩容
void SeqCheckCapacity(SeqList* pa);
//头插
void SLPushFront(SeqList* pa, SLDataType x);
//尾插
void SLPushBack(SeqList* pa, SLDataType x);
//任意位置插入
void SLInsert(SeqList* pa, int pos, SLDataType x);
//头删
void SLPopFront(SeqList* pa);
//尾删
void SLPopBack(SeqList* pa);
//任意位置删除
void SLErase(SeqList* pa);
//查找数据
int SeqListFind(SeqList* pa, SLDataType x);
//修改数据
void SeqListModify(SeqList* pa, int pos, SLDataType x);

3.1 定义SeqList

定义SeqList这里我们是采用结构体来定义，其中a表示的是动态空间首地址、size表示当前存储数据的多少、capacity表示当前开辟空间的大小（容量）。

typedef struct
{
  SLDataType* a;
  int size;
  int capacity;
}SeqList;

3.2 初始化

初始化：a用malloc开辟动态空间，其余设置初始值。

void SeqListInit(SeqList* pa)
{
  pa->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
  if (pa->a == NULL)
  {
    perror("malloc error!!");
    return;
  }
  pa->size = 0;
  pa->capacity = INIT_CAPACITY;
}

//两个便捷操作：
typedef int SLDataType;
#define INIT_CAPACITY 2

两个便捷操作：

1.数据类型默认用SLDataType替代，方便后续数据更改。
2.定义初始化值INIT_CAPACITY，注意define不需要分号（；），不然会有不小麻烦

3.3 销毁

销毁开辟的内存空间，防止内存泄露（实际上是归还访问权限）

void SeqListDestory(SeqList* pa)
{
  free(pa->a);
  pa->a = NULL;
  pa->capacity = pa->size = 0;
  //从左向右：size赋值0，然后再把size赋值给capacity，size值为0;
}

3.4 打印

//SeqList 打印
void SeqListPrint(SeqList* pa)
{
  assert(pa);
  for (int i = 0; i < pa->size; i++)
  {
    printf("%d ", pa->a[i]);
  }
  printf("\n");
}

3.5 扩容

当我们不断添加数据，总会超出默认容量，所以我们就需要扩容，采用realloc函数来对malloc申请的空间进行扩容，但值得注意的是这里要考虑原地扩容与异地扩容，我们最好在后面添加一句代码pa->a = tmp;//原地扩容与异地扩容问题

void SeqCheckCapacity(SeqList* pa)
{
  assert(pa);
  if (pa->size == pa->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(pa->a, pa->capacity * sizeof(SLDataType) * 2);
    if (tmp == NULL)
    {
      perror("realloc error");
    }
    pa->a = tmp;//原地扩容与异地扩容问题
    pa->capacity = 2 * pa->capacity;
  }
}

3.6 数据插入

1.头插

这里的头插其实就是采用覆盖，依次从后往前覆盖，每次后一个数据被前一个数据覆盖，最后在将所需插入的值覆盖第一个位置。

void SLPushFront(SeqList* pa, SLDataType x)
{
  assert(pa);
  SeqCheckCapacity(pa);
  int i = pa->size;
  while (i)
  {
    pa->a[i] = pa->a[i - 1];
    i--;
  }
  pa->a[i] = x;
  pa->size++;
}

2.尾插

尾插更简单，增加访问个数，直接插入。

void SLPushBack(SeqList* pa, SLDataType x)
{
  assert(pa);
  SeqCheckCapacity(pa);
  pa->a[pa->size] = x;
  pa->size++;
  //pa->a[pa->size++]=x;
}

3.下标插入

根据下标插入，原理其实和头插相近，可以简单的看成初始位置为pos的头插。

void SLInsert(SeqList* pa, int pos, SLDataType x)
{
  assert(pa);
  assert(pos >= 0 && pos <= pa->size);
  SeqCheckCapacity(pa);
  int end = pa->size;
  while (end>pos)
  {
    pa->a[end] = pa->a[end - 1];
    end--;
  }
  pa->a[pos] = x;
  pa->size++;
}

{

学会了下标插入，头插和尾插也可以直接调用下表插入！

3.7 数据删除

1.头删

这里原理其实和前面头插差不多，只是整体空间缩小，所以是从前往后覆盖，用后一个数据覆盖前一个数据，然后再缩小访问空间(指size大小，而并非实际容量)。

void SLPopFront(SeqList* pa)
{
  assert(pa);
  assert(pa->size > 0);
  int start = 0;
  while (start<pa->size-1)
  {
    pa->a[start] = pa->a[start+1];
    start++;
  }
  pa->size--;
}

2.尾删

直接收回访问空间即可

void SLPopBack(SeqList* pa)
{
  assert(pa->size > 0);
  pa->size--;
}

3.下表删除

同下标插入，将pos位置当做起始位置，采取头删操作。

void SLErase(SeqList* pa,int pos)
{
  assert(pa);
  assert(pos >= 0 && pos <= pa->size);
  int begin = pos;
  while (begin<pa->size-1)
  {
    pa->a[begin] = pa->a[begin + 1];
    begin++;
  }
  pa->size--;
}

同样这里的头删和尾删都可以用下标删除替代

3.8 查询数据

很简单，遍历访问，找到数据返回下标，未找到数据，则返回-1；

int SeqListFind(SeqList* pa, SLDataType x)
{
  assert(pa);
  for (int i = 0; i < pa->size; i++)
  {
    if (pa->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

3.9 数据修改

直接修改即可很简单

void SeqListModify(SeqList* pa, int pos, SLDataType x)
{
  assert(pa);
  assert(0 <= pos && pos <= pa->size);
  pa->a[pos] = x;
}

4.顺序表存在的部分问题

我们可以很容易看出，顺序表在头删与头插部分的空间复杂度比较高，假如插入或删除n个数据，空间复杂度都为O(N^2)，所以比较复杂，这是顺序表的劣势，这一点将会在后续的链表得到解决，可以插个眼，关注一下！码字不易，谢谢支持！

顺序表详解（接口详解）