【数据结构入门】顺序表详解(增删查改)

这篇具有很好参考价值的文章主要介绍了【数据结构入门】顺序表详解(增删查改)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构入门】顺序表详解(增删查改),数据结构,数据结构,c语言,学习,算法

目录

顺序表的基本概念

动态顺序表的实现

初始化

插入

尾插法

头插法

指定位置之前插入

删除

尾删法

头删法

指定位置删除

查找

销毁


顺序表的基本概念

什么是顺序表?

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

简单来讲,顺序表的底层结构就是数组,只不过在数组的基础上,实现的增删改查等接口。

顺序表的分类:

  • 静态顺序表
  • 动态顺序表

静态顺序表:使用定长数组存储元素;

typedef struct Seqlist {
    SLdatatye arr[N];//定长数组
    int size;//有效数据个数
}SL;

静态顺序表缺陷:空间开少了不够用,开多了造成空间浪费;

因此我们在日常主要使用动态顺序表;


动态顺序表:按需申请空间;

typedef struct Seqlist {
    SLdatatye* arr;//存储数据的底层结构
    int capacity;//记录顺序表空间大小
    int size;//记录顺序表当前有效的数据个数
}SL;

动态顺序表的实现

首先创建一个工程:

【数据结构入门】顺序表详解(增删查改),数据结构,数据结构,c语言,学习,算法

  • SeqList.h:定义顺序表的结构,顺序表要实现的接口/方法;
  • SeqList.c:具体实现顺序表定义的接口/方法;
  • test.c:测试顺序表;

初始化

SeqList.h:

void SLinit(SL* s);

SeqList.c:

void SLinit(SL* s)
{
    s->arr = NULL;
    s->size = s->capacity = 0;
}

插入

数据的插入有多种方法:

  • 头插法;
  • 尾插法;
  • 指定位置插入;

尾插法

对于空间足够的情况我们选择直接插入即可;

如果空间不够,我们就需要扩容;

【数据结构入门】顺序表详解(增删查改),数据结构,数据结构,c语言,学习,算法

SeqList.h:

 void SLinsertback(SL* s, SLdatatye x);

void SLcheakcapacity(SL* s);//扩容

SeqList.c:

void SLinsertback(SL* s, SLdatatye x)
{
    assert(s != NULL);
    //空间不够,扩容
    SLcheakcapacity(s);

    //空间足够
    s->arr[s->size++] = x;
}

