你还不懂《顺序表》?那就不要错过这篇文章!!!

这篇具有很好参考价值的文章主要介绍了你还不懂《顺序表》?那就不要错过这篇文章!!!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🎇🎇🎇作者:
@小鱼不会骑车
🎆🎆🎆专栏:
《java练级之旅》
🎓🎓🎓个人简介:
一名专科大一在读的小比特,努力学习编程是我唯一的出路😎😎😎
顺序表中return true,java练级之路,数据结构,java,开发语言

顺序表中return true,java练级之路,数据结构,java,开发语言
顺序表中return true,java练级之路,数据结构,java,开发语言

介绍线性表

在认识顺序表前我们先认识一下线性表:

小鱼曾在一本书中看到这么一个例子他是这样介绍线性表的:

在一个幼儿园中,每次放学时老师带领着小朋友们一个接着一个从教室出来,并且他们之间的次序都是一样的,例如小明排在第4位,则每次放学时他都是排在第四位,前面同样是那个的小女孩,后面也一直是那个男孩。
顺序表中return true,java练级之路,数据结构,java,开发语言

老师是这么解释的:为了保障小朋友的安全,避免漏掉小朋友,所以在出门前就安排好了他们出门的次序,谁谁在前,谁谁在后,当这样养成习惯时,如果是有哪个小朋友没有到位,则他前面的和后面的小朋友就会发现并且报告给老师,谁谁不在,老师也可以很快地清点人数,万一有人走丢,也能在最快时间知道,及时去寻找。

通过上面的例子我们就可以看出:线性表是一个序列,也可以理解为他们之间的元素是有顺序的,并且第一个元素无前驱,最后一个元素无后继,其余元素有且仅有一个前驱和后继,并且如果一个小朋友的衣服被两个或多个小朋友拉扯,这其实是在打架!不是有序排队。

总结

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

顺序表

在简单介绍完线性表之后,我们可以将顺序表理解为用数组的形式来实现线性表。

那一个顺序表都会有什么操作呢?举个例子:

如果有小朋友排队的时候突然想去厕所,那么当他去厕所之后,是不是他后面的同学都向前移动一下,先将这个空位补上?
对的! 大概就是如下图的过程
顺序表中return true,java练级之路,数据结构,java,开发语言
过了一会上厕所的小朋友回来了,是不是刚刚移动的小朋友需要集体后移来给这个小朋友腾出地方啊?
就像下图:
顺序表中return true,java练级之路,数据结构,java,开发语言
我们可以将上述的两个操作理解为增加和删除元素,那我们还是不是需要有查找和修改的功能啊?

那么大体的思路我们有了,接下来就是实现顺序表了!

定义一个顺序表类(Arraylist)

我们这个顺序表用到的是数组,所以我们就可以在这个顺序表中定义一个数组的成员变量,由于顺序表中的元素没有指定是什么类型,那么我们就创建一个泛型类的顺序表,以及一个泛型数组!并且我们还需要一个值来记录数组内元素的个数,那么为了方便,我们还可以利用构造方法初始化我们的数组大小。

代码如下:

public class Arraylist<E> {

    public E[] elem;//创建这个成员变量
    public int usedSize;//0/。记录长度
    //默认容量
    private static final int DEFAULT_SIZE = 10;

    public Arraylist() {//初始化数组
        this.elem = (E[]) new Object[DEFAULT_SIZE];
    }

    public Arraylist(int p) {
        this.elem = (E[]) new Object[p];
    }
 }   

我们对构造方法进行了重载,如果需要指定数组大小则可以在实例化顺序表类时输入指定的数组大小,如果没有指定数组的大小,我们就将数组大小默认设置为10个元素的大小!

那么成员属性和构造方法我们都实现了,接下来就是顺序表中的增删查改等方法了!

查找顺序表元素(indexOf)

我们查找元素一般时有两个需求。

