• 数据结构_顺序表_尾插、尾删、头插、头删(附带详解)

    文章目录

    前言

    顺序表_尾插、尾删、头插、头删

    一. 线性表

    二. 顺序表 - - - 数组

    2.1 什么是顺序表

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

    2.2 顺序表一般可以分为

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

    • 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
    • 所以基本使用动态顺序表，根据需要，动态的分配空间大小。
      缺陷：给小了不够用，给大了，不实用。

    2.2.2 动态顺序表：使用动态开辟的数组存储

    • 动态顺序表可根据我们的需要分配空间
    • size 表示当前顺序表中已存放的数据个数
    • capacity 表示顺序表总共能够存放的数据个数

    2.2.3 顺序表的接口实现

    先建一个工程（此次用的是vs2019)用的是动态顺序表

    • SeqList.h (顺序表的类型定义、接口函数声明、引用的头文件)
    • SeqList.h （顺序表接口函数的实现）
    • Test.c (主函数、测试顺序表各个接口功能)
    • SeqList.h 头文件代码：
    #pragma once // 防止头文件被二次引用

#include
#include //assert
#include //realloc

typedef int SLDataType; //后续要存储其他类型时方便更改
//顺序表的动态存储
typedef struct SeqList
{
    SLDataType* a;//指向动态开辟数组
    size_t size; //有效数据个数
    size_t capacity;//容量大小
}SeqList;