void SLcheakcapacity(SL* s)
{
    if (s->size == s->capacity)
    {
        //三目表达式:
        int newcapacity = s->capacity == 0 ? 4 : 2 * s->capacity;
        SLdatatye* tmp = (SLdatatye*)realloc(s->arr, 2 * newcapacity * sizeof(SLdatatye));
        if (tmp == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        //扩容成功
        s->arr = tmp;
        s->capacity = newcapacity;
    }

}

从图中我们可以看到当capacity ==size时说明空间已满,此时如若再添加数据就需要进行扩容,增大空间,这里使用的是realloc;因为在头插法,指定位置插入都需要扩容,为了方便,我们将扩容单独写成一个函数;

头插法

【数据结构入门】顺序表详解(增删查改),数据结构,数据结构,c语言,学习,算法

  •  先将数据全部往后平移;
  •  再在首位插入; 

SeqList.h:

void SLinsertfront(SL* s, SLdatatye x);

SeqList.c:

void SLinsertfront(SL* s, SLdatatye x)
{
    assert(s != NULL);
    SLcheakcapacity(s);
    for (int i = s->size; i >= 0; i--)//平移
    {
        s->arr[i] = s->arr[i-1];
    }
    s->arr[0] = x;//插入
    s->size++;
}

指定位置之前插入

先平移,后插入,注意size要变化

SeqList.h:

void SLinsert(SL* s, int pos, SLdatatye x);

SeqList.c:

void SLinsert(SL* s, int pos, SLdatatye x)
{
    assert(s);
    SLcheakcapacity(s);
    for (int i = s->size; i >pos; i--)//平移
    {
        s->arr[i] = s->arr[i - 1];
    }
    s->arr[pos] = x;//插入
    s->size++;
}

删除

  • 头删法;
  • 尾删法;
  • 指定位置删除;

尾删法

SeqList.h:

void SLdeleteback(SL* s);

SeqList.c:
void SLdeleteback(SL* s)
{
    s->size--;
}

头删法

SeqList.h:

void SLdeletefront(SL* s);

SeqList.c:

void SLdeletefront(SL* s)
{
    for (int i = 0; i < s->size-1; i++)
    {
        s->arr[i] = s->arr[i + 1];
    }
    s->size--;
}

指定位置删除

SeqList.h:

void SLdelete(SL* s, int pos);

SeqList.c:

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

查找

插入本质就是变量;找到就返回其下标,未找到就返回-1

SeqList.h:

int SLfind(SL* s, SLdatatye x);

SeqList.c:

int SLfind(SL* s, SLdatatye x)
{
    assert(s);
    for (int i = 0; i < s->size; i++)
    {
        if (s->arr[i] == x)
            return i;
    }
    return -1;
}

销毁

SeqList.h:

void SLdestroy(SL* s);

SeqList.h:

void SLdestroy(SL* s)
{
    if(s->arr!=NULL)
    {
        free(s->arr);
        s->arr = NULL;
    }

    s->capacity = s->size = 0;
}

对于顺序表的修改比较简单:想要修改某个数值:s->arr[i]=x;即可。

以上就是顺序表的基本内容,希望有所帮助!文章来源地址https://www.toymoban.com/news/detail-854607.html

到了这里,关于【数据结构入门】顺序表详解(增删查改)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构---手撕顺序表---顺序表增删查改寻找功能的实现

    顺序表作为数据结构的入门知识,整体知识较为简单,主要对动态内存开辟 结构体 指针有要求,其余难度较低 顺序表主要需要实现的有顺序表的增删查改和定向搜索销毁等,具体实现函数如下 要实现顺序表,就需要对顺序表进行定义,在c语言中通常使用结构体进行写入,

    2024年02月16日
    浏览(41)
  • 【数据结构.C】顺序表和单链表的增删查改

    宝子,你不点个赞吗?不评个论吗?不收个藏吗? 最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!! 喵喵喵,你对我真的很重要。 目录 单链表增删查改 c1.h sqlist.c number.c 单链表的增删查改  c1.h stuscore.c c1.h sqlist.c number.c  c1.h stuscore.c   宝子,你不点

    2024年02月11日
    浏览(114)
  • 【数据结构】单链表的增删查改(C实现)

    优势 : 可通过 下标i (数据连续(物理空间连续)) 便捷查询查找顺序表中的信息,也会在后面的 排序算法 和 堆算法 中尽显身手 问题 : 在头部/中间的插入与删除需要 挪动数据 ,时间复杂度为O(N),效率低; 增容需要申请新空间, 可能会拷贝数据 ,释放旧空间,会有

    2024年02月05日
    浏览(57)
  • 【数据结构】链表:带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表,以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候,我们所学仅仅所学的

    2024年02月05日
    浏览(89)
  • 【数据结构与算法】单链表的增删查改(附源码)

      这么可爱的猫猫不值得点个赞吗 😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构  2.物理结构 三.结构体的定义 四.增加 1.尾插   SListpushback 2.头插  SListpushfront 五.删除 1.尾删  SListpopback 2.头删  SListpopfront 六.查找  插入  释放   打印 1.查找

    2024年02月02日
    浏览(74)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(59)
  • 【数据结构】双向链表的增删查改(C 代码实现)

    引入双向链表:关于单链表的问题与讨论 单链表存在的毛病: 因为单链表 只能单向 遍历链表, 对于 前插 这个操作,单链表必 须得找到所需前插节点位置的前一个 ,那么这时就得 从头指针重新遍历一次 链表,会造成时间复杂度大大增加。 没有头节点(哨兵位)无法删除

    2024年02月08日
    浏览(53)
  • 【数据结构】单向链表的增删查改以及指定pos位置的插入删除

    目录  单向链表的概念及结构  尾插 头插 尾删 ​编辑  头删  查找  在pos位置前插  在pos位置后插  删除pos位置  删除pos的后一个位置 总结 代码  概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的

    2024年02月05日
    浏览(47)
  • 数据结构入门 — 顺序表详解

    数据结构入门 — 顺序表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 顺序表是连续存储的 顺序表是一种线性表的数据结构,它的数据元素按照一定次序依次存储在计算机存储器中,使

    2024年02月11日
    浏览(37)
  • 《Java数据结构入门》顺序表详解

     大家好,我是小鱼儿 目录 顺序表介绍: 顺序表的手动实现 顺序表功能接口概览 基本功能的实现 四大功能 一、增加数据  二、删除数据 三、查找数据 四、修改数据  总代码 MyArraysList.java  Test.java 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一

    2023年04月18日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包