第一:查找到元素返回元素的下标
第二:判断数组中有没有这个元素,如果有返回true否则返回false。

所以根据着两个需求我们可以写两个方法

第一个:当该元素存在时返回该元素的下标

  // 查找某个元素对应的位置
  //toFind是我们要查找的元素
    public int indexOf(E toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i].equals(toFind)) {
                return i;
            }
        }
        return -1;
    }

第二个:当该元素存在时返回true否则返回false

 // 判定是否包含某个元素
    public boolean contains(E toFind) {
        for (int i = 0; i <usedSize ; i++) {
            if (elem[i].equals(toFind)) {
                return true;
            }
        }
        return false;
    }

两者的区别其实就是返回值的不同,其实实现起来是很简单的。

遍历顺序表(display)

那我们也可以接着这个思路再写一个打印方法,打印出数组所有元素的值

遍历数组有五种方法,虽然有些不会经常用到,但是小鱼还是一一给大家列举出来!
①、使用 for 循环打印

最简单的方法,但是需要自己去实现

  /**
     * 打印顺序表:
     * 根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }

②、使用 Arrays.toString() 或 Arrays.deepToString()

对于一维数组,可以使用Arrays.toString()方法,它支持将任意类型的数组转换为字符串
一维数组用 Arrays.toString() 方法,多维数组用 Arrays.deepToString() 方法

 public void display() {
       //自己顺序表中不推荐使用 
        System.out.println(Arrays.toString(elem));
    }

:在自己实现的顺序表中不推荐使用Arrays.toString() 方法以及后面介绍到的遍历数组的方法,因为顺序表每次都是扩容2倍或者1.5倍的内存,这就说明我们的数组其实是有很多元素是没有被赋值默认为null或0的,又因为Arrays.toString() 方法会将数组中所以元素打印出来,那么就会有下面的情景
顺序表中return true,java练级之路,数据结构,java,开发语言

③、使用 Arrays.asList()

该方法是将数组转化为list
以下几点需要注意:
(1)该方法不适用于基本数据类型
byte,short,int,long,float,double,boolean),但可以用基本数据类型的包装类。比如int的包装类Integer.(Object 数组也是有效)
(2)该方法将数组与列表链接起来,当更新其中之一时,另一个自动更新
(3)不支持add和remove方法

 public void display() {
        //运行结果和上面情况一样!
        System.out.println(Arrays.asList(elem));
    }

运行结果
顺序表中return true,java练级之路,数据结构,java,开发语言

④、使用for each

for-each 是 for 循环的另外一种使用方式. 能够更方便的完成对数组的遍历. 可以避免循环条件和更新语句写错.

   public void display() {
        //依旧是打印全部数组
        for (E x:elem) {
            System.out.print(x+" ");
        }
        System.out.println();

    }

运行结果
顺序表中return true,java练级之路,数据结构,java,开发语言

⑤、使用迭代器

迭代器是设计模式的一种,后序容器接触多了再给大家铺垫(由于自己实现的顺序表没有迭代器,于是用的是java自带的)

public static void main(String[] args) {
     List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(666);
        list.add(888);
        Iterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
   }

运行结果

顺序表中return true,java练级之路,数据结构,java,开发语言

注意:

  1. ArrayList最长使用的遍历方式是:for循环+下标 以及 foreach
  2. 迭代器是设计模式的一种,后序容器接触多了再给大家铺垫

定义一个异常(SubscriptException)

由于我们的增,删,改以及获取下标对应得元素的值,都需要传下标这个参数,又因为我们输入的下标可能会越界,所以我们自己实现一个异常,一旦输入的下标越界,则抛出这个异常
注:

我们继承的是一个编译时异常也可以称之为受查异常的Exception,所以我们如果用到这个异常就需要声明这个异常!

class SubscriptException extends Exception {

    public SubscriptException(String e) {
        super(e);
    }
}

接下来我们就可以去实现后面经常会用到的判断下标是否会越界的方法了.

在这个方法中,当我们输入的下标的值如果比我们的数组的长度长或者说等于我们的数组的长度那么就抛出这个异常!

  public void transBoundary(int pos) throws SubscriptException {
       
        if (pos>=usedSize) {
            throw new  SubscriptException("输入下标异常");
        }
    }

那么有人抛出异常就一定有人去接收这个异常,在下面实现

   //检查要输入的位置是否合法
    private boolean checkPosInAdd(int pos) throws SubscriptException {
        try {
            transboundary(pos);
        }catch (SubscriptException e) {
            System.out.println("捕捉到了下标异常");
            e.printStackTrace();
            return false;
        }
        return true;//合法
    }

当我们捕捉到这个异常的时候返回false,否则返回true,注意我们在方法的参数后面都声明了这个异常!!!

增加元素(Add)

我们将铺垫整理好了之后就可以进行增,删,改等操作了!

我们增加元素有两种方式:

第一种是在数组的最后一个位置插入,也可以称为尾插!
第二种是指定位置插入。

我们先来讨论一下,插入元素需要注意什么?

1.注意下标是否越界
2.注意数组容量是否够用
3.在插入元素之后数组元素加一

第一种方式的实现(比较简单):

代码如下:

    // 新增元素,默认在数组最后新增
    public void add(E data) {
        if (isFull()) {
           elem= Capacity(elem);
        }
        elem[usedSize]=data;
        usedSize++;
    }

根据上面提到需要注意的第二点,我们就可以知道,该方法中的isFull方法就是判断数组容量是否够用,方法的实现如下

  /**
     * 判断当前的顺序表是不是满的!
     *
     * @return true:满   false代表空
     */
    public boolean isFull() {
    //当我的数组长度和我的元素个数一样多时,就返回true
    //意思就是需要扩容
        return usedSize==elem.length;
    }

