【数据结构】顺序表的应用

2024-07-15 02:34:01
开发
21

一.引言

二.顺序表概念

三.顺序表的实现

一.引言

在计算机科学中，数据结构是计算机存储、组织数据的方式。顺序表作为一种线性表，以其简单、易用的特点，成为了许多高级数据结构的基础。了解顺序表的工作原理和实现方法，对于我们更好地理解计算机科学具有重要意义。

二.顺序表概念

顺序表（Sequential List）是一种线性表，它的特点是数据元素在物理存储上连续，且元素之间的逻辑顺序与物理顺序相同。在顺序表中，数据元素按照一定的顺序排列，每个元素都有一个确定的位置，可以通过索引（或称为下标）直接访问。

以下是顺序表的基本概念和特性：

数据元素：顺序表中的每一个对象称为数据元素，可以是整数、浮点数、字符或者更复杂的记录类型。
索引（下标）：顺序表中的每个数据元素都有一个索引，通常从0开始计数，用于指示元素在表中的位置。
长度：顺序表的长度是指表中数据元素的个数，长度可以根据需要进行动态调整，但通常有一个最大容量限制。
存储空间：顺序表通常在计算机内存中占用一段连续的存储空间，以便于通过索引快速访问元素。
随机访问：顺序表支持随机访问，即可以在O(1)的时间复杂度内直接访问到任意位置的元素。
顺序性：顺序表中的元素按照一定的顺序排列，元素之间的顺序关系是相邻的，即第一个元素紧邻第二个元素，以此类推。

顺序表的主要操作包括：

初始化：创建一个空的顺序表。
插入：在顺序表的指定位置插入一个新的数据元素。
删除：从顺序表中删除指定的数据元素。
查找：根据特定条件在顺序表中查找数据元素。
排序：对顺序表中的元素进行排序。
清空：将顺序表中的所有元素删除，使其变为空表。
遍历：按照顺序访问顺序表中的每一个元素。

顺序表的优缺点如下：

优点：

访问效率高：随机访问能力强，访问任意元素的时间复杂度为O(1)。
存储密度高：顺序表的数据元素紧密排列，不需要额外的空间存储元素间的关系。

缺点：

插入和删除操作效率低：在顺序表的中间或头部插入或删除元素时，可能需要移动大量元素，时间复杂度为O(n)。
固定容量：通常顺序表的容量是固定的，若存储空间不足，需要进行扩容操作，这可能会导致性能下降。

顺序表是实现其他复杂数据结构（如栈、队列等）的基础，它在算法设计和实际应用中有着广泛的使用。（后续也会发布用顺序表来实现栈和队列）

三.顺序表的实现

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

1.定义顺序表

这里使用typedef函数来讲重命名为SLDateType是因为插入顺序表的数据不会是固定不变的，这么做也是为了方便后续管理和更新。

2.顺序表初始化

将结构体里的array指向空指针，防止其变为野指针。

3.检查空间，如果满了，进行增容

结构体里的capacity的主要功能就在这一板块实现，主要是为了检查顺序表内数据是否存满。如果满了就使用realloc函数来再次开辟空间。（这里使用了三目操作符，不懂的小伙伴可以点击三目操作符）

4.顺序表尾插

5.顺序表尾删

此操作简单易懂，需要注意的是这里的删除并不是真正物理上删除了数据，而是逻辑上减小了size的值，使print读取不到他，来做到删除的效果。