数据结构(C语言)——顺序表详解

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

一、数据结构简介

数据结构是计算机存储和组织数据的方式。常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)等;而数据结构又可以通过逻辑结构与物理结构进行分类,逻辑结构是指数据元素之间的逻辑关系,也就是数据元素之间的逻辑排列方式。常见的逻辑结构有线性结构、树形结构、图形结构等。物理结构是指数据元素在计算机内存中的存储方式,常见的物理结构包括顺序存储结构和链式存储结构。

二、顺序表简介

线性表是一种数据结构,线性表是具有相同特性的数据结构的集合。而它的物理结构上不一定连续,但是在逻辑结构上抽象为线性结构,一定是连续的。常见线性表有顺序表、链表、栈、队列、字符串等。今天我们将介绍顺序表

顺序表是线性表的一种,他在逻辑结构和物理结构上都连续,且为线性。顺序表的本质是数组

数据结构(C语言)——顺序表详解,数据结构,c语言,开发语言

三、顺序表的分类

顺序表可以分为静态顺序表和动态顺序表。静态顺序表是创建结构体时就开辟了固定的一块空间,而动态顺序表则是在使用时再主动申请空间。很明显,静态顺序表的缺陷是我们在一开始就将它所需要的空间固定下来了,如果它的空间过小,我们在存储数据时就会遗漏泄露数据,如果它的空间过大,则会浪费空间。而动态顺序表可以按需索取空间,动态顺序表可以动态地进行增容或者删减。

下面我们来看一下代码表示。

1、静态顺序表

typedef int Datatype//我们将int 重新命名,这样可以方便我们更换数据类型

typedef struct SeqList
{
    int arr[10];//假设在内存静态区开辟固定的10个整形字节大小的空间
    int size;//顺序表中数据个数
    int capacity;//顺序表的容量,取决于arr[]的大小
}SL;

2、动态顺序表

typedef int Datatype//我们将int 重新命名,这样可以方便我们更换数据类型

typedef struct SeqList
{
    int* arr;//定义一个指针,用于之后申请和更改空间
    int size;//顺序表中数据个数
    int capacity;//顺序表的容量
}SL;

四、顺序表的基本操作

我们主要介绍动态顺序表的基本操作,静态顺序表的操作可以参考静态数组的做法。

1.动态顺序表的初始化

由于动态顺序表内涵指针,所以我们需要对其中的指针初始化,当我们不知道具体需要申请多大空间时可以赋NULL,也可以用malloc申请空间。

//对动态顺序表进行初始化
void SLInit(SL* ps)//传参为结构体的地址
{
    ps->arr=NULL;//可以赋NULL进行初始化,也可以申请空间 ps->arr=(int *)malloc(10*sizeof(int))
    int ps->size=ps->capacity=0;
}

2.动态顺序表的销毁

因为动态顺序表是在堆区申请了空间,我们需要手动释放掉这块空间。

void SLDestory(SL *ps)
{
    if(ps->arr)//判断ps是否为空指针
    {
        free(ps->arr);//用free函数对申请的空间进行释放
    }
    ps->arr=NULL;//赋空指针,防止错误错误访问其它空间
    ps->size=ps->capacity=0;
}

3.尾插与头插操作以及扩容操作

有的时候我们需要在顺序表的末端或者头部或者其他位置插入一些数据,这个时候我们就需要头插与尾插操作等,今天我们先介绍这两种操作。

1.尾插

尾插,顾名思义,就是在顺序表的末端插入新的数据,这个操作看似比较简单,但是我们需要考虑到很多问题,比如,是否有足够空间让我们插入数据?如果空间不够我们应该如何扩容?扩与尾插后的数据个数以及空间大小?这些都是我们需要考虑到的问题。

void SLPushBack(SL* ps,Datatype x)//地址传递,并且传递需要尾插的数据
{
    assert(ps);//我们需要对传过来的结构体地址判断是否为空,为空则会造成空间无法访问
              //我们可以用到assert断言,也可以用if进行判断

    //下面我们需要对顺序表的空间进行判断
    if(ps->size==ps->capacity)//如果实际数据个数等于我们所申请的空间,那么我们就需要进行扩容处理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判断arr空间大小,如果为0就假设给4个单位的空间,
               //不为0则给两倍大小的空间(也可以给3倍,按照经验给定,不浪费也不缺乏)

        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我们先用临时指针进行扩容,因为realloc有时申请空间会失败。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果扩容失败,则退出程序
        }
        ps->arr =tmp;//如果成功了就赋给arr
    }
    ps->arr[ps->size++]=x;//此处完成了数据个数增加和尾插数据两个操作
}

2.扩容

其实扩容是我们在顺序表中经常用到的步骤,我们可以将它写成一个函数,方便我们使用以及简化代码。