如果数组容量不够,就去调用Capacity()方法,当然这个扩容数组的方法也是需要咱们自己实现的,方法具体内容如下

   //扩容数组
    public E[] Capacity(E[]array) {

        return Arrays.copyOf(array,array.length*2);
    }

我们的数组需要扩容时,一次扩容一倍,如果是扩容的容量太小,那么就需要扩容很多次,这就造成了时间上的浪费!虽然这样扩容可能会存在空间上的浪费,但是当我们学到线性表中的链表时就可以进一步的解决这个问题。

数组扩容之后,将数组进行尾插,最后数组元素个数加一!

第二种(指定位置插入):

这里需要考虑的就是,我们该如何插入,以及需要注意的事项.

小鱼先将总的代码拿出来,下面进行分析:

  public void add(int pos, E data) throws SubscriptException {
		//判断要插入的元素是否是最后一个位置
        if (pos==usedSize) {//如果是则调用尾插的方法
            add(data);
            return;
        }
       if (!checkPosInAdd(pos)) {
       //判断输入的下标是否越界,
       //如果越界则直接返回
           return;
       }
        //检查容量
        if (isFull()) {
            elem=Capacity(elem);
        }
        for (int i = usedSize-1; i >=pos; i--) {
            //向后覆盖
            elem[i+1]=elem[i];
        }
        set(pos,  data);
        usedSize++;
        System.out.println("添加成功");
    }

这一部分理解起来有一些困难,不过小鱼会画图一步一步剖析,大家如果看完之后还有疑问,或者改进的方法请大胆私信小鱼!!!
画图一步一步分析

顺序表中return true,java练级之路,数据结构,java,开发语言

第一步:我们先不管第一个方法,直接看第二个方法(蓝色框框)

顺序表中return true,java练级之路,数据结构,java,开发语言

