【数据结构与算法】顺序表的原理及实现

news/2024/9/18 6:25:40/

1.什么是顺序表

  • 顺序表是用一段物理地址连续的存储单元进行存储元素的线性结构，通常是以数组进行存储。
  • 通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

在这里插入图片描述

2.顺序表的实现

判断顺序表是否为空表public boolean isEmpty()
判断顺序表是否满public boolean ifFull()
向顺序表中添加元素public void add(T ele)
删除指定位置的元素public void delete(int index)
删除指定的元素public void remove(T ele)
在指定的位置添加元素public void add(int index,T ele)
修改数据public void update(int index,T ele)
获取顺序表的长度public int size()
获取对应位置的元素public T getIndex(int index)
遍历输出顺序表public void show()

在这里插入图片描述

（1）定义构造方法

public class SequenceList<T> {/*** 定义默认的数组长度*/private final static int DEFAULT_SIZE = 10;/*** 定义存储数组*/private T[] list;/*** 定义顺序表的有效元素个数*/private int num;/*** 定义数组的长度*/private int size;/*** 无参构造方法，默认长度10*/public SequenceList(){list = (T[]) new Object[DEFAULT_SIZE];this.size = DEFAULT_SIZE;this.num=0;}/*** 有参构造，长度为size* @param size*/public SequenceList(int size){list = (T[]) new Object[size];this.size = size;this.num=0;}
}