void SLCheckCapacity(SL * ps)
{
    assert(ps);
 if(ps->size==ps->capacity)//如果实际数据个数等于我们所申请的空间,那么我们就需要进行扩容处理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判断arr空间大小,如果为0就假设给4个单位的空间,
               //不为0则给两倍大小的空间(也可以给3倍,按照经验给定,不浪费也不缺乏)

        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我们先用临时指针进行扩容,因为realloc有时申请空间会失败。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果扩容失败,则退出程序
        }
        ps->arr =tmp;//如果成功了就赋给arr
    }
}

3.头插

头插操作就是在顺序表(数组)的首位插入一个数据,那么我们需要思考如何进行操作。首先,为了确保数据的完整性,我们需要将arr[0]空出来,那么我们就需要将原顺序表的数据整体往后挪动一个单位。这里也要涉及空间大小判断以及数据的增加。

void SLPushFront(SL *ps)
{
    assert(ps);
    SLCheckCapacity(ps);//将扩容操作写成一个函数会简化很多代码
    //下面进行整体后挪操作
    for(int i=ps->size;i>0;i--)
    {
        ps->arr[i]=ps->arr[i-1];
    }
    //头插操作
    ps->arr[0] = x;
    ps->size++;//注意插入了数据,size要增加
}

4.尾删和头删操作

1.尾删

尾删操作也很好理解,就是删除末尾的数据,同样要注意一些细节,如顺序表大小是否为0,数据个数要进行删减等

void SLPopBack(SL* ps)//尾删
{
	assert(ps);//顺序表为空不能执行删除,如果空则会访问arr[-1]造成越界访问
	assert(ps->size);//size不能为空
	--ps->size;//此处直接将size的大小减一,同时也删除了数据
}

2.头删

和头插反着理解,我们要先删除第一个数据,再将顺序表整体前移一个单位

void SLPopFront(SL* ps)//头删
{
	assert(ps);//顺序表为空不能执行删除,如果空则会访问arr[-1]造成越界访问
	assert(ps->size);
	
	//数据整体往前挪动一位
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

5.打印顺序表

我们有的时候需要一边对顺序表进行操作,一边要测试我们的代码是否正确,除了进行调试外,我们还可以将顺序表打印出来直观地观察。

void SLPrint(SL ps)//打印,此处我们进行值传递即可
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
}

以上就是动态顺序表的基本操作,感谢各位的浏览。希望这篇文章对你理解和使用顺序表有帮助,如有不足或者错误请指出。文章来源地址https://www.toymoban.com/news/detail-853333.html

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

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

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

相关文章

  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(39)
  • 【数据结构】——顺序表详解

    大家好!当我们学习了动态内存管理后,就可以写一个管理数据的顺序表了!!! 顺序表的理解: 线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。 顺序表是在计算机内存

    2024年02月08日
    浏览(48)
  • 【数据结构】顺序表详解

    当我们写完通讯录后,顺序表肯定难不倒你,跟着小张一起来学习顺序表吧! 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就

    2024年02月10日
    浏览(46)
  • 数据结构:顺序表详解

    线性表(linear list)是n个具有 相同特性的数据元素的有限序列 。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是 在物理结构上并不一定是连续的 。 线性表在物理

    2024年02月14日
    浏览(34)
  • 【数据结构<顺序表>】C语言

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月05日
    浏览(39)
  • [数据结构 - C语言] 顺序表

    目录 1、线性表 2、顺序表 2.1 顺序表的概念 2.2 接口 3、接口实现 3.1 初始化 3.2 销毁 3.3 容量检测 3.4 打印数据 3.5 顺序表的头插 3.6 顺序表的尾插 3.7 顺序表的头删、尾删 3.8 顺序表查找 3.9 指定位置插入数据 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性

    2023年04月21日
    浏览(35)
  • 数据结构——顺序表(C语言)

    1.线性表 (1).线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列,字符串... (2).线性表在逻辑上是线性结构,也就是说连续的一条直线。但是在物理结构上并不是一定是连续的,线性表

    2024年02月13日
    浏览(47)
  • 数据结构之顺序表详解

    hello,大家好,今天的内容是关于顺序表的,其实之前也发过文章,但是那个时候水平还是差了一点,有些地方不是很详细,这次会把每个点都讲清楚,也当给自己在复习一遍。 顺序表在本质上就是数组,顺序表是连续的,我们的数组在内存上也是连续存储的,所以我们可以

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

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

    2024年02月11日
    浏览(37)
  • 数据结构(一):顺序表详解

    在正式介绍顺序表之前,我们有必要先了解一个名词:线性表。 线性表: 线性表是,具有n个相同特性的数据元素的有限序列。常见的线性表:顺序表、链表、栈、队列、数组、字符串... 线性表在逻辑上是线性结构,但在物理结构上并不一定是连续的。 1. 顺序表概念 顺序表

    2024年02月13日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包