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

news/2025/3/14 1:10:24/

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;卷积后输出特征图的宽…
阅读更多...
最新文章

Copyright @ 2022~2023