数据结构 - 顺序表

一. 线性表的概念

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

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

外传：

在数组实现的线性表中，所有元素都连续存储在内存的一段固定区域内，可以通过索引直接访问每个元素。这种实现方式的优点是访问速度快，但缺点是大小固定，不够灵活。

在链表实现的线性表中，元素可以分散存储在内存中，每个元素通过指针或引用与其前驱和后继元素相连接。这种实现方式的优点是可以动态调整大小，更加灵活，但缺点是访问某个特定元素时可能需要从头开始遍历，访问速度较慢。

二. 顺序表介绍

2.1 顺序表的概念

顺序表是一种线性表的实现方式，它使用连续的内存空间来存储表中的元素，使得每个元素都可以通过数组索引快速访问。这种数据结构非常类似于数组，事实上，在很多编程语言中，顺序表就是以数组的形式实现的。那顺序表和数组有区别吗？

顺序表：顺序表是用一段物理地址连续存储单元，依次存储数据元素的线性结构（顺序表就是将数据连着存放，存放的数据空间也是连着的）

数组：数据不用按顺序的存放，可以随意的存放（数组不按空间顺序随意地存放数据，但是顺序表的数据是要按照空间的的顺序存放）

2.2 顺序表的结构

1. 静态顺序表

静态顺序表使用固定大小的数组来存储数据，这意味着在创建顺序表时，必须指定一个最大容量，之后这个容量不能改变。因此，静态顺序表的大小在其生命周期内保持不变。

特点：

固定容量：一旦确定，容量不能增加或减少。
内存连续性：所有元素都存储在连续的内存位置，这样可以通过索引快速访问任何元素。
高效的访问速度：由于直接通过数组索引访问，访问速度非常快。
内存浪费：如果不使用全部容量，内存资源可能会被浪费。反之，如果需要的元素超出了初始设定的容量，无法存储更多的数据，这限制了其使用的灵活性。

静态顺序表适用于数据量已知且数据量不会改变的情况，如在嵌入式系统或有严格内存管理需求的应用中非常有用。

1. 动态顺序表

动态顺序表则更为灵活，它使用一个可以在运行时根据需要自动扩容的数组来存储元素。这意味着初始时，顺序表可能具有一个较小的容量，但当添加的元素超过当前容量时，顺序表可以动态地分配一个更大的数组，将旧元素复制到新的数组中，并释放旧数组。

特点：

动态扩容：当需要更多空间时，可以自动扩展其容量。
内存连续性：尽管动态顺序表可以扩容，但其元素仍然存储在连续的内存位置。
灵活性高：适应不同的数据存储需求，尤其是数据量不确定的场合。
可能的高扩容成本：动态扩容涉及到复制整个数组到新的内存地址，这可能导致较高的运行时开销，特别是数组很大时。

我们会发现，动态顺序表的结构体比静态顺序表的结构体多了一个 capacity 成员。

我们用这个成员记录当前顺序表的最大容量，当有效数据个数 size 和 capacity 相等时，说明了当

前顺序表空间已满，需要进行扩容。

三. 动态顺序表的实现

首先建立三个文件：

SeqList.h文件，用于函数声明

SeqList.c文件，用于函数的定义

Test.c文件，用于测试函数

建立三个文件的目的：将顺序表作为一个项目来进行书写，方便我们的学习与观察。

3.1 定义结构体(SL)

// 定义SLDateType为int类型，这是顺序表中将要存储的数据类型
typedef int SLDateType;

// 定义一个结构体，用来表示顺序表
typedef struct SeqList
{
    SLDateType* a; // 声明了一个指向动态分配数组的指针，这个数组用于存储顺序表中的元素
    int size;      // 记录当前顺序表中已经存储的元素的数量，即顺序表的当前大小
    int capacity;  // 记录顺序表分配的存储容量，即数组的最大可能大小
} SeqList;

外传：

在C语言中使用 typedef 来定义新的数据类型名有多个原因，尤其是在实现如顺序表这样的数据结构时。SLDateType 在顺序表定义中的使用有以下几个主要好处：

1. 抽象数据类型

通过定义 SLDateType 作为数据类型，可以轻松地抽象和封装数据结构中元素的具体类型。这种抽象化允许程序设计者更改数据的基础类型而不影响使用该数据结构的代码。例如，如果将来需要将顺序表中的数据从整数 (int) 改为浮点数 (double) 或其他类型，只需更改 SLDateType 的定义，而不需修改顺序表的每个实现细节。

2. 代码可维护性

当你将数据类型定义为 SLDateType 而不是直接使用 int 或其他具体类型时，代码的可读性和可维护性提高了。它在代码中创建了一个明确的表示点，表明所有使用 SLDateType 的地方都是处理相同类型的数据，使得数据类型的更改集中化和简化。

