文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java数据结构顺序表的详细讲解

2024-04-02 19:55

关注

写在前面

关于数据结构,Java官方其实已经帮我们写好并封装起来了,在真正需要使用的时候直接调用即可,但为了更好的理解数据结构,我会按照源码的思路写一个简化后的数据结构,默认接收的数据为int

1.线性表

线性表是多个具有相同特性的数据元素的序列,线性表在逻辑上是一条连续的直线,但在实际存储上却不一定

顺序表则是线性表的一种,是用一段物理地址连续的存储单元依次存储数据元素的线性结构,通常是使用数组来实现

2.顺序表的实现

新建一个类叫做ArrList,顺序表的底层是数组,所以类里面也要有数组,其次还需要一个计数器来判断数组目前使用的空间是多少,那么顺序表的框架就完成了

public class ArrList {
    public int[] arr;
    public int count;
    public ArrList() {
        this.arr = new int[5];  //初始给5个大小空间
    }
}

接下来就是顺序表的增删改查等操作了

2.1增加数据

增加数据有两个方法:末尾增加数据和任意位置增加数据

2.1.1尾部增加数据

在这之前需要进行的一项工作是判断顺序表的空间是否已满,如果空间已满的话需要进行扩容,判断顺序表空间是否已满的依据是计数器的值和数组的长度是否相等

public boolean isFull() {
        return this.count==this.arr.length;
    }
public void tailAdd(int data) {
        //首先判断顺序表是否已满
        if(isFull()) {
            //顺序表已满,需要扩容,这里是扩大为原来的两倍
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        //程序走到这,不管有没有扩容,此时顺序表都是未满,直接添加数据
        this.arr[this.count]=data;
        this.count++;
    }

2.1.2任意位置增加数据

任意位置添加数据的话首先要判断输入的值是否是合法的,有一点要注意:如果输入的值和计数器的值是相等的,那么此时就是在顺序表末尾添加数据,这个数是合法的

public void add(int index,int data) {
        //首先需要判断index的值是否合法,不合法直接抛出异常
        if(index<0||index>this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        if(isFull()) {
            //顺序表已满,需要扩容
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        if(index==this.count) {
            this.arr[this.count]=data;
            this.count++;
        } else {
            //中间位置添加数据需要先把从此处开始到末尾的数据都往后移动一位,从后往前移
            for (int i = this.count-1; i >=index ; i--) {  
                this.arr[i+1]=this.arr[i];
            }
            this.arr[index]=data;
            this.count++;
        }
    }

2.2查找数据

输入一个值,遍历顺序表进行查找,有则返回下标,没有返回-1

public int find (int data) {
       for (int i = 0; i < this.count; i++) {
            if(this.arr[i]==data) {
                return i;
            }
        }
        return -1;
    }

之所以返回值是int而不是boolean是因为后面的删除和修改数据的方法会使用到此方法

2.3删除数据

找到要删除的值的下标,从此处开始用后面的值对前面的值进行覆盖,最后将尾部的值改为0

public void delData(int data) {
        int i=find(data);
        if(i!=-1) {
            for (int j = i; j <this.count-1 ; j++) {
                this.arr[j]=this.arr[j+1];
            }
            this.count--;
            this.arr[this.count]=0;
        }
    }

2.4修改数据

修改指定位置的值,依旧首先要判断位置是否合法

public void setIndex (int index,int data) {
        if(index<0||index>=this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        this.arr[index]=data;
    }

最后是销毁顺序表,不需要吧数组进行销毁,否则下次使用的时候还需要再实例化一个对象,只需要让计数器为0即可

public void clear () {
        this.count=0; 
    }

3.ArrayList

Java中的顺序表叫做ArrayList,这是一个泛型类,这个类继承了多个其它类以及接口,其中包括List接口,List提供了很多抽象方法,ArrayList实现此接口对这些方法进行重写

3.1ArrayList的实例化

ArrayList有三种构造方法

ArrayList()无参构造
ArrayList(Collection<? extends E> c)利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)指定顺序表初始容量

要说明的是:调用无参数构造方法,默认数组的大小为0,之后在调用里面的方法(比如add方法)的时候会有专门的扩容的方法将其扩容为10,之后如果数组满了的话扩容为之前的1.5倍(源码里面套的方法太多就不展示了)

3.2ArrayList常用的方法

boolean add(E e)

尾插 

void add(int index, E element)

将元素插入到 index 位置

boolean addAll(Collection<? extends E> c)

尾插 c 中的元素

E remove(int index)

删除 index 位置元素

boolean remove(Object o)

删除遇到的第一个指定的值

E get(int index)

获取下标 index 位置元素

E set(int index, E element)

修改下标 index 位置的元素

void clear()

销毁顺序表

boolean contains(Object o)

判断指定元素是否在表中

int indexOf(Object o)

返回第一个指定元素所在下标

int lastIndexOf(Object o)

返回最后一个指定元素的下标

List<E> subList(int fromIndex, int toIndex)

截取指定部分的元素

最后的截取方法是在原数组上进行截取

到此这篇关于Java数据结构顺序表的详细讲解的文章就介绍到这了,更多相关Java顺序表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