【动态顺序表】的增删改查等方法

系列文章目录

🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
😍 👋🏼🎉🎊创作不易，欢迎大家留言、点赞加收藏！！！ 🥳😁😍

前言

各位博友，大家好！👋 今天为大家带来动态顺序表的总结🔍。
我将详细地将总结顺序表的实现步骤，助你更好地理解和运用！🚀

一、线性表

（1）线性表的定义

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

（2）线性表的分类

线性表是一种在实际中广泛使用的数据结构，
常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

（1）顺序表的定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组上完成数据的增删查改。

（2）顺序表的分类

（a）静态顺序表：使用定长数组存储元素。

（b） 动态顺序表：使用动态开辟的数组存储。

三、动态顺序表的增删查改等方法

（1）初始化顺序表

// 初始化顺序表
// 函数接收顺序表的指针 ps 作为参数，用于初始化顺序表
void InitSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 使用 calloc 分配 INIT_CAPACITY 个元素的内存空间，并初始化为 0
    SLDataType* tmp = (SLDataType*)calloc(INIT_CAPACITY, sizeof(SLDataType));

    // 如果内存分配失败
    if (tmp == NULL) 
    {
        // 打印错误信息
        perror("InitSeqList::calloc");
        return;
    }

    // 将分配的内存地址赋值给顺序表的数组指针
    ps->a = tmp;
    // 设置顺序表的容量为 INIT_CAPACITY
    ps->capacity = INIT_CAPACITY;
    // 设置顺序表的有效数据当前大小为 0，表示顺序表为空
    ps->size = 0;
}

（2）打印顺序表

// 打印顺序表
// 函数接收顺序表的指针 ps 作为参数，用于打印顺序表中的所有元素
void PrintSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 遍历顺序表中的每个元素
    for (int i = 0; i < (ps->size); i++) 
    {
        // 打印当前元素的值
        printf("%d ", ps->a[i]);
    }
    // 在打印完所有元素后换行
    printf("\n");
}

（3）检查容量是否要扩容

// 检查容量是否要扩容
// 函数接收顺序表的指针 ps 作为参数，用于检查顺序表是否需要扩容
void CheckCapacity(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 如果顺序表的当前容量等于当前大小，即没有剩余空间，需要扩容
    if (ps->capacity == ps->size) 
    {
        // 尝试将顺序表的容量扩大一倍
        SLDataType* tmp = (SLDataType*)realloc(ps->a, (ps->capacity) * 2 * sizeof(SLDataType));
        // 如果 realloc 失败，即内存分配失败
        if (tmp == NULL) 
        {
            // 打印错误信息
            perror("CheckCapacity::realloc");
            return;
        }

        // 更新顺序表的数组指针为新的内存地址
        ps->a = tmp;

        // 将顺序表的容量扩大一倍
        ps->capacity *= 2;
    }
}

（4）顺序表头插数据

// 顺序表头插
// 函数接收顺序表的指针 ps 和要插入的数据 x 作为参数，用于在顺序表头部插入一个新元素
void PushFrontSeqList(SL* ps, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 检查顺序表的容量是否需要扩容
    CheckCapacity(ps);

    // 初始化 end 为顺序表的最后一个元素的下标
    int end = ps->size - 1;
    // 从顺序表的末尾开始，将所有元素向后移动一位，为新元素腾出空间（从后往前）
    while (end >= 0) 
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }

    // 在顺序表头部（下标 0）插入新元素 x
    ps->a[0] = x;

    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

（5）顺序表头删数据

// 顺序表头删
// 函数接收顺序表的指针 ps 作为参数，用于删除顺序表的第一个元素
void PopFrontSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 初始化 start 为 1，因为要删除第一个元素，所以从第二个元素开始复制
    int start = 1;
    // 循环，将所有元素向前移动一位，覆盖第一个元素（从前往后）
    while (start < ps->size) 
    {
        // 将 start 位置的元素复制到 start - 1 的位置
        ps->a[start - 1] = ps->a[start];
        // 移动到下一个元素
        ++start;
    }

    // 删除元素后，顺序表有效数据个数的大小减一
    --(ps->size);
}

