顺序表(数据结构)---排队啦!

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

目录

前言:

1.线性表的性质

2.静态数组or动态数组

2.1静态数组

2.2动态数组

3.结构体的创建

4*接口函数的详细讲解

4.1初始化结构体

4.2尾插

4.3打印数据

4.4用完后销毁创建的堆空间

4.5 尾删

4.6头插

4.7头删

4.8查找

4.9任意位置插入

4.10任意位置删除 


❤博主CSDN:啊苏要学习

    ▶专栏分类:数据结构◀

  学习数据结构是一件有趣的事情,希望读者能在我的博文切实感受到数据之间存在的关系,在对数据元素进行操作的时候,能心中有数,脑中有画! 


前言:

  这节我们来学习和实现线性结构中最简单的顺序表,由于博主使用C语言实现的,所以读者要对C语言的结构体、指针、内存管理这三部分知识做到理解并掌握。看代码能理解,能看懂,相信自己的实力!

1.线性表的性质

  数据在内存中存储有两种结构、分别是逻辑结构和物理结构顺序表就是逻辑结构中的线性结构+物理结构中的顺序结构

  线性结构的性质:线性意味着内存中的数据之间的关系呈现一条线状

  顺序结构的要求:顺序结构要求数据之间是有序的,数据元素与数据元素是紧挨着的,就像排队一样

  顺序表的本质:看完线性结构和顺序结构后,脑海里有没有涌现一股灵感呢?是的,顺序表的本质就是一个数组这个数组和普通的数组不太一样,我们普通的数组可以进行以下这样的操作

#include <stdio.h>

int main()
{
    int arr[10] = {0};
    arr[0] = 1;
    arr[5] = 10;
    arr[9] = 20;
    return 0;
}

  假如我们要把3个整型值放到一个数组里面,普通数组可以将这3个整型值放到该数组中的任意位置比如这个数组的第一个元素、第六个元素、最后一个元素分别被赋值了1、10、20然而,顺序表要存放这3个值,只能按顺序存放在下标为0、1、2的元素位置上

2.静态数组or动态数组

2.1静态数组

  静态数组是我们一开始就确定好数组的大小,在运行时不能改变数组存储多少。所以这里就有个问题:

  • 当我们在用静态数组开辟空间的时候,给了100个元素空间,但实际情况需要存101个元素,但存不了了,数组已经满了
  • 所以我决定给个大一点的数组,创建一个能存放1000个元素的数组,但实际情况只需要存200个元素,造成了不必要的浪费。

  总结:静态数组的缺陷就是,数组空间开辟小了不够用,开辟大了用不完

2.2动态数组

  所以我们选择能根据具体的存储情况,开辟大小适合的数组,动态数组可以实现

  动态开辟的空间是在堆区上开辟的,会使用到realloc函数开辟堆区上的空间,我们在这里描述一下这个函数的功能吧。realloc本意是追增空间,malloc才是一个纯正实现开辟空间的函数,但realloc的功能更强大

realloc的功能
情形: 功能:
接收地址的指针为空指针 相当于malloc开辟堆区空间
指针指向的堆空间够追加 原地扩容,不需要换内存位置
指针指向的堆空间不够追加 将原先内存空间数据搬家到扩容后的内存上

    相信没学过内存管理的同学一脸茫然,头顶打着问号,看图理解:

  • 接收地址的指针未空指针的情况

顺序表(数据结构)---排队啦!

  • 指针指向的堆空间够追加的情况

顺序表(数据结构)---排队啦!

  • 指针指向的堆空间不够追加的情况

顺序表(数据结构)---排队啦!

  就这样,一开始给数组小一点的空间,空间不够了,在realloc的帮助下增容就实现动态数组了。一般每次增容,新容量都是原容量的2倍

3.结构体的创建

  进度有点慢了,我们直接看代码:

  1.静态顺序表: 

顺序表(数据结构)---排队啦!

  将数组元素个数用宏(N)表示,此后凡是需要改变数组个数,不用一个一个改,只用改N就可以全部替换了将顺序表的数组元素类型改名为SLDataType也是同理

  2.动态顺序表

顺序表(数据结构)---排队啦!

  其实动态数组的创建的一些情况还是和静态数组一样的,比如把struct SeqList的名字改成SL,元素类型用SLDataType主要不同的点是用指针管理开辟的数组空间,多一个capacity变量表示数组的最大容量

  补充:分模块写的重要性

