顺序表(快速上手数据结构)

这篇具有很好参考价值的文章主要介绍了顺序表(快速上手数据结构)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在介绍ArrayList之前, 我们需要先了解List.

List是一个接口,它继承于Collection接口(Collection又继承于最顶层的接口Iterable).  从数据结构的角度来看,List就是一个线性表(Linear List),即n个具有相同类型元素的有限序列, 在该序列上可以执行增删查改等操作.

注意: List是一个接口,不能直接用来实例化. 在集合框架中, ArrayList类和LinkedList类都实现了List接口. 我们可以通过这两个类来实例化对象. 本篇博客主要讲述ArrayList类(顺序表).

目录

顺序表

1. 新增元素

2. 在pos位置新增元素

3. 判定是否包含某个元素

4. 查找某个元素对应的位置,并返回下标 

5. 获取pos位置的元素

6. 给pos位置的元素设为value(给某位置的元素更新)

7. 删除某数字key

8. 获取顺序表的长度

9.清空顺序表


顺序表

顺序表中主要有如下几种方法:

public interface IList {
    void add(int data); //新增元素(默认在数组最后新增)
    
    void add(int pos, int data); //在pos位置新增元素
    
    boolean contains(int toFind); //判定是否包含某个元素
    
    int indexOf(int ToFind); //查找某个元素对应的位置,并返回下标
    
    int get(int pos); //获取pos位置的元素
    
    void set(int pos, int value); //给pos位置的元素设为value(更新)
    
    void remove(int toRemove); //删除第一次出现的关键字key
    
    void size(); //获取顺序表的长度
    
    void clear(); //清空顺序表

    void display(); //打印数组(不属于顺序表中的方法)
}

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

今天,我们就用Java来实现一遍这七种方法. 相信在我们自己实现完一遍顺序表之后,我们的代码能力和思维会有不小的提升!

首先,我们需要定义一个操作数组,用来让方法对其进行操作:

public class MyArrayList {
    public int[] elem; //定义一个整型类型的操作数组
    public int usedSize; //定义一个变量表示已使用空间 (没有初始化--默认是0)
    public MyArrayList() { //构造方法 (将数组长度初始化为10)
        this.elem = new int[10];
    }
}

 顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

1. 新增元素

void add(int data) 默认在数组的最后新增.

在这里,我们只需要在数组有数据的位置的后一个(即:usedSize位置上(例如: usedSize=5, 那么0,1,2,3,4 位置上有元素, 将新增数据放到5位置上就行))放上我们要新增的数据即可.但是:如果数组满了,还能新增吗? -- 不能,此时需要将数组扩容才能继续新增操作.

结合上面两方面的考虑,我们写出如下代码:

 public void add(int data) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = data;
        this.usedSize ++;
    }
    boolean isFull() {
        return (usedSize == elem.length);
    }

我们在main方法里调用它测试一下:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.display();

    }
}

 运行结果:

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

2. 在pos位置新增元素

在pos位置新增元素,我们需要考虑的点有以下几个: (1) 将pos位置后的元素整体向后移. (2) 插入新的数据. (3) 检查pos位置是否合法.

  • 检查pos位置是否合法: pos<0时不合法; pos>usedSize时不合法(pos=usedSize时是合法的,因为此时相当于在数组的最后新增一个元素)
  • 移动元素: 令i等于数组最后一个位置(usedSize-1), 从数组最后一个位置开始遍历数组,将 i位置上的元素赋到 i+1位置上
  • 插入数据: 将数据data放到数组下标为pos的位置上即可. 所有操作完成后, 再让usedSize++即可.

注意: pos位置不合法我们可以写一个异常出来,方便检查和处理.

根据上述步骤,我们可以写出如下代码:

    public void add(int pos, int data) {
        try{
            checkOfPosAdd(pos); //检查pos是否合法
        }
        catch(PosIllegalException e){
            e.printStackTrace(); //打印异常
        }
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length); //如果数组满了需要扩容
        }
        for (int i = usedSize-1; i >= pos ; i--) {
            elem[i+1] = elem[i]; //向后移动元素
        }
        elem[pos] = data; //插入新的元素
        usedSize ++;
    }
    private void checkOfPosAdd(int pos) throws PosIllegalException {
        if (pos < 0 || pos > usedSize) {
            throw new PosIllegalException("pos位置不合法");
        }
    }

在main方法中调用:

    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        iList.add(2,88);
        iList.display();

    }
}

运行结果: 

 顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

3. 判定是否包含某个元素

对于这个方法的实现, 我们只需遍历数组, 看是否有要找的数据,如果有,则返回true

代码:

    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

在main方法中调用:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        System.out.println(iList.contains(2));
    }
}

运行结果: 

 顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

4. 查找某个元素对应的位置,并返回下标 

对于这个方法的实现, 我们还是遍历数组.  如果有要找的数据,则返其对应的下标; 如果没有, 则返回-1.

代码:

    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