（6）顺序表尾插数据

// 顺序表尾插
// 函数接收顺序表的指针 ps 和要插入的数据 x 作为参数，用于在顺序表末尾插入一个新元素
void PushBackSeqList(SL* ps, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 检查顺序表的容量是否需要扩容
    CheckCapacity(ps);

    // 在顺序表末尾的位置插入新元素 x
    ps->a[ps->size] = x;

    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

（7）顺序表尾删数据

// 顺序表尾删数据
// 函数接收顺序表的指针 ps 作为参数，用于删除顺序表最后一个元素
void PopBackSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 顺序表有效数据个数的大小减一，实际上是移除最后一个元素
    --(ps->size);
}

（8）顺序表指定位置插入数据

// 顺序表指定位置插入数据
// 函数接收顺序表的指针 ps、要插入元素的位置 pos 和要插入的数据 x 作为参数
void InsertSeqList(SL* ps, int pos, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 断言 pos 在有效范围内，即 pos 必须在 0 到 ps->size 之间（包括 ps->size，表示插入到末尾）
    assert((pos >= 0) && (pos <= (ps->size)));

    // 检查顺序表的容量是否需要扩容
    CheckCapacity(ps);

    // 从顺序表的末尾开始
    int end = ps->size - 1;
    // 将 pos 位置及其后面的元素向后移动一位，为新元素腾出空间（从后往前）
    while (end >= pos) 
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }

    // 将新元素 x 插入到指定位置 pos
    ps->a[pos] = x;

    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

（9）顺序表指定位置删除数据

// 顺序表指定位置删除数据
// 函数接收顺序表的指针 ps 和要删除元素的位置 pos 作为参数
void EraseSeqList(SL* ps, int pos) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 断言 pos 在有效范围内，即 pos 必须在 0 到 ps->size - 1 之间
    assert((pos >= 0) && (pos < (ps->size)));

    // 从 pos 位置的下一个元素开始
    int start = pos + 1;
    // 将 pos 位置及其后面的元素向前移动一位，覆盖要删除的元素（从前往后）
    while (start < ps->size) 
    {
        ps->a[start - 1] = ps->a[start];
        ++start;
    }

    // 删除元素后，顺序表有效数据个数的大小减一
    --(ps->size);
}

（10）返回查找顺序表元素的下标

// 返回查找顺序表元素的下标
// 函数接收顺序表的指针 ps 和要查找的元素 x 作为参数
void FindSeqList(SL* ps, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 遍历顺序表中的每个元素
    for (int i = 0; i < (ps->size); ++i) 
    {
        // 如果当前元素与要查找的元素相等
        if ((ps->a[i]) == x) 
        {
            // 打印出元素 x 的下标，并结束函数
            printf("要查找 %d 的下标是 %d\n", x, i);
            return;
        }
    }
    // 如果遍历完顺序表后没有找到元素 x
    printf("顺序表中没有%d!\n", x);
}

（11）销毁顺序表

// 销毁顺序表
// 函数接收顺序表的指针 ps 作为参数
void DestorySeqList(SL* ps) 
{
    // 释放顺序表的内存空间
    free(ps->a);
    // 将指向数组的指针设置为 NULL，避免野指针
    ps->a = NULL;

    // 将顺序表的容量和大小都设置为 0，表示顺序表已被销毁
    ps->capacity = ps->size = 0;

    // 打印提示信息，顺序表已被销毁
    printf("销毁成功!\n");
}

四、完整示例代码展示

提示：
SeqList.h 头文件中存放着 相应头文件的包含、宏定义、类型声明、函数的声明等等。

SeqList.c 源文件中存放着 相应函数的定义等。

（1）SeqList.h 头文件

// 指示编译器这个头文件已经被包含过，避免重复包含
#pragma once

// 包含标准输入输出库
#include<stdio.h>
// 包含标准库，提供内存分配、释放等功能
#include<stdlib.h>
// 包含字符串操作库
#include<string.h>
// 包含断言库，用于调试
#include<assert.h>