顺序表(数据结构)---排队啦!

  1. test.c文件是用来测试SeqList的功能的一个文件。
  2. SeqList.h用来声明接口函数的,还有一些宏,程序用得到的库函数头文件等。
  3. SeqList.c是用来实现接口函数的。

  补充:使用宏#pragma once可以防止头文件被多次包含我们引头文件的时候,编译器会把头文件里的内容复制一份放到我们的程序当中,如果我们多次引用,就会有很多重复的代码,这个宏就够很好的防止头文件被多次引用

  好的,前提都说完了,进入正题。学习思想,实现接口函数。

4*接口函数的详细讲解

4.1初始化结构体

  记住结构体中,有三个结构成员,a是用来指向堆区数组的指针、size是用来表示数组里有多少个数据、capacity是用来表示数组能存储的数据个数

顺序表(数据结构)---排队啦!

  下面我们就不再写结构体是什么了,就是写接口函数,这样才不会占用太多的篇幅。 

//初始化结构体
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

int main()
{
    SL s1;
    SeqListInit(&s1)
    
}

  看到下面这个图,相信不是很理解指针和结构的读者都可以尝试理解。 

顺序表(数据结构)---排队啦!

4.2尾插

void SeqListPushBack(SL* ps, SLDataType x)
{
    //检查容量
    if(ps->size == ps->capacity)
    {
        //为了防止初始化capacity为0,每次乘二也为0,所以判断capacity是否为0,为零先赋值成4。
        int newcapacity = ps->capacity == 0 ? 4: capacity*2;
        //注意是SLDataType*,返回这块空间的首元素地址,是SLDataType类型。
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
        //判断realloc成不成功,不成功realloc返回NULL
        if(tmp == NULL)
        {
            printf(realloc 失败\n);
            //系统函数exit,执行到exit整个程序直接结束,-1是一个错误码而已。
            exit(-1);
        }
        //将新空间的地址交给a管理
        ps->a = tmp;
        //更新capacity的容量
        ps->capacity = newcapacity;
    }
    //尾部加元素,size是数组最后一个数据下一个位置的下标
    ps->a[ps->size] = x;
    size++;
}

  尾插其实不难的:大家看看下面的图吧

顺序表(数据结构)---排队啦!

   需要额外关注的一点是:每次插入数据,数据个数增加,我们需要考虑size会不会等于capacity,一旦等于就扩容,我们前面的检查容量就是做这个事情

4.3打印数据

  既然通过尾插插入了一些数据,我们需要看一看有没有成功,把数组里的内容打印出来看看。

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

  打印也很简单~,用VS编译器测试一下出来看吧!

顺序表(数据结构)---排队啦!

4.4用完后销毁创建的堆空间

void SeqListDestory(SL* ps)
{
    free(ps->a);
    ps->a = NULL;
    //可以连续赋值
    ps->size = ps->capacity = 0;
}

顺序表(数据结构)---排队啦!

  补充如果一个堆区空间没有被释放,那么将会引起内存泄漏,导致程序的内存空间越来越少,因为没有释放的堆区空间既不能被我们使用(指向该处的指针已被销毁),操作系统也没法回收所以,只要动态开辟了空间的,最后要释放掉

4.5 尾删

void SeqListPopBack(SL* ps)
{
    //不动于声的方式,当size不符合条件是,不执行就是了,
    //assert是只要有触碰的倾向,直接报错,可以看下面另一种方式的解释。
    if(ps->size > 0)
    {
         ps->size--;    
    }
   
}

  尾删的时候,让size--就可以了因为size是标识着顺序表的有效数据个数的,当size减一的时候,顺序表的最后一个数据就不再是有效数据了,顺序表访问不到了

  当没有数据的时候,size不要继续往后减了,因为这样size表示的就是数组外的下标了,此时很容易造成非法访问的错误,所以加上size>0的限制条件。比如当size为1的时候,尾删1个,此时,size符合条件进入if并成功将size减成了0,再次调用的时候,不符合条件,防止将size减减。

  下面是另一种方式

#include <assert.h>
void SeqListPopBcak(SL* ps)
{
    //断言,如果条件为真则相安无事,如果条件为假,直接挂断程序,并报出错误。
    assert(ps->size > 0);
    ps->size--;
}

顺序表(数据结构)---排队啦!

