一、前言

前面介绍了如何分析一个算法的时间复杂度和空间复杂度，但那些都是数据结构学习的预备工作。而本文介绍的顺序表，则是数据结构中较为基础的类型。虽然基础，但也有它自己独有的特性，具体是那些特性，就让我们往下看吧。

二、线性表

再介绍顺序表之前，我们先认识一下线性表。

线性表，全名为线性存储结构。即 “ 把所有数据用一根线儿串起来，再存储到物理空间中 ”。如下图所示，既然线性表是排成像一条线一样的结构，那么每个线性表上的数据最多只有前和后两个方向。

顺序表、链表、栈、队列等都属于线性表中的一种。

而与线性表的概念相对应的是非线性表。
非线性表里的数据之间并不是一对一关系，而是一对多或多对多关系。

树、图、堆等都属于非线性表中的一种。

三、顺序表

1、定义

维基百科：顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

好吧，那就直接看定义里面的重点。
顺序表是用一段连续的存储单元依次存储数据元素的线性结构

2、静态顺序表

静态顺序表就是，使用定长数组存储元素。再简单点说，就是数组的容量是固定的，用完就没了。少了不够，多了浪费。

#define N 100            //（0）
typedef int SLDataType;  //（1）
typedef struct SeqList   
{
    SLDataType arr[N];     //（2）
    size_t size;         //（3）
}SeqList;                 //（4）

（0）规定N等于100
（1）重新定义int类型名为SLDataType（便于后面修改类型）
（2）静态数组来保存顺序表中的元素，一共N个位置（最多存入N个元素）
（3）顺序表当前长度
（4）定义SeqList代表这个结构体类型名

3、动态顺序表

动态顺序表，是先开辟一块小空间，然后利用realloc函数或malloc函数按需开辟空间，空间不够了，就开辟，多了就不开辟。

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* array;//（0）
    size_t size;      //（1）
    size_t capicity;  //（2）
}SeqList;

（0）指向动态开辟的数组
（1）顺序表当前长度
（2）容量空间的大小

额....那是因为开辟空间的接口函数还都没写呢。

4、接口实现

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

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* array;
    size_t size;     
    size_t capicity;  
}SeqList;

Ⅰ、初始化

初始化的目的就是清理内存中可能遗留的“脏数据”。

void SeqListInit(SeqList* psl)
{
    assert(psl);//断言防止其为空指针
    psl->array=NULL;//讲该指针置空
    psl->size = 0;//设置有效数据个数为0
    psl->capacity = 0;//设置空间容量为0
}

assert函数的作用就是：求表达式的值，当结果为假时，打印诊断消息并中止程序。它的作用就像是下面这个if函数。

if(假设成立)
{
     程序正常运行；
}
else
{
      报错&&终止程序！（避免由程序运行引起更大的错误）  
}

Ⅱ、销毁

void SeqListDestory(SeqList* psl)
{
    assert(psl);
    //释放动态开辟的空间
    if (psl->array)
    {
        free(psl->array);
        psl->array = NULL;
        psl->capacity = 0;
        psl->size = 0;
    }
}

Ⅲ、增容

利用realloc函数或者malloc函数给一个表增容，最先做的就是先检查顺序表内元素个数是否已达顺序表容量上限。若已达上限，那么我们就需要先对顺序表进行扩容，然后才能增加数据。

