【数据结构】顺序表的学习

前言:在之前我们学习了C语言的各种各样的语法,因此我们今天开始学习数据结构这一个模块,因此我们就从第一个部分来开始学习"顺序表"。

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力!
在这里插入图片描述


目录

  • 顺序表
    • 动态顺序表
      • 顺序表的初始化
      • 顺序表的销毁
      • 顺序表的空间容量检查
      • 顺序表的打印
      • 顺序表的尾增
      • 顺序表的头增
      • 顺序表的头删
      • 顺序表的尾删
      • 顺序表的选择插入
      • 顺序表的删除数据
      • 顺序表数据的查找
    • 练习


顺序表

  1. 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
  2. 顺序表一般可以分为两个部分,静态顺序表(使用定长数组存储元素)和动态顺序表(使用动态开辟的数组存储)。
  3. 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。

动态顺序表

首先我们创建一个结构体,去实现数据的动态存储。
在这里插入图片描述

代码如下:

typedef int SLDataype;//定义整型,方便后面进行数据的更改typedef struct SeqList //动态顺序表的开辟
{SLDataype* a;int size; //记录多少个有效数据int capacity; //记录空间有多大
}SL;

接下来我们就实现一个个接口来实现顺序表的基本功能

顺序表的初始化

顺序表的初始化十分简单,只需要将开辟的指针置为空指针,有效数据清零,空间容量清零即可。
代码如下:

void SLInit(SL* ps1)//顺序表的初始化
{assert(ps1);ps1->a = NULL;//将指针置为空指针ps1->size = 0;//数据清零ps1->capacity = 0;//容量清零
}

顺序表的销毁

同理,顺序表的销毁,只需要判断所开辟的空间是否已经是被释放了,和被置为空指针了,如果不是,就把所开辟的空间释放和数据清零即可。
代码如下:

void SLDestory(SL* ps1)//顺序表的销毁
{if (ps1->a != NULL)//判断该指针是否为空指针{free(ps1->a);//释放该指针所开辟的空间ps1->a = NULL;//置为空指针ps1->size = 0;//数据清零ps1->capacity = 0;//容量清0}
}

顺序表的空间容量检查

我们想要实现在所开辟的空间中,增加数据,就不可避免的需要去检查所开辟的空间的容量是否充足,如果不充足,我们就需要去增容,那该增加多少呢?增加太多,会导致空间的浪费,太少又会导致不断的扩容,这是一个双向的问题,因此这也没有什么十分固定的答案,通常来讲,一般增容一倍即可。

代码思路:在检查空间的时候,我们应该考虑传过来的指针是否是空指针,即是否是初始化后的顺序表,但realloc函数是可以对空指针进行扩容的,但是我们为了防止扩容失败,应该开辟一个新的结构体指针来接收这块空间,在开辟成功后重新覆盖回去。

代码实现:

void SLCheckCapacity(SL* ps1)//检查空间
{if (ps1->size == ps1->capacity)//判断记录的数据个数,与空间容量释放相同,相同的时候即空间满了,需要增容{int newCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;//判断开辟的空间是否是初始化的空间,如果是就让他容量为4,如果不是就开辟当前空间的两倍SLDataype* tmp = (SLDataype*)realloc(ps1->a, sizeof(SLDataype) * newCapacity);//创建一个新的结构体指针,在他的后面扩容,放在开辟失败后原本的数据也不见了//realloc 可以对空指针进行扩容if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;//将开辟后面的指针传给原本的地址ps1->capacity = newCapacity;//更新容量}
}

顺序表的打印

void SLPrint(SL* ps1)
{for (int i = 0; i < ps1->size; i++)//变量开辟的数据{printf("%d ", ps1->a[i]);//直接打印}printf("\n");
}

顺序表的尾增

代码思路:因为前面我们提到了size是有效数据的个数,也是指向的数组的最后一个元素的后一个的位置,因此只需要在此位置赋值即可,然后再让size往后偏移一位。

代码实现:

void SLPushBack(SL* ps1, SLDataype x)//尾增
{SLCheckCapacity(ps1);//检查空间容量ps1->a[ps1->size] = x;//因size指向的是数组最后一个元素的后一个元素,因此只需要直接在此位置赋值即可ps1->size++;//size继续指向后一个元素
}