4.6头插

  在数组的第一个位置插入一个元素,为了实现这个做法,我们需要把原先所有的数据往后挪一个位置

  不管是头插还是尾插,只要是插入,就得保证插入数据后不会超出容量,也就是在头插实现部分也要使用检查容量的代码,因此我们可以把检查容量的代码封装成一个函数,调用就可以了。

顺序表(数据结构)---排队啦!

  接下来看到头插的实现部分

void SeqListPushFront(SL* ps, SLDataType x)
{
    SeqListCheckCapacity(ps);//检查容量的接口函数
    int end = ps->size-1;
    while(end>=0)
    {
        ps->a[end+1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

//用for循环实现移动数据
int end = ps->size-1;
for(int i = end; i >= 0; i--)
{
    ps->a[i+1] = ps->[i];
}
ps->a[0] = x;
ps->size++;

  将检查容量,决定需不需要扩容的代码块分装成函数,很方便。 

顺序表(数据结构)---排队啦!

顺序表(数据结构)---排队啦!

4.7头删

  头删其实就是将第一个数据后的所有元素向前移动一个数据位置

void SeqListPopFront(SL* ps)
{
    assert(ps->size > 0);
    int begin = 1;
    while(begin < ps->size)
    {
        ps->a[begin-1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

//用for循环实现移动数据
int begin = 1;
for(int i = begin; i < ps->size; i++)
{
    ps->a[i-1] = ps->a[i];
}
ps->size--;

//也可以是
int begin = 0;
for(int i = begin; i < ps->size-1; i++)
{
    ps->a[i] = ps->a[i+1];
}

顺序表(数据结构)---排队啦!

4.8查找

  查找是在数组里查找到一个数据,找到了返回数据的下标,找不到返回-1

int SeqList(SL* ps, SLDataType x)
{
    for(int i = 0; i < ps->size; i++)
    {
        if(ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

4.9任意位置插入

  对于任意位置插入,有一定的插入范围限制一个是不能插入到超过size下标的地方,可以等于。插入在以size为下标的地方,这相当与尾插;另一个是不能在小于0的下标处插入数据

void SeqListInsert(SL* ps, int pos, SLDataType x)//pos是要插入的下标
{
    //温柔的方式
    /*
    if(pos > ps->size || pos < 0)
    {
        printf("下标pos不能插入数据\n");
        return;
    }
    */
    //暴力的方式
    assert(pos <= ps->size && pos>=0);
    SeqListCheckCapacity(ps);
    int end = ps->size-1;
    //包括要插入的位置的数据也给往后挪,也就是end=pos进入循环
    while(end>=pos)
    {
        ps->a[end+1] = ps->a[end];
        --end;
    }
    ps->a[pos] = x;
    ps->size++;
}

//使用for循环挪动数据
int end = ps->size-1;
for(int i = end; i >= pos; i--)
{
    ps->a[i+1] = ps->a[i];
}

顺序表(数据结构)---排队啦!

  如果想在某个数据位置上插入一个新的数据,我们可以使用SeqListFind计算出相应的下标,带进任意插入的接口函数中就可以了

顺序表(数据结构)---排队啦!

  改变其它的函数

  改变头插

  既然我们现在已经实现了可以再任意位置插入,那头插就是任意插入的一个特殊情况,我们可以直接锁定插入的位置pos为0,调用函数SeqListInsert(&s1, 0, 数据)尾插也一样

void SeqListPushFront(SL* ps, SLDataType x)
{
    //一句代码搞定头插
    SeqListInsert(ps, 0, x);

  尾插如下

void SeqListPushBack(SL* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);
}

4.10任意位置删除 

  任意删除的位置的范围限制是:pos的位置不能小于下标0、pos的位置不能大于size这里不像插入数据一样可以等于size,因为size为下标处没有数据

void SeqListErase(SL* ps, int pos)
{
    assert(ps->size > 0);//保证有数字可以删除
    assert(pos >= 0 && pos < ps->size);
    
    int begin = pos + 1;
    while(begin < ps->size)
    {
        ps->a[begin-1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

//用for循环移动数据
int begin = pos;
for(int i = begin; i < ps->size-1; i++)
{
    ps->a[i] = ps->a[i+1];
}
ps->size--

顺序表(数据结构)---排队啦!

  同上:学完任意位置删除元素,我们可以对头删和尾删给改一下,它们都是是任意位置删除的特殊情况

  头删

void SeqListPopFront(SL* ps)
{
    SeqListEras(ps, 0);
}

  尾删

void SeqListPopBack(SL* ps)
{
    SeqLisErase(ps, ps->size-1);
}

  尾部删除就是最后一个数据,下标自然是size-1啦

顺序表(数据结构)---排队啦!

  好啦,到这里,顺序表的内容就讲完啦,更新不易,求波点赞吧~


结语:希望读者读完能有所收获!对数据结构有进一步的认识!✔

  读者对本文不理解的地方,或是发现文章内容上有误等,请在下方评论留言告诉博主哟~,也可以对博主提出一些文章改进的建议,感激不尽!最后的最后!

  ❤求点赞,求关注,你的点赞是我更新的动力,一起进步吧。文章来源地址https://www.toymoban.com/news/detail-440864.html

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

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

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

相关文章

  • 数据结构-线性表-顺序表

    线性表的定义:由n(n=0)个数据特性相同的元素构成的有限序列,称为线性表。当n=0时称之为空表。 因为构件线性表时元素数组已经使用静态分配,所以在此只需要对线性表的长度执行初始化即可。 获取数据需要参数: sqList:需要给定一个线性表从而获取数据,因为只是拿值

    2024年02月08日
    浏览(48)
  • 数据结构——线性表①(顺序表)

    线性表是一种数据结构,它是由n个具有 相同数据类型 的数据元素a1,a2,…,an组成的 有限序列 。 其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。 线性表可以用 顺序存储结构 或 链式存储结构

    2024年02月06日
    浏览(54)
  • 数据结构---顺序表示的线性表

             数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简言之,数据

    2024年02月16日
    浏览(54)
  • 数据结构: 线性表(顺序表实现)

    线性表(linear list)是 n 个具有相同特性的数据元素的有序序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表,链表,栈,队列,字符串… 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删

    2024年02月14日
    浏览(50)
  • 数据结构:线性表之-顺序表

    目录 1.线性表概念 1.1 什么是顺序列表 1.2 线性表 2.顺序表实现 将有以下功能: 详细过程 顺序表的动态存储 顺序表初始化 尾插 扩容 头插 更改后的尾插 尾删 头删 打印 释放内存 优化顺序表 (任意位置插入删除) 优化后的头插尾插 优化后的头删尾删 查找和删除 进行装饰(菜单

    2024年02月10日
    浏览(51)
  • C/C++数据结构---顺序表---线性存储结构

    个人主页: 仍有未知等待探索_小项目,洛谷刷题,数据结构-CSDN博客 专题分栏---数据结构: 数据结构_仍有未知等待探索的博客-CSDN博客 目录 一、知识储备 二、引例  三、顺序表 第一步,先创建一个顺序表类型 第二步,定义和初始化顺序表    第三步,顺序表的基本操作

    2024年02月08日
    浏览(42)
  • 数据结构——线性表之顺序表

    目录 一.线性表 二.顺序表实现  2.1 概念及结构  2.2 动态顺序表 2.2.1 初始化与销毁函数 2.2.2 打印函数 2.2.3 尾插函数 2.2.4 尾删函数 2.2.5 扩容函数 2.2.6 头插函数 2.2.7 头删函数 2.2.8 任意位置插入函数 2.2.9 查找函数 2.2.10 任意位置删除函数  2.2.11 修改函数 三.完整代码 四.力扣

    2024年02月07日
    浏览(49)
  • 数据结构(二)----线性表(顺序表,链表)

    目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 (1)顺序表 •顺序表的概念 •顺序表的实现 静态分配: 动态分配: 顺序表的插入: 顺序表的删除: 顺序表的按位查找: 顺序表的按值查找: 顺序表的特点: (2)单链表 •单链表的实现 不带头结点的单链表

    2024年04月16日
    浏览(57)
  • 【数据结构】线性表与顺序表

    ⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈数据结构 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 它是一种在实际中广泛使用的数据结构,常见的线性表:顺序表

    2024年02月07日
    浏览(46)
  • 【数据结构】线性表和顺序表

    Yan-英杰的主页 悟已往之不谏 知来者之可追 目录 1.线性表 2.顺序表         2.1 静态顺序表         2.2 动态顺序表         2.3移除元素         线性表( linear list )是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线

    2023年04月08日
    浏览(84)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包