【初阶数据结构】顺序表

文章目录

前言

本节内容开启新篇章，将为大家带来数据结构，数据结构分为两个阶段一个是初阶另一个是进阶。我首先给大家先介绍初阶数据结构，虽然内容看起来难但沉下心来学并没有你想象中的难学。

一、线性表

在认识顺序表之前，我们先来了解一下线性表。

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

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

二、顺序表

1.概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

既然顺序表底层是采用数组存储，那为什么不能直接使用数组，反而要单独提出顺序表的概念，两者之间有什么区别吗？因为顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口让我们可以合理的管理数据；而数组只是一种连续存储数据的结构并不能实现增删改查等多种方法。

所以顺序表是一个结构体，不同的顺序表定义的结构体不同。接下来学习顺序表的分类。

2.分类

顺序表分为两种，静态顺序表和动态顺序表。接下来介绍这两种顺序表：

静态顺序表：

定义：静态顺序表的静态是指顺序表底层的数组的元素大小是静态的，也就是静态顺序表使用的是定长的数组存储元素。

缺点：空间给少了不够用，空间给多了造成空间浪费

typedef int SLDataType;
#define N 1000
typedef struct SeqList {
    SLDataType arr[N];
    int size;//有效数据个数
}SL;

//SeqList--->sequence list--->顺序表

在静态顺序表中的结构有两个成员，第一个成员是底层存储数据的数组arr[N]，它的大小是确定的；第二个成员是整型变量size，它的含义是当前顺序表中有效元素的个数。

动态顺序表：

定义：动态顺序表里面的动态就是指顺序表的大小是不固定的，也就是顺序表底层的数组的大小是不固定的，可以动态的变化。

缺点：频繁增容会导致内存有损失

typedef struct SeqList {
    SLDataType* arr;
    int size;//有效数据个数
    int capacity;//容量大小
}SL;

动态顺序表中的结构有三个成员，第一个成员是底层存储数据的数组arr；第二个是成员是整型变量size是顺序表中有效数据个数；第三个成员是capacity是当前顺序表的容量大小。

因此，一般情况下我们是难以知道所需空间的大小，用静态顺序表就出现空间过小过大的情况，用动态顺序表可以方便我们实现空间是动态变化，所以我们要用动态顺序表来实现顺序表中增删改查等方法。

三、顺序表的实现

在顺序表中，我们用顺序表的初始化，销毁顺序表，打印，增容，尾插，头插，尾删，头删，查找指定位置数据，在指定位置之前插入数据，以及删除指定位置的数据，这些方法来对顺序表进行实现。

接下来我们先了解顺序表的结构体，因为顺序表是用动态顺序表来实现所以使用动态顺序表；为了使用方便我们为顺序表起一个名字为SL.

typedef struct SeqList {
    SLDataType* arr;
    int size;
    int capacity;
}SL;

1.初始化

在创建完一个顺序表后，我们要对其进行初始化才能正常使用。由于要把顺序表的结构体里数据传参到初始化函数里，因此初始化函数的参数类型就是SL*；首先我们对ps指向的数组置为NULL，因为数组中的元素和空间是为0 所以再对ps指向的有效数据size和容量大小capacity置为0.

//初始化
void SLInit(SL* ps)
{
    ps->arr =NULL;//用箭头来解引用
    ps->size = ps->capacity=0;//因为上面数组空间为0，则两者都为0

}

2.销毁

由于顺序表是动态申请空间，所以在使用完顺序表后我们对其进行空间的释放，避免造成内存的泄露。先对ps指向的arr进行判断是否为有效数据，是有效数据就对其进行消耗，释放空间，销毁完成要对其设置NULL；再对ps->size和ps->capacity置为0.

//销毁

void SLDesTroy(SL* ps)
{
    if (ps->arr)//判断是不是有效数据，是有效数据就销毁
        free(ps->arr);
    ps->arr = NULL;//销毁完后要设空值
    ps->size = ps->capacity = 0;
}

3.打印

对顺序表的结果进行打印，方便展示顺序表的结果。

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

4.增容

实现顺序表的增删改查等方法之前，我们要对空间大小进行判断，先判断再对方法进行讨论。因为动态顺序表底层数组的大小是动态变化的，所以写一个增容函数来检查数组空间大小的情况；如果空间已满则对其进行扩容，每次对空间的增大我们进行两倍增容，这样进可能减少空间浪费和避免频繁增容。

