探索数据结构：深入了解顺序表的奥秘

✨✨ ���迎大家来到贝蒂大讲堂✨✨

养成好习惯，先赞后看哦~

所属专栏：数据结构与算法

贝蒂的主页：Betty’s blog

1. 什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，它与数组非常类似，但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小

2. 顺序表的功能

顺序表可以大致包含以下几个功能：

1. 初始化顺序表中的数据。

2. 打印顺序表中的数据。

3. 对顺序表进行尾插(末尾插入数据)。

4. 对顺序表进行尾删(末尾删除数据)。

5. 对顺序表进行头插(开头插入数据)。

6. 对顺序表进行头删(开头删除数据)。

7. 对顺序表就像查找数据。

8. 对顺序表数据进行修改。

9. 任意位置的删除和插入数据。

10. 销毁顺序表。

3. 顺序表的定义

定义顺序表我们首先需要一个动态内存开辟的空间，当前数据的个数(size)，以及方便扩容的容量大小(capacity)。

typedef int SLDataType; //类型重命名，方便后续修改类型#define N 4 //初始化空间大小typedef struct SeqList{SLDataType* a;    //指向动态开辟的数组size_t size;      //有效数据个数size_t capacity;  //容量大小}SeqList;

4. 功能的具体实现

4.1 初始化顺序表

(1) 代码实现

初始化顺序表时我们可以先开辟四个空间，之后不够再进行扩容。

