顺序表基础概念、C 语言实现与典型算法解析

顺序表基础概念、C 语言实现与典型算法解析

本文详细介绍了线性表中的顺序表的概念以及其接口如增删查找等关键操作，最后通过算法题来感受顺序表的细节。

一、线性表是什么？

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

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

上面是书本的定义，可以这样理解逻辑结构和线性结构，举个例子：夏天喝奶茶去排队，我们把队伍看成'1'字形，也就是线性的，这里是人为抽象理解为是从第一个人到最后一个人一一对齐，也就是在逻辑结构上一定是线性的，而物理结构上，也就是在事实情况下，排队大概率是东边一个人，西边一个人，不是'1'字形，也就不连续（不是线性的），所以在物理结构上不连续。但也有素质高的队伍，完全成'1'字形，也就是说明线性表在物理结构上可能线性也可能不是线性的，但是在逻辑结果（也就是人为想象下）一定是线性的。

二、顺序表的概念及分类

1. 概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（在逻辑结构和物理结构上均是线性的），一般情况下采用数组存储。在数组上完成数据的增删查改。这里可以参照上面线性表我的理解，逻辑结构一定是线性的，物理结构上是数组，也是连续的。

顺序表的本质就是数组

2. 分类

1. 静态顺序表

定义：使用定长数组存储元素。

//宏定义常量
#define N 7
//类型别名声明，方便后续代码维护
typedef int SLDataType;
typedef struct SeqList {
    SLDataType a[N]; //定长数组
    int size;        //有效数据个数
}SeqList;

2. 动态顺序表

定义：使用动态开辟的数组存储。

typedef int SLDataType;
typedef struct Seqlist {
    SLDataType* array; //指向动态开辟的数组
    int size;          //有效数据个数
    int capacity;      //容量空间大小
}SL;

这里顺序表绝大部分情况使用的是动态顺序表，因为静态顺序表如果空间给少了不够用，给多了会造成空间浪费。动态顺序表可以根据需要的多少来进行 realloc 来进行扩容，调整顺序表的大小。

三、动态顺序表的实现

1. 顺序表的初始化

//顺序表的初始化
void SLInit(SL* ps) {
    ps->arr = NULL; //顺序表初始化为空
    ps->size = ps->capacity = 0; //有效数据个数和空间容量均置为 0
}

2. 顺序表的扩容

在进行扩容前首先我们要分析下两种情况：1. capacity 和 size 均为空；2. capacity 和 size 不为空。

在扩容的时候我们要判断在顺序表中它存储的元素和它的空间容量是否相等，如果相等的话，那么我们再想继续存储元素就需要扩容。

（1）使用 if 语句判断 capacity 和 size 是否相等。 （2）使用三目操作符来对判断，情况 1：给 capacity 开辟 4 个容量，情况 2：capacity 扩大两倍。 （3）为了防止 realloc 增容失败，导致原有数据缺失，所以选择临时变量 temp 来存放 realloc。 （4）使用 if 语句判断如果 temp 为 NULL 则扩容失败直接退出程序即可。 （5）代码走到这里，即可证明扩容成功，并把扩容的大小赋值给 capacity。

小细节 1：扩容这里我们选择 realloc 进行扩容而不使用 malloc 扩容原因是：realloc 可以调整已分配内存块的大小，并尽可能在原地完成扩容，时间复杂度为 O(1)，malloc 需要手动实现，时间复杂度为 O(n)。

小细节 2：这里扩容为什么选择 2 倍扩容而不是其他，大家可以想一下，百度上也有相关证明哦！！！

代码如下：

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        //capacity 可能初始为 0，所以要把他存放到临时的 newcapacity 中
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        //如果 realloc 扩容失败，则返回 null，如果直接赋值给 arr，则会丢失之前存储的数据，所以用临时变量来存储
        SLDataType* temp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        if (temp == NULL) {
            perror("realloc fail!");
            exit(1); //直接退出程序
        }
        ps->arr = temp;
        ps->capacity = newcapacity;
    }
}

3. 顺序的尾插

在进行尾插前需要断言，防止顺序表传入空指针，如若是空指针则不能对其解引用，下图中共有五个数字，size 为 5，a[5] 对应的是原本顺序表最后一个元素的下一个位置，所以尾插后的数据 x 应存放在 a[5] 中，最后存放完 x 后不能忘记把 size++。