// 定义顺序表的初始容量宏
#define INIT_CAPACITY 4

// 定义顺序表的数据类型为 int
typedef int SLDataType;

// 定义顺序表结构体
typedef struct SeqList 
{
    int size;       	// 顺序表有效数据的大小
    SLDataType* a;  	// 指向顺序表数组的指针
    int capacity; 	 	// 顺序表的容量
} SL;

// 初始化顺序表的函数声明
void InitSeqList(SL* ps);

// 销毁顺序表的函数声明
void DestorySeqList(SL* ps);

// 打印顺序表的函数声明
void PrintSeqList(SL* ps);

// 检查容量是否需要扩容的函数声明
void CheckCapacity(SL* ps);

// 头插元素的函数声明
void PushFrontSeqList(SL* ps, SLDataType x);

// 头删元素的函数声明
void PopFrontSeqList(SL* ps);

// 尾插元素的函数声明
void PushBackSeqList(SL* ps, SLDataType x);

// 尾删元素的函数声明
void PopBackSeqList(SL* ps);

// 指定位置插入元素的函数声明
void InsertSeqList(SL* ps, int pos, SLDataType x);

// 指定位置删除元素的函数声明
void EraseSeqList(SL* ps, int pos);  

// 查找元素下标的函数声明
void FindSeqList(SL* ps, SLDataType x);

（2）SeqList.c 源文件

// 定义宏，关闭 Visual Studio 中对某些函数（如 scanf, strcpy 等）的安全警告
#define _CRT_SECURE_NO_WARNINGS 1

// 包含顺序表的头文件
#include "SeqList.h"

// 初始化顺序表
// 函数接收顺序表的指针 ps 作为参数，用于初始化顺序表
void InitSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 使用 calloc 分配 INIT_CAPACITY 个元素的内存空间，并初始化为 0
    SLDataType* tmp = (SLDataType*)calloc(INIT_CAPACITY, sizeof(SLDataType));

    // 如果内存分配失败
    if (tmp == NULL) 
    {
        // 打印错误信息
        perror("InitSeqList::calloc");
        return;
    }

    // 将分配的内存地址赋值给顺序表的数组指针
    ps->a = tmp;
    // 设置顺序表的容量为 INIT_CAPACITY
    ps->capacity = INIT_CAPACITY;
    // 设置顺序表的当前大小为 0，表示顺序表为空
    ps->size = 0;
}

// 打印顺序表
// 函数接收顺序表的指针 ps 作为参数，用于打印顺序表中的所有元素
void PrintSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 遍历顺序表中的每个元素
    for (int i = 0; i < (ps->size); i++) 
    {
        // 打印当前元素的值
        printf("%d ", ps->a[i]);
    }
    // 在打印完所有元素后换行
    printf("\n");
}

// 检查容量是否要扩容
// 函数接收顺序表的指针 ps 作为参数，用于检查顺序表是否需要扩容
void CheckCapacity(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 如果顺序表的当前容量等于当前大小，即没有剩余空间，需要扩容
    if (ps->capacity == ps->size) 
    {
        // 尝试将顺序表的容量扩大一倍
        SLDataType* tmp = (SLDataType*)realloc(ps->a, (ps->capacity) * 2 * sizeof(SLDataType));
        // 如果 realloc 失败，即内存分配失败
        if (tmp == NULL) 
        {
            // 打印错误信息
            perror("CheckCapacity::realloc");
            return;
        }

        // 更新顺序表的数组指针为新的内存地址
        ps->a = tmp;

        // 将顺序表的容量扩大一倍
        ps->capacity *= 2;
    }
}

// 顺序表头插
// 函数接收顺序表的指针 ps 和要插入的数据 x 作为参数，用于在顺序表头部插入一个新元素
void PushFrontSeqList(SL* ps, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 检查容量是否要扩容
    CheckCapacity(ps);

    // 从顺序表的末尾开始，将所有元素向后移动一位，为新元素腾出空间
    int end = ps->size - 1;
    while (end >= 0) 
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }

    // 在顺序表头部（下标 0 的位置）插入新元素 x
    ps->a[0] = x;

    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