我们先对pc->size和pc->capacity是否相等进行判断；如果相等，是否需要增容进行判断；如果需要增容，我们用realloc()函数来增容，将realloc的申请的空间先放在临时变量tmp中，增容空间的大小用两倍的方式进行增容；最好对ps->arr和ps->capacity进行数据更新。

//增容
void SLcheckCapacity(SL* ps)
{
    //空间不够，申请空间
    if (ps->size == ps->capacity)
    {   
        //空间不够-2倍增容
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));

        if (tmp == NULL)
        {
            perror("realloc fail!");//报错的写法
            exit(1);//退出：写一个非0的数就可以退出程序
        }

        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

5.尾插

尾插顾名思义，就是在一个数组中的最后一个元素的后面插入一个数据。在尾插之前要先判断空间容量的大小是否需要增容，然后再对其进行尾插。(时间复杂度O(1))

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps != NULL);
    SLcheckCapacity(ps);//先判断

    ps->arr[ps->size++] = x;//再执行
}

6.头插

头插就是在数组第一个元素之前插入一个数据。跟尾插一样在执行之前先判断空间容量是否需要增容，然后将下标为0之后的元素整体往后移一位，把下标为0的位置空置出来，再把数据插入到下标为0的位置.(时间复杂度O(n))

//头插
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);//简写方式，可以做到避免冗余的情况，等价写法：assert(ps != NULL);
    SLcheckCapacity(ps);
    for (int i = ps->size; i > 0; i--)//i>0是因为循环到下标0就结束了
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ++ps->size;
}

7.尾删

尾删就是把数组中最后一个元素进行删除。在执行尾删之前先断言判断ps和ps->size是否为NULL，再对size--.(时间复杂度O(1))

//尾删
void SLPopBack(SL* ps)
{
    assert(ps && ps->size);//assert(ps && ps->size>0);两者写法都可；ps和ps->size都不能为NULL
    
    --ps->size;
}

8.头删

头删就是在一个数组中把第一个元素进行删除。在执行尾删之前先断言判断ps和ps->size是否为NULL；把下标为1之后的元素整体向前移一位从而覆盖下标为0的元素，这样就可以把下标为0的元素进行删除；再对size--.(时间复杂度为O(N))

//头删
void SLPopFront(SL* ps)
{
    assert(ps && ps->size);
    for (int i = 0; i < ps->size - 1; i++)//i< ps->size - 1是因为执行到size-1就结束
    {
        ps->arr[i] = ps->arr[i + 1];
    }
    --ps->size;
}

9.查找指定位置数据

查找数组中某一元素，需要对顺序表进行遍历。给出需要查找的数据，用i对顺序表进行向前遍历，找到数据就返回1反则返回-1.(时间复杂度为O(N))

//查找
int SLFind(SL* ps, SLDataType x)
{
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
            return 1;//找到了返回1
    }
    //没找到返回-1
    return -1;
}

10.指定位置之前插入数据

在指定位置的前面插入一个数据。比如在一个数组中下标为2的元素是指定的位置pos，则就在下标为2的元素的前面插入一个数据；需要把下标为2的元素和下标为3的元素往后移一位，变成下标为3和下标为4的元素，原来下标为2的元素的位置变成0，把数据插入到下标为2的位置。(时间复杂度为O(N))

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);//pos是指定位置；pos在0-size范围内都不能为NULL;
    //在数组下标中在下标为0的地方插入为头插;在下标为size的地方插入为尾插

    SLcheckCapacity(ps);
    
    for (int i = ps->size; i > pos; i--)//i从size开始到指定位置pos结束(从后往前找)
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ++ps->size;
}

11.删除指定位置的数据

在指定的位置对数据进行删除。比如在一个数组中下标为1的元素是指定位置pos，对下标为1的元素进行删除；需要把下标为2和下标为3的元素往前移一位覆盖下标为1的元素，从而删除下标为1的元素。(时间复杂度为O(N))

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    
    //在数组下标中在下标为0的地方插入为头删;在下标为size的地方插入为尾删

    for (int i = pos; i < ps->size; i++)//i从pos位置开始到size结束
    {
        ps->arr[i] = ps->arr[i + 1];
    }
    --ps->size;
}

总结

非常感谢大家阅读完这篇博客。给大家详细介绍了顺序表的定义和分类以及实现顺序表的方法，希望这篇文章能够为您带来一些有价值的信息和启示。