void SeqListCheckCapacity(SeqList* psl)
{
    assert(psl);

    if (psl->size == psl->capacity)
    {
        int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SeqListDataType* tmp = (SeqListDataType*)realloc(psl->array, newCapacity * sizeof(SeqListDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }

        psl->array = tmp;
        psl->capacity = newCapacity;
    }
}

Ⅳ、插入

因为顺序表中每个数据元素在内存中是连续存储的，所以如果要在某个位置插入一个元素，则需要把原来该位置的元素依次向后移动。

• 头插

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{
    assert(psl);
    SeqListCheckCapacity(psl);
    int end = psl->size - 1;
    while (end >= 0)
    {
        psl->array[end + 1] = psl->array[end];
        end--;
    }
    //或者用for循环
    //    for (int i = psl->size - 1; i >= 0; i--)  
    //顺序表中[0,size-1]的元素依次向后挪动一位
    //{
    //    psl->array[i + 1] = psl->array[i];
    //}
    psl->array[0] = x;
    psl->size++;
}

• 中间插

void SeqListInsert(SeqList* psl, int pos, SeqListDataType x)
{
    assert(psl);
    assert(pos >= 0);
    assert(pos <= psl ->size);

    SeqListCheckCapacity(psl);
    int end = psl->size - 1;
    while (end >= pos)
    {
        psl->array[end + 1] = psl->array[end];
        end--;
    }

    psl->array[pos] = x;
    psl->size++;
}

• 尾插

void SeqListPushBack(SeqList* psl, SeqListDataType x)
{
    assert(psl);
    SLCheckCapacity(psl);
    psl->array[psl->size] = x;
    psl->size++;
}

• 中插改头插

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{
   SeqListInsert(psl, 0, x);
}

• 中插改尾插

void SeqListPushBack(SeqList*psl,SeqListDataType X)
{
    SLInsert(psl, ps->size, x);
}

Ⅴ、删除

因为顺序表中每个数据元素在内存中是连续存储的，所以如果删除某个位置的元素，则需要依次把该位置后面的元素依次向前移动。

• 头删

void SeqListPopFront(SeqList* psl)
{
    assert(psl);  //断言
    assert(psl->size>0);//防止数据为0时还删数据
    assert(psl->size > 0);  //顺序表不能为空
    int begin = 1;
    while(begin<ps->size)
    {
        psl->array[begin-1]=psl->array[begin];
        begin++;
    }
//    int i = 0;
//    for (i = 1; i < psl->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
//    {
//        psl->array[i - 1] = psl->array[i];
//    }
    psl->size--;  //有效数据个数-1
}

• 中删

void SeqListErase(SeqList* psl, int pos)
{
    assert(psl);
    assert(pos >= 0);
    assert(pos < psl->size);
    int begin = pos + 1;
    while (begin < psl->size)
    {
        psl->array[begin - 1] = psl->array[begin];
        begin++;
    }
    psl->size--;
}

• 尾删

void SeqListPopBack(SeqList* psl)
{
    assert(ps);
    assert(ps->size > 0);
    psl->array[ps->size - 1] = 0;
    psl->size--;
}

• 中删改头删

void SeqListPopFront(SeqList* psl)
{
    SeqListErase(psl, 0);//直接调用
}

• 中删改尾删

void SeqListPopBack(SeqList*psl)
{
    SeqListErase(psl, psl->size-1);//直接调用
}

Ⅵ、查找

int SeqListFind(SeqList* psl, SeqListDataType x, int begin)
{
    assert(psl);
    for (int i = begin; i < psl->size; i++) //遍历顺序表
    {
        if (ps->array[i] == x)
        {
            return i; //找到了返回下表
        }
    }
    return -1; //没找到
}

Ⅶ、打印

void SeqListPrint(SeqList* psl)
{
    assert(psl);
    if (psl->size == 0)
    {
        printf("空表");
        return;
    }
    for (int i = 0; i < psl->size; i++)
    {
        printf("%d ", psl->array[i]);
    }
    printf("\n");
}

四、总结

顺序表的实际应用：C语言顺序表实现学生管理系统

1、分类

顺序表是线性表中的一种，顺序表可以分为：
1.静态顺序表：使用定长数组存储元素。
2.动态顺序表：使用动态开辟的数组存储。

2、特点

顺序表的特点：
①随机访问，即可以在 O(1) 时间内找到第 i 个元素。（访问速度极快）
②存储密度高，每个节点只存储数据元素
③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
④插入、删除操作不方便，需要移动大量元素

3、缺陷

1.空间不够，需要扩容。扩容是有代价的，并且会存在空间浪费。
2.头部或者中部的插入删除，需要挪动数据，效率低。