但是其实是存在坑的,假如我要插入元素的位置是数组的最后一个位置,那么由于transBoundary()中的判定条件,当我输入的下标是数组的最后一个位置,又因为相等所以他就会抛出数组越界的异常,我们为了解决这个问题,我在执行这个方法前先进行了第一步的判断,也就是上图中绿色的框框里面,当我输入的下标就是数组的最后一个位置时,则直接调用尾插方法,避免了抛出异常。(解决方法很多,这只是小鱼认为好一些的)

第二步

接下来就是检查容量了,这个在上面讲到过这里就不再重复,直接跳到红框框里面的第四个方法。

前面讲到的一个小朋友上厕所的例子大家还记得吧,当在队伍中的小朋友去上厕所回来时,就需要各位小朋友将他之前的位置腾出来,那么他原来位置后的小朋友就需要集体后移,如图

顺序表中return true,java练级之路,数据结构,java,开发语言

所以我们可以根据该图的思路,自己实现一个插入方法!

    for (int i = usedSize-1; i >=pos; i--) {
            //向后覆盖
            elem[i+1]=elem[i];
        }
        set(pos,data);
        usedSize++;
        System.out.println("添加成功");

让我们的数组中所有在pos位置及pos位置后面的元素后移一位,移动之后将调用set()方法。

方法实现如下:

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, E value) throws SubscriptException {
        //修改元素
       if (!checkPosInAdd(pos)) {
           return;
       }
           elem[pos]=value;
    }

将pos位置的元素修改为要插入的元素,并且在使用这个方法时,也需要判断下标是否越界!
最后数组元素个数加一,打印添加成功提示程序员。

删除元素(Delete)

经过上述的增加元素,我们也可以发现,删除元素其实也是有两个方法:
方法一:删除最后一个元素
方法二:删除指定元素

方法一(尾删):

    public void delete() {
        //删除最后一个元素
        elem[usedSize-1]=null;
        usedSize--;
    }

由于我们的usedSize是数组元素的个数,又因为我们的数组是从0下标开始的,所以我们需要将usedSize-1,将该下标置为null之后再对数组元素个数进行减一。

方法二(指定删除):

这个问题就相当于前面讲到过的小朋友去厕所问题,当这个小朋友去厕所后,那么他后面的小朋友就需要向前走将他的位置补上,也就是都像前移,具体如何实现呢?

顺序表中return true,java练级之路,数据结构,java,开发语言

所以我们的大概思路就是,将要删除的元素的后面的元素都进行前移的操作,最后将最后一个元素置为null,最后数组元素个数减一.

注意:

需要判断下标是否越界

    public void delete(int pos) throws SubscriptException {
        //判断是否越界
        if (!checkPosInAdd(pos)) {
            return;
        }
        for (int i = pos; i < usedSize-1; i++) {
            elem[i]=elem[i+1];
        }
        //将最后一个元素置为null
        elem[usedSize-1]=null;
        //元素个数减一
        usedSize--;
        
    }

删除下标为2的元素,运行结果

顺序表中return true,java练级之路,数据结构,java,开发语言

还有一些小鱼就不进行讲解了,大家可以自己实现:

清空顺序表
获取顺序表长度
获取下标对于位置的元素
判断顺序表是否为空
删除第一次出现的关键字

总结

顺序表的缺点:

  • ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N)
  • 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  • 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

那么我们如何解决呢?

这些问题将会在链表中给大家讲解!!!

顺序表中return true,java练级之路,数据结构,java,开发语言文章来源地址https://www.toymoban.com/news/detail-831705.html

