数据结构(初阶)第二节:顺序表

news/2024/6/16 11:06:00/文章来源:https://blog.csdn.net/zwznzje/article/details/137275978

从本文正式进入对数据结构的讲解,开始前友友们要有C语言的基础,熟练掌握动态内存管理结构体指针等章节,方便后续的学习。

顺序表(Sequence List)

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

        线性表是对存储具有某种共同点的数据集合的统称,顺序表和数组就是线性表的一种。顺序表的底层逻辑是利用数组实现的,但是相较于数组,顺序表的功能更齐全、丰富,顺序表新增了增、删、查、改等功能。

顺序表的分类

        根据定义格式的不同,顺序表又可分为静态顺序表动态顺序表

静态顺序表

#include <stdio.h>struct SeqList//定义顺序表
{int arr[10];//定长数组int size;//顺序表中有序的元素个数
};

静态顺序表的缺陷:空间给少了不够⽤,给多了造成空间浪费静态顺序表的定义方式已经基本被淘汰,现在大多采用动态顺序表的定义方式。

动态顺序表

        动态顺序表不同于静态顺序表,它很好的解决了空间浪费的问题,动态顺序在定义时不直接指明内存空间的大小(在初始化时有一定的空间),而是根据需求通过动态内存分配的方式开辟内存,等到存储空间不够时再扩容。

#include <stdio.h>typedef int SLDateType;typedef struct SeqList
{SLDateType* a;//动态数组int size;//有效元素个数int capacity;//已经开辟的空间大小
}SL;

在一开始定义时,使用typedef关键字对数据类型和结构体重命名,方便后续修改,比如说将存储int的数组改为存储char的数组,只需要将typedef int SLDateType中的int改为char即可,可以提高开发效率。

顺序表的功能

初始化

        在初始化时,我们选择malloc函数为数组分配内存,初始的内存空间一般定义为4个字节的大小。

注意:在对初始化函数传参时一定要传地址值,也就是参数一定是指针变量,不能直接将非指针变量传递过去,因为形参和实参不在同一块内存空间中,直接传参的话会导致初始化失败,程序报错。

void SLinit(SL* ps)
{ps->a = malloc((sizeof(SLDateType)) * 4);//初始内存4个字节if (ps->a == NULL)//分配内存失败{perror("malloc fail");return;}ps->capacity = 4;ps->size = 0;
}

扩容        

        在对顺序表进行扩容时应该首先判断该情况下是否需要扩容,即ps->capacity == ps->size,判断之后使用realloc函数进行扩容,每次扩容应为上一次的两倍。

