数据结构之顺序表的增删查改

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

别丢了你的勇敢

前言:

自今日起,我们正式越过C语言的大山,走向了数据结构的深山,现如今摆在我们面前的第一个坎就是顺序表,我们需要了解顺序表的定义,并且知道,如何对其进行增删查改,之后我们需要在此处基础上写出一份通讯录代码,ok,顺序表,启动!

1.什么是顺序表

1.1线性表

线性表( linear list )是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使
⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的,
线性表在物理上存储时,通常以数组和链式结构的形式存储。
线性表指的是具有部分相同特性的⼀类数据结构的集合

1.2顺序表

顺序表是一种线性表的数据结构,它是由一组具有相同特性的数据元素按照一定的顺序排列而成的。顺序表的底层结构是数组,对数组的封装,实现了常⽤的增删改查等接口。 顺序表可以使用数组来实现,也可以使用动态数组来实现。

顺序表分为静态顺序表和动态顺序表

静态顺序表是使用固定长度的数组来存储元素,数组的长度在创建时就确定了,无法改变。静态顺序表的优点是访问元素的时间复杂度为O(1),缺点是插入和删除元素的时间复杂度较高。

数据结构之顺序表的增删查改,数据结构,数据结构,c语言,算法

图片来自比特就业课官网链接:https://www.bitejiuyeke.com

动态顺序表是使用可以动态开辟的数组来存储元素,数组的长度可以根据需要进行动态调整。动态顺序表的优点是可以灵活地插入和删除元素,缺点是访问元素的时间复杂度为O(1)。

顺序表是一种常见的数据结构,它在实际中被广泛使用,常见的应用场景包括数组、字符串等。

数据结构之顺序表的增删查改,数据结构,数据结构,c语言,算法

图片来自比特就业课官网链接:https://www.bitejiuyeke.com

动态顺序表和静态顺序表的使用是极其相似的,只是静态的顺序表建立在栈区,动态顺序表通过动态内存分配建立于堆区,由于动态涉及了动态内存分配,难度会稍稍高一些,所以我们今天的增删查改直接是以动态顺序表为对象,如果你能明白了这个,那静态顺序表也是同样的原理,也是可以写出来的。

2、 动态顺序表的实现

2.1头文件

⭐️ 🌟我先把头文件列出来,让各位先知道我们要实现的内容有什么
# define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
//初始化顺序表
void SLInit (SL* ps);
// 销毁顺序表
void SLDestroy (SL* ps);
// 打印顺序表内容
void SLPrint (SL* ps);
// 扩容
void SLCheckCapacity (SL* ps);
//尾 部插⼊ 数据
void SLPushBack (SL* ps, SLDataType x);
//尾 部删除 数据
void SLPopBack (SL* ps);
// 头部插⼊ 数据
void SLPushFront (SL* ps, SLDataType x);
// 头部删除 数据
void SLPopFront (SL* ps);
// 指定位置插⼊ 数据
void SLInsert (SL* ps, int pos, SLDataType x);
// 指定位置 删除数据
void SLDelete(SL* ps, int pos);
// 指定位置修改 数据
void SLModify(SL* ps, int pos,SLDataType x);
// 指定位置查找 数据
void SLSearch(SL* ps, int pos, SLDataType x);

2.2具体分析

ok,然后咱们,从上到下,挨个分析

🍎2.2.1

#define INIT_CAPACITY 4

这是一个宏定义,也是我们初始化默认通讯录的初始容量,即四个单位空间

🍏2.2.2

typedef int SLDataType;

这是用typedef给int换了个名字,这时候肯定有人会问了,为啥不直接用int,

⭐️ 原因如下:

我们的顺序表是对数组的封装,但我们不能确实是什么类型的数组,如果我直接用int,那后面代码里也都是int,可假如我后来想给这个数组换成char类型呢,那我就要把所有int都改为char,于是乎我们直接用typedef创建一个类型名,之后代码也都用这个类型名,这样我之后想修改就只需要把

typedef int  SLDataType改为typedef char  SLDataType就ok了

这点在我们之后写通讯录时会体现出来

🍐 2.2.3

typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
这是一个结构体,SLDataType*是顺序表中存储的元素类型,size是当前顺序表的存储数据数量,
capacity是顺序表的存储数据数量最大值。

🍊 2.2.4

void SLInit (SL* ps);
这是对顺序表的初始化,我们传一个顺序表变量进去,该函数对其进行初始化,具体如下
给ps->a开辟了4个单位空间
将通讯录目前数据数量设置为0
容量设置为4
void SLInit(SL* ps)
{
        ps->a = (SLDataType*)malloc(CAPACITY * sizeof(SLDataType));
        ps->size = 0;
        ps->capacity = 4;
}