//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

4. 顺序表的头插

这里和尾插一样，都需要断言，后面的实现方法就不解释了，原因是一样的。思路：在头插前，我们显而易见需要把原本顺序表中的所有元素往后移动，假设我们从 0 这个数字开始往后移动，会把后面数字 1 给覆盖掉，所以从前往后移动是不行的，需要从后把最后一个数字 4 移动到空白位置 a[5], 3 移动到 a[4] 位置，然后前面的数字依次这样移动。

上面的移动方法我们通过使用 for 循环来实现，原顺序表中所有元素均移动完成后，将新的数据存放到已经空出来的 a[0] 位置，则实现了顺序表的头插。

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    //先让顺序表已有的数据往后移动
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

5. 尾删

这里除了要断言 ps 还要断言 ps->size 不能为空，因为如果链表为空不能尾删。断言完后尾删完要让 size--。

//尾删
void SLPopBack(SL* ps) {
    assert(ps);
    assert(ps->size);
    --ps->size;
}

6. 头删

头删如下图，删除 a[0] 位置的元素 0，则后面的 1-4 均要向前移动，这里我们要使用 for 循环从头遍历，让 a[i+1] 的数据赋值给 a[i]，这里要注意 for 循环的结束条件为 size-1，最后别忘了让 size--啦。

//头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

7. 在指定位置之前插入数据

插入数据前，要让 pos 及其后面位置的数据往后移动，在这里通过从后往前遍历，把 pos 位置空出来，然后在 pos 位置插入数据，最后别忘让 size++啦。

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    //插入数据要判断空间是否够
    SLCheckCapacity(ps);
    //让 pos 及之后的数据往后移动
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

8. 删除指定位置的数据

这里除了断言顺序表存在和存储的数据不为 0 以外，还要确保删除的位置大于 0 并且不能等于 size，因为这两种情况数据均不存在，因此需要再次断言。之后使用 for 循环让 pos 及其之后数据均往前移动。

void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(ps->size);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

9. 查找

这个方法就很 easy 啦，使用 for 循环遍历判断存储数据是否等于 x，如果找到就返回。

//顺序表的查找
int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            //找到了
            return i;
        }
    }
    return -1;
}

10. 销毁顺序表

之前动态申请的内存当然需要释放啦，防止内存泄漏，释放之后，还要将指针置为 NULL 避免出现野指针，避免后续代码误操作已释放的内存。同时将 size 和 capacity 置零，使顺序表恢复到初始空状态，确保状态一致性。

void SLDestroy(SL* ps) {
    if (ps->arr) {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

四、完整代码

以下代码非唯一，仅供参考。

SeqList.h

头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;

typedef struct Seqlist {
    SLDataType* arr;
    int size;
    int capacity;
}SL;

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType X);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//顺序表的查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"

//顺序表的初始化
void SLInit(SL* ps) {
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

void SLDestroy(SL* ps) {
    if (ps->arr) {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        //capacity 可能初始为 0，所以要把他存放到临时的 newcapacity 中
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        //如果 realloc 扩容失败，则返回 null，如果直接赋值给 arr，则会丢失之前存储的数据，所以用临时变量来存储
        SLDataType* temp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        if (temp == NULL) {
            perror("realloc fail!");
            exit(1); //直接退出程序
        }
        ps->arr = temp;
        ps->capacity = newcapacity;
    }
}

//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    //先让顺序表已有的数据往后移动
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

//尾删
void SLPopBack(SL* ps) {
    assert(ps);
    assert(ps->size);
    --ps->size;
}

//头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    //插入数据要判断空间是否够
    SLCheckCapacity(ps);
    //让 pos 及之后的数据往后移动
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

//删除指定位置的顺序
void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(ps->size);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

//顺序表的查找
int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            //找到了
            return i;
        }
    }
    return -1;
}

test.c

测试代码

#include"SeqList.h"

void test() {
    SL s;
    SLInit(&s);
    SLPushBack(&s, 1);
    SLPushBack(&s, 2);
    SLPushBack(&s, 3);
    SLPushBack(&s, 4);
    
    int find = SLFind(&s, 2);
    if (find < 0) {
        printf("所查找的数据不存在！\n");
    } else {
        printf("所查找的数据存在，该数据所在位置下标为%d\n", find);
    }
    
    SLInsert(&s, find, 100);
    SLErase(&s, find);
}

