• 数据结构之手撕顺序表(讲解➕源代码)


    0.引言

            在本章之后,就要求大家对于指针、结构体、动态开辟等相关的知识要熟练的掌握,如果有小伙伴对上面相关的知识还不是很清晰,要先弄明白再过来接着学习哦!

            那进入正题,在讲解顺序表之前,我们先来介绍线性表这个数据结构。

    0.1 线性表

            线性表是 n个具有相同特性的数据元素组成的有限的序列。
            并且在逻辑上是一对一的,一个接着一个的。比如我们之前学过的数组,字符串等。

            相同特性:同一种数据类型
            有限:数据元素的个数是有限的

            常见的线性表:顺序表、链表、栈、队列、字符串等。

            我们在讲解数据结构的时候通常要先看它的逻辑结构和物理结构。

    0.2 线性表的逻辑结构和物理结构

    0.2.1 逻辑结构

            线性表的逻辑结构是线性结构,线性结构 是一条连续的直线,也就是说 线性表在逻辑上是连续的,比如我们在C语言学过的的数组(顺序表),指针(可以构成链表)。

            上图分别为顺序表链表,他们在逻辑结构上都是一个接着一个,连续的。但是在物理结构他们还依旧连续吗?让我们带着疑问往下走。

    0.2.2 线性表的物理结构

            明确告诉大家,线性表在物理结构上不一定连续,因为我们可以构成线性表的结构有数组和指针,指针又被称作链式结构。

    那什么时候是连续的?

    当线性表是由数组构成时:物理结构连续

            线性表的物理结构一定连续,因为数组是一个一个挨着的空间,地址上是紧挨着的,所以是连续的。

    如图:

    什么时候又不是连续的呢?​​​​​​​

    当线性表为链式结构时:物理结构不连续

             首先链式结构在逻辑上一定是连续的,因为我们可以通过指针就找到该指针对应的地址。
            但指针的地址不一定是连续的,我们可以这存一个,那存一个,通过指针给他们链接起来。

    如图:

            当了解了线性表的物理结构和逻辑结构之后,就让我们一起学习第一种数据结构---顺序表吧!

    1. 顺序表

    1.1概念

            顺序表是 用一段物理地址连续的存储单元依次存储数据元素的线性结构,通常采用数组的形式存储。在数组上完成数据的增删查改。
            这是什么意思呢?首先顺序表是物理地址连续的,那物理地址连续,就应该是用数组的形式来存储,之后根据数组的性质进行数据的增加,删除,查找和更改。

            我们知道顺序表是由什么构成之后,让我们看看顺序表都分为哪几种吧!

    1.2 顺序表的分类

            我们顺序表只分为静态顺序表和动态顺序表两种,下面我们会给大家展示这两种顺序表。

    1.2.1 静态顺序表

            静态顺序表指的是利用定长数组来存储元素

    1. //顺序表的静态存储
    2. #define N 7 //顺序表一次开辟的空间个数
    3. typedef int SLDataType; //将数据类型重命名,以便我们未来换用其他的数据类型
    4. typedef struct SeqList
    5. {
    6. SLDataType arr[N]; //定长数组
    7. size_t size; //有效的数据个数,size_t指的是无符号整型
    8. }Seqlist;

            我们在使用静态顺序表的时候,只能每次开辟N个大小的空间,这也就要求我们在使用之前就要想好你要存放多少个数据,非常不灵活,没有办法做到你想插入几个数据的时候就插入几个数据,所以我们大多时候不使用静态顺序表,而是改用动态顺序表作为我们日常应用。

    这也是我们常说的要适应大环境的需要,而不是一味不变。

    1.2.2 动态顺序表

            动态顺序表:使用动态开辟的数组存储。在这里需要大家对动态开辟内存知识有一定的掌握。

    1. 动态顺序表的定义

    我们首先要明确自己需要什么

    1.动态开辟的数组

    2.有效的数据个数(你存入的数据个数)

    3.数组的容量(开辟的空间大小)

            这三个数据是绑定一起的吧!因为你有数组,你才可以存入元素,你存入元素,你的有效的数据个数才会增加,而在你存入元素之前,你必须开辟空间,给数组一定的容量。

            所以我们在这里用了结构体包含三者,目的就是能让他们三个绑定,便于大家完成代码。

            未来大家如果要创造更多的关系数据(具有关系的数据),强烈推荐使用结构体来给它们打包。

    1. typedef int SLDataType; //数据类型的重命名,方便更改数据类型
    2. typedef struct SeqList
    3. {
    4. SLDataType *a; //指向动态开辟的数组
    5. int size; //有效的数据个数
    6. int capacity; //动态开辟的数组的容量
    7. }SL;
    2.初始化

            在初始化这里,我们要给数组开辟一定的空间,方便在插入数据的时候进行操作,但是在这里,我们只是开辟空间,并没有给数组插入元素,所以我们的有效元素个数size就是0,容量就是你开辟的空间个数。

            我们一般开辟空间第一次给4个数据类型的空间。但是这个没有定性要求(固定的要求)你想开辟几个就开辟几个。

    1. void SLInit(SL*ps) //初始化
    2. {
    3. ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
    4. if(ps->a == NULL)
    5. {
    6. perror("malloc");
    7. exit(EXIT_FAILURE);
    8. }
    9. ps ->size = 0;
    10. ps ->capacity = 4;
    11. }
    3.退出程序时的销毁

    注意⚠️⚠️⚠️⚠️⚠️⚠️

            这个函数有讲头了,我们要记住一点,凡是通过动态开辟的空间,一定要进行销毁释放,因为由malloc,realloc等开辟的空间是在堆上开辟的,无法自动释放掉。我们没有这个函数,那么就会造成内存的泄漏。

            那么如何释放呢?

            free函数来释放开辟的空间,谁被开辟free谁,之后要将free的对象置为空就OK啦!不要忘了你释放空间之后,有效的数据元素是0了哈,容量也是0.

    1. void SLDestroy(SL*ps) //退出时销毁
    2. {
    3. free(ps->a);
    4. ps->a = NULL;
    5. ps->size = 0;
    6. ps->capacity = 0;
    7. }
    4.扩容

            这个函数是解决当你第一次开辟的空间不够的问题,就要用到这个函数来进行扩容,扩容一般是扩原来空间的二倍这么大。

            那扩容的条件是什么呢?

            就是当我们插入的  有效元素的个数size = 容量capacity  的时候,完成扩容之后一定要判断你扩容是否成功了,如果 tmp🟰NULL,那就说明开辟空间失败,用perror函数告诉你哪里失败了,之后用exit函数退出程序,exit函数是直接强制退出,不回到主函数,跟return不一样。当开辟成功了,就让a指向这段空间就OK,再更新一下capacity;

    1. void SLCheckCapacity(SL*ps) //扩容函数
    2. {
    3. if(ps->size == ps->capacity)
    4. {
    5. SLDataType *tmp = (SLDataType*)realloc(ps->a,((sizeof(SLDataType)) * ((ps->capacity) * 2)));
    6. if(tmp == NULL)
    7. {
    8. perror("realloc");
    9. exit(EXIT_FAILURE);
    10. }
    11. ps -> a = tmp;
    12. ps->capacity *= 2;
    13. }
    14. }
    6.尾插尾删
            顺序表的尾插:

            在尾插的时候,我们要判断是否插满了,就需要用到我们的扩容函数来判断一下,没满就直接插入,满了则扩容。

    如图:这就是没有插满的情况,我们目前已经插入了5个元素,ps->size=5,我们再插入一个元素的时候就可以在下标为size这里插入了,之后再size++就可以了

    如图:是插满的情况,我们就要先扩容

    如图:扩容之后,这个时候我们就可以插入啦!

            顺序表的尾删:

            尾删就好写多了,我们只需要将size减1即可,因为size代表有效的元素个数,将元素个数减一,就相当于删除了。

    1. 尾插
    2. void SLPushBack(SL*ps,int i)
    3. {
    4. SLCheckCapacity(ps);
    5. ps->a[ps->size] = i;
    6. ps->size++;
    7. }
    8. 尾删
    9. void SLPopBack(SL*ps)
    10. {
    11. assert(ps->size > 0);
    12. ps->size--;
    13. }
    5.头插头删
     顺序表的头插:

            对于头插就要麻烦很多了,我们需要将数据一个个覆盖给下一个。再将我们的第一个元素值变成要插入的元素值,这里也要判断是否需要扩容哦!

            

            顺序表的头删:

            同理头删也是需要覆盖数据的,要把第二个数据给第一个,第三个给第二个等等以此类推

    1. 头插
    2. void SLPushFront(SL*ps,int i)
    3. {
    4. SLCheckCapacity(ps);
    5. int end = ps->size;
    6. for(;end - 1 >= 0 ; end--)
    7. {
    8. ps->a[end] = ps->a[end - 1];
    9. }
    10. ps->a[0] = i;
    11. ps->size++;
    12. }
    13. ///头删
    14. void SLPopFront(SL*ps)
    15. {
    16. assert(ps->size > 0);
    17. int i = 0;
    18. for(i = 0 ; i + 1 < ps->size ; i++)
    19. {
    20. ps->a[i] = ps->a[i+1];
    21. }
    22. ps->size--;
    23. }
    7.顺序表的查找

            查找某一值x是否存在顺序表里,存在返回数组下标,不存在返回-1.

    1. int SeqListFind(SL*ps,SLDataType x) //查找
    2. {
    3. int i = 0;
    4. for(i = 0 ; i < ps->size ; i++)
    5. {
    6. if(ps->a[i] == x)
    7. {
    8. return i;
    9. }
    10. }
    11. return -1;
    12. }
    8.在下标为pos的位置的插入

    下面的大家自行画图理解哦,相信经过前面的讲解,大家有一定的收获啦!

    1. void SeqListInsert(SL* ps, int pos, SLDataType x)// 顺序表在pos位置插入x
    2. {
    3. if(ps->size == ps->capacity)
    4. {
    5. SLCheckCapacity(ps);
    6. }
    7. int i = SeqListFind(ps,pos);
    8. int j = ps->size;
    9. for(;j > i ; j--)
    10. {
    11. ps->a[j] = ps->a[j-1];
    12. }
    13. ps->a[i] = x;
    14. ps->size++;
    15. }
    9.删除下标为pos位置的值
    1. void SeqListErase(SL* ps, int pos)// 顺序表删除pos位置的值
    2. {
    3. assert(ps->size > 0);
    4. int i = SeqListFind(ps,pos);
    5. for(i;i < ps->size - 1; i++ )
    6. {
    7. ps->a[i] = ps->a[i+1];
    8. }
    9. ps->size--;
    10. }
    9.打印

    打印就是遍历一边数组就OK啦!

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

    以上就是顺序表的相关接口实现啦!谢谢大家过来与博主一起学习,如果觉得博主写的还可以,对各位有帮助,别忘了点赞和收藏,方便以后再次查看呀!

  • 相关阅读:
    在线副业教程之 02 你学的越多,你赚的越多+你必须开始学习的5个最好的在线副业
    软件测试基础篇
    渗透测试 | APP信息收集
    CICD—Jenkins Gitlab自动化打包前端到K8S
    基于Vue3在线商城(Vue3+VueCLI+VueRouter+vuex+axios+Bootstrap)
    kfed修复损坏asm头部
    Richardson Software RazorSQL 10.0 Crack
    sqlmap语法介绍
    Spring Cloud alibaba Ribbon 负载调用说明(4)
    Linux——ansible剧本
  • 原文地址:https://blog.csdn.net/2302_76941579/article/details/133838265