（2）判断队列是否为空

    /*** 顺序表的判空实现* @return*/public boolean isEmpty(){//如果num == 0的时候return num==0;}

（3）判断队列是否为满

    /*** 顺序表的判满实现* @return*/public boolean isFull(){//如果num（当前顺序表元素个数 == 顺序表的长度时）return num==list.length;}

（4）遍历顺序表元素

    /*** 顺序表的遍历*/public void show(){for(int i=0;i<num;i++){System.out.println(list[i]);}}

（5）向顺序表中添加元素

    /*** 顺序表添加元素，添加到指定的下标下* @param index* @param ele*/public void add(int index,T ele){if(isFull()){//这块后续会加上扩容的方法System.out.println("当前集合元素已满");}//如果index 为 -1 表示直接插入末尾if(index == -1){list[num++]=ele;return;}//不为-1的话，则插入到指定的下标if(index<0 || index>num){System.out.println("参数不合法");}//把i的位置腾出来 i位置的元素全部向后移动一位if (num - index >= 0) System.arraycopy(list, index, list, index + 1, num - index);//直接插入元素list[i]=ele;num++;}/*** 顺序表添加元素，添加到末尾* @param ele*/public void add(T ele){this.add(-1,ele);}

（6）获取元素的下标索引

    /*** 获取元素的下标索引* @param ele* @return*/public int indexOf(T ele){for (int i = 0; i < list.length; i++) {if(list[i].equals(ele)){return i;}}return -1;}

（7）向顺序表中删除指定元素

    /*** 删除指定位置的元素* @param ele*/public void delete(int index){if(index <0 || index>num){System.out.println("参数不合法");}//把每个元素向前移动一位if (num - (index + 1) >= 0) System.arraycopy(list, index + 1, list, index + 1 - 1, num - (index + 1));num--;}/*** 删除指定元素* @param ele*/public void remove(T ele){//获取元素下标索引int index = this.indexOf(ele);if(index == -1){System.out.println("当前元素不存在:"+ele);}//删除元素this.delete(index);}

（8）修改指定下标元素

    /*** 修改指定下标元素* @param index* @param ele*/public void update(int index,T ele){list[index]=ele;}

（9）获取有效元素个数

    /*** 获取元素个数* @return*/public int getNum(){return num;}

（10）顺序表扩容

    /*** 扩充顺序表容量* 私有方法，不对外提供，在插入元素时，判断是否已经满的情况下调用* 如果顺序表的元素已经满了，则调用扩容方法* @param size*/private void reList(int size){//保存之前的顺序表T []temp=list;//创建新的顺序表list = (T[]) new Object[size];//拷贝元素System.arraycopy(temp, 0, list, 0, temp.length);}

# 修改add方法中判断元素是否已经满了的逻辑
# 如果元素已经满了，则进行扩容原长度的2倍
# 同时修改容量的大小
if(isFull()){this.size = list.length*2;reList(this.size);
}

（11）获取顺序表的最大容量

    /*** 返回顺序表容量大小* @return*/public int size(){return size;}

（12）整体顺序表实现代码

/*** @description 顺序表数据结构实现* @author lixiang* @param <T>*/
public class SequenceList<T> {/*** 定义默认的数组长度*/private final static int DEFAULT_SIZE = 10;/*** 定义存储数组*/private T[] list;/*** 定义顺序表的有效元素个数*/private int num;/*** 定义数组的长度*/private int size;/*** 无参构造方法，默认长度10*/public SequenceList(){list = (T[]) new Object[DEFAULT_SIZE];this.size = DEFAULT_SIZE;this.num=0;}/*** 有参构造，长度为size* @param size*/public SequenceList(int size){list = (T[]) new Object[size];this.size = size;this.num=0;}/*** 顺序表的判空实现* @return*/public boolean isEmpty(){return num==0;}/*** 顺序表的判满实现* @return*/public boolean isFull(){return num==list.length;}/*** 顺序表的遍历*/public void showNum(){for(int i=0;i<num;i++){System.out.println(list[i]);}}/*** 顺序表添加元素，添加到指定的下标下* @param index* @param ele*/public void add(int index,T ele){if(isFull()){//这块后续会加上扩容的方法this.size = list.length*2;reList(this.size);}//如果index 为 -1 表示直接插入末尾if(index == -1){list[num++]=ele;return;}//不为-1的话，则插入到指定的下标if(index<0 || index>num){System.out.println("参数不合法");}//把i的位置腾出来 i位置的元素全部向后移动一位if (num - index >= 0) System.arraycopy(list, index, list, index + 1, num - index);//直接插入元素list[index]=ele;num++;}/*** 顺序表添加元素，添加到末尾* @param ele*/public void add(T ele){this.add(-1,ele);}/*** 删除指定位置的元素* @param ele*/public void delete(int index){if(index <0 || index>num){System.out.println("参数不合法");}//把每个元素向前移动一位if (num - (index + 1) >= 0) System.arraycopy(list, index + 1, list, index + 1 - 1, num - (index + 1));num--;}/*** 删除指定元素* @param ele*/public void remove(T ele){//获取元素下标索引int index = this.indexOf(ele);if(index == -1){System.out.println("当前元素不存在:"+ele);}//删除元素this.delete(index);}/*** 获取元素的下标索引* @param ele* @return*/public int indexOf(T ele){for (int i = 0; i < list.length; i++) {if(list[i].equals(ele)){return i;}}return -1;}/*** 修改指定下标元素* @param index* @param ele*/public void update(int index,T ele){list[index]=ele;}/*** 获取元素个数* @return*/public int getNum(){return num;}/*** 扩充顺序表容量* 私有方法，不对外提供，在插入元素时，判断是否已经满的情况下调用* 如果顺序表的元素已经满了，则调用扩容方法* @param size*/private void reList(int size){//保存之前的顺序表T []temp=list;//创建新的顺序表list = (T[]) new Object[size];//拷贝元素System.arraycopy(temp, 0, list, 0, temp.length);}/*** 返回顺序表容量大小* @return*/public int size(){return size;}}

3.顺序表功能验证

（1）验证顺序表初始化

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();SequenceList<Integer> sequenceCustomSizeList = new SequenceList<>(5);System.out.println("默认定义顺序表容量大小:"+sequenceDefaultSizeList.size());System.out.println("自定义顺序表容量大小:"+sequenceCustomSizeList.size());}
}

在这里插入图片描述

（2）验证添加元素

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);sequenceDefaultSizeList.add(3);//输出sequenceDefaultSizeList.show();}
}

在这里插入图片描述

（3）验证修改元素

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);sequenceDefaultSizeList.add(3);//输出sequenceDefaultSizeList.show();sequenceDefaultSizeList.update(0,9);sequenceDefaultSizeList.show();}
}

在这里插入图片描述

（4）验证删除元素

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);sequenceDefaultSizeList.add(3);//输出sequenceDefaultSizeList.show();sequenceDefaultSizeList.delete(0);sequenceDefaultSizeList.show();}
}

在这里插入图片描述

（5）验证集合扩容

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(2);System.out.println("扩容前："+sequenceDefaultSizeList.size());//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);sequenceDefaultSizeList.add(3);//输出System.out.println("扩容后："+sequenceDefaultSizeList.size());}
}

在这里插入图片描述

（6）验证获取元素的下标索引

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(2);//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);//输出System.out.println("元素index："+sequenceDefaultSizeList.indexOf(2));}
}

在这里插入图片描述

（7）获取当前集合有效元素个数

