当前位置: 首页 > news >正文

【数据结构】---顺序表的实现

最近学校开始学习数据结构了,没事就手搓一个顺序表。

🌈线性表

线性表是n个具有相同特性的数据元素的有限序列,是一种实际中广泛使用的数据结构,常见的线性表有顺序表、链表、栈、队列、字符串。
线性表在逻辑上是线性结构,即连续的一条直线,但在物理上不一定连续,线性表在物理上存储时,通常以数组和链式结构的形式存储。

1.1啥是顺序表?

顺序表是在计算机内存中数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

1.2顺序表和数组的区别

两者的区别主要有:
1.顺序表可以实现动态增长,而普通数组的长度是固定的
2顺序表要求插入的数据在内存中是连续的,普通数组的数据存放可以不连续。

🌈顺序表功能实现:

2.1初始化顺序表SLInit()

在实现初始化之前,我们先来创建一个顺序表类型,其中包括顺序表起始位置的指针容量数据个数

静态顺序表类型:

#define N 100
typedef int SLDateType;
//类型命名//静态顺序表--N太小可能不够用
struct Seqlist
{//int a[N];//以后我不想用int类型的a[]SLDateType  a[N];int sz;
};

这个的致命缺点就是如果说存储的数据多,而N小的话就不行了,一般写线性表都是用动态版的。

动态顺序表类型:

#define N 100
typedef int SLDateType;typedef struct SeqList
{SLDateType* a;   //记录顺序表的起始位置int capacity;   //顺序表的容量int size;       //记录顺序表中的数据个数
}SL;

typedef为C语言的关键字,作用是为一种数据类型定义一个新名字

初始化函数SLInit():

void SLInit(SL* ps)
{assert(ps);    //判断是否为空,如果是空就不再进行了ps->a = NULL;   //指针赋值为空ps->capacity = ps->size = 0;  //整形赋值为0
}
上面的SL* ps之所以用到指针,就是因为在进行初始化的时候需要将模板也一并改掉。所以用指针找到原来的地址来改变模板。

2.2销毁顺序表SLDestory()

因为顺序表所用的内存空间是动态开辟在堆区的,所以我们在使用完后需要及时对其进行释放,避免造成内存泄漏

void SLDestory(SL* ps)
{assert(ps);   //断言,如果顺序表是空,就不在销毁了free(ps->a);      //这一步最为关键 ,把指针释放掉ps->a = NULL;   //指针赋值为空ps->capacity = ps->size = 0;  //整形赋值为0
}

其实销毁和初始化基本大差不差,最关键的一点就是销毁时有一个free来释放指针。

assert的好处

我们在其中运用到了assert函数,它包含在assert.h头文件中。
assert的好处就是判空,如果一个顺序表是空的,那就不需要进行初始化,和销毁,如果调用这两个函数就直接报错。可以让我们更快的找到漏洞。

2.3打印顺序表SLPrint()

需要打印的个数就是size的大小,然后一个for循环就可以了。

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

2.4顺序表的容量检查SLCheckCapacity()

检查顺序表的容量是否够用是顺序表的一个很关键的问题。其实检查容量的大小很好检查的,只要判断size和capacity的大小就可以了。

  • 如果capacity>size,就说明顺序表还没有存满。

  • 如果capacity=size,就说明需要扩容了。

void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size)  //需要扩容了{    //先扩容int newCapacity = ps->capacity == 0 ? 4 : 2 *ps->capacity;    //1//再让指针指向这块空间SLDateType* tmp = (SLDateType*)realloc(ps->a, newCapacity * sizeof(SLDateType));if (tmp == NULL)   {//如果扩容后的容量还是空,直接报错printf("realloc fail\n");exit(-1);} ps->a = tmp;     //3ps->capacity = newCapacity;}
}

这里面1中的代码可能有些不好理解,它的意思是如果说capacity是0的话,就给他4个空间,如果不是0,就把它的空间扩大2倍,然后复制给newCapacity。

2中的代码是新建一个指针,这个指针的目的是让原来的指针指向新开辟的空间。

