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

数据结构与算法--顺序表(Java)

news 来源：原创 2024/9/20 15:02:10

📝个人主页🌹：誓则盟约
⏩收录专栏⏪：Java SE
🤡往期回顾🤡：Java SE--基本数据类型（详细讲解）
🌹🌹期待您的关注 🌹🌹

什么是顺序表？

  • 顺序表是一种线性表的数据结构。
  • 顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素。

顺序表的主要特点：

  1. 逻辑上相邻的元素在物理位置上也相邻。
  2. 可以随机访问表中的任意元素，通过元素的位置序号可以在 O(1) 的时间复杂度内直接获取对应元素。
  3. 插入和删除操作的效率相对较低。例如，在顺序表的中间位置插入一个元素，需要移动大量后续元素，时间复杂度为 O(n) ；删除操作同理。

顺序表的优点：

  1. 随机访问速度快，能够快速获取指定位置的元素。
  2. 存储密度高，不需要额外的指针来链接元素。

顺序表的缺点：

  1. 长度固定，不易扩展。
  2. 插入和删除操作可能涉及大量元素的移动，效率较低。

        举个例子，如果有一个顺序表存储了学生的成绩 [85, 90, 78, 95, 88] ，如果要获取第三个学生的成绩，直接通过索引 2 就能快速得到 78 。但如果要在第二个位置插入一个新成绩 80 ，就需要将后面的元素 90, 78, 95, 88 依次向后移动一位，然后再插入 80 。

        顺序表在很多程序设计中都有应用，比如简单的数组实现、一些对随机访问要求较高而插入删除操作较少的场景等，今天我们用java来简单实现一下顺序表。

构造方法：    

    首先，构造一个顺序表，需要int capacity 表示顺序表的内存大小(这里先传入一个值作为参数，后面内存不够用我们会有专门申请内存的方法)、int size表示表里面元素的个数、Object [] array 来命名这个顺序表，这时候一个最基本的顺序表就被构造出来了，以下是代码实现：

public class Linear_List<E> {private  int capacity = 10;private int size=0;private Object [] array = new Object [capacity];

添加方法：

        要对顺序表array进行添加操作，需要传入两个参数 泛型 element 以及 int index，代表在index下标插入 泛型 element。

        注意：这里需要判断 index 和 size 的大小，如果index<0 || index>size,则理应抛出错误。

        在index位置插入元素，只需要将原来index以及index后面的元素往后移一位，空出来的位置给element即可。下面是添加方法的代码实现：

public void add(E element , int index) {if (index<0 || index>size)throw new IndexOutOfBoundsException("Index out of bounds");for (int i = size; i >index; i--) {array[i] = array[i-1];}array[index] = element;size++;}

        但是当顺序表中存储的元素数量达到当前分配的存储空间上限时，就需要进行扩容。具体来说，常见的情况有：

  • 持续向顺序表中添加元素，导致已分配的存储空间被填满。

        例如，最初分配的顺序表空间能存储 10 个整数，当已经存储了 10 个整数后，如果还需要继续添加新的整数，就需要扩容。

  • 事先无法准确预估元素数量，且实际存储的元素数量超出了初始的预计。

        假设一个用于存储用户订单信息的顺序表，由于促销活动导致订单数量大幅增加，超出了初始分配的空间。

  • 业务需求发生变化，导致需要存储更多的元素。

        比如原本的系统只需要存储一个月内的交易记录，但业务调整后需要存储半年甚至更长时间的交易记录，原有的顺序表空间可能就不够了。

        在进行扩容时，通常会重新分配一块更大的连续存储空间，并将原有的元素复制到新的空间中。扩容的策略可以是按照一定的比例增加空间，例如每次扩容为原来的两倍；也可以是增加固定的大小，如每次增加一定数量的存储单元，原来的那块空间也并不会造成空间浪费，通常会被JVM的垃圾回收机制自动回收。

        通常把扩容操作放在添加方法内部，因为在添加元素时才会有可能需要用到扩容操作，以下是添加了扩容操作的添加方法的代码实现：

public void add(E element, int index) {// 如果索引不在有效范围内，抛出异常if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index out of bounds");// 如果当前元素数量达到容量，进行扩容操作if (size >= capacity) {  int newCapacity = capacity * 2;  // 新容量为原容量的两倍Object[] newArray = new Object[newCapacity];  // 创建新的数组System.arraycopy(array, 0, newArray, 0, size);  // 将原数组内容复制到新数组array = newArray;  // 更新数组引用capacity = newCapacity;  // 更新容量}// 将指定索引及之后的元素向后移动一位for (int i = size; i > index; i--) {array[i] = array[i - 1];}array[index] = element;  // 在指定索引位置插入新元素size++;  // 元素数量加 1
}

删除方法：

        首先，要检查删除操作中指定的索引是否合法。如果索引小于 0 或者大于等于顺序表的当前元素数量，就会抛出一个索引越界的异常，因为这样的索引不存在有效的元素可删除。

        若索引合法，就将指定索引位置之后的元素依次向前移动一位，覆盖要删除的元素位置。然后，把原本顺序表的最后一个位置设置为 null，并将顺序表的元素数量减 1，表示完成了一个元素的删除操作。以下是删除方法的代码实现：

public E remove(int index) {if (index<0 || index>size-1)  throw new IndexOutOfBoundsException("Index out of bounds");E key = (E) array[index];for (int i = index; i <size; i++) {array[i] = array[i+1];}size--;return key;}

判空和get方法：

