[数据结构与算法]【C数据结构】什么是顺序表？一文迅速搞懂！

一、什么是线性表？

线性表，顾名思义，其会呈现出一种线性进行存储。这和我们所学过的数组的概念很像，回顾一下数组的基本知识：数组的各个元素连续存放在内存中，并按照数组类型为每一个变量分配对应大小的存储空间。在线性表中也是如此，当内存中的数据是连续存储时我们可以将其用数组的角度理解，我们称之为顺序表。当数据以指针的形式连接起来时，此时我们称其为链表。

二、如何创建一个顺序表？

由上面的叙述，我们可以知道，一个顺序表可以近似理解为一个数组。但与数组不同的是，顺序表本质上是一个需要不断的进行数据的存储、删除动态空间。所以我们需要用多个接口函数来维护顺序表。

由于顺序表不仅仅是一个数组，还需要我们不断的探索其长度，所以我们并不能简单的通过创建数组的方式创建顺序表。所以我们想到用一个结构体就能够有效的将数组与其大小紧密联合起来：

#pragma once
#define N 1000
typedef int SLDataType;

//静态数据表
typedef struct SeqList
{
    SLDataType a[N];
    int size;
}SL;

注意到，这里的N是我们预先进行定义的1000，若我们需要更多的数据存储进顺序表，那么我们需要不断的修改#define N的值。这显得有些麻烦。
所以稍微改进一下，我们就可以用一个指针将静态顺序表转变为一个可以扩展空间的动态顺序表。

typedef struct SeqList
{
    SLDataType *a;
    int size;//表示数组实际存储了多少个数据
    int capacity//数据实际能存储数据的空间容量是多大
}SL;

注意到，在创建动态顺序表时，我们又引入了一个capacity变量来探索当前顺序表的“存储数据的能力”而选择是否进行扩容。capacity变量在后续的接口函数中起着至关重要的作用。请注意，这里的size是当前顺序表实际存储数据的多少，capacity是整个顺序表的容量。比如说容量可以是8（capacity=8)，但当前顺序表可以只存储4个元素（size=4)

三、接口函数

一个动态的顺序表需要用多个接口函数进行维护，以实现对数据元素的增删查改操作。我们定义如下的接口函数类型：

void SeqListCheckCapacity(SL*ps)
//容量判断函数
void SeqListInit(SL* ps);
//初始化函数
void SwqListDestory(SL*ps);
//销毁函数
void SeqListPushBack(SL* ps,SLDataType x);
//尾插
void SeqListPopBack(SL* ps);
//尾删
void SeqListPushFront(SL*ps,SLDataType x);
//头插
void SeqListPopFront(SL*ps);
//头删
int SeqListFind(SL* ps,SLDataType x);
//找到了返回x位置下标，没有找到返回-1
void SeqListInsert(SL*ps,int pos,SLDataType x);
//指定pos下标位置插入
void SeqListErase(SL*ps,int pos);
//删除pos位置的数据

容量审查函数：

但是在写入或者读出数据之前，我们需要先对线性表空间进行审查，以确定能否进行后续的操作。
函数创建的基本思想：当前存储数据与容量相等时，说明顺序表已经没有多余空间进行增加操作，那么需要对其扩容。只有在第一次扩容时，容量为4。之后均用当前容量的二倍形式进行扩容。