🍋2.2.5

void SLDestroy (SL* ps);
有初始化就有销毁,当我们要退出程序时要对顺序表的内容进行销毁,这时候有人要问了:程序退出不是会自动销毁吗,为什么还要再写一个函数呢?
 ✨答:我们使用了动态内存开辟,有开辟就要有释放,当你不用它时就释放它是一个好的代码习惯,不然如果一直想着靠结束代码时释放空间以后当你写项目时就容易忘记及时释放空间导致内存泄漏。
 ✨具体如下:
把之前的空间释放掉
把通讯录目前的数据数量设置为0
把通讯录容量设置为0
void SLDestroy(SL* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;

🍌 2.2.6

void SLPrint (SL* ps);
这个是打印顺序表的信息,直接遍历数组挨个打印就可以
循环控制条件依靠顺序表中的ps->size就可以
void SLPrint(SL* ps)
{
    for (int i = 0; i < ps->size; i++)
        printf("%d  ", ps->a[i]);
}

🍉 2.2.7

void SLCheckCapacity (SL* ps);
要知道我们给顺序表设置的初始容量只有4个单位,在你不断输入数据的情况下,他很快就会满,于是我们就需要设置一个函数用来给顺序表扩容
直接调用realloc函数就可以
这里我们的扩容方式是直接将容量扩大到现在容量的2倍
🔥🔥🔥 为什么不是扩大一个固定的数呢?🔥🔥🔥
假如我们每次扩2个或3个,那很容易就会不够,扩容很频繁,导致性能消耗,如果一次扩1000个,2000个又很容易空间浪费,但如果我们以倍数扩容,随着空间越来越大每次增加的空间也会越来越大,这样扩容就不会很频繁,浪费空间也不会很多,我们通常是采用2倍扩容或1.5倍扩容,至于为什么是这俩数字就涉及到数学原理了,我能力有限,无法作答。(去找你数分的朋友吧)
void SLCheckCapacity(SL* ps)
{
    SLDataType* p = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));
    if (p == NULL)
    {
        perror("realloc fail");
        exit(1);
    }
    ps->a = p;
    ps->capacity *= 2;
}
🔥这里有个小知识点别忘了,realloc会自动释放之前的空间,所以不用free了

🍇 2.2.8

void SLPushBack(SL* ps, SLDataType x);  

☄️这个是尾插文章来源地址https://www.toymoban.com/news/detail-817756.html

  1. 在增加之前判断一下顺序表是不是满了,如果满了就调用扩容函数
  2. 再来一个尾插,也就是在数组最后面加入元素
  3. 之后直接在末尾加上该元素即可
void SLPushBack(SL* ps, SLDataType x)
{
    if (ps->size + 1 > ps->capacity)
        SLCheckCapacity(ps);
    ps->a[ps->size] = x;
    (ps->size)++;
}

🍓  2.2.9

void SLPopBack (SL* ps);
 ☄️ 这个是尾删
  1. 尾删之前要判断一下顺序表是不是空的,
  2. 如果是就打印提示信息,若不是就把最后一个元素设置其值为0,
  3. 然后把顺序表的当前数据数量减一
void SLPopBack(SL* ps)
{
    if (ps->size - 1 < 0)
    {
        printf("顺序表空了,无法删除\n");
        //perror("SLPopFront Fail");
        return ;
    }
    ps->a[ps->size - 1]=0;
    (ps->size)--;
}

🍈2.2.10

void SLPushFront (SL* ps, SLDataType x);
 ☄️这个是头插,比尾插麻烦一些,
  1. 第一步还是检验顺序表是不是满了
  2. 第二步我们要通过循环把所有元素集体向后移动一个单位,然后在空出来的第一个位置插入我们要插的值。
  3. 记得ps->size++
void SLPushFront(SL* ps, SLDataType a)
{
    if (ps->size + 1 > ps->capacity)
        SLCheckCapacity(ps);
    for (int i = 1; i <= ps->size; i++)
    {
        ps->a[i] = ps->a[i - 1];
    }
    (ps->size)++;
    ps->a[0] = a;
}

🍒 2.2.11

void SLPopFront (SL* ps);
 ☄️ 这个是头删
  1. 第一步检验顺序表是不是为空
  2. 第二步通过循环把元素集体向前移动一个单位,从而覆盖掉第一个元素
  3. 第三步ps->size--