3. 便于代码重用

如果你有多个数据结构或算法需要处理相同类型的数据，使用 SLDateType 可以确保这些组件可以更容易地共享和重用。例如，可以为不同的数据结构（如链表、堆、栈等）定义通用的操作和函数，而不必为每种类型写重复的代码。

4. 易于进行类型检查和修改

在大型项目或需要严格类型检查的项目中，使用 typedef 可以更容易地管理类型安全。更改底层数据类型时，通过查看 SLDateType 的使用情况，可以很容易地识别出可能受影响的代码部分。

5. 兼容性与扩展性

在开发库或框架时，使用 typedef 为数据类型命名提供了额外的兼容性和扩展性。如果库的用户需要将库与其它代码或第三方库整合，他们可以通过修改 typedef 定义来实现类型匹配，而不是修改库本身的代码。

3.2 初始化结构体(SLInit)

初始化一个顺序表，存在一个关键的问题，那就是是否写成了参数传递的方式。如果使用的传参的方式传递参数，这意味着函数内部的修改仅影响原始的顺序表对象的拷贝。这样的初始化实际上是无效的，因为调用这个函数后，原始的顺序表不会被初始化。

为了让初始化生效，需要通过指针来传递顺序表，这样在函数内部对顺序表的修改才会影响到原始的对象。

// 初始化顺序表
// 参数 ps 是指向顺序表的指针
void SLInit(SL* ps)
{
    assert(ps); // 断言：确保传入的指针ps非空，防止解引用空指针造成程序崩溃

    ps->a = NULL;        // 将数组指针设置为NULL，表示当前没有分配任何内存给数据
    ps->size = 0;        // 将顺序表的当前元素数量设置为0，表示顺序表为空
    ps->capacity = 0;    // 将顺序表的容量设置为0，表示还没有分配任何容量
}

外传：

如果顺序表没有进行适当的初始化，就会出现一系列潜在的问题，这些问题可能会严重影响程序的运行。在C语言中，未初始化的变量特别是指向动态内存的指针，以及相关的整型变量（如数组的大小和容量）可以有不确定的初始值，这些都会引起以下问题：

1. 不确定的指针值

如果指向数组的指针没有初始化，它可能指向任意的内存地址。尝试通过这个未初始化的指针访问或修改数据会导致未定义行为，这通常包括：

程序崩溃：访问无效或不属于程序的内存地址通常会导致程序异常终止。
数据损坏：如果指针偶然指向某些敏感区域，通过该指针的写操作可能会破坏其他数据。
安全漏洞：未初始化的指针被恶意利用可能会导致安全漏洞，例如缓冲区溢出攻击。

2. 不确定的数组大小和容量

如果顺序表中的size和capacity没有初始化，它们的值将是不确定的。这会导致一系列问题，如：

越界访问：如果size或capacity不小心设置为一个非常大的数，程序可能会尝试访问数组的不存在的部分，这同样会导致程序崩溃。
内存分配错误：如果capacity的值是随机的，当尝试基于这个值分配内存时，可能因为请求了过多的内存而失败。
错误的行为：基于错误的size值，顺序表的行为可能不正确，例如认为它已经满了或还有大量空间。

3.3 检查顺序表是否需要扩容(SLCheckCapacity)

扩容是一个常见且有用的特性，可以在运行时根据数据量的变化调整内存使用。这里是几个关键点来说明何时以及为什么顺序表需要扩容：

1. 容量达到极限

当顺序表的元素数量达到其当前容量的极限时，再添加新元素就无法进行了，除非扩展其容量。在这种情况下，扩容是必要的，以避免数据丢失或程序错误。

2. 性能优化

在顺序表接近满容量时，即使还可以添加少量元素，执行扩容也是一种常见的做法。这样做可以减少将来可能的多次扩容操作所需的总成本，因为频繁的小扩容操作（例如每次只增加一个元素的空间）会导致多次昂贵的内存复制操作。

扩容机制的实现

扩容通常涉及以下步骤：

确定新容量：新容量通常是当前容量的两倍，这种加倍策略是为了平衡扩容的成本和频率（称为幅度扩展）。
分配新数组：创建一个新的、更大的数组来存储元素。
复制元素：将现有元素从旧数组复制到新数组。
释放旧数组：释放旧数组占用的内存空间。
更新指针和容量值：将顺序表的数据指针指向新数组，并更新容量值。

在扩容是，会需要用到动态分配函数 realloc ()函数，如果对这个函数不太了解，可以看一下这篇文章：动态分配函数

