数据结构之手撕顺序表（讲解➕源代码）_线性表什么时候连续

0.引言

        在本章之后，就要求大家对于指针、结构体、动态开辟等相关的知识要熟练的掌握，如果有小伙伴对上面相关的知识还不是很清晰，要先弄明白再过来接着学习哦！

        那进入正题，在讲解顺序表之前，我们先来介绍线性表这个数据结构。

0.1 线性表

        线性表是 n个具有相同特性的数据元素组成的有限的序列。
        并且在逻辑上是一对一的，一个接着一个的。比如我们之前学过的数组，字符串等。

        相同特性：同一种数据类型
        有限：数据元素的个数是有限的

        常见的线性表：顺序表、链表、栈、队列、字符串等。

        我们在讲解数据结构的时候通常要先看它的逻辑结构和物理结构。

0.2 线性表的逻辑结构和物理结构

0.2.1 逻辑结构

        线性表的逻辑结构是线性结构，线性结构 是一条连续的直线，也就是说 线性表在逻辑上是连续的，比如我们在C语言学过的的数组（顺序表），指针（可以构成链表）。

        上图分别为顺序表跟链表，他们在逻辑结构上都是一个接着一个，连续的。但是在物理结构他们还依旧连续吗？让我们带着疑问往下走。

0.2.2 线性表的物理结构

        明确告诉大家，线性表在物理结构上不一定连续，因为我们可以构成线性表的结构有数组和指针，指针又被称作链式结构。

那什么时候是连续的？

当线性表是由数组构成时：物理结构连续

        线性表的物理结构一定连续，因为数组是一个一个挨着的空间，地址上是紧挨着的，所以是连续的。

如图：

什么时候又不是连续的呢？​​​​​​​

当线性表为链式结构时：物理结构不连续

         首先链式结构在逻辑上一定是连续的，因为我们可以通过指针就找到该指针对应的地址。
        但指针的地址不一定是连续的，我们可以这存一个，那存一个，通过指针给他们链接起来。

如图：

        当了解了线性表的物理结构和逻辑结构之后，就让我们一起学习第一种数据结构---顺序表吧！

1. 顺序表

1.1概念

        顺序表是 用一段物理地址连续的存储单元依次存储数据元素的线性结构，通常采用数组的形式存储。在数组上完成数据的增删查改。
        这是什么意思呢？首先顺序表是物理地址连续的，那物理地址连续，就应该是用数组的形式来存储，之后根据数组的性质进行数据的增加，删除，查找和更改。

        我们知道顺序表是由什么构成之后，让我们看看顺序表都分为哪几种吧！

1.2 顺序表的分类

        我们顺序表只分为静态顺序表和动态顺序表两种，下面我们会给大家展示这两种顺序表。

1.2.1 静态顺序表

        静态顺序表指的是利用定长数组来存储元素

//顺序表的静态存储
#define N 7 //顺序表一次开辟的空间个数
typedef int SLDataType; //将数据类型重命名，以便我们未来换用其他的数据类型
typedef struct SeqList
{
    SLDataType arr[N]; //定长数组
    size_t size; //有效的数据个数，size_t指的是无符号整型
}Seqlist;

        我们在使用静态顺序表的时候，只能每次开辟N个大小的空间，这也就要求我们在使用之前就要想好你要存放多少个数据，非常不灵活，没有办法做到你想插入几个数据的时候就插入几个数据，所以我们大多时候不使用静态顺序表，而是改用动态顺序表作为我们日常应用。

这也是我们常说的要适应大环境的需要，而不是一味不变。

1.2.2 动态顺序表

        动态顺序表：使用动态开辟的数组存储。在这里需要大家对动态开辟内存知识有一定的掌握。

1. 动态顺序表的定义

我们首先要明确自己需要什么

1.动态开辟的数组

2.有效的数据个数（你存入的数据个数）

3.数组的容量（开辟的空间大小）

        这三个数据是绑定一起的吧！因为你有数组，你才可以存入元素，你存入元素，你的有效的数据个数才会增加，而在你存入元素之前，你必须开辟空间，给数组一定的容量。

        所以我们在这里用了结构体包含三者，目的就是能让他们三个绑定，便于大家完成代码。

        未来大家如果要创造更多的关系数据（具有关系的数据），强烈推荐使用结构体来给它们打包。

typedef int SLDataType; //数据类型的重命名，方便更改数据类型
typedef struct SeqList
{
    SLDataType *a; //指向动态开辟的数组
    int size;     //有效的数据个数
    int capacity; //动态开辟的数组的容量
}SL;

2.初始化

        在初始化这里，我们要给数组开辟一定的空间，方便在插入数据的时候进行操作，但是在这里，我们只是开辟空间，并没有给数组插入元素，所以我们的有效元素个数size就是0，容量就是你开辟的空间个数。

        我们一般开辟空间第一次给4个数据类型的空间。但是这个没有定性要求（固定的要求）你想开辟几个就开辟几个。

void SLInit(SL*ps) //初始化
{
    ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
    if(ps->a == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    ps ->size = 0;
    ps ->capacity = 4;
}

3.退出程序时的销毁

注意⚠️⚠️⚠️⚠️⚠️⚠️

        这个函数有讲头了，我们要记住一点，凡是通过动态开辟的空间，一定要进行销毁释放，因为由malloc，realloc等开辟的空间是在堆上开辟的，无法自动释放掉。我们没有这个函数，那么就会造成内存的泄漏。

        那么如何释放呢？

        free函数来释放开辟的空间，谁被开辟free谁，之后要将free的对象置为空就OK啦！不要忘了你释放空间之后，有效的数据元素是0了哈，容量也是0.

void SLDestroy(SL*ps) //退出时销毁
{
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

4.扩容

        这个函数是解决当你第一次开辟的空间不够的问题，就要用到这个函数来进行扩容，扩容一般是扩原来空间的二倍这么大。

        那扩容的条件是什么呢？

        就是当我们插入的  有效元素的个数size = 容量capacity  的时候，完成扩容之后一定要判断你扩容是否成功了，如果 tmp