现在我们实现了四个小的接口,忙活了这么久,我们来见一下效果,好歹听个响是吧。
效果图:

void TestSL1()//测试函数
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);//打印数据SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPrint(&s1);//打印数据SLDestory(&s1);//销毁顺序表
}int main()
{TestSL1();return 0;
}

在这里插入图片描述


顺序表的头增

代码实现思路:我们记录数据的最后一个位置为end,最后一个数据后面的一个数据位置为end+1,让end依次往后覆盖,然后end–直到end到起始位置即停止循环,具体思路如下图:
在这里插入图片描述
代码实现:

void SLPushFront(SL* ps1, SLDataype x)//头增
{SLCheckCapacity(ps1);//先检查数据//挪动数据int end = ps1->size - 1;//记录最后一个位置while (end >= 0)//end到起始位置时即覆盖完成{ps1->a[end + 1] = ps1->a[end];//将数据依次往后覆盖--end;}ps1->a[0] = x;//将数据赋值给起始位置就可以实现头增ps1->size++;//size++
}

当然了,不能白忙活,我们来测试一下这个函数,来看看效果如何

void TestSL2()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);//打印尾增的数据printf("上面是尾增的数据\n");printf("------------------------------\n");printf("下面是头增的数据\n");SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1,9);SLPrint(&s1);//打印头增的数据SLDestory(&s1);//销毁顺序表
}int main()
{//TestSL1();TestSL2();return 0;
}

在这里插入图片描述


顺序表的头删

代码思路:我们记录一个起始位置即数组的第二个元素记录为begin,让他往前面一个数据begin-1覆盖,然后再放入循环中不断覆盖,当运行到size的位置的时候停止循环具体思路如下图:
在这里插入图片描述
代码如下:

void SLPopFront(SL* ps1)//头删
{assert(ps1->size > 0);//判断传过来是是不是为空数据int begin = 1;//将起始位置置为1while (begin < ps1->size)//再起始位置等于size时即覆盖完成{ps1->a[begin - 1] = ps1->a[begin];//后面覆盖前面++begin;}ps1->size--;//size减减
}

当然,我们依然来听个响,听听声音,效果图如下:


void TestSL3()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1, 9);SLPrint(&s1);//打印原本的数据printf("上面是原本的数据\n");printf("--------------------------------------\n");printf("下面是删除后的数据\n");SLPopFront(&s1);//头删数据SLPopFront(&s1);SLPopFront(&s1);SLPrint(&s1);//打印删除后的数据SLDestory(&s1);//销毁顺序表
}int main()
{//TestSL1();//TestSL2();TestSL3();return 0;
}

在这里插入图片描述


顺序表的尾删

代码思路:我们可以通过前面的打印函数可以知道,我们是通过打印到size前面的一个下标来访问所有的元素,因此我们只需要让size往前面走一个,就可以把尾部的元素删除,可以看下图思路:
在这里插入图片描述

代码实现:

void SLPopBack(SL* ps1)//尾删
{//空if (ps1->size == 0)//判断删除的是否为空{return;}ps1->size--;//size--即可
}

我们依然来测试一下我们函数,看看效果是否成功实现,代码和效果图如下:

void TestSL4()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1, 9);SLPrint(&s1);//打印原本的数据printf("上面是原本的数据\n");printf("--------------------------------------\n");printf("下面是删除后的数据\n");SLPopBack(&s1);//尾删数据SLPopBack(&s1);SLPrint(&s1);//打印删除后的数据SLDestory(&s1);//销毁顺序表
}int main()
{//TestSL1();//TestSL2();//TestSL3();TestSL4();return 0;
}

在这里插入图片描述


顺序表的选择插入

代码思路:选择插入,即将一个值,任意插入到顺序表中的范围内,当然了口头总是不太好说清,我们对着下图来进行一一分析,我们可以记录一个end坐标记录数据的尾部,然后将值一一覆盖,pos为我们想要出入数据的位置,例如下图,当end走到pos的位置的时候,即可停止覆盖,这有点类似与我们前面的头删,将值pos之后的值全部往后挪动了一位,然后将最后重复的值被想插入的值覆盖即可。
在这里插入图片描述

代码实现:

