• 数据结构 - 顺序表

    一. 线性表的概念

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

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

    外传：

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

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

    二. 顺序表介绍

    2.1 顺序表的概念

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

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

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

     2.2 顺序表的结构

    1. 静态顺序表

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

    特点：

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

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

    1. 动态顺序表 

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

    特点：

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

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

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

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

    三. 动态顺序表的实现

    首先建立三个文件：

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

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

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

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

    3.1 定义结构体(SL)

    1. // 定义SLDateType为int类型，这是顺序表中将要存储的数据类型
    2. typedef int SLDateType;
    3.  
    4. // 定义一个结构体，用来表示顺序表
    5. typedef struct SeqList
    6. {
    7.     SLDateType* a; // 声明了一个指向动态分配数组的指针，这个数组用于存储顺序表中的元素
    8.     int size;      // 记录当前顺序表中已经存储的元素的数量，即顺序表的当前大小
    9.     int capacity;  // 记录顺序表分配的存储容量，即数组的最大可能大小
    10. } SeqList;

    外传：

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

    1. 抽象数据类型

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

    2. 代码可维护性

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

    3. 便于代码重用

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

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

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

    5. 兼容性与扩展性

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

    3.2 初始化结构体(SLInit)

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

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

    1. // 初始化顺序表
    2. // 参数 ps 是指向顺序表的指针
    3. void SLInit(SL* ps)
    4. {
    5.     assert(ps); // 断言：确保传入的指针ps非空，防止解引用空指针造成程序崩溃
    6.  
    7.     ps->a = NULL;        // 将数组指针设置为NULL，表示当前没有分配任何内存给数据
    8.     ps->size = 0;        // 将顺序表的当前元素数量设置为0，表示顺序表为空
    9.     ps->capacity = 0;    // 将顺序表的容量设置为0，表示还没有分配任何容量
    10. }

    外传：

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

    1. 不确定的指针值

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

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

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

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

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

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

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

    1. 容量达到极限

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

    2. 性能优化

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

    扩容机制的实现

    扩容通常涉及以下步骤：

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

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

    1. void SLCheckCapacity(SL* ps)
    2. {
    3.     assert(ps); // 断言，确保传入的顺序表指针非空
    4.  
    5.     if (ps->size == ps->capacity)
    6.     { // 如果当前元素数量等于容量，需要扩容
    7.         int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  // 新容量计算策略：如果当前容量为0，则初始为4；否则容量翻倍
    8.  
    9.         SLDateType* temp = (SLDateType*)realloc(ps->a, newCapacity * sizeof(SLDateType)); // 尝试重新动态分配内存
    10.         if (temp == NULL)
    11.         { // 检查realloc是否成功，注意这里是比较操作，应使用两个等号==
    12.             perror("realloc failed"); // 如果内存分配失败，输出错误消息
    13.             exit(-1);  // 退出程序
    14.         }
    15.  
    16.         ps->a = temp;  // 更新顺序表的数据指针
    17.         ps->capacity = newCapacity;  // 更新顺序表的容量
    18.     }
    19. }

    3.4 尾插(SLPushBack）

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

    1. void SLPushBack(SL* ps, SLDateType x) {
    2.     assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    3.  
    4.     SLCheckCapacity(ps); // 检查顺序表的容量是否足够，如果不足则进行扩容
    5.  
    6.     ps->a[ps->size] = x; // 将新元素x存放在数组的当前末尾位置，ps->size是指向下一个空闲位置的索引 
    7. //这里为什么用size而不用size-1或者别的呢，因为size的大小，就是数组最后一个数+1的下标
    8.  
    9.     ps->size++; // 更新顺序表的元素计数，增加1，以反映添加了新元素
    10. }

    3.5 尾删(SLPopBack)

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

    1. void SLPopBack(SL* ps) {
    2.     assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    3.  
    4.     //ps->a[ps->size - 1] = 0;  //用于清除顺序表最后一个元素的数据，将其设置为 0。
    5.  
    6.     // 温和的错误处理方式: 检查顺序表是否为空，如果为空则打印信息并退出函数
    7.     /*if (ps->size == 0) {
    8.         printf("顺序表已空\n");
    9.         return;
    10.     }*/
    11.  
    12.     // 暴力的错误处理方式: 使用断言确保顺序表不为空，如果为空程序在调试模式下会中断执行
    13.     assert(ps->size > 0); // 确保顺序表中至少有一个元素，防止下溢
    14.  
    15.     // 可选的清除操作: 清除顺序表最后一个元素的数据，将其设置为 0
    16.     // ps->a[ps->size - 1] = 0;
    17.  
    18.     ps->size--; // 减少顺序表的大小，逻辑上移除最后一个元素
    19. }

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

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

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

    3.6 头插(SLPushFront)

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

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

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

    1. // 在顺序表的开始位置插入一个新元素
    2. void SLPushFront(SL* ps, SLDataType x) {
    3.     assert(ps);  // 断言，确保传入的顺序表指针非空
    4.  
    5.     SLCheckCapacity(ps);  // 检查顺序表的容量是否足够，如果不足则进行扩容
    6.  
    7.     int end = ps->size - 1;  // 计算顺序表最后一个元素的索引位置
    8.     while (end >= 0) {
    9.         ps->a[end + 1] = ps->a[end];  // 将元素向后移动一个位置
    10.         end--;  // 向前移动索引，继续移动前一个元素
    11.     }
    12.  
    13.     ps->a[0] = x;  // 在顺序表的第一个位置插入新元素
    14.     ps->size++;  // 更新顺序表的大小
    15. }

    由于头插需要移动大量元素，因此在元素较多时，头插操作的效率比较低。如果频繁进行头插操作，可能需要考虑使用其他数据结构，如链表，这样可以更高效地在头部添加元素。 

    3.7 头删(SLPopFront)

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

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

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

    1. void SLPopFront(SL* ps) {
    2.     assert(ps);  // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    3.  
    4.     assert(ps->size > 0);  // 断言，确保顺序表中有元素，避免下溢错误
    5.  
    6.     int begin = 1;  // 从顺序表的第二个元素开始
    7.     while (begin < ps->size) {
    8.         ps->a[begin - 1] = ps->a[begin];  // 将每个元素向前移动一个位置
    9.         begin++;  // 递增索引，继续处理下一个元素
    10.     }
    11.  
    12.     ps->size--;  // 减少顺序表的大小，逻辑上移除最后一个空出的位置的元素
    13. }

    3.8 在指定位置插入数据(SLInsert)

    在顺序表中在指定位置插入数据时，需要注意以下几个要点：

    1. 位置有效性：首先要确认指定的插入位置是否有效。有效位置一般是指从0到当前元素个数（n）的位置（假设数组从0开始索引），即在数组的开始位置到最后一个元素之后的直接位置。

    2. 空间容量：确保顺序表的存储空间足够，如果插入新元素导致元素总数超过当前数组容量，需要进行扩容。这通常涉及分配一个更大的数组空间，将旧数组中的数据复制到新数组中，然后再插入新元素。

    3. 数据移动：与头插类似，指定位置插入也需要移动数据。具体而言，从插入点开始的所有后续元素需要向后移动一个位置，以空出位置来插入新的元素。例如，如果在位置i插入新元素，那么原位置i及之后的所有元素都要向后移动。

    4. 更新长度：插入新元素后，需要更新顺序表的长度信息，确保它反映了当前元素的正确数量。

    5. 效率考虑：在指定位置插入的效率取决于插入位置。如果插入位置接近数组的末端，移动的元素较少，效率较高；如果插入位置接近开始位置，可能需要移动大量元素，效率较低。因此，插入操作的平均时间复杂度为O(n)，其中n为元素数量。

    6. 边界条件处理：实现时要特别注意处理边界条件，包括处理数组边界以防止索引越界，以及在数组已满时进行正确的扩容操作。

    1. // 函数定义：在顺序表ps的指定位置pos插入一个新元素x
    2. void SLInsert(SL* ps, int pos, SLDateType x)
    3. {
    4.     assert(ps); // 断言：确保传入的顺序表指针ps非空，防止空指针引用导致的程序崩溃
    5.     assert(ps->size > 0); // 断言：确保顺序表的大小至少为1，这个断言可能不总是必要，特别是如果允许在空表中插入
    6.     assert(pos <= ps->size); // 断言：确保插入位置有效，插入位置可以在数组的最后一个元素之后（即等于size）
    7.  
    8.     SLCheckCapacity(ps); // 检查顺序表的容量，如果不够则进行扩容操作，保证有空间插入新元素
    9.  
    10.     int end = ps->size - 1; // 获取顺序表中最后一个元素的位置
    11.  
    12.     // 循环移动元素，为新元素腾出位置
    13.     while (end >= pos)
    14.     {
    15.         ps->a[end + 1] = ps->a[end]; // 将元素向后移动一个位置
    16.         end--; // 更新处理的元素位置
    17.     }
    18.  
    19.     ps->a[pos] = x; // 在指定位置pos放入新元素x
    20.     ps->size++; // 更新顺序表的元素数量
    21. }

    同样也要考虑是从前往后删还是从后往前删，需要一个end下标，数据从后往前依次后挪，直到pos下标移动完毕。

    拓展：

    该功能其实也可以实现头插和尾插，所以我们可以在头插和尾插中复用该功能

    1. // 函数定义：在顺序表的开始位置进行头插操作
    2. void SeqListPushFront(SL* ps, SLDataType x)
    3. {
    4.     SeqListInsert(ps, 0, x); // 调用通用的插入函数，将新元素x插入到顺序表的第一个位置（索引0）
    5. }
    6.  
    7. // 函数定义：在顺序表的末尾进行尾插操作
    8. void SeqListPushBack(SL* ps, SLDataType x)
    9. {
    10.     SeqListInsert(ps, ps->sz, x); // 调用通用的插入函数，将新元素x插入到顺序表的末尾
    11.                                   // 这里ps->sz是当前顺序表中元素的数量，即新元素的插入位置
    12. }

    3.9 在指定位置删除数据(SLErase) 

    要实现这一功能，我们需要一个begin下标，数据从前往后依次前挪，直到sz-1下标移动完毕。

    在顺序表中删除指定位置的数据时，需要注意以下几个关键点：

    1. 位置有效性：确保指定的位置有效，即该位置索引应该在顺序表的当前元素范围内。通常，有效的索引范围是从0到当前元素个数减一（0 至 size-1）。

    2. 数据移动：删除元素后，需要将指定位置后的所有元素向前移动一个位置来填补被删除元素留下的空位。这样可以保持顺序表的连续性。

    3. 更新长度：完成删除操作后，需要更新顺序表的元素数量，即减少顺序表的size属性。

    4. 效率考虑：删除操作的效率取决于删除点的位置。如果删除位置靠近顺序表的起始位置，则需要移动更多的元素，效率较低；如果靠近末尾，则需要移动的元素较少，效率较高。因此，平均时间复杂度为O(n)，其中n为元素数量。

    5. 边界条件处理：实现时要特别注意处理边界条件，比如删除操作前顺序表是否为空，以及处理数组边界以防止索引越界。

    1. void SLErase(SL* ps, int pos)
    2. {
    3.     assert(ps); // 断言：确保顺序表的指针ps非空，防止空指针引用导致的程序崩溃
    4.     assert(pos >= 0); // 断言：确保指定的位置pos是有效的，不能是负数
    5.     assert(pos < ps->size); // 断言：确保指定的位置pos在顺序表的当前元素范围内（即小于元素数量size）
    6.     assert(ps->size > 0);  // 断言：检查顺序表的元素数量不为零，确保有元素可以删除
    7.  
    8.     int begin = pos + 1; // 设置开始移动数据的位置，从pos的下一个位置开始
    9.  
    10.     // 循环移动元素，覆盖需要删除的元素
    11.     while (begin < ps->size)
    12.     {
    13.         ps->a[begin - 1] = ps->a[begin]; // 将后续元素向前移动一位，填补被删除元素的位置
    14.         begin++; // 移动到下一个元素
    15.     }
    16.  
    17.     ps->size--; // 删除元素后，顺序表的元素总数减少1
    18. }

    同样的，该接口也可复用于头删和尾删中： 

    1. // 头删
    2. void SeqListPopFront(SL* ps)
    3. {
    4. 	SeqListErase(ps, 0);
    5. }
    6.  
    7. // 尾删
    8. void SeqListPopBack(SL* ps)
    9. {
    10. 	SeqListErase(ps, ps->sz - 1);
    11. }

    3.10 查找某一个数据的位置(SLFind) 

    在顺序表ps中查找元素x的位置

    1. int SLFind(SL* ps, SLDateType x)
    2. {
    3.     assert(ps); // 断言：确保顺序表的指针ps非空
    4.  
    5.     // 遍历顺序表中的所有元素
    6.     for (int i = 0; i < ps->size; i++)
    7.     {
    8.         if (ps->a[i] == x) // 如果当前元素等于x
    9.         {
    10.             return i; // 返回当前元素的索引
    11.         }
    12.     }
    13.  
    14.     return -1; // 如果没有找到元素x，返回-1作为失败的标志
    15. }

    3.11 查找某一个数据的起始位置(SLFinds)   

    在顺序表ps中从索引begin开始查找元素x的位置

    1. int SLFinds(SL* ps, SLDateType x, int begin)
    2. {
    3.     assert(ps); // 断言：确保顺序表的指针ps非空，防止空指针引用导致的程序崩溃
    4.  
    5.     // 从指定的开始位置begin遍历顺序表
    6.     for (int i = begin; i < ps->size; i++)
    7.     {
    8.         if (ps->a[i] == x) // 如果当前元素等于x
    9.         {
    10.             return i; // 返回当前元素的索引
    11.         }
    12.     }
    13.  
    14.     return -1; // 如果遍历完毕没有找到元素x，返回-1表示未找到
    15. }

    3.12 打印函数(SLPrint)

    在每次操作后，可以打印出顺序表，观察操作情况

    1. void SLPrint(SL *ps)  // 打印函数
    2. {
    3. 	assert(ps);
    4. 	for (int i = 0; i < ps->size; i++)
    5. 	{
    6. 		printf("%d ", ps->a[i]);
    7. 	}
    8. 	printf("\n");
    9. }

    3.13 销毁(SLDestory)

    主要目的是销毁顺序表，确保释放与顺序表关联的所有内存资源，防止内存泄漏。

    • 函数首先确认传入的顺序表指针非空，这是为了确保对有效的顺序表进行操作。
    • 如果顺序表的数组指针非空，表明数组已经分配了内存，需要通过free函数释放这部分内存。
    • 释放内存后，数组指针设置为NULL，这是一种良好的编程习惯，可以防止后续代码错误地引用已释放的内存（称为悬挂指针或野指针）。
    • 同时，顺序表的size（元素数量）和capacity（容量）被设置为0，这表明顺序表已经被完全清空并且不再占用任何资源。
    1. void SLDestory(SL* ps)
    2. {
    3.     assert(ps); // 断言：确保顺序表的指针ps非空，防止空指针引用导致的程序崩溃
    4.  
    5.     if (ps->a != NULL) // 检查顺序表的数组指针是否为非空，确保其指向有效的内存区域
    6.     {
    7.         free(ps->a); // 使用free函数释放顺序表数组所占用的内存
    8.         ps->a = NULL; // 将数组指针设置为NULL，避免产生悬挂指针
    9.  
    10.         ps->size = ps->capacity = 0; // 将顺序表的大小和容量重置为0，标记顺序表为空和无容量状态
    11.     }
    12. }

    四. 动态顺序表完整代码

     SeqList.h

    1. #pragma once    // 防止重复包含，防止头文件被重复包含多次
    2.  
    3. // 引入必要的库文件
    4. #include     // 提供动态内存分配、随机数生成等
    5. #include     // 提供字符串操作函数
    6. #include      // 提供输入输出函数
    7. #include       // 提供数学函数
    8. #include     // 提供断言函数
    9.  
    10. #define M 1000         // 预设的某些操作或容量限制的宏定义，具体用途未详细说明
    11.  
    12. // 定义数据类型和顺序表结构体
    13. typedef int SLDateType;   // 数据类型，此处定义为int，可根据实际需要调整
    14. typedef struct Seqlist {
    15. 	SLDateType* a;        // 指向动态分配数组的指针
    16. 	int size;             // 记录存储了多少个有效数据
    17. 	int capacity;         // 空间容量大小
    18. } SL;
    19.  
    20. // 动态顺序表的操作函数声明
    21. void SLInit(SL* ps);                // 初始化顺序表
    22. void SLDestory(SL* ps);             // 销毁顺序表，释放资源
    23. void SLPushBack(SL* ps, SLDateType x);  // 尾插函数，向顺序表末尾添加元素
    24. void SLPrint(SL* ps);               // 打印函数，输出顺序表内容
    25. void SLPopBack(SL* ps);             // 尾删函数，删除顺序表末尾元素
    26. void SLPushFront(SL* ps, SLDateType x); // 头插函数，向顺序表头部添加元素
    27. void SLPopFront(SL* ps);            // 头删函数，删除顺序表头部元素
    28. void SLCheckCapacity(SL* ps);       // 检查是否需要扩容，确保有足够空间添加元素
    29.  
    30. // 中间位置的插入和删除操作
    31. void SLInsert(SL* ps, int pos, SLDateType x);  // 在pos位置插入数据
    32. void SLErase(SL* ps, int pos);                 // 删除pos位置的数据
    33.  
    34. int SLFind(SL* ps, SLDateType x);              // 查找某一个数字的位置
    35. int SLFinds(SL* ps, SLDateType x, int begin);  // 从指定位置开始查找某数字的位置

    SeqList.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include "SeqList.h"
    4.  
    5. void SLInit(SL* ps)
    6. {
    7.     ps->a = NULL;
    8.     ps->size = 0;
    9.     ps->capacity = 0;
    10. }
    11.  
    12. void SLCheckCapacity(SL* ps)
    13. {
    14.     assert(ps); // 断言，确保传入的顺序表指针非空
    15.  
    16.     if (ps->size == ps->capacity)
    17.     { // 如果当前元素数量等于容量，需要扩容
    18.         int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  // 新容量计算策略：如果当前容量为0，则初始为4；否则容量翻倍
    19.  
    20.         SLDateType* temp = (SLDateType*)realloc(ps->a, newCapacity * sizeof(SLDateType)); // 尝试重新动态分配内存
    21.         if (temp == NULL)
    22.         { // 检查realloc是否成功，注意这里是比较操作，应使用两个等号==
    23.             perror("realloc failed"); // 如果内存分配失败，输出错误消息
    24.             exit(-1);  // 退出程序
    25.         }
    26.  
    27.         ps->a = temp;  // 更新顺序表的数据指针
    28.         ps->capacity = newCapacity;  // 更新顺序表的容量
    29.     }
    30. }
    31.  
    32.  
    33. void SLPushBack(SL* ps, SLDateType x) {
    34.     assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    35.  
    36.     SLCheckCapacity(ps); // 检查顺序表的容量是否足够，如果不足则进行扩容
    37.  
    38.     ps->a[ps->size] = x; // 将新元素x存放在数组的当前末尾位置，ps->size是指向下一个空闲位置的索引 //这里为什么用size而不用size-1或者别的呢，因为size的大小，就是数组最后一个数+1的下标
    39.  
    40.     ps->size++; // 更新顺序表的元素计数，增加1，以反映添加了新元素
    41. }
    42.  
    43. void SLPopBack(SL* ps) {
    44.     assert(ps); // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    45.  
    46.     //ps->a[ps->size - 1] = 0;  //用于清除顺序表最后一个元素的数据，将其设置为 0。
    47.  
    48.     // 温和的错误处理方式: 检查顺序表是否为空，如果为空则打印信息并退出函数
    49.     /*if (ps->size == 0) {
    50.         printf("顺序表已空\n");
    51.         return;
    52.     }*/
    53.  
    54.     // 暴力的错误处理方式: 使用断言确保顺序表不为空，如果为空程序在调试模式下会中断执行
    55.     assert(ps->size > 0); // 确保顺序表中至少有一个元素，防止下溢
    56.  
    57.     // 可选的清除操作: 清除顺序表最后一个元素的数据，将其设置为 0
    58.     // ps->a[ps->size - 1] = 0;
    59.  
    60.     ps->size--; // 减少顺序表的大小，逻辑上移除最后一个元素
    61. }
    62.  
    63. // 在顺序表的开始位置插入一个新元素
    64. void SLPushFront(SL* ps, SLDateType x) {
    65.     assert(ps);  // 断言，确保传入的顺序表指针非空
    66.  
    67.     SLCheckCapacity(ps);  // 检查顺序表的容量是否足够，如果不足则进行扩容
    68.  
    69.     int end = ps->size - 1;  // 计算顺序表最后一个元素的索引位置
    70.     while (end >= 0) {
    71.         ps->a[end + 1] = ps->a[end];  // 将元素向后移动一个位置
    72.         end--;  // 向前移动索引，继续移动前一个元素
    73.     }
    74.  
    75.     ps->a[0] = x;  // 在顺序表的第一个位置插入新元素
    76.     ps->size++;  // 更新顺序表的大小
    77. }
    78.  
    79. void SLPopFront(SL* ps) {
    80.     assert(ps);  // 断言，确保传入的顺序表指针非空，避免解引用空指针导致程序崩溃
    81.  
    82.     assert(ps->size > 0);  // 断言，确保顺序表中有元素，避免下溢错误
    83.  
    84.     int begin = 1;  // 从顺序表的第二个元素开始
    85.     while (begin < ps->size) {
    86.         ps->a[begin - 1] = ps->a[begin];  // 将每个元素向前移动一个位置
    87.         begin++;  // 递增索引，继续处理下一个元素
    88.     }
    89.  
    90.     ps->size--;  // 减少顺序表的大小，逻辑上移除最后一个空出的位置的元素
    91. }
    92.  
    93. void SLInsert(SL* ps, int pos, SLDateType x)
    94. {
    95.     assert(ps); // 断言：确保传入的顺序表指针ps非空，防止空指针引用导致的程序崩溃
    96.     assert(ps->size > 0); // 断言：确保顺序表的大小至少为1，这个断言可能不总是必要，特别是如果允许在空表中插入
    97.     assert(pos <= ps->size); // 断言：确保插入位置有效，插入位置可以在数组的最后一个元素之后（即等于size）
    98.  
    99.     SLCheckCapacity(ps); // 检查顺序表的容量，如果不够则进行扩容操作，保证有空间插入新元素
    100.  
    101.     int end = ps->size - 1; // 获取顺序表中最后一个元素的位置
    102.  
    103.     // 循环移动元素，为新元素腾出位置
    104.     while (end >= pos)
    105.     {
    106.         ps->a[end + 1] = ps->a[end]; // 将元素向后移动一个位置
    107.         end--; // 更新处理的元素位置
    108.     }
    109.  
    110.     ps->a[pos] = x; // 在指定位置pos放入新元素x
    111.     ps->size++; // 更新顺序表的元素数量
    112. }
    113.  
    114.  
    115. void SLErase(SL* ps, int pos)
    116. {
    117.     assert(ps); // 断言：确保顺序表的指针ps非空，防止空指针引用导致的程序崩溃
    118.     assert(pos >= 0); // 断言：确保指定的位置pos是有效的，不能是负数
    119.     assert(pos < ps->size); // 断言：确保指定的位置pos在顺序表的当前元素范围内（即小于元素数量size）
    120.     assert(ps->size > 0);  // 断言：检查顺序表的元素数量不为零，确保有元素可以删除
    121.  
    122.     int begin = pos + 1; // 设置开始移动数据的位置，从pos的下一个位置开始
    123.  
    124.     // 循环移动元素，覆盖需要删除的元素
    125.     while (begin < ps->size)
    126.     {
    127.         ps->a[begin - 1] = ps->a[begin]; // 将后续元素向前移动一位，填补被删除元素的位置
    128.         begin++; // 移动到下一个元素
    129.     }
    130.  
    131.     ps->size--; // 删除元素后，顺序表的元素总数减少1
    132. }
    133.  
    134. // 函数定义：在顺序表ps中查找元素x的位置
    135. int SLFind(SL* ps, SLDateType x)
    136. {
    137.     assert(ps); // 断言：确保顺序表的指针ps非空
    138.  
    139.     // 遍历顺序表中的所有元素
    140.     for (int i = 0; i < ps->size; i++)
    141.     {
    142.         if (ps->a[i] == x) // 如果当前元素等于x
    143.         {
    144.             return i; // 返回当前元素的索引
    145.         }
    146.     }
    147.  
    148.     return -1; // 如果没有找到元素x，返回-1作为失败的标志
    149. }
    150.  
    151.  
    152. // 函数定义：在顺序表ps中从索引begin开始查找元素x的位置
    153. int SLFinds(SL* ps, SLDateType x, int begin)
    154. {
    155.     assert(ps); // 断言：确保顺序表的指针ps非空，防止空指针引用导致的程序崩溃
    156.  
    157.     // 从指定的开始位置begin遍历顺序表
    158.     for (int i = begin; i < ps->size; i++)
    159.     {
    160.         if (ps->a[i] == x) // 如果当前元素等于x
    161.         {
    162.             return i; // 返回当前元素的索引
    163.         }
    164.     }
    165.  
    166.     return -1; // 如果遍历完毕没有找到元素x，返回-1表示未找到
    167. }
    168.  
    169. void SLPrint(SL* ps)  // 打印函数
    170. {
    171.     assert(ps);
    172.     for (int i = 0; i < ps->size; i++)
    173.     {
    174.         printf("%d ", ps->a[i]);
    175.     }
    176.     printf("\n");
    177. }
    178.  
    179. void SLDestory(SL* ps)   //销毁
    180. {
    181.     assert(ps);
    182.     if (ps->a != NULL)
    183.     {
    184.         free(ps->a);
    185.         ps->a = NULL;
    186.         ps->size = ps->capacity = 0;
    187.     }
    188. }

    test.c

    1. #include "SeqList.h" // 确保包含顺序表的头文件
    2.  
    3. // 主函数入口
    4. int main()
    5. {
    6.     // 打印欢迎信息
    7.     printf("*************  欢迎大家使用GalaxyPokemon的动态顺序表 **************\n");
    8.     int option = 0; // 用户的选项
    9.     SL s;           // 创建顺序表结构体实例
    10.     SLInit(&s);     // 初始化顺序表
    11.  
    12.     // 使用do-while循环，直到用户选择退出程序
    13.     do
    14.     {
    15.         menu(); // 显示菜单，函数未展示，需要自行实现
    16.         printf("请输入你的操作：>");
    17.         scanf("%d", &option); // 接收用户选择的操作
    18.         
    19.         // 根据用户输入执行相应的操作
    20.         switch (option)
    21.         {
    22.         case 1: // 尾插操作
    23.             printf("请依次输入你要尾插的数据：，以-1结束\n");
    24.             int sum = 0;
    25.             scanf("%d", &sum);
    26.             while (sum != -1)
    27.             {
    28.                 SLPushBack(&s, sum); // 尾插数据
    29.                 scanf("%d", &sum);
    30.             }
    31.             break;
    32.         case 2: // 尾删操作
    33.             SLPopBack(&s); // 尾删数据
    34.             break;
    35.         case 3: // 头插操作
    36.             int x = 0;
    37.             scanf("%d", &x);
    38.             SLPushFront(&s, x); // 头插数据
    39.             break;
    40.         case 4: // 头删操作
    41.             SLPopFront(&s); // 头删数据
    42.             break;
    43.         case 5: // 任意位置插入操作
    44.             SLInsert(&s, 5, 20); // 在位置5插入数据20
    45.             break;
    46.         case 6: // 任意位置删除操作
    47.             SLErase(&s, 3); // 删除位置3的数据
    48.             break;
    49.         case 7: // 查找并删除特定数据
    50.             int z = 0;
    51.             printf("请输入要删除序列的中的某个数字\n");
    52.             scanf("%d", &z);
    53.             int y = SLFind(&s, z); // 查找数据z的位置
    54.             printf("%d的位置在%d处： \n", z, y);
    55.             if (y != -1) // 如果找到，则删除
    56.             {
    57.                 SLErase(&s, y);
    58.             }
    59.             break;
    60.         case 8: // 删除顺序表中所有的某个数据
    61.             int w = 0;
    62.             printf("请输入要删除序列的中的数字\n");
    63.             scanf("%d", &w);
    64.             int pos = SLFinds(&s, w, 0); // 查找数据w的位置
    65.             while (pos != -1) // 循环删除所有w
    66.             {
    67.                 SLErase(&s, pos);
    68.                 pos = SLFinds(&s, w, pos);
    69.             }
    70.             break;
    71.         case 9: // 打印顺序表
    72.             SLPrint(&s); // 打印顺序表中的数据
    73.             break;
    74.         default: // 处理无效输入
    75.             if (option == -1)
    76.             {
    77.                 SLDestory(&s); // 销毁顺序表，释放资源
    78.                 exit(0);       // 退出程序 
    79.             }
    80.             else
    81.             {
    82.                 printf("输入错误，请重新输入\n");
    83.             }
    84.             break;
    85.         }
    86.     } while (option != -1); // 当用户输入-1时退出循环
    87.     
    88.     SLDestory(&s); // 循环结束后销毁顺序表，释放资源
    89.     return 0; // 程序正常退出
    90. }

  • 相关阅读:
    【Java练习生】每日面试题学习打卡！
    Java web应用性能分析之【自定义prometheus监控指标】
    深入理解Nginx~Nginx配置的通用语法
    mac 升级node到指定版本
    奶茶店冬天怎么提升销量 | 奶茶技术培训
    nginx配置指南
    源码编译安装LAMP
    算法萌新闯力扣：同构字符串
    【CVPR 2022】半监督目标检测：Dense Learning based Semi-Supervised Object Detection
    【Java成王之路】EE初阶第十六篇:(网络原理) 6
  • 原文地址：https://blog.csdn.net/2402_83315537/article/details/138044107