void SeqListCheckCapacity(SL*ps)
{
    if(ps->size==ps->capacity)
    {
        int newcapacity=ps->capacity==0?4:ps->capacity*2;//三目运算符
        SLDataType *tmp=(SLDataType*)realloc(ps->a,newcapcity*sizeof(SLDataType));//realloc追加内存空间进行扩容
        if(tmp==NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity=newcapaticy;
    }
}

初始化函数：

//初始化函数
void SeqListInit(SL* ps)
{
    ps->a=NULL;
    ps->size=ps->capacity=0;
}//这里要注意，要对结构体进行传址操作，否则不能进行初始化
//结构体变量本质上是一个变量，不是一个函数。通过函数指针的学习我明白了函数的名字就是函数的地址，当使用回调函数时可以&函数名 也可以不进行取地址操作。但对于一个变量来说，必须进行传址操作才能改变其值

销毁函数：

当使用完内存之后，需要对顺序表申请的内存空间进行销毁，以防止内存泄漏。

//销毁函数
void SeqlistDestory(SL*ps)
{
    free( ps->a);
    ps->a=NULL;
    ps->sz=ps->capacity=0;
}

尾插函数:

对于一个动态的顺序表来说，尾插一种重要的元素增加方式，但在尾插之前我们需要检查当前顺序表的容量是否已满。元素插入的思想便是向数组末尾进行插入数据。注意：size表示的是数组长度，而对应的最后一个元素的角标应是size-1

void SeqListPushBack(SL* ps,SLDataType x)//尾插
{
    //首先要判断当前空间够不够用
    //第一种情况：第一次插入之前，是空的数组
    //第一种情况：当前空间不够
    //第三种情况：当前空间足够
    //通过调用容量检查函数检查空间是否足够
    SeqListCheckCapacity(pc);
    ps->a[ps->size]=x;
    ps->size++;
}

尾删函数：

尾删函数的基本思想更为简单，只需要对size维护空间进行缩小，即对size以外的内容不进行访问就完成了删除操作。

void SeqListPopBack(SL* ps);//尾删
{
    //最基本的思想就是将ps->a[ps->sz-1]的位置上的元素置零 //然后对ps->sz进行减一操作。
    //但是事实上仅对size进行——操作就行，但是当size为0的时候就不能进行删除了，//所以要对size为0的极限情况进行限制
    if(ps->size>0)
    {
        ps->size--;
    }
    //或者用assert 方法
    /*assert(ps->size>0);
    ps->size--;*/
}

头插函数：

连续存储的所有数据结构的所有的插入函数在插入元素之前，都需要对容量进行判定，以确定是否可以进行插入操作。头插的基本思想与尾插类似，只不过需要对数据元素进行相邻赋值，最后将第一块空间腾出来以进行头插。所有插入函数结束之后，不要忘记对size+1。

void SeqListPushFront(SL*ps,SLDataType x)//头插
{
    SeqListCheckCapacity(ps);
    //基本思想就是从数组的最后向后移动，依次移动一个单位
    //每移动一次 end指针减一 当end指针为0时，跳出循环
    //此时数组的第一个元素空了出来，我们可以对其进行赋值
    //当插入之后有效容量就会加一，size就要进行加一
    int end=ps->size-1;
    while(end)
    {
        ps->a[end+1]=ps->a[end];
        end--;
    }
    ps->a[0]=x;
    ps->size++;//头插之后容量变大 size表示的是实际的有效数据的容量
}

头删函数：

在头删时，要将元素从后向前的覆盖，最终使得size-1。需要注意begin变量的起始位置，这里给出了begin从第二个元素开始的情况。若设置begin为0，那么相应的循环终止条件也要发生改变。

void SeqListPopFront(SL*ps)//头删
{
    assert(ps->size>0);
    //挪动数据
    int begin=1;
    while(begin< ps->size)
    {
        ps->a[begin -1]=ps->a[begin];//向前赋值
        begin++;
    }
    ps->size--;
}

寻找函数:

使用for循环对顺序表元素进行遍历寻找，当所需目标元素在顺序表内时返回其角标，反之返回-1

int SeqListFind(SL* ps,SLDataType x)
{
    SeqListCheckCapacity(ps);
    int i=ps->size-1;
    for(i=ps->size-1;i>=0;i--)
    {
        if(x==ps->a[i])
        {
            printf("找到了，为第%d个元素",i);
            return i;
            break;
        }
        
    }
    return -1;
}

指定下标插入：

这里采用循环的方式进行空间转换，通过循环将元素相邻从左向右赋值，最终将所指定位置空出，将指定下标的元素插入

void SeqListInsert(*SL ps,int pos,SLDataType x)
{
    SeqListCheckCapacity(ps);
    assert(pos<ps->size || pos>=0);
    int end=ps->size-1;
    if(pos<ps->size)
    {
        int turn=ps->size-pos;//控制跳出循环条件就是插入位置到末尾的距离
        while(turn)
        {
            ps->a[end+1]=ps->a[end];
            end--;//end做减法来不断的向前移动进行前后位赋值
            turn--;
        }
        ps->a[pos]=x;
        ps->size++;
    }
    else if(pos==ps->size)
    {
        ps->a[end+1]=ps->a[end];
        ps->a[end]=x;
        ps->size++;
    }
    else 
    {
        printf("越界插入，错误");
        exit(-1);
    }
    
}

删除指定下标元素：

删除指定下标元素时，给出了第二种指定下标的写法，即从指定下标pos的下一个位置开始进行循环，将pos位置数据进行覆盖，最终size-1。完成指定下标的元素删除

void SeqListErase(SL*ps,int pos)
{
    assert(pos>=0||pos<ps->size);
    
    int begin=pos+1;
    while(begin<ps->size)
    {
        ps->a[begin-1]=ps->a[begin];
        begin++;
    }
    ps->size--;
}

小结

综上，我们对顺序表的结构就有了一个宏观的认识。从逻辑上来说，顺序表本质上是一种数组的变型，即用各种接口函数对顺序表整个动态的数组进行动态维护。从代码实现角度，我们用结构体定义了顺序表的基本内容：用于空间申请的指针、当前存储量size、与整体容量capacity。并定义了多种接口函数用于对顺序表的增删查改。需要注意的是，在结构体实体化时，结构体变量仍是一个变量，若需要对其进行值的修改操作，必须进行传址操作。当完成顺序表存储功能后，需要对其进行销毁，必须要对申请的内存空间进行释放，以避免内存泄漏而产生的不可预知的错误。

希望本文能对你有所帮助??。