void SLCheckCapacity(SL* ps)
{
    assert(ps); // 断言，确保传入的顺序表指针非空

    if (ps->size == ps->capacity)
    { // 如果当前元素数量等于容量，需要扩容
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  // 新容量计算策略：如果当前容量为0，则初始为4；否则容量翻倍

        SLDateType* temp = (SLDateType*)realloc(ps->a, newCapacity * sizeof(SLDateType)); // 尝试重新动态分配内存
        if (temp == NULL)
        { // 检查realloc是否成功，注意这里是比较操作，应使用两个等号==
            perror("realloc failed"); // 如果内存分配失败，输出错误消息
            exit(-1);  // 退出程序
        }

        ps->a = temp;  // 更新顺序表的数据指针
        ps->capacity = newCapacity;  // 更新顺序表的容量
    }
}

3.4 尾插(SLPushBack）

尾插操作是指在顺序表（或类似的数据结构如动态数组、列表等）的末端插入一个新元素。

void SLPushBack(SL* ps, SLDateType x) {
    assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃

    SLCheckCapacity(ps); // 检查顺序表的容量是否足够，如果不足则进行扩容

    ps->a[ps->size] = x; // 将新元素x存放在数组的当前末尾位置，ps->size是指向下一个空闲位置的索引 
//这里为什么用size而不用size-1或者别的呢，因为size的大小，就是数组最后一个数+1的下标

    ps->size++; // 更新顺序表的元素计数，增加1，以反映添加了新元素
}

3.5 尾删(SLPopBack)

尾删操作是指在顺序表的尾部删除数据。

void SLPopBack(SL* ps) {
    assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃

    //ps->a[ps->size - 1] = 0;  //用于清除顺序表最后一个元素的数据，将其设置为 0。

    // 温和的错误处理方式: 检查顺序表是否为空，如果为空则打印信息并退出函数
    /*if (ps->size == 0) {
        printf("顺序表已空\n");
        return;
    }*/

    // 暴力的错误处理方式: 使用断言确保顺序表不为空，如果为空程序在调试模式下会中断执行
    assert(ps->size > 0); // 确保顺序表中至少有一个元素，防止下溢

    // 可选的清除操作: 清除顺序表最后一个元素的数据，将其设置为 0
    // ps->a[ps->size - 1] = 0;

    ps->size--; // 减少顺序表的大小，逻辑上移除最后一个元素
}

注意：当顺序表没有元素时，也就是 sz 为 0 时，不可以进行删除

举例： 假如顺序表有 5 个数据，此时需要尾删 6 个数据，那么这时，顺序表的 size = -1。此时程序不会报错，因为本身就没有数据可以删除，但是让我们在进行尾插的时候，程序就会报错了，因为尾插数据会访问 size 的下表 -1 此时出现了越界访问，程序出错。

解决方案 ：加入断言进行判断，防止size 的下标越界

3.6 头插(SLPushFront)

头插操作是指在最前端插入一个新元素。这意味着将所有现有元素向后移动一个位置以空出第一个位置，然后将新元素放置在顺序表的起始位置。头插操作相较于尾插操作，通常更为耗时，因为它涉及到移动更多的元素。

当你想进行挪动数据的时候，现在给你有两个选择，你会选择哪个呢？

从第一个数据进行从先往后的挪动
从最后一个数据进行从后往前的挪动

// 在顺序表的开始位置插入一个新元素
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);  // 断言，确保传入的顺序表指针非空

    SLCheckCapacity(ps);  // 检查顺序表的容量是否足够，如果不足则进行扩容

    int end = ps->size - 1;  // 计算顺序表最后一个元素的索引位置
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];  // 将元素向后移动一个位置
        end--;  // 向前移动索引，继续移动前一个元素
    }

    ps->a[0] = x;  // 在顺序表的第一个位置插入新元素
    ps->size++;  // 更新顺序表的大小
}

3.7 头删(SLPopFront)

头删原理：头删就是将下标为 0 的数据删除，其余数据依次向前挪动，此时同样出现两情况。

当你想进行挪动数据的时候，现在给你有两个选择，你又会选择哪个呢？

先从下标为 1 的数据向前挪动
先从最后一个数据向前挪动

void SLPopFront(SL* ps) {
    assert(ps);  // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃

    assert(ps->size > 0);  // 断言，确保顺序表中有元素，避免下溢错误

    int begin = 1;  // 从顺序表的第二个元素开始
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];  // 将每个元素向前移动一个位置
        begin++;  // 递增索引，继续处理下一个元素
    }

    ps->size--;  // 减少顺序表的大小，逻辑上移除最后一个空出的位置的元素
}