void SLInsert(SL* ps1, int pos, SLDataype x)//插入数据
//pos是下标,size是数据个数,看作下标的话,他是最后一个数的下一个位置
{assert(ps1);//判断传来的值是否是空指针assert(pos >= 0 && pos <= ps1->size);//插入的值必须是再范围内(可以包括尾增)SLCheckCapacity(ps1);//检查空间// 挪动数据int end = ps1->size - 1;//找到尾坐标while (end >= pos){ps1->a[end + 1] = ps1->a[end];//将值一一覆盖,类似于头删--end;}ps1->a[pos] = x;//赋值ps1->size++;
}

我们依然来看看函数的效果是否实现,测试代码和效果图如下:

void TestSL5()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1, 9);SLPrint(&s1);//打印原本的数据printf("上面是原本的数据\n");printf("--------------------------------------\n");printf("下面是选择插入后的数据\n");SLInsert(&s1, 3, 99);SLInsert(&s1, 1, 2);SLPrint(&s1);//打印选择插入后的数据SLDestory(&s1);//销毁顺序表
}
int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();TestSL5();return 0;
}

在这里插入图片描述


顺序表的删除数据

代码思路:删除数据和选择插入的概念其实大差不差,首先也应当判断传过来的数是否是空指针,删除的数据在不在数据范围内,然后我们再通过图文来进行分析,如下图,先把删除的位置记录下来,当然了,和前面同理依次往前面覆盖,再打印的时候直接将size往前移一位即可把最后重复的值给去掉,达到顺序表的删除的功能。
在这里插入图片描述
函数代码:

void SLErase(SL* ps1, int pos)//删除数据
{assert(ps1);assert(pos >= 0 && pos < ps1->size);int begin = pos + 1;//记录删除数据后的位置while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];//依次覆盖++begin;}ps1->size--;
}

代码实现和函数实现效果图如下:

void TestSL6()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1, 9);SLPrint(&s1);//打印原本的数据printf("上面是原本的数据\n");printf("--------------------------------------\n");printf("下面是选择插入后的数据\n");SLErase(&s1, 3);//删除数据SLErase(&s1, 1);//删除数据SLPrint(&s1);//打印选择插入后的数据SLDestory(&s1);//销毁顺序表}int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();//TestSL5();TestSL6();return 0;
}

在这里插入图片描述


顺序表数据的查找

代码思路:顺序表数据的查找就过于简单了,我们只需要遍历数据,看看是否有对应的值,有则返回该数的下标,没有则返回**-1**。代码如下:

int SLFind(SL* ps1, SLDataype x)//顺序表数据的查找
{assert(ps1);//判断传来的数据是否是空指针for (int i = 0; i < ps1->size; i++)//遍历数组{if (ps1->a[i] == x)return i;//找到即返回坐标i}return -1;//没找到返回-1
}

函数测试与效果图:

void TestSL7()
{SL s1;//创建动态顺序表SLInit(&s1);//初始化顺序表SLPushBack(&s1, 2);//尾增数据SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 20);//头增的数据SLPushFront(&s1, 10);SLPushFront(&s1, 0);SLPushFront(&s1, 9);SLPrint(&s1);//打印原本的数据printf("上面是原本的数据\n");printf("--------------------------------------\n");printf("下面是选择插入后的数据\n");printf("该数的下标是:%d\n",SLFind(&s1, 2));SLDestory(&s1);//销毁顺序表
}
int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();//TestSL5();//TestSL6();TestSL7();return 0;
}

在这里插入图片描述
讲到这里,关于顺序表的基本内容实现全部讲完了,接下来我们来看一题目练习一下把!


练习

题目链接:
在这里插入图片描述

思路分析:看到这个题,大家都会想到一个很通俗易懂的方法,就是开辟一个辅助数组,将所有的数放进去,然后进去排序,当然我们今天是不讲这个方法的,因为这个方法的时间复杂度过于高。我们看到这个是一个非递减顺序,可以知道最大的数都放在了后面,因此我们可以将两个数中最后的元素拿出来依次比较,然后将较大的放在nums1中的最后面,依次类推,放到最后自然而然的可以将所有数进行排序,那怎么去实现它呢?看图说话,如下图,我们记录一个坐标i1i2分别记录下两个数组中的最后一个元素,然后依次进行比较,如果i1中的数较大就放在下标j的位置,反之则把i2放进去,且如果nums1中走完了,nums2还没有,就只需要将nums2中的数据单独拿出来,放再j所在的位置即可。
在这里插入图片描述
代码实现如下:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int i1 = m - 1;//记录第一个数组的尾坐标int i2 = n - 1;//第二个数组尾坐标int j = m + n - 1;//记录总元素的坐标while(i1 >= 0 &&  i2 >= 0){if(nums1[i1] > nums2[i2]){nums1[j--] = nums1[i1--]; }else{nums1[j--] = nums2[i2--];}}while(i2 >= 0){nums1[j--] = nums2[i2--];}
}