在main方法中调用:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        System.out.println(iList.indexOf(2));
    }
}

运行结果:

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

5. 获取pos位置的元素

 实现这个方法,分两步: (1) 判断pos位置是否合法. (2) 返回pos位置元素的值.

(1) pos<0 或 pos>=usedSize 时不合法(pos==UsedSize时此位置上没有元素, 所以不合法). 所以这里我们就需要写一个方法来判断pos是否合法.

(2) 返回pos位置的元素: 直接返回即可.

代码:

public int get(int pos) {
    try{
        checkPosOfGetAndSet(pos);
    }
    catch(PosIllegalException e) {
        e.printStackTrace();
    }
    return elem[pos];

在main方法中调用:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        System.out.println(iList.get(2));
    }
}

 运行结果:

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

6. 给pos位置的元素设为value(给某位置的元素更新)

实现这个方法, 也要分为两步: (1) 判断pos位置是否合法.  (2) 给pos位置的元素设为value

代码:

    public void set(int pos, int value) {
        try{
            checkPosOfGetAndSet(pos);
        }
        catch(PosIllegalException e){
            e.printStackTrace();
        }
        elem[pos] = value;
    }

在main方法中调用:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        iList.set(2,333);
        iList.display();
    }
}

 运行结果:

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

7. 删除某数字key

我们首先要判断这个数字书是否在数组里面.然后在删除(删除的方法是"覆盖"--用后面的数据覆盖前面的数据从而实现对前面数据的删除)

代码:

    public void remove(int toRemove) {
        int pos = indexOf(toRemove);
        if (pos == -1) {
            System.out.println("没有要删除的数字");
            return; //为什么要写return? 有必要吗?
        }
        for (int i = pos; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        this.usedSize--;

在main方法中调用:

public class Test {
    public static void main(String[] args) {
        IList iList = new MyArrayList();//实例化一个MyArraList的对象.
        iList.add(1);
        iList.add(2);
        iList.add(3);
        iList.display();
        iList.remove(2);
        iList.display();
    }
}

 运行结果:

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构

8. 获取顺序表的长度

 代码:

    public int size() {
        return this.usedSize;
    }

9.清空顺序表

本例中:数组是基本类型(int)的, 所以我们只需要把usedSize置为0即可. 但是如果数组中存放的时引用类型,那么即使将usedSize置为0,堆上存放的对象还是被栈上的变量引用着(但是这些对象没用了),这样的话就会造成内存泄漏,形成不必要的内存损失.

所以: 数组中如果存放的是引用类型, 需要先将数组元素置为null, 再将usedSize置为0.

    public void clear() {
        usedSize = 0;
    }

 以上就是本篇博客的全部内容啦,如果喜欢小编的文章,可以点赞,评论,收藏~

顺序表(快速上手数据结构),数据结构初阶 (Java版),java,数据结构文章来源地址https://www.toymoban.com/news/detail-861577.html

到了这里,关于顺序表(快速上手数据结构)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 初阶数据结构之---二叉树的顺序结构-堆

    今天要讲的堆,不是操作系统虚拟进程地址空间中(malloc,realloc等开空间的位置)的那个堆,而是数据结构中的堆,它们虽然名字相同,却是截然不同的两个概念。堆的底层其实是 完全二叉树 ,如果你问我,完全二叉树是什么。好吧,那我先从树开始讲起,开始我们今天的

    2024年03月14日
    浏览(47)
  • 初阶数据结构:顺序表相关题目练习

    在对顺序表这一数据结构进行了学习与自实现后,我明白了顺序表的是使用了 物理地址上连续的数组模型 实现的,而 插入删除 的操作都会涉及到其中 数据的挪动与边界问题 。接下来,就结合算法时空间复杂的要求来对这一相关问题通过几道题目进行巩固练习。 题目要求:

    2024年01月20日
    浏览(37)
  • 数据结构(初阶):顺序表实战通讯录

    数据结构(初阶)第一节:数据结构概论-CSDN博客 数据结构(初阶)第二节:顺序表-CSDN博客         本文将以C语言和顺序表实现通讯录基础管理,实现功能包括增、删、改、查等,在实现相关功能时需要用到在第二节中顺序表的相关内容,需要友友们掌握顺序表的相关

    2024年04月16日
    浏览(27)
  • 【数据结构初阶】顺序表和链表(1)

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

    2024年02月08日
    浏览(34)
  • 【数据结构初阶】二、 线性表里的顺序表

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月09日
    浏览(32)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(30)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(34)
  • 初阶数据结构之---顺序表和链表(C语言)

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

    2024年02月22日
    浏览(43)
  • 『初阶数据结构 • C语言』⑦ - 静态顺序表详解(附完整源码)

    本章内容 1.什么是线性表 2.什么是顺序表  3.静态顺序表结构的定义 4.静态顺序表的函数接口实现 5.静态顺序表的问题及思考     线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、

    2024年02月15日
    浏览(37)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包