        判空方法通常用于判断顺序表是否为空。这可以通过检查顺序表中元素的数量来实现。如果元素数量为 0 ，则认为顺序表为空。

        get方法用于获取顺序表中指定索引位置的元素。在实现时，需要先检查索引的合法性，如果索引不合法（小于 0 或大于等于元素数量），则抛出异常。如果索引合法，就返回该索引位置的元素。以下是两种方法的代码实现：

 public boolean is_Empty(){return size==0;}public E get(int index) {if (index<0 || index>size-1)  throw new IndexOutOfBoundsException("Index out of bounds");return (E) array[index];}

转字符串输出(toString)方法：

        toString方法其主要目的是将顺序表的相关信息以字符串的形式进行展示。通常会先获取顺序表中实际存储元素的数组部分，并将其转换为字符串表示。同时，还会获取顺序表中当前元素的数量。

        当调用顺序表对象的 toString 方法时，就能得到一个清晰反映顺序表内部状态的字符串描述，方便进行输出、调试或其他需要以字符串形式获取顺序表信息的操作。以下是toString方法的代码实现：

    public String toString() {StringBuilder builder = new StringBuilder();for (int i = 0; i < size; i++){builder.append(array[i]).append(" "); }return builder.toString();}

完整代码实现：

public class Linear_List<E> {private  int capacity = 10;private int size=0;private Object [] array = new Object [capacity];public void add(E element , int index) {if (index<0 || index>size)throw new IndexOutOfBoundsException("Index out of bounds");if (size>=capacity){  // 扩容int newCapacity = capacity*2;Object[] newArray = new Object[newCapacity];System.arraycopy(array,0,newArray,0,size);array = newArray;capacity = newCapacity;}for (int i = size; i >index; i--) {array[i] = array[i-1];}array[index] = element;size++;}public E remove(int index) {if (index<0 || index>size-1)  throw new IndexOutOfBoundsException("Index out of bounds");E key = (E) array[index];for (int i = index; i <size; i++) {array[i] = array[i+1];}size--;return key;}public boolean is_Empty(){return size==0;}public E get(int index) {if (index<0 || index>size-1)  throw new IndexOutOfBoundsException("Index out of bounds");return (E) array[index];}public String toString() {StringBuilder builder = new StringBuilder();for (int i = 0; i < size; i++) { builder.append(array[i]).append(" "); }return builder.toString();}
}

“静静地目送，享受这一刻，在混乱之中。”——《xingyu_xuan》

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • java如何同时继承接口和抽象类
  • qt做的分页控件
  • Dubbo 参数调优指南
  • 【数据结构】栈（基于数组、链表实现 + GIF图解 + 原码）
  • 【开源库学习】libodb库学习（十一）
  • 【ROS2】演示:为有损网络使用服务质量设置
  • pytest使用
  • 2024年网络安全焦点：新兴威胁与防御技术创新
  • SQL Server 设置端口
  • 记录使用el-form的resetFields时遇到的表单数据回显失败的问题，去除nextTick解决
  • C#初级——条件判断语句、循环语句和运算符
  • 文件系统中元数据的隐患——缓存
  • prompt面试三道题
  • mysql的主从复制和读写分离
  • Java二十三种设计模式-代理模式模式（8/23）
  • 【译】React性能工程(下) -- 深入研究React性能调试
  • CSS进阶篇--用CSS开启硬件加速来提高网站性能
  • IDEA常用插件整理
  • iOS | NSProxy
  • JavaScript异步流程控制的前世今生
  • js 实现textarea输入字数提示
  • leetcode388. Longest Absolute File Path
  • oldjun 检测网站的经验
  • scrapy学习之路4(itemloder的使用)
  • spring学习第二天
  • Yeoman_Bower_Grunt
  • 百度小程序遇到的问题
  • 创建一种深思熟虑的文化
  • 从PHP迁移至Golang - 基础篇
  • 高度不固定时垂直居中
  • 容器服务kubernetes弹性伸缩高级用法
  • 通过git安装npm私有模块
  • 微信开放平台全网发布【失败】的几点排查方法
  • 温故知新之javascript面向对象
  • 小程序开发中的那些坑
  • 小试R空间处理新库sf
  • ​​​​​​​ubuntu16.04 fastreid训练过程
  • ​520就是要宠粉，你的心头书我买单
  • ​软考-高级-系统架构设计师教程（清华第2版）【第9章 软件可靠性基础知识（P320~344）-思维导图】​
  • #每日一题合集#牛客JZ23-JZ33
  • #微信小程序（布局、渲染层基础知识）
  • (poj1.3.2)1791(构造法模拟)
  • （python）数据结构---字典
  • （Redis使用系列） Springboot 实现Redis 同数据源动态切换db 八
  • (附源码）spring boot网络空间安全实验教学示范中心网站 毕业设计 111454
  • （附源码）springboot工单管理系统 毕业设计 964158
  • （附源码）springboot猪场管理系统 毕业设计 160901
  • （附源码）ssm户外用品商城 毕业设计 112346
  • （十二）devops持续集成开发——jenkins的全局工具配置之sonar qube环境安装及配置
  • （转）Android学习笔记 --- android任务栈和启动模式
  • ***微信公众号支付+微信H5支付+微信扫码支付+小程序支付+APP微信支付解决方案总结...
  • *1 计算机基础和操作系统基础及几大协议
  • .NET 8.0 发布到 IIS
  • .NET Framework 服务实现监控可观测性最佳实践
  • .NET/ASP.NETMVC 深入剖析 Model元数据、HtmlHelper、自定义模板、模板的装饰者模式（二）...