int main() {
    test();
    return 0;
}

五、算法的暴力美学

1. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/description/

题目解释：

将数组中存储的数据等于 val 的数据移除，最后返回新数组的长度。

思路 1：创立新数组

重新定义一个新的数组，遍历原数组，把值不等于 val 存放在新数组中。如下图中，我们要把值等于 3 的数据移除，则我们遍历 nums 数组，如果 i 不等于 3，则存放到新数组 tmp[] 中，最后返回数组长度 2。

思路 2：双指针法

顾名思义双指针法就是定义两个指针，这里我们定义 src（源数据）和 dst（目标数据）两个指针初始状态下都指向数组的第一个位置。

• （1）若 src 指向的值为 val，src++，dst 不动
• （2）若 src 指向的值不是 val，nums[dst]=nums[src], src++, dst++
• (3) 当 src 等于数组长度的时候跳出循环，dst 的值便是数组长度

代码实现

int removeElement(int* nums, int numsSize, int val) {
    //思路：双指针：创建两个变量指向数组的起始位置
    //nums[src]==val; src++
    //nums[src]!=val, 赋值给 dst，src 和 dst 都++
    int dst = 0, src = 0;
    while (src < numsSize) {
        if (nums[src] != val) {
            nums[dst++] = nums[src];
        }
        src++;
    }
    //此时 dst 的值刚好就是新数组的有效长度
    return dst;
}

2. 合并两个有序数组

题目链接：https://leetcode.cn/problems/merge-sorted-array/

题目解释：

给了两个数组 nums1 和 nums2（均递增），需求是把 nums2 的数据全部存放到 num1 中（num1 数组容量正好可以存放下 nums1 和 nums2 的所有元素）并且顺序为升序，题目提到不能开辟新的数组。

思路 1：

放到 nums1 数组的后面中，再使用冒泡排序算法对 nums1 进行升序，但是冒泡排序的时间复杂度为 O(n^2),不推荐。

思路 2：

定义三个个指针 l1（指向 nums1 的最后一个有效数据），l2（指向 nums2 的最后一个有效数据），l3（指向 nums1 的最后位置）。

从后往前比较大小：比谁大，谁大谁往后放。在图中是比较 l1 和 l2 指向的数据谁大，l2 大，则把 l2 的数据 6 给 l3，然后 l2--, l3--，按照这个规律进行下去，直到 l1 或者 l2 中某一个指针出了数组（ji 小于 0），跳出循环。

比较完的图如下：发现 nums2 中还有数据未放到 nums1 中，所以需要循环 nums2 中剩余的数据放到 l3 中。

代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    //从后往前找：比谁大，谁大谁往后放
    int l1 = m - 1; //放在第一个数组最后一个有效元素对应的下标
    int l2 = n - 1; //放在第二个数组最后一个有效元素对应的下标
    int l3 = m + n - 1; //放在第一个数组下标为第一个数组加第二个数组有效元素的下标处
    
    //比较 l1 和 l2 对应元素的大小，谁大,l3 放谁，然后 l3 和大的元素对应的下标--
    while (l1 >= 0 && l2 >= 0) //只要有一个为假就跳出循环
    {
        if (nums1[l1] > nums2[l2]) {
            nums1[l3--] = nums1[l1--];
        } else {
            nums1[l3--] = nums2[l2--];
        }
    }
    //l1 已经越界，nums2 中还有数据没有放到 nums1 中
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
}

这里不存在 l1 和 l2 都越界的情况，假设 nums1 中 l1 和 nums2 中 l2 存放的数据一样，让其中任意一个为大即可。 大家可能纠结可不可以从前往后比较大小呢？答案是否定的，因为从前往后比较会把原本数据覆盖，这里就不再详细介绍，大家可以画图来判断下。

总结

顺序表的问题

1. 中间/头部的插入效率低下，时间复杂度为 O(n)
2. realloc 增容效率低下，要申请新空间，拷贝数据，释放旧空间
3. 增容以二倍扩大造成空间浪费 思考：有没有一种新的数据结构可以解决以上问题呢？敬请期待下节分解…