public class Main {public static void main(String[] args) {SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(4);//添加1 2 3 元素sequenceDefaultSizeList.add(1);sequenceDefaultSizeList.add(2);//输出System.out.println("当前集合有效元素个数为："+sequenceDefaultSizeList.getNum());}
}

在这里插入图片描述


http://www.ppmy.cn/news/12720.html

相关文章

【论文精读】Scaling distributed machine learning with the parameter server

【论文精读】Scaling distributed machine learning with the parameter server

Scaling distributed machine learning with the parameter server前言Abstract1. Introduction1.1 Contributions1.2 Engineering Challenges1.3 Related Work2. Machine Learning2.1 Goals2.2 Risk Minimization2.3 Generative Models3. Architecture3.1 (Key,Value) Vectors…
阅读更多...
SH-PEG-Silane巯基-聚乙二醇-硅烷试剂简介Silane-PEG-SH

SH-PEG-Silane巯基-聚乙二醇-硅烷试剂简介Silane-PEG-SH

SH-PEG-Silane巯基-聚乙二醇-硅烷 外观&#xff1a;固体或液体&#xff0c;取决于分子量大小。 PEG可选分子量: 1000,2000,3400&#xff0c;5000&#xff0c;10000 溶剂: 溶于DMSO,DMF,DCM&#xff0c;溶于水。 纯度&#xff1a;>95% 保存&#xff1a;-20℃&#xff0c…
阅读更多...
新入公司 git基本命令使用(二) 小乌龟版

新入公司 git基本命令使用(二) 小乌龟版

git命令行的操作复杂不直观,且容易出错. 这里推荐大家使用 git版小乌龟插件进行使用 下载地址 :https://tortoisegit.org/download/ 安装一路next即可 创建本地仓库 右键点击克隆, 然后输入项目地址,确认 拉取代码 右键点击同步 , 然后再界面中选择好对应的分支, 点击拉取 …
阅读更多...
Express做后端服务详细步骤，从零到一

Express做后端服务详细步骤，从零到一

文章目录一、全局安装脚手架二、生成项目1.生成项目2.目录结构介绍3.拓展&#xff1a;配置文件热更新&#xff08;避免改一次文件重启一次服务&#xff09;步骤1&#xff1a;安装nodemon步骤2&#xff1a;创建nodemon.json文件步骤3&#xff1a;更改启动命令步骤4&#xff1a;上…
阅读更多...
Python基础（二十四）：面向对象核心知识

Python基础（二十四）：面向对象核心知识

文章目录 面向对象核心知识 一、面向对象三大特性 1、封装 2、继承 3、多态 二、多态 1、了解多态 2、体验多态 三、类属性和实例属性 1、类属性 2、实例属性 四、类方法和静态方法 1、类方法 2、静态方法 面向对象核心知识 一、面向对象三大特性 1、封装 将…
阅读更多...
Java中的包装类

Java中的包装类

基本数据类型的豪华版---包装类基本数据类型包装类基本数据类型 在我们刚开始学习Java的时候,我们学习的应该就是Java中的八种基本数据类型: byte short int long float double char boolean 当时我们还说过Java是面向对象编程的语言,一切皆对象,但是受到当时知识的限制,我们还…
阅读更多...
校招求职HR常问问题汇总

校招求职HR常问问题汇总

前言 前言&#xff1a;面试是一次重要的自我销售的过程&#xff0c;只不过销售的产品是你自己&#xff0c;你要做的就是说服面试官认为你是优秀的&#xff0c;从而给你一个工作机会。 文章目录前言一、回答问题的原则二、自我介绍1、注意2、模板3、达到的效果三、你还有什么问题…
阅读更多...
卷积神经网络中特征图大小计算公式总结

卷积神经网络中特征图大小计算公式总结

W&#xff1a;输入特征图的宽&#xff0c;H&#xff1a;输入特征图的高K&#xff1a;kernel size卷积核宽和高&#xff0c;P&#xff1a;padding&#xff08;特征图需要填充的0的个数&#xff09;&#xff0c;S&#xff1a;stride步长width_out&#xff1a;卷积后输出特征图的宽…
阅读更多...
回首2022展望2023

回首2022展望2023

回首2022&#xff0c;虽然经历反复的居家办公&#xff0c;但仍然努力客服家庭与工作的时间冲突&#xff0c;很好的完成了开发任务。并在疫情变换间隙&#xff0c;带着部门同事做了几次团建&#xff0c;锻炼了队伍&#xff0c;提高了凝聚力。我同时坚信迟早会全面放开。在闲暇之…
阅读更多...
Go语言运算符

Go语言运算符

Go语言运算符 参考资料主要来源于菜鸟教程。 运算符用在程序运行时执行数学逻辑运算。 Go语言内置的运算符有&#xff1a; 算术运算符关系运算符逻辑运算符位运算符赋值运算符其它运算符 算术运算符 下表列出所有Go语言的算术运算符。假定A值为10&#xff0c;B值20。 运算符…
阅读更多...
理解CSS

理解CSS

CSS 作为前端技术栈中关键一环&#xff0c;对页面元素及样式呈现起到了直接作用。本节课旨在通过对 CSS 的工作流程及原理、页面中 CSS 使用方法等详细解读&#xff0c;帮助前端新手建立对 CSS 的全面而深刻的认知。 CSS概念 CSS 即 Cascading Style Sheets&#xff0c;是用来…
阅读更多...
[idekCTF 2023] Malbolge I Gluttony,Typop,Cleithrophobia,Megalophobia

[idekCTF 2023] Malbolge I Gluttony,Typop,Cleithrophobia,Megalophobia

这些题名字我都不认识&#xff0c;这是什么语呀。这个比赛感觉太难了&#xff0c;加上春节将近比较忙&#xff0c;仅作了4个简单题。记录一下。Misc/Malbolge I Gluttony这是个虚拟机的题&#xff0c;放入misc感觉有点不可思忆&#xff0c;题目给了7个命令&#xff0c;有"…
阅读更多...
【初阶数据结构】——写了将近 5 万字，终于把 二叉树 初阶的内容讲清楚了

【初阶数据结构】——写了将近 5 万字，终于把 二叉树 初阶的内容讲清楚了

文章目录前言1. 树的概念及结构1.1 树的概念1.2 树与非树1.3 树的相关概念1.4 树的表示1.5 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09;2. 二叉树概念及结构2.1 概念2.2 现实中的二叉树2.3 特殊的二叉树2.3.1 满二叉树2.3.1 完全二叉树2.4 二叉树的性质…
阅读更多...
计讯物联数字乡村解决方案赋能乡村振兴

计讯物联数字乡村解决方案赋能乡村振兴

项目背景 数字乡村是乡村振兴的战略方向&#xff0c;是推动农村现代化的重要途径。当前&#xff0c;数字乡村建设正在加速推进&#xff0c;打造乡村数字治理新模式&#xff0c;提升乡村的数字化水平&#xff0c;进一步推动乡村振兴进入高质量发展新赛道。计讯物联作为数字乡村…
阅读更多...
3.Python基础之流程控制

3.Python基础之流程控制

文章目录Python基础之流程控制顺序结构分支(选择)结构单项分支双项分支多项分支巢状分支循环结构whilefor ... in(字典的特殊使用)[https://blog.csdn.net/yaoyuanna/article/details/126009259]流程控制语句breakcontinuepassPython基础之流程控制 流程分类&#xff1a; 流程…
阅读更多...
SpringBoot 注册自己的Servlet（三种方式）

SpringBoot 注册自己的Servlet（三种方式）

SpringBoot 注册自己的Servlet&#xff08;三种方式&#xff09; 目录SpringBoot 注册自己的Servlet&#xff08;三种方式&#xff09;方法1:使用servlet3.0规范提供的注解方式注册Servlet1,声明servlet及映射2&#xff0c;加上ServletComponentScan 才会扫描加了这个注解运行结…
阅读更多...
HTTP/HTTPS协议介绍

HTTP/HTTPS协议介绍

数据来源 HTTP简介 01 什么是HTTP 超文本传输协议(HyperTextTransferProtocol缩写&#xff1a;HTTP&#xff09;是一种用于分布式、协作式和超媒体信息系统的应用层协议。 HTP( Hyper Text Transfer Protocol超京本传输协议) 是一个基于请求与响应 无状态的&#xff0c;应…
阅读更多...
《Stealth秘密行动》游戏开发记录

《Stealth秘密行动》游戏开发记录

游戏开发的学习记录项目&#xff1a;Stealth秘密行动开始时间&#xff1a;2022.12.30一、新学到的&#xff1a;二、遇到的问题&#xff1a;三、成品部分展示&#xff1a;游戏开发的学习记录⑧ 项目&#xff1a;Stealth秘密行动 开始时间&#xff1a;2022.12.30 &#xff08;…
阅读更多...
【ESP 保姆级教程】玩转emqx篇 ——初识emqx

【ESP 保姆级教程】玩转emqx篇 ——初识emqx

忘记过去，超越自己 ❤️ 博客主页 单片机菜鸟哥，一个野生非专业硬件IOT爱好者 ❤️❤️ 本篇创建记录 2023-01-15 ❤️❤️ 本篇更新记录 2022-01-15 ❤️🎉 欢迎关注 🔎点赞 👍收藏 ⭐️留言📝🙏 此博客均由博主单独编写，不存在任何商业团队运营，如发现错误，请…
阅读更多...
AtCoder Beginner Contest 285解题报告

AtCoder Beginner Contest 285解题报告

A - Edge Checker 2 Problem Statement Determine if there is a segment that directly connects the points numbered a and b in the figure below. Constraints 1≤a<b≤15a and b are integers.Input The input is given from Standard Input in the following for…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站