void SLPopFront(SL* ps)
{
    if (ps->size - 1 < 0)
        perror("SLPopFront Fail");
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->a[i] = ps->a[i + 1];
    }
    ps->a[ps->size - 1] = 0;
    (ps->size)--;
}

🍑2.2.12

void SLInsert (SL* ps, int pos, SLDataType x);
 ☄️ 指定位置之前插⼊数据
  1. 第一步检查是否需要扩容
  2. 第二步通过循环让下标pos及pos之后的元素集体后移一个单位,
  3. 第三步把数据放入下标为pos的地方
void SLInsert(SL* ps, int pos, SLDataType x)
{
    if (ps->size + 1 < ps->capacity)
        SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)
        ps->a[i] = ps->a[i - 1];
    ps->a[pos] = x;
ps->size++;
}

🥭2.2.13

void SLDelete(SL* ps, int pos);
 ☄️ 指定位置删除数据
  1. 第一步检查顺序表是否为空
  2. 第二步通过循环把下标pos之后的元素向前移动一个单位,从而覆盖掉pos对位空间的值
  3. 第三步ps->size--
void SLDelete(SL* ps, int pos)
{
    if (ps->size - 1 < 0)
    {
        printf("顺序表空了\n");
        //perror("SLPopFront Fail");
        return;
    }
    for (int i = pos; i < ps->size - 1; i++)
        ps->a[i] = ps->a[i + 1];
    ps->size--;
}

🍍 2.2.14

void SLModify(SL* ps, int pos,SLDataType x);
 ☄️这个是修改数据:
先判断下标是否有效
若有效则修改数据
void SLModify(SL* ps, int pos,SLDataType x)
{
    if (pos >= ps->size)
        printf("要修改的元素不存在\n");
    else
        ps->a[pos] = x;
}

🍍 2.2.15

void SLSearch(SL* ps, int pos, SLDataType x);
☄️查找数据:
先判断下标是否有效
若有效则打印数据
{
    if (pos >= ps->size)
        printf("要查找的元素不存在\n");
    else
        printf("%d\n",ps->a[pos]);
}
ok,至此,我们知道了什么是顺序表,顺序表的增删查改四种功能我们也都实现了,可以说是迈出了相当大的一步,下一次我们将会在此基础上实现通讯录,
我先把要求放下面了,感兴趣的朋友可以自己动手试试哦
. 基于动态顺序表实现通讯录
C语⾔基础要求:结构体、动态内存管理、顺序表、⽂件操作
1、功能要求
1)⾄少能够存储100个⼈的通讯信息
2)能够保存⽤⼾信息:名字、性别、年龄、电话、地址等
3)增加联系⼈信息
4)删除指定联系⼈
5)查找制定联系⼈
6)修改指定联系⼈
7)显⽰联系⼈信息
当然了,与这次的顺序表不同的是我们下次还会用到文件操作来保存你存入的数据,毕竟写完就丢也太离谱了。
ok,那么今天在数据结构的第一场战役就打完了,倘若你觉得我的博客对你有帮助,就请点个免费的赞支持一下吧。
数据结构之顺序表的增删查改,数据结构,数据结构,c语言,算法

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

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

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

相关文章

  • 【数据结构】单链表的增删查改(C实现)

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

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

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

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

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

    2024年02月02日
    浏览(75)
  • 数据结构---手撕顺序表---顺序表增删查改寻找功能的实现

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

    2024年02月16日
    浏览(42)
  • 数据结构:手撕顺序表---顺序表增删查改寻找功能的实现

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

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

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

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

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

    2024年02月05日
    浏览(48)
  • 详解初阶数据结构之顺序表(SeqList)——单文件文件实现SeqList的增删查改

    目录 一、线性表 二、顺序表 2.1概念及结构 2.2接口实现 2.3动态顺序表的创建 2.3动态顺序表的初始化 2.3.1传值初始化 2.3.2传址初始化 2.4动态顺序表的清空 2.5动态顺序表的扩容 2.6动态顺序表内容的打印 三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 3.1.2尾删 3.2头插头删 3.2.1头插

    2024年02月09日
    浏览(41)
  • 对顺序表的基本操作(增删查改),并编写makefile进行编

    1.定义顺序表结构体 2.创建顺序表 3.从尾部插入数据 4.遍历顺序表 5.从尾部删除数据 6.按下标插入数据 7.按下标删除数据 8.按下标修改数据 9.按下标查找数据 10.按数据修改数据 11..按数据查找位置 12.顺序表去重         删除重复数据         (提示:将先出现的数据与后面

    2024年02月20日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包