您现在的位置是:首页 >学无止境 >顺序表(数据结构)---排队啦!网站首页学无止境

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

啊苏要学习 2024-06-04 12:00:02
简介顺序表(数据结构)---排队啦!

目录

前言:

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 失败
);
            //系统函数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("
");
}

  打印也很简单~,用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不能插入数据
");
        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啦

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


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

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

  ❤求点赞,求关注,你的点赞是我更新的动力,一起进步吧。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。