void SeqListInit(SeqList* p){assert(p);  //断言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间if (p == NULL){perror("malloc fail:");                return ;}p->size = 0;  //初始数据个数为0p->capacity = 4;  //初始空间容量为4}

(2) 复杂度分析

• 时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
• 空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。

  4.2 打印数据

  (1) 代码实现

  打印数据只用循环打印就可以了。

  void SeqListPrint(const SeqList* p){assert(p);  //断言if (p->size == 0)  //判断顺序表是否为空{printf("顺序表为空\n");return;}int i = 0;for (i = 0; i size; i++)  //打印顺序表{printf("%d ", p->a[i]);}printf("\n");}

  (2) 复杂度分析

  • 时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
  • 空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(1)。

    4.3 尾插数据

    尾插数据，顾名思义就是在顺序表末尾插入数据，在插入数据之前我们应该检查顺序表是否为满。

    (1) 检查是否已满

    void CheckCapacity(SeqList* p){assert(p);  //断言if (p->size == p->capacity)  //检查容量，满了则增容{size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容if (prt == NULL){perror("realloc fail:");return ;}p->a = prt;  // prt不为空，开辟成功p->capacity = newcapacity;  //更新容量}}

    (2) 插入数据

    void SeqListPushBack(SeqList* p, SLDataType x){assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满p->a[p->size] = x;  //尾插数据p->size++;  //有效数据个数+1}

    (3) 复杂度分析

    • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
    • 空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。

      4.4 尾删数据

      同理，尾删数据就是删除顺序表中最后一个元素，我们只需将size–。注意：删除之前要保证顺序表中有数据。

      (1) 代码实现

      void SeqListPopBack(SeqList* p){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空p->size--;  //有效数据个数-1}

      (2) 复杂度分析

      • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
      • 空间复杂度：没有变量影响空间，空间复杂度为O(1)。

        4.5 头插数据

        头部插入数据就是在第一个元素位置插入一个元素。

        (1) 代码实现

        void SeqListPushFront(SeqList* p, SLDataType x){assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满int i = 0;for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //头插数据p->size++;  //有效数据个数+1}

        (2) 复杂度分析

        • 时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
        • 空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。

          4.5 头删数据

          从头部删除数据，与尾部删除数据不同，需要依次往前覆盖。

          (1) 代码实现

          void SeqListPopFront(SeqList* p){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空int i = 0;for (i = 1; i size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1}

          (2) 复杂度分析

          • 时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
          • 空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。

            4.6 查找指定值

            根据输入参数，在顺序表中查找指定的值并返回其下标，若未找到则返回-1。

            (1) 代码实现

            int SeqListFind(const SeqList* p, SLDataType x){assert(p);  //断言int i = 0;for (i = 0; i size; i++){if (p->a[i] == x){return i;  //查找到，返回该值在数组中的下标}}return -1;  //没有查找到}

            (2) 复杂度分析

            • 时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
            • 空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。

              4.7 指定位置修改

              我们可以通过指定下标或者查找指定值的下标来修改任意位置的值。

              (1) 代码实现

              void SeqListModify(SeqList* p, int pos, SLDataType x){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos size);  //检查pos下标的合法性p->a[pos] = x;  //修改pos下标处对应的数据}

              (2) 复杂度分析

              • 时间复杂度：因为是通过指定下标修改，所以时间复杂度为O(1)。
              • 空间复杂度：没有开辟额外的空间，所以空间复杂度为O(1)。

                4.8 指定位置插入

                和前面其他插入一样，指定位置插入也需要判断是否扩容。

                (1) 代码实现

                void SeqListInsert(SeqList* p, int pos, SLDataType x){assert(p);//断言assert(pos size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆盖--cur;}p->a[pos] = x;p->size++;}

                (2) 复杂度分析

                • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
                • 空间复杂度：可能需要扩容，空间复杂度为O(N)。

                  4.9 指定位置删除

                  和前面的删除差不多，但是指定删除可能会依次覆盖。

                  (1) 代码实现

                  void SeqListErase(SeqList* p, int pos){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos size);  //检查pos下标的合法性int i = 0;for (i = pos + 1; i size; i++)  //将pos位置后面的数据依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1}

                  (2) 复杂度分析

                  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
                  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

                    4.10 回收空间

                    在结束操作之后，需要释放开辟的空间，以防止内存泄漏。

                    (1) 代码实现

                    void SeqListDestory(SeqList* p){assert(p);  //断言free(p->a);   //释放动态开辟的空间p->a = NULL;  //置空p->size = 0;  //数据个数置0p->capacity = 0;  //空间容量大小置0}

                    (2) 复杂度分析

                    • 时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
                    • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

                      5. 完整代码

                      5.1 SeqList.h

                      #include#include#include#define N 4 //初始化空间大小typedef int SLDataType; //类型重命名，方便后续修改类型typedef struct SeqList{SLDataType* a;    //指向动态开辟的数组size_t size;      //有效数据个数size_t capacity;  //容量大小}SeqList;void SeqListInit(SeqList* p);//初始化顺序表void SeqListPrint(const SeqList* p);//打印顺序表void SeqListPushBack(SeqList* p, SLDataType x);//尾插void SeqListPopBack(SeqList* p);//尾删void SeqListPushFront(SeqList* p, SLDataType x);//头插void SeqListPopFront(SeqList* p);//头删int SeqListFind(const SeqList* p, SLDataType x);//查找数据void SeqListModify(SeqList* p, int pos, SLDataType x);//修改数据void SeqListInsert(SeqList* p, int pos, SLDataType x);//指定插入void SeqListErase(SeqList* p, int pos);//指定删除void SeqListDestory(SeqList* p);//释放空间

                      5.2 SeqList.c

                      #define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"void SeqListInit(SeqList* p){assert(p);  //断言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间if (p == NULL){perror("malloc fail:");return ;}p->size = 0;  //初始数据个数为0p->capacity = 4;  //初始空间容量为4}void CheckCapacity(SeqList* p){assert(p);  //断言if (p->size == p->capacity)  //检查容量，满了则增容{size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容if (prt == NULL){perror("realloc");return ;}p->a = prt;  // prt不为空，开辟成功p->capacity = newcapacity;  //更新容量}}void SeqListPushBack(SeqList* p, SLDataType x){assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满p->a[p->size] = x;  //尾插数据p->size++;  //有效数据个数+1}void SeqListPrint(const SeqList* p){assert(p);  //断言if (p->size == 0)  //判断顺序表是否为空{printf("顺序表为空\n");return;}int i = 0;for (i = 0; i size; i++)  //打印顺序表{printf("%d ", p->a[i]);}printf("\n");}void SeqListPopBack(SeqList* p){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空p->size--;  //有效数据个数-1}void SeqListPushFront(SeqList* p, SLDataType x){assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满int i = 0;for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //头插数据p->size++;  //有效数据个数+1}void SeqListPopFront(SeqList* p){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空int i = 0;for (i = 1; i size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1}int SeqListFind(const SeqList* p, SLDataType x){assert(p);  //断言int i = 0;for (i = 0; i size; i++){if (p->a[i] == x){return i;  //查找到，返回该值在数组中的下标}}return -1;  //没有查找到}void SeqListModify(SeqList* p, int pos, SLDataType x){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos size);  //检查pos下标的合法性p->a[pos] = x;  //修改pos下标处对应的数据}void SeqListInsert(SeqList* p, int pos, SLDataType x){assert(p);//断言assert(pos size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆盖--cur;}p->a[pos] = x;p->size++;}void SeqListErase(SeqList* p, int pos){assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos size);  //检查pos下标的合法性int i = 0;for (i = pos + 1; i size; i++)  //将pos位置后面的数据依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1}void SeqListDestory(SeqList* p){assert(p);  //断言free(p->a);   //释放动态开辟的空间p->a = NULL;  //置空p->size = 0;  //数据个数置0p->capacity = 0;  //空间容量大小置0}