运行结果:
在这里插入图片描述


结语:今天的内容就到这里吧,谢谢各位的观看,如果有讲的不好的地方也请各位多多指出,作者每一条评论都会读的,谢谢各位。


🫵🫵🫵 祝各位接下来好运连连 💞

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/179257.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

能源管理系统为什么选择零代码开发平台?

市面上有很多能源管理系统&#xff0c;但是零代码开发能源管理系统却非常少。那为什么推荐选择零代码开发平台呢&#xff1f;因为很多企业缺少技术人员&#xff0c;但是却仍然需要数字化工具和流程推进业务和项目&#xff0c;解决能源管理技术人员不懂代码的矛盾问题&#xff0…

206. 反转链表、Leetcode的Python实现

博客主页&#xff1a;&#x1f3c6;看看是李XX还是李歘歘 &#x1f3c6; &#x1f33a;每天分享一些包括但不限于计算机基础、算法等相关的知识点&#x1f33a; &#x1f497;点关注不迷路&#xff0c;总有一些&#x1f4d6;知识点&#x1f4d6;是你想要的&#x1f497; ⛽️今…

教师减负神器

在传统的成绩管理模式中&#xff0c;教师需要手动输入、整理、分析成绩数据&#xff0c;工作量大且繁琐。这不仅耗费了教师大量的时间和精力&#xff0c;还容易出现错误。为了解决这个问题&#xff0c;我们可以通过各种代码和Excel来实现学生自助查询成绩的功能。 一、建立成绩…

Linux设置ssh免密登录

ssh连接其他服务器 基本语法 ssh 另一台机器的ip地址 连接后输入连接主机用户的密码&#xff0c;即可成功连接。 输入exit 可以登出&#xff1b; 由于我配置了主机映射所以可以不写ip直接写映射的主机名即可&#xff0c;Linux配置主机映射的操作为 vim /etc/hosts # 我自己…

BEM:css命名规范

BEM BEM(Block-Element-Modifier)&#xff0c;块、元素、修饰符&#xff0c;是一种CSS命名规范&#xff0c;旨在前端开发中创建可重用组件和代码共享的方法&#xff0c;使样式易于扩展&#xff0c;易于维护&#xff0c;易于理解 规范&#xff1a; 1、块&#xff08;Block&am…

4-注册中心

今天聊一下服务的注册与发现。大家先思考一个问题&#xff0c;如果有五六个服务&#xff0c;大概100个接口&#xff0c;要调用其中某一个接口&#xff0c;怎么调&#xff1f;首先你得知道服务所在的ip地址和端口吧&#xff0c;然后得知道服务的名字和需要的参数&#xff0c;再然…

口袋参谋:如何玩转手淘“问大家”?这招超好用!

​现在应该不会还有商家不知道&#xff0c;手淘“问大家”分析吧&#xff01; “问大家”模块对于转化率的影响非常关键&#xff0c;它的影响力不亚于买家秀&#xff0c;以前买家下单前都会去参考买家秀&#xff0c;现在买家更倾向于参考“问大家”然而&#xff0c;真正玩转“问…

win10系统nodejs的安装npm教程

1.在官网下载nodejs&#xff0c;https://nodejs.org/en 2&#xff0c;双击nodejs的安装包 3&#xff0c;点击 next 4&#xff0c;勾选I accpet the terms in…… 5&#xff0c;第4步点击next进入配置安装路径界面 6,点击next&#xff0c;选中Add to PATH &#xff0c;旁边…

集简云浏览器插件:无代码开发,实现CRM系统与用户运营的高效集成

无代码开发实现连接 集简云浏览器插件是一种强大的工具&#xff0c;可以帮助公司实现网页端数据的自动化同步&#xff0c;例如新闻媒体网站的数据抓取和采集&#xff0c;以及每天同步文章和视频等最新营销数据。这种插件的功能使得企业可以在没有编程技能的情况下实现无代码开…