// 顺序表头删
// 函数接收顺序表的指针 ps 作为参数，用于删除顺序表的第一个元素
void PopFrontSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 将所有元素向前移动一位，覆盖第一个元素
    int start = 1;
    while (start < ps->size) 
    {
        ps->a[start - 1] = ps->a[start];
        ++start;
    }

    // 删除元素后，顺序表有效数据个数的大小减一
    --(ps->size);
}

// 顺序表尾插
// 函数接收顺序表的指针 ps 和要插入的数据 x 作为参数，用于在顺序表末尾插入一个新元素
void PushBackSeqList(SL* ps, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 检查容量是否要扩容
    CheckCapacity(ps);

    // 在顺序表末尾的位置插入新元素 x
    ps->a[ps->size] = x;
    
    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

// 顺序表尾删数据
// 函数接收顺序表的指针 ps 作为参数，用于删除顺序表的最后一个元素
void PopBackSeqList(SL* ps) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);

    // 减少顺序表有效数据的大小，实际上是移除最后一个元素
    --(ps->size);
}

// 顺序表指定位置插入数据
// 函数接收顺序表的指针 ps、要插入元素的位置 pos 和要插入的数据 x 作为参数
void InsertSeqList(SL* ps, int pos, SLDataType x) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 断言 pos 在有效范围内，即 pos 必须在 0 到 ps->size 之间（包括 ps->size，表示插入到末尾）
    assert((pos >= 0) && (pos <= (ps->size)));

    // 检查容量是否要扩容
    CheckCapacity(ps);

    // 从顺序表的末尾开始，将 pos 位置及其后面的元素向后移动一位，为新元素腾出空间
    int end = ps->size - 1;
    while (end >= pos) 
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }

    // 将新元素 x 插入到指定位置 pos
    ps->a[pos] = x;

    // 插入元素后，顺序表有效数据个数的大小加一
    ++(ps->size);
}

// 顺序表指定位置删除数据
// 函数接收顺序表的指针 ps 和要删除元素的位置 pos 作为参数
void EraseSeqList(SL* ps, int pos) 
{
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 断言 pos 在有效范围内，即 pos 必须在 0 到 ps->size - 1 之间
    assert((pos >= 0) && (pos < (ps->size)));

    // 将 pos 位置及其后面的元素向前移动一位，覆盖要删除的元素
    int start = pos + 1;
    while (start < ps->size) 
    {
        ps->a[start - 1] = ps->a[start];
        ++start;
    }

    // 删除元素后，顺序表有效数据个数的大小减一
    --(ps->size);
}

// 返回查找顺序表元素的下标
// 函数接收顺序表的指针 ps 和要查找的元素 x 作为参数
void FindSeqList(SL* ps, SLDataType x) {
    // 断言 ps 不为空，如果为空则触发错误
    assert(ps);
    // 遍历顺序表中的每个元素
    for (int i = 0; i < (ps->size); ++i) 
    {
        // 如果当前元素与要查找的元素相等
        if ((ps->a[i]) == x) 
        {
            // 打印出元素 x 的下标，并结束函数
            printf("要查找 %d 的下标是 %d\n", x, i);
            return;
        }
    }
    // 如果遍历完顺序表后没有找到元素 x
    printf("顺序表中没有%d!\n", x);
}

// 销毁顺序表
// 函数接收顺序表的指针 ps 作为参数，用于释放顺序表占用的内存
void DestorySeqList(SL* ps) 
{
    // 释放顺序表的内存空间
    free(ps->a);
    // 将指向数组的指针设置为 NULL，避免野指针
    ps->a = NULL;

    // 将顺序表的容量和大小都设置为 0，表示顺序表已被销毁
    ps->capacity = ps->size = 0;
    
    // 打印提示信息，顺序表已被销毁
    printf("销毁成功!\n");
}

END

每天都在学习的路上！
On The Way Of Learning