void SLcheckCapcity(SL* ps)
{if (ps->capacity == ps->size)//判断是否需要扩容{SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);//一般每次扩容到上一次的2倍if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}

头插        

        在顺序表的头部插入一个元素,其余元素按顺序向后移动。

void SLpopFront(SL* ps, SLDateType x)
{assert(ps);SLcheckCapcity(ps);for (int i = ps->size; i >= 1; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;
}

尾插 

        顺序表尾部插入元素,在尾部插入时就一定要进行数组扩容。通过调用SLpopBack函数在尾部插入元素,ps->size最开始指向0索引,每次插入元素时size总在最后一个有效元素的下一位。

void SLpopBack(SL* ps, SLDateType x)
{assert(ps);SLcheckCapcity(ps);ps->a[ps->size++] = x;
}

头删 

     从顺序表头部删除元素,将元素按顺序前移,覆盖要删除的元素。

void SLpushFront(SL* ps)
{assert(ps && ps->size);//当顺序表为空时不用删除元素for (int i = 1; i < ps->size; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

尾删

void SLpushBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}

销毁

void SLdestory(SL* ps)
{free(ps);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}

打印顺序表

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

示例

int main()
{SL p;SLinit(&p);printf("这是尾插:");//尾插1 2 3 4 5SLpopBack(&p, 1);SLpopBack(&p, 2);SLpopBack(&p, 3);SLpopBack(&p, 4);SLpopBack(&p, 5);SLprint(&p);printf("这是头插:");//头插6 7 8SLpopFront(&p, 8);SLpopFront(&p, 7);SLpopFront(&p, 6);SLprint(&p);printf("这是头删:");//头删6 7 8SLpushFront(&p);SLpushFront(&p);SLpushFront(&p);SLprint(&p);printf("这是尾删:");//尾删3 4 5SLpushBack(&p);SLpushBack(&p);SLpushBack(&p);SLprint(&p);SLdestory(&p);return 0;
}

 运行结果:

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

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

相关文章

Docker 部署 FRP 内网穿透 实现端口映射

Frp 是一个专注于内网穿透的高性能的反向代理应用&#xff0c;支持 TCP、UDP、HTTP、HTTPS 等多种协议&#xff0c;且支持 P2P 通信。可以将内网服务以安全、便捷的方式通过具有公网 IP 节点的中转暴露到公网。 官网地址&#xff1a;https://github.com/fatedier/frp 准备工作…

MySql实战--MySQL为什么有时候会选错索引

前面我们介绍过索引&#xff0c;你已经知道了在MySQL中一张表其实是可以支持多个索引的。但是&#xff0c;你写SQL语句的时候&#xff0c;并没有主动指定使用哪个索引。也就是说&#xff0c;使用哪个索引是由MySQL来确定的。 不知道你有没有碰到过这种情况&#xff0c;一条本来…

C 练习实例97 - 读磁盘 写磁盘

题目&#xff1a;从键盘输入一些字符&#xff0c;逐个把它们送到磁盘上去&#xff0c;直到输入一个‘#’为止 在桌面新建一个hello.txt文件&#xff0c;内容示例&#xff1a; 代码&#xff1a; #include <stdio.h> #include <stdlib.h>int main() {FILE *fp; //文…

2024年MathorCup数学建模思路B题思路分享

文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间&#xff1a;2024…

视频号不入镜自动开播的机器人真的来啦

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。&#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精通…

Can‘t connect to server on ‘localhost‘ (10061)

问题&#xff1a;电脑关机重启后&#xff0c;连接不上mysql了&#xff0c;报错信息如下&#xff1a;2002 - Cant connect to server on localhost (10061)解决办法&#xff1a;很大的原因是mysql服务没有启动&#xff0c;需要你重启一下mysql&#xff1a; 以管理员的身份运行cm…

vivado 高级编程功能1

适用于 7 系列、 UltraScale 和 UltraScale FPGA 和 MPSoC 的回读和验证 为 7 系列器件生成已加密文件和已经过身份验证的文件 注释 &#xff1a; 如需获取其它信息 &#xff0c; 请参阅《使用加密确保 7 系列 FPGA 比特流的安全》 ( XAPP1239 ) 。 要生成加密比特流…

excel匹配替换脱敏身份证等数据

假如excel sheet1中有脱敏的身份证号码和姓名&#xff0c;如&#xff1a; sheet2中有未脱敏的数据数据 做法如下&#xff1a; 1、在sheet2的C列用公式 LEFT(A2,6)&REPT("*",8)&RIGHT(A2,4) 做出脱敏数据&#xff0c;用来与sheet1的脱敏数据匹配 2、在sheet…

曲面及其方程常见二次曲面记忆特点

1.椭圆柱面 方程特点:与椭圆方程一样,由于方程没有z,所以z可以取任何值. 2.椭圆面 方程特点:遮掉任何一坐标轴的项都是一个椭圆,所以在任何一个坐标平面的投影都是椭圆 3.圆锥面 方程特点:由一条直线旋转得到,两坐标的平方和是另一坐标平方的倍数 4.椭圆锥面 方程特点:集结椭圆…

如何确认前端的部署错误

进行前端部署的时候 通过pm2 list 发现进程报错&#xff0c;如何处理&#xff1f; 通过pm2 logs id 显示出具体的错误进行处理。

msvcp140.dll丢失相关问题的解决方法分享,如何快速修复msvcp140.dll

启动游戏或特定应用程序时出现"msvcp140.dll丢失"的问题。这种情况相对常见&#xff0c;不一定意味着系统存在严重bug。msvcp140.dll是一个动态链接库文件&#xff0c;通常与Visual C Redistributable相关&#xff0c;当它丢失时可能导致依赖该文件的程序无法正常运行…

2024最新华为OD机试试题库全 -【两个字符串间的最短路径问题】- C卷

1. 🌈题目详情 1.1 ⚠️题目 给定两个字符串,分别为字符串 A 与字符串 B。 例如 A字符串为 “ABCABBA”,B字符串为 “CBABAC” 可以得到下图 m * n 的二维数组,定义原点为(0,0),终点为(m,n),水平与垂直的每一条边距离为1,映射成坐标系如下图。 从原点 (0,0) 到 (0,…

crc校验

CRC(Cyclic Redundancy Check)&#xff0c;即循环冗余校验 理论知识 一个视频看懂CRC校验_哔哩哔哩_bilibili crc校验详解_12694841的技术博客_51CTO博客 crc的原理 基本原理&#xff1a;在K位信息码后再拼接R位的校验码&#xff0c;整个编码长度为N位&#xff0c;因此&a…

MySQL---事务

目录 一、事务简介 二、事务操作 1.未控制事务 2.事务控制一 3.控制事务二 三、事务的四大特性 四、并发事务问题 五、事务隔离级别 一、事务简介 事务 是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或…

Node.js-知识点学习总结归纳

Node.js-知识点学习总结归纳 安装nodenode运行方式通过Node.js直接运行js文件&#xff08;也就不用通过网页html了&#xff09;绝对路径调用:相对路径调用&#xff1a;直接运行js命令&#xff1a; Vscode控制台使用node运行js文件 安装node 这个就不用讲了吧&#xff0c;网上搜…

Linux——逻辑卷(LVM)管理

目录 LVM简介 LVM机制的基本概念 PV&#xff08;Physical Volume&#xff0c;物理卷&#xff09; VG&#xff08;Volume Group&#xff0c;卷组&#xff09; LV&#xff08;Logical Volume&#xff0c;逻辑卷&#xff09; PE&#xff08;Physical Extent&#xff0…

Maven依赖管理项目构建工具

一、Maven简介 1、为什么学习Maven 1.1、Maven是一个依赖管理工具 ①jar 包的规模 随着我们使用越来越多的框架&#xff0c;或者框架封装程度越来越高&#xff0c;项目中使用的jar包也越来越多。项目中&#xff0c;一个模块里面用到上百个jar包是非常正常的。 比如下面的例…

X射线源电流电压的实际影响

在进行实际实验的时候&#xff0c;感觉X射线电流电压好像对于成像质量的影响差不多&#xff0c;分不清楚了&#xff0c;这里记录一下&#xff0c;还没探索到原因。 80kv 500uA 功率&#xff1a;40W 90kv 300uA 功率&#xff1a;27W 90kev 600uA 110v 300uA

CSS面试题---基础

1、css选择器及优先级 选择器优先级&#xff1a;内联样式>id选择器>类选择器、属性选择器、伪类选择器>标签选择器、微元素选择器 注意&#xff1a; !important优先级最高&#xff1b; 如果优先级相同&#xff0c;则最后出现的样式生效&#xff1b; 继承得到的样式优先…

Modbus转Profinet网关解决主从设备间通信数据丢失难题

在接到现场关于Modbus转Profinet网关&#xff08;XD-MDPN100&#xff09;配置时出现信不稳定或数据丢失的问题的反馈后。对于现场反馈的Modbus转Profinet网关配置问题&#xff0c;特出专项答疑。 解决Modbus转Profinet网关&#xff08;XD-MDPN100&#xff09;通信不稳定或数据丢…