【蓝桥杯选拔赛真题44】python小蓝晨跑 青少年组蓝桥杯python 选拔赛STEMA比赛真题解析

目录 python小蓝晨跑 一、题目要求 1、编程实现 2、输入输出 二、算法分析

国内某发动机制造工厂RFID智能制造应用解决方案

一、工厂布局和装备 国内某发动机制造工厂的装配车间布局合理&#xff0c;设备先进&#xff0c;在这个5万平方米的生产区域内&#xff0c;各个工位之间流程紧密&#xff0c;工厂采用了柔性设备&#xff0c;占比达到了67%&#xff0c;数控化率超过90%&#xff0c;自动化率达到了…

若依笔记(三):权限控制与数据隔离

目录 数据隔离/权限控制 用户/权限/部门/岗位 ​数据隔离 mybatis的maaper写法 注解和切面 前端路由拦截 已知若依单体的前端采用vue-element-admin&#xff0c;在前端的专栏系列vue-element-admin的动态路由已详细拆解&#xff0c;其最大特点是使用后端返回数据控制前端…

react和vue的区别

目录 react和vue区别的主要区别 react和vue区别的部分详情 1. 语法&#xff1a; 2. 组件化开发&#xff1a; 3. 状态管理&#xff1a; 4. 生态系统&#xff1a; 5. 性能特点&#xff1a; react和vue区别的主要区别 React和Vue是两种流行的JavaScript库&#xff0c;用于构…

pom.xml详解

我们在开发Java应用程序时&#xff0c;pom.xml文件是项目中的核心配置文件之一&#xff0c;它结合Maven实现对项目依赖的拉取&#xff0c;今天就详细了解一下pom.xml文件的配置 Maven是一种构建工具&#xff0c;它用于构建、管理和发布Java项目pom.xml文件包含了项目的所有重要…

降低边际成本:跨境电商的利润增长策略

在竞争激烈的跨境电商领域&#xff0c;降低成本是提高利润的关键。边际成本&#xff0c;即生产或销售一件额外商品所需的额外成本&#xff0c;在跨境电商中起到至关重要的作用。在本文中&#xff0c;我们将探讨降低边际成本的策略&#xff0c;以实现跨境电商的利润增长。 供应链…

苹果M3 Max芯片跑分曝光:GPU性能不及M2 Ultra

驱动中国2023年11月2日消息&#xff0c;近日&#xff0c;据外媒报道&#xff0c;在苹果 M3 芯片现身 GeekBench 跑分库之后&#xff0c;M3 Max 芯片也出现在该跑分平台上。 据悉&#xff0c;搭载 M3 Max 芯片的设备标识符为 Mac15,9&#xff0c;目前共有 4 条信息&#xff0c;其…

【Linux】Nignx的入门使用负载均衡动静分离(前后端项目部署)---超详细

一&#xff0c;Nignx入门 1.1 Nignx是什么 Nginx是一个高性能的开源Web服务器和反向代理服务器。它使用事件驱动的异步框架&#xff0c;可同时处理大量请求&#xff0c;支持负载均衡、反向代理、HTTP缓存等常见Web服务场景。Nginx可以作为一个前端的Web服务器&#xff0c;也可…

微信小程序:实现多个按钮提交表单

效果 核心步骤 通过data-type给不同按钮进行设置&#xff0c;便于很好的区分不同按钮执行不同功能 data-type"" 完整代码 wxml <form action"" bindsubmit"formSubmit"><button style"margin-bottom:5%" data-type"pa…

IDEA创建Springboot多模块项目

一、创建父模块 File --> New --> Project &#xff0c;选择 “ Spring Initalizr ” &#xff0c;点击 Next Next Next --> Finish 二、创建子模块 右键根目录&#xff0c;New --> Module 选择 “ Spring Initializr ”&#xff0c;点击Next 此处注意T…

Springboot JSP项目如何以war、jar方式运行

文章目录 一&#xff0c;序二&#xff0c;样例代码1&#xff0c;代码结构2&#xff0c;完整代码备份 三&#xff0c;准备工作1. pom.xml 引入组件2. application.yml 指定jsp配置 四&#xff0c;war方式运行1. 修改pom.xml文件2. mvn执行打包 五&#xff0c;jar方式运行1. 修改…