//初始化顺序表
void SeqListInit(SeqList* ps1);
//销毁顺序表
void SeqListDestory(SeqList* ps1);
//检查顺序表容量是否满了，好进行增容
void CheckCapacity(SeqList* ps1);
//顺序表尾插
void SeqListPushBack(SeqList* ps1, SLDataType x);//O(1)
//顺序表尾删
void SeqListPopBack(SeqList* ps1);//O(1)
//顺序表头插
void SeqListPushFront(SeqList* ps1, SLDataType x);//O(n)
//顺序表头删
void SeqListPopFront(SeqList* ps1);//O(n)
//打印顺序表
void SeqListPrint(const SeqList* ps1);
//在顺序表中查找指定的值
int SeqListFind(const SeqList* ps1, SLDataType x);
//在顺序表指定下标位置插入数据
void SeqListInsert(SeqList* ps1, size_t pos, SLDataType x);
//在顺序表中删除指定下标位置的数据
void SeqListErase(SeqList* ps1, size_t pos);
//查看顺序表中数据个数
size_t SeqListSize(const SeqList* ps1);
//修改指定下标位置的数据
void SeqListAt(SeqList* ps1, size_t pos, SLDataType x);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    三. SeqList.c 中各个接口的实现。

    3.1 初始化顺序表

    （要加上断言，防止传进来的指针为空）

    void SeqListInit(SeqList* psl)
{
    assert(psl != NULL);//断言
 

    psl->a = NULL;  //初始顺序表为空
    psl->size = 0;  //初始数据个数为0
    psl->capacity = 0;  //初始空间容量为0
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    3.2 销毁（释放）顺序表

    （也是要加上断言，防止传进来的指针为空）

    //销毁（释放）顺序表
void SeqListDestory(SeqList* ps1)
{
    assert(ps1 != NULL);//断言

    free(ps1->a); //释放动态开辟的空间
    ps1->a = NULL;//置空
    ps1->size = 0;//数据个数置零
    ps1->capacity = 0;//空间容量大小置零

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3.3 检查顺序表容量是否满了，好进行增容

    多少倍都可以，不过一般扩2倍。2倍、1.5倍、是比较合适的方案。

    void CheckCapacity(SeqList* ps1)//检查顺序表容量是否已满
{
    //满了则扩容
    if (ps1->size == ps1->capacity)
    {
        size_t Newcapacity;//新容量
        if (ps1->capacity == 0)
            Newcapacity = ps1->capacity = 4;//原来容量为零，扩容为4
        else
            Newcapacity = 2 * ps1->capacity;//原来容量不为0，扩容为原来2倍

        SLDataType* p = (SLDataType*)realloc(ps1->a, Newcapacity * sizeof(SLDataType));//扩容
        if (p == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps1->a = p;// P不为空、开辟成功
        ps1->capacity = Newcapacity;//
        //ps1->capacity *= 2;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    3.4 realloc 原地扩容、异地扩容

    异地扩容，会帮你把原数据拷贝过去，并且原空间会释放

    3.5 顺序表尾插

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    测试

    void SeqListPrint(const SeqList* ps1)
{
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        printf("%d ", ps1->a[i]);
    }
}

void TestSeqList1()
{
    SeqList s1;
    //初始化顺序表
    SeqListInit(&s1);
    //尾差数据
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPushBack(&s1, 6);
    SeqListPrint(&s1);
    SeqListDestory(&s1);

}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    3.6 顺序表尾删

    SLDataType 不知道是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的。

    void SeqListPopBack(SeqList* ps1 )
{
    assert(ps1 !=NULL);
    assert(ps1->size > 0);//顺序表不能为空

    ps1->size--; //有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    测试结果

    完整代码

    //尾删

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

void SeqListPrint(const SeqList* ps1)
{
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        printf("%d ", ps1->a[i]);
    }
    printf("\n");
}

void SeqListPopBack(SeqList* ps1 )
{
    assert(ps1 !=NULL);
    assert(ps1->size > 0);//顺序表不能为空

    ps1->size--; //有效数据个数-1
}

void TestSeqList1()
{
    SeqList s1;
    //初识化顺序表
    SeqListInit(&s1);
    //尾插数据
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);

    SeqListPrint(&s1);

    //尾删数据
    SeqListPopBack(&s1);
    SeqListPrint(&s1);
    SeqListPopBack(&s1);
    SeqListPrint(&s1);

    SeqListDestory(&s1);

}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    3.7 顺序表头插

    顺序表是连续的，所以头插时要依次挪动数据

    //头插

void SeqListPushFront(SeqList* ps1, SLDataType x)
{
    assert(ps1);
    CheckCapacity(ps1);
    int i = 0;
    for (i = ps1->size - 1; i >= 0; i--)
    {
        ps1->a[i + 1] = ps1->a[i];
    }
    ps1->a[0] = x;//头插数据
    ps1->size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    测试结果

    完整代码

    //头插

void SeqListPushFront(SeqList* ps1, SLDataType x)
{
    assert(ps1);
    CheckCapacity(ps1);
    int i = 0;
    for (i = ps1->size - 1; i >= 0; i--)
    {
        ps1->a[i + 1] = ps1->a[i];
    }
    ps1->a[0] = x;//头插数据
    ps1->size++;
}


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

void TestSeqList1()
{
    SeqList s1;
    //初始化顺序表
    SeqListInit(&s1);
    //尾插数据
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPrint(&s1);
    //头插数据
    SeqListPushFront(&s1, 11);
    SeqListPushFront(&s1, 22);
    SeqListPushFront(&s1, 33);
    SeqListPrint(&s1);

    SeqListDestory(&s1);
}

void SeqListPrint(const SeqList* ps1)
{
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        printf("%d ", ps1->a[i]);
    }
    printf("\n");
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    3.8 顺序表头删

    顺序表是连续的，头删时要依次挪动数据

    //头删
void SeqListPopFront(SeqList* psl)
{
    assert(psl);  //断言
    assert(psl->size > 0);  //顺序表不能为空

    int i = 0;
    for (i = 1; i < psl->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
    {
        psl->a[i - 1] = psl->a[i];
    }
    psl->size--;  //有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    测试结果

    完整代码

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

void SeqListPrint(const SeqList* ps1)
{
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        printf("%d ", ps1->a[i]);
    }
    printf("\n");
}
//头删
void SeqListPopFront(SeqList* psl)
{
    assert(psl);  //断言
    assert(psl->size > 0);  //顺序表不能为空

    int i = 0;
    for (i = 1; i < psl->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
    {
        psl->a[i - 1] = psl->a[i];
    }
    psl->size--;  //有效数据个数-1
}



void TestSeqList1()
{
    SeqList s1;
    //初始化顺序表
    SeqListInit(&s1);
    //尾插数据
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPrint(&s1);

    //头删数据
    SeqListPopFront(&s1);
    SeqListPopFront(&s1);
    SeqListPrint(&s1);
    
    SeqListDestory(&s1);
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    四. 打印顺序表

    五. 在顺序表中查找指定值

    int SeqListFind(const SeqList* ps1, SLDataType x)
{
    assert(ps1);
     
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        if (ps1->a[i] == x)
        {
            return i; //找到，返回该值下标
        }
    }
    return -1; //没找到
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    测试结果

    完整代码

    int SeqListFind(const SeqList* ps1, SLDataType x)
{
    assert(ps1);
     
    int i = 0;
    for (i = 0; i < ps1->size; i++)
    {
        if (ps1->a[i] == x)
        {
            return i; //找到，返回该值下标
        }
    }
    return -1; //没找到
}


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

void TestSeqList1()
{
    SeqList s1;
    //初始化顺序表
    SeqListInit(&s1);
    //尾插数据
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 5);
    SeqListPushBack(&s1, 7);
    SeqListPushBack(&s1, 9);
    //查找指定数据
    int ret = SeqListFind(&s1, 7);
    if (ret == -1)
        printf("没找到\n");
    else
        printf("x=%d\n", s1.a[ret]);
    SeqListDestory(&s1);

}


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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    六. 在顺序表指定下标位置插入数据

    void SeqListInsert(SeqList* ps1, size_t pos, SLDataType x)
{
    assert(ps1);
    assert(pos >= 0 && pos <= ps1->size);//先检查pos下标的合法性

    CheckCapacity(ps1);

    size_t i = 0;
    for (i = ps1->size; i > pos; i--)//将pos位置后面的数据依次向后挪动一位
    {
        ps1->a[i] = ps1->a[ i - 1];
    }
    ps1->a[pos] = x;
    ps1->size++;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    测试结果

    七. 在顺序表中删除指定下标位置的数据

    void SeqListErase(SeqList* psl, size_t pos)
{
    assert(psl);  
    assert(psl->size > 0);  //顺序表不能为空
    assert(pos >= 0 && pos < psl->size);  //检查pos下标的合法性

    size_t i = 0;
    for (i = pos + 1; i < psl->size; i++)  //将pos位置后面的数据依次向前挪动一位
    {
        psl->a[i - 1] = psl->a[i];
    }
    psl->size--;  //有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    测试结果

    我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1u9vtbbi0b3tm

  • 相关阅读:
    月薪2w+的测试，到底强在哪里？
    APP逆向案例之（一）过 app 更新提示
    [JVM]类加载的过程（学习总结）
    spring boot 自定义注解封装(@RequestLimit注解)
    基于X86+FPGA+AI的智能仓储AGV机器人解决方案
    寒假训练——第三周（记忆化搜索）
    蓝牙学习六（GATT）
    锐捷Ruijie交换机补丁升级及补丁卸载
    哪些人需要考PMP®证书呢?考了PMP®证书有什么用呢？
    基于ssm框架的农产品扶农商农平台的设计与实现
  • 原文地址：https://blog.csdn.net/Ghr_C99/article/details/133213316