到了这里,关于你还不懂《顺序表》?那就不要错过这篇文章!!!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • stable diffusion webui界面布局(很多大佬一键安装包的样式,自己部署却没有?那就看这篇文章吧!)

    自己部署stable diffusion界面布局(很多大佬一键安装包的样式,自己部署却没有?那就看这篇文章吧!) 如下图,使用一键部署的项目,有【外挂vae模型】【跳过CLIP部署】,且【采样方法】的部署不是下拉列表,而是所有采样方法都放出来了 如下图:这是不适用一键部署包,

    2024年02月16日
    浏览(56)
  • 【Java】还不理解继承?一篇文章看懂继承|继承入门

    作者: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: Java岛冒险记【从小白到大佬之路】;该专栏专注于Java相关知识,持续更新,每一篇内容优质,浅显易懂,不失深度!

    2024年02月01日
    浏览(49)
  • 还是搞不懂Anaconda是什么?读这一篇文章就够了

    概述 Anaconda ,中文 大蟒蛇 ,是一个开源的Anaconda是专注于数据分析的Python发行版本,包含了conda、Python等190多个科学包及其依赖项。 Anaconda就是可以便捷获取包且对包能够进行管理,包括了python和很多常见的软件库和一个包管理器conda。常见的科学计算类的库都包含在里面了

    2024年02月03日
    浏览(91)
  • 视频裁剪软件电脑端有哪些?这篇文章分享的内容可千万不可错过

    在制作视频的过程中,我们经常遇到两种常见问题: ①视频画面大小不符合预期或规范,需要进行画面裁剪。 ②视频中存在一些不必要的片段,需要对视频时长进行裁剪。 为了解决这些问题,我们需要使用一些视频裁剪工具。那么,视频裁剪下载在哪里呢? 今天,这篇文章

    2024年01月21日
    浏览(42)
  • 【数据结构——顺序表】线性表很难嘛?这篇文章能让你轻松掌握顺序表

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

    2024年02月07日
    浏览(54)
  • Linux - 还不懂 gdb 调试器?(调试软件)

    当前,我们可以使用 make/makefile 来程序化执行代码文件;可以使用 gcc/g++ 等编译器来编译代码;可以使用 vim 编辑器来编写代码;其实在 Linux 当中还有一个工具,可以实现调试工作,这个工具就是 -- gdb。 在了解调试器之前,你应该对代码的发布版本做一些了解: 我们在 VS

    2024年02月07日
    浏览(53)
  • Outlook邮箱注册教程 不信你看完还不懂

    Outlook作为Microsoftnbsp;Office家族的办公软件套装之一,关联着很多微软的其他产品。而且Outlook是欧美地区认可度比较高的,不仅可以用于一些境外联络还可以拿来注册Instagram、Twitter、Facebook等各种社交媒体平台。龙哥在这里就给大家出一份详细的Outlook邮箱注册流程,兄弟们对

    2023年04月25日
    浏览(44)
  • 【MySQL】不允许你还不了解创建计算字段

    🎬 博客主页:博主链接 🎥 本文由 M malloc 原创,首发于 CSDN🙉 🎄 学习专栏推荐:LeetCode刷题集! 🏅 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📆 未来很长,值得我们全力奔赴更美好的生活✨ 😁大家好呀,今天是我第N次写MySQL,也是最近才学习MySQL,也想着记录

    2024年02月11日
    浏览(42)
  • 电脑硬盘数据恢复?这3个方法不要错过!

    “我在使用电脑办公时,不小心将电脑硬盘里的数据误删了。这些数据对我来说都是比较重要的!有什么比较简单的方可以恢复吗?” 电脑硬盘中一般会保存用户很多重要的资料和数据,如果这些资料误删了,可能会带来各种麻烦和不便。怎么进行电脑硬盘数据恢复呢?对于

    2024年02月19日
    浏览(45)
  • GPT-5: 超越人类语言的模型,你还不了解一下?

    目录 一、GPT-5时代引领者 二、技术特性  1,音频和视频处理 — 更强大的多模态处理能力 2,GPT-5颠覆影视制作:重写媒体消费时代 3,为机器人提供智慧大脑 4,更强的垂直行业应用 三、回顾一下GPT5被紧急叫停?幕后发生了什么事 GPT5来了! 彻底颠覆传统的影视制作方式、

    2024年02月06日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包