C语言实现顺序表的基本操作的示例详解-C/C++开发

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。本文将通过示例为大家讲解一下顺序表的基本操作，需要的可以参考一下

一、认识顺序表

1.线性表

线性表是n个具有相同特性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串……线性表在逻辑上是线性结构，也就是说是一条连续的直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式来存储。

2.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删改查。顺序表一般可分为：静态顺序表和动态顺序表（使用动态开辟的数组存储）。

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

#define MAX 10
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
    SLDataType arr[MAX];//用来存储数据
    int size;//用来记录数组中存储有效数据元素的个数
}SL;

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

//动态顺序表
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
    SLDataType* arr;//指向动态开辟的数组
    int size;//用来记录数组中存储有效数据元素的个数
    int capacity;//用来记录容量大小
}SL;

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

二、顺序表的基本操作（接口实现）

1.初始化顺序表

void SLInit(SL* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

初始化时设置其有效数据个数和容量都为0，指针指向NULL。

2.打印顺序表

void SLPrint(SL* ps)
{
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

3.尾插

void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断刚开始是否有空间
        SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
        if (tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->arr = tmp;
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->size] = x;
    ps->size++;
}

尾插就是在尾部插入数据，因为刚开始的时候没有给数组分配空间，所以要考虑当没有空间时要去申请空间，realloc函数是扩容函数，在指针为空的情况下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判断当前容量大小并确定要开辟的空间大小。

SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用来在堆内存中开辟空间，realloc之后注意将其强制转化成SLDataType*类型。当成功开辟空间之后赋给ps->arr，同时注意将NewCapacity赋给ps->capacity。

4.尾删

void SLPopBack(SL* ps)
{
    assert(ps);
    //暴力的检查
    assert(ps->size > 0);//判断ps->size是否大于0，当等于0时再删的话ps->size就会变为-1，越界
    //温柔的检查
    //if (ps->size == 0)
    //{
    //    return;
    /