接下来就该实现重点功能了。

🌈顺序表的增删实现

3.尾插功能SLPushBack()

尾插就是在顺序表的表尾插入数据,所以第一步是先判断顺序表的容量大小。容量不够就扩容。

//尾插
void SLPushBack(SL* ps, SLDateType x)
{//检查容量空间SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

之所以有两个参数,这两个参数中,参数1代表的是顺序表,参数2代表的是要插入的数。

4.头插功能SLPushFront()

要想在顺序表的表头插入数据,那么就需要先将顺序表原有的数据从后往前依次向后挪动一位,最后再将数据插入表头。

头插成功的前提是顺序表还有空间可供插入。所以第一步就是检查容量。容量够就进行插入操作。

//头插
void SLPushFront(SL* ps, SLDateType x)
{//检查容量SLCheckCapacity(ps);int end = ps->size - 1;  //size-1代表的就是顺序表存储的最后一个数while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

就是把顺序表往后挪一位,然后把第一位插入x就行了。

5.尾删功能SLPopBack()

尾删就是把最末尾数据给干掉,但是其实仔细想一下,直接把顺序表元素个数-1就行了。

//尾删
void SLPopBack(SL* ps)
{assert(ps->size > 0);//顺序表不为空才可以进行尾删,否则直接报错ps->size--;
}

6.头删功能SLPopFront()

头删功能和头插正好相反,头删是往前覆盖。

//头删
void SLPopFront(SL* ps)
{assert(ps->size > 0);int begin = 1;  //数据最起码是一个,不是空顺序表while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;  //数据减少一个
}

出现多删情况:

如果说把顺序表删成空后还继续删除,那会出现啥情况?

这个就会报错,之所以能检查出来错误就是上面咱们写的断言判断出来的。

其实这几种情况用到的不很多,最多的就是任意位置的插入删除操作。

🌈任意位置的插入删除

7.任意位置(pos)插入

这个pos是位置英文的缩写,在任意位置,我们首先就要指定位置pos.所以又加入一个形参。然后后移pos后面的数据。

对于这个插入来说,我们要进行两次断言:

首先·顺序表不为空,其次:指定的位置在顺序表中,不能小于0,不能大于size。

接下来就是往后移动。

//某位置插入
void SLInsert(SL * ps, int pos, SLDateType x)
{//先防止越界SLCheckCapacity(ps);assert(ps);assert(pos >= 0 && pos <= ps->size);//加上=,可实现尾插int end = ps->size - 1;//从后往前while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}

8.任意位置(pos)删除

这个跟前面的没事两样,就是加一个形参pos,然后把pos以后的数往前移动。

//某位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//不能等于int begin = pos;for (begin = pos; begin < ps->size - 1; begin++){ps->a[begin] = ps->a[begin + 1];}ps->size--;
}

🌈查改功能的实现

写到这一步,顺序表基本就写完了,只剩下几个功能了。

9.查找功能实现SLfind()

要想实现查找功能,还需要两个形参,但是第二个形参是操作者查找的对象,比如我要去顺序表中查找2,那第二个形参就是2。

如果找到就返回该数字,没找到返回-1.

//查找
int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;//没找到
}

10.修改功能SLModify()

//修改
int SLModify(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}

这里直接在pos位置上修改就行了。

🌈总结:

到这顺序表的大致功能函数就解决完了,但是还是要说一个问题--》

为啥第一个参数要用指针?

形参是实参的一份临时拷贝,修改功能函数里的形参并不会改变实参的任何数据。

就好比你去复印户口簿,复印完发现复印件的地址错了,你如果说你只改复印件上的,那下一次复印地址还是错的。所以必须要通过复印件连着户口本上的一起改成正确地址才行。

这个用指针就是上面的意思,要想改变顺序表中的数据,就要通过指针把顺序表上的内容一起改变。

上面的打印函数就可以不要指针,但是为了更准确和一致,把它也带上把。

相关文章:

【数据结构】---顺序表的实现

最近学校开始学习数据结构了&#xff0c;没事就手搓一个顺序表。&#x1f308;线性表线性表是n个具有相同特性的数据元素的有限序列&#xff0c;是一种实际中广泛使用的数据结构&#xff0c;常见的线性表有顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构&#xff0…...

JavaScript刷LeetCode拿offer-经典高频40题vaScript刷LeetCode拿offer-经典高频40题

工作太忙没有时间刷算法题&#xff0c;面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题&#xff0c;整理的内容有点长&#xff0c;建议先收藏&#xff0c;慢慢消化&#xff0c;在来年顺利拿到满意的offer。 1、[LeetCode] 两数之和 给定一个整数数组和一个目标值…...

动态规划,这将是你见过最详细的讲解

文章目录一、为什么要讲动态规划呢&#xff1f;二、什么是动态规划三、感受一下递归算法、备忘录算法、动态规划递归算法带备忘录的递归解法&#xff08;自定向下&#xff09;自底向上的动态规划四、动态规划的解题套路1. 穷举分析2. 确定边界3. 确定最优子结构4. 写出状态转移…...

【服务器数据恢复】FreeNAS层UFS2文件系统数据恢复案例

服务器数据恢复环境&#xff1a; Dell存储服务器&#xff0c;采用esxi虚拟化系统&#xff0c;esxi虚拟化系统里有3台虚拟机&#xff1b;上层iSCSI使用FreeNAS构建&#xff0c;通过iSCSI方式实现FCSAN功能&#xff1b;FreeNAS层采用UFS2文件系统。 esxi虚拟化系统里有3台虚拟机中…...

Zookeeper安装和基本使用

目录标题一、下载二、安装三、启动客户端测试四、使用zk一、下载 注意&#xff1a;自zk3.5.5版本以后&#xff0c;已编译的jar包&#xff0c;尾部有bin&#xff0c;应该使用的是apache-zookeeper-3.8.0-bin.tar.gz。&#xff0c;因此在下载高版本时&#xff0c;因该下载后缀带b…...

字节面试惨败,闭关修炼再战美团(Android 面经~)

作者&#xff1a;王旭 前言 本人从事Android 开发已经有5年了&#xff0c;受末日寒气影响&#xff0c;被迫在家休整&#xff0c;事后第一家选择字节跳动面试&#xff0c;无奈的被面试官虐得“体无完肤”&#xff0c;好在自己并未气馁&#xff0c;于是回家开始回家进行闭关修炼…...

【机器学习实战】七、梯度下降

梯度下降 一、线性回归 线性回归算法推导过程可以基于最小二乘法直接求解&#xff0c;但这并不是机器学习的思想&#xff0c;由此引入了梯度下降方法。本文讲解其中每一步流程与实验对比分析。 1.初始化 import numpy as np import os %matplotlib inline import matplotli…...

什么是极速文件传输,极速文件传输如何进行大文件传输

当谈到大文件传输时&#xff0c;人们总是担心大数据文件的大小以及将它们从一个位置交换到另一个位置需要多长时间。由于数据捕获高分辨率视频和图像的日益复杂&#xff0c;文件的大小不断增加。数据工作流在地理上变得越来越分散。在一个位置生成的文件在其他位置处理或使用。…...

Spring Boot 日志

目录 1.概述 2.切换日志实现 3.使用 3.1.日志级别 3.3.日志离线 3.4.详细定制 1.概述 由一些历史原因&#xff0c;JAVA领域存在有很多日志框架&#xff0c;如Log4j、Logback、log4j2。 log4j是Java日志框架的元老&#xff0c;在log4j被Apache Foundation收入门下之后&a…...

好用的研发管理看板工具有哪些?10款主流看板管理软件盘点

10大企业看板工具软件&#xff1a;1.软件开发项目看板 PingCode&#xff1b;2.通用看板软件 Worktile&#xff1b;3.开源看板软件 Wekan&#xff1b;4.免费看板软件 Trello&#xff1b;5.个人和小团队的看板软件 Todoist &#xff1b;6.开源免费看 Kanboard&#xff1b;7.面向个…...

【软考系统架构设计师】2022下案例分析历年真题

【软考系统架构设计师】2022下案例分析历年真题 【软考系统架构设计师】2022下案例分析历年真题【软考系统架构设计师】2022下案例分析历年真题2022下案例分析历年真题第一题&#xff08;25分&#xff09;2022下案例分析历年真题第二题&#xff08;25分&#xff09;2022下案例分…...

Java skill - @JsonAlias 和 @JsonProperty

Java skill - JsonAlias 和 JsonPropertyJava skill系列目录&#xff1a;JsonAlias 和 JsonProperty使用 JsonProperty 的麻烦场景&#xff1a;使用 JsonAlias 应对麻烦场景&#xff1a;Java skill系列目录&#xff1a; 【Java skill - 统计耗时用StopWatch】 【Java skill - …...

【实际开发18】- 静态 3

目录 1. 调试与评估 2. 单元测试的管理 1. 单元测试的文档 3. 系统集成的模式与方法 1. 集成测试前的准备 2. 集成测试的模式 3. 大棒集成方法 ( Big-bang Integration) 4. 自顶向下和自底向上集成方法 1. 自顶向下法 ( Top-down Integration ) 2. 自底向上法 ( Bott…...

【swagger2】开发api文档

文章目录一、swagger2 简介背景Open API ???swagger2的作用swagger2常用工具组件&#xff1a;二、Springfox三、springBoot使用swagger2&#xff08;简单示例&#xff09;四、Swagger-UI使用五、配置文件1、配置类&#xff1a;给docket上下文配置api描述信息2、配置类&#…...

Github 上如何提交 pull request

什么是复刻&#xff08;forking&#xff09;? 我们可以通过复刻操作将喜爱的仓库保存自己的Github账户中&#xff0c;以便独立地对其进行操作。 通过复刻&#xff0c;我们可以得到包含完整版本历史的目标仓库的实例&#xff0c;之后可以对复刻得到的仓库进行任意操作而不会影响…...

Redis面试知识

概述 Redis 是速度非常快的非关系型(NoSQL)内存键值数据库,可以存储键和五种不同类型的值之间的映射。 键的类型只能为字符串,值支持五种数据类型:字符串、列表、集合、散列表、有序集合。 Redis 支持很多特性,例如将内存中的数据持久化到硬盘中,使用复制来扩展读性能…...

Spring面试重点(四)——Spring事务

Spring事务 事务的方式 spring中使用事务有两种方式&#xff0c;一种是编程式事务&#xff0c;一种是声明式事务。编程式事务推荐使用TransactionTemplate&#xff0c;实现TransactionCallback接口&#xff0c;需要编码实现&#xff1b;声明式事务只需要在函数增加注解Transa…...

♡ — MySQL 存储引擎

MySQL 存储引擎架构 MySQL 存储引擎采用的是插件式架构&#xff0c;支持多种存储引擎&#xff0c;我们甚至可以为不同的数据库设置不同的存储引擎以适应不同场景的需要&#xff1b;存储引擎是基于表的&#xff0c;而不是数据库。 MyISAM 和 InnoDB 的区别 MySQL 5.5 之前&am…...

大数据技术架构(组件)34——Spark:Spark SQL--Optimize

2.2.3、Optimize2.2.3.1、SQL3.3.1.1、RB1、Join选择在Hadoop中&#xff0c;MR使用DistributedCache来实现mapJoin。即将小文件存放到DistributedCache中&#xff0c;然后分发到各个Task上&#xff0c;并加载到内存中&#xff0c;类似于Map结构&#xff0c;然后借助于Mapper的迭…...

Zookeeper实现分布式锁

文章目录ZK节点类型watch监听机制Zookeeper实现分布式锁锁原理创建锁的过程释放锁的过程ZK锁的种类代码实现Zookeeper是一个开源的分布式协调服务&#xff0c;是一个典型的分布式数据一致性解决方案。 分布式应用程序可以基于Zookeeper实现诸如数据发布/订阅&#xff0c;负载均…...

MFC 添加重新启动管理器支持

重启管理器是添加到 Visual Studio for Windows Vista 或更高版本操作系统的功能 如果发生意外关闭或重启&#xff0c;重新启动管理器将为你的应用程序添加支持。 重新启动管理器的行为取决于应用程序的类型。 如果你的应用程序是文档编辑器&#xff0c;则重新启动管理器让应用…...

一文带你深刻的进入Python,并且了解Python的优缺点

最近几年Python被吹的神乎其神&#xff0c;很多同学都不清楚Python到底能干什么&#xff1f;就盲目去学习Python,今天我就Python的应用领域来简单盘点一下&#xff0c;让想学习Python 的同学找对方向不迷茫。 2. Python 的特点 这里就谈谈自己的看法&#xff0c;首先 Python是…...

别具一格,原创唯美浪漫情人节表白专辑,(复制就可用)(html5,css3,svg)表白爱心代码(4)

别具一格,独此一家&#xff0c;原创唯美浪漫情人节表白专辑 不一样的惊喜哦~&#xff01;&#xff08;html5,css3,svg)表白爱心代码&#xff08;复制就可用&#xff09;&#xff08;4&#xff09; 目录 款式四&#xff1a;时光的记忆款 1、拷贝完整源代码 2、更新时光盒所…...

编译原理—翻译方案、属性栈代码

系列文章戳这里&#x1f447; 什么是上下文无关文法、最左推导和最右推导如何判断二义文法及消除文法二义性何时需要消除左递归什么是句柄、什么是自上而下、自下而上分析什么是LL(1)、LR(0)、LR(1)文法、LR分析表LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系编译原理第三章习…...

链表

一、从尾到头打印链表题目&#xff1a;输入一个链表&#xff0c;按链表从尾到头的顺序返回一个ArrayList。解题思路&#xff1a;使用栈作为中转&#xff0c;可以实现倒置打印classSolution { public:vector<int> printListFromTailToHead(ListNode* head){//使用栈完成中…...

CSS 样式优先级

CSS 样式优先级决定了最终呈现在浏览器中的样式是哪一组样式&#xff0c;在多组样式中有冲突时&#xff0c;最终呈现在浏览器中的样式是具有最高优先级的样式。 CSS 样式优先级顺序如下&#xff1a; 内联样式 > 内部样式 > 外部样式 !important > 内联样式 > ID…...

SpingMVC获取请求参数

通过ServletAPI获取请求参数将HttpServletRequest作为控制器方法的形参&#xff0c;此时HttpServletRequest类型的参数表示封装了当前请求的请求报文的对象。html<form th:action"{/param/servletAPI}" method"post">用户名&#xff1a;<input ty…...

微搭使用笔记(二)微搭低代码平台介绍及基础使用

概述 官网地址&#xff1a; 官网 官方文档&#xff1a; 官方文档 FAQ: FAQ 腾讯云微搭低代码是一个高性能的低代码开发平台&#xff0c;用户可通过拖拽式开发&#xff0c;可视化配置构建 PC Web、H5 和小程序应用。支持打通企业内部数据&#xff0c;轻松实现企业微信管理、工…...

CountDownLatch的定义、使用 、原理

一、定义 CountDownLatch的作用很简单&#xff0c;就是一个或者一组线程在开始执行操作之前&#xff0c;必须要等到其他线程执行完才可以。我们举一个例子来说明&#xff0c;在考试的时候&#xff0c;老师必须要等到所有人交了试卷才可以走。此时老师就相当于等待线程&#xff…...

《Terraform 101 从入门到实践》 Terraform在公有云Azure上的应用

《Terraform 101 从入门到实践》这本小册在南瓜慢说官方网站和GitHub两个地方同步更新&#xff0c;书中的示例代码也是放在GitHub上&#xff0c;方便大家参考查看。 简介 Azure是微软的公有云&#xff0c;它提供了一些免费的资源&#xff0c;具体可以查看&#xff1a; https:/…...