数据结构——线性表（顺序表）

前言

在计算机科学中，数据结构（data structure）是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。 数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。它包含三个方面的内容：即数据的逻辑结构、数据的存储结构和数据的操作，只有这三个方面的内容完全相同，才能成为完全相同的数据结构。

数据结构是计算机四大件之一，是与计算机组成原理、操作系统、计算机网络齐名的存在，因此数据结构的重要性不言而喻。

常见的数据结构有线性表（包含顺序表、链表、栈、队列），树，堆，图，哈希表等。

本章将带领大家走进数据结构的世界，我们从最基本的线性表中的顺序表讲起。

1.线性表

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

2.顺序表

2.1概念

顺序表是一种基本的数据结构，它使用一段连续的存储空间来依次存储数据元素。顺序表是一种线性表，其特点是逻辑上相邻的元素在物理上也相邻。

优点：访问速度快，因为可以根据元素的索引直接访问。 缺点：插入和删除操作需要移动大量的元素，时间复杂度较高。

顺序表的底层实现逻辑是数组，与之不同的是数组只是用于存放数据，而顺序表则可以进行增删查改等一系列操作。

2.2定义

在C语言中，我们用一个结构体来定义顺序表。其中分为静态顺序表和动态顺序表。其中静态顺序表是使用定长数组储存元素

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

而动态顺序表则是按需申请，大大提高了内存的利用率。因此我们来实现动态顺序表。

上图是一个用结构体定义的动态顺序表，我们一句一句进行剖析。

" typedef int SLDateType " 该句是将int重新用一个单词来进行替换，这样做的好处在于当我们储存不同类型的结构时只需将上述中的int修改为相应的数据类型即可，而不需要修改整个文件中的每一个int；

结构体中的第一个成员 " SLDateType* a "此时该成员是一个整形指针，我们可以用malloc函数对其进行动态开辟，使其存储我们的元素。size 是我们所存储元素的数量。capacity 是 a 指针动态开辟空间的大小，当size和capacity相等时，我们则需要进行扩容，下面让我们一起来看一看代码的实现。

2.3实现

想要实现一个顺序表，我们需要有下列的几个函数。

因为我们是用结构体来定义顺序表，因此我们只需要传入结构体的地址，便可以在函数中修改结构体中的成员变量。所以我们实现的这些函数传参是需要传入结构体的地址，形参用结构体指针来接收即可。

2.3.1顺序表初始化

我们首先为顺序表开辟一个可以存放三个元素的空间，并将顺序表的容量（capacity）更新为3

2.3.2顺序表扩容

在我们后续添加元素时，当容量不够用时，我们可以对其进行扩容，具体的函数实现如下：

在扩容时 ，我们并不选择一次增大固定的容量，而是一次直接增大到之前的两倍。这是因为增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。并且会增加程序出错的风险。

2.3.3顺序表尾插

在尾插前我们需要先进行判断，看顺序表的容量是否满了，如果满了，那么我们需要先进行扩容。进行尾插我们只需要在数组的末尾，也就是size位置添加元素，添加完成后size++即可。

尾插相对于头插来说要更加方便，不需要挪动其他的元素，时间复杂度为O（1）；

2.3.4顺序表头插

与尾插一样，在进行头插时我们也需要判断顺序表是否满了。头插相对于尾插来说较为麻烦，需要先将数组中的元素先向后挪动一位，因此头插的的时间复杂度为O（N）。

2.3.4顺序表打印

如何在屏幕上看到我们存储的数据呢，只需要打印在终端上即可，代码也极为简单，就是数组的打印。

2.3.5顺序表尾删

尾删也比较简单，只需将size--即可，这样数组中最后一个数据就不会取到。再进行尾删时，我们需要判断顺序表是否为空，若为空肯定是无法进行尾删的，因此我们可以使用assert断言来避免顺序表为空时还进行尾删。

尾删的空间复杂度也为O（1）.

2.3.6顺序表头删

头删时，我们只需将数组中的每一位元素朝前移一位，并使size--。与尾删同理，当顺序表为空时无法进行头删。

头删的时间复杂度为O（N）；

2.3.6顺序表查找

顺序表的最大的优势便是可以进行快速的查找，代码如下：

顺序表的查找的代码实现也极为简单，若是直接以下标进行查找时间复杂度为O（1）。若是对元素进行查找时间复杂度为O（N）。

2.3.7顺序表在任意位置插入

该函数可以实现在顺序表中的任意位置插入数据，与头插相似，pos是我们想插入的下标位置。需要插入的数我们只需将目标位置即以后的元素朝后移动一位即可，当然不要忘记判断顺序表是否已满。

顺序表在任意位置插入的时间复杂度也为O（N）。

2.3.8顺序表在任意位置删除

该函数可以实现在顺序表中删除任意位置的数据，与头删类似，pos是我们需要删除位置的下标。只需将目标位置之后的数据前移一位并使size--即可。当然若是顺序表为空或者目标位置超出范围是不可进行删除的。

顺序表在任意位置删除的时间复杂度也为O（N）。

2.3.9顺序表摧毁

我们的顺序表中的数组是用malloc开辟的空间，因此当我们退出程序时需要释放我们动态开辟的空间，防止造成内存泄漏，代码实现如下：

顺序表的摧毁十分简单，只需释放掉开辟的数组空间即可。

尾声

本章为大家较为详细的介绍了线性表中的顺序表的概念以及代码实现，下一章将为大家讲解线性表中的另一个结构-链表。

初次创作，若有错误，欢迎大家在评论区或者私信留言。同时也欢迎各位一起讨论，感谢您的观看！