1. Toy模板网首页
  2. > Toy博客

【Java】实现顺序表基本的操作（数据结构）

8月前 作者：權sir 分类：Toy博客 阅读(33) 违法举报

这篇具有很好参考价值的文章主要介绍了【Java】实现顺序表基本的操作（数据结构）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在了解顺序表之前我们要先了解什么是线性表，线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改
【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言
接下来我们要实现一些方法来对数组进行增删查改等操作

创建一个类：

public class MyArrayList {
    //数组
    public int[] elem;
    //数组中的元素个数
    public int usedSize;
    //当前数组默认的容量
    public static final int DEFAULT_CAPACITY = 5;
    public MyArrayList() {
        elem = new int[DEFAULT_CAPACITY];
    }
}

1、打印顺序表

public void display() {
    for (int i = 0; i < usedSize; i++) {
        System.out.print(elem[i]+" ");
    }
    System.out.println();
}

2、增加元素

增加元素默认是在数组的最后位置增加元素
在增加元素之前我们要先判断数组是否满了

判读数组是否满：

public boolean isFull() {
    return usedSize == elem.length;
}

增加元素：

public void add(int data) {
    if(isFull()) {
        //满了进行扩容
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    elem[usedSize] = data;
    usedSize++;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        myArray.display();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

3、在任意位置增加元素

注意：这里的增加元素要保证位置的合法性不能小于0，也不能大于数组的长度，更不能间隔着插入，即插入的位置前面一定要有元素；同时插入时其余元素要后移；如果不合法就抛一个异常
同样增加元素之前我们要判断数组是否满了

位置是否合法：

private void checkPosOfAdd(int pos) {
    if(pos < 0||pos > usedSize) {
        throw new PosException("pos位置不合法:"+pos);
    }
}

任意位置增加元素：

public void add(int pos, int data) {
    //判断位置是否合法
    checkPosOfAdd(pos);
    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++;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        myArray.add(1,15);
        myArray.display();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

4、判断是否包含某个元素

遍历数组判断是否与这个元素相同：

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

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        System.out.println(myArray.contains(20));
        System.out.println(myArray.contains(200));
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

5、查找某个元素对于的位置

遍历这个数组找与要查找的元素是否相同，相同返回该元素的下标，不同返回-1：

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

测试:

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        System.out.println(myArray.indexOf(20));
        System.out.println(myArray.indexOf(200));
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

6、获取任意位置的元素

同样我们要判断该位置是否合法，还有要判断顺序表是否为空，两个条件都合法时返回该位置的元素

顺序表是否为空：

public boolean isEmpty() {
    return usedSize == 0;
}

位置是否合法：
注意： 这里的判断位置是否合法=是无法获取的，而在任意位置增加元素=是可以增加的

private void checkPosOfGet(int pos) {
    if(pos < 0||pos >= this.usedSize) {
        throw new PosException("pos位置不合法:"+pos);
    }
}

获取任意位置的元素：

public int get(int pos) {
    //判断该位置是否合法
    checkPosOfGet(pos);
    if(isEmpty()) {
        throw new EmptyException("顺序表为空");
    }
    return elem[pos];
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        System.out.println(myArray.get(1));
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

7、将任意位置的元素设为value

与获取任意位置的元素方法相同，要判断该位置是否合法，还要判断顺序表是否为空

将任意位置的元素设为value：

public void set(int pos, int value) {
    //判断位置是否合法
    checkPosOfGet(pos);
    if(isEmpty()) {
        	throw  new EmptyException("顺序表为空");
    }
    this.elem[pos] = value;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        myArray.set(1,15);
        myArray.display();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

8、删除第一次出现的关键字

在进行删除操作时要判断顺序表是否为空，找到要删除元素的下标，最后
挪动数据

删除操作：

 public void remove(int toRemove) {
     if(isEmpty()) {
         throw new EmptyException("顺序表为空");
     }
     int ret = indexOf(toRemove);
     for (int i = ret; i < usedSize; i++) {
         elem[i] = elem[i+1];
     }
     usedSize--;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        myArray.remove(10);
        myArray.display();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

9、获取顺序表长度

public int size() {
    return usedSize;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        System.out.println(myArray.size());
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

10、清空顺序表

public void clear() {
    usedSize = 0;
}

测试：

public class Test {
    public static void main(String[] args) {
        MyArrayList myArray = new MyArrayList();
        myArray.add(10);
        myArray.add(20);
        myArray.add(30);
        myArray.add(40);
        myArray.display();
        System.out.println("*******");
        myArray.clear();
        myArray.display();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

顺序表Arraylist的遍历方式

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(12);
        list.add(23);
        list.add(34);
        list.add(45);
        //直接打印
        System.out.println(list);
        //for循坏遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("***********");
        //for——each遍历
        for (int x : list) {
            System.out.print(x+" ");
        }
        System.out.println();
        System.out.println("***********");
        //迭代器
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        System.out.println("***********");
        //从前往后打印
        ListIterator<Integer> it2 = list.listIterator();
        while (it2.hasNext()) {
            System.out.print(it2.next()+" ");
        }
        System.out.println();
        System.out.println("***********");
        //从后往前打印
        ListIterator<Integer> it3 = list.listIterator(list.size());
        while (it3.hasPrevious()) {
            System.out.print(it3.previous()+" ");
        }
        System.out.println();
    }
}

【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言

总结

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
【Java】实现顺序表基本的操作（数据结构）,java,数据结构,开发语言
1.ArrayList是以泛型方式实现的，使用时必须要先实例化
2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4.ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5.和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表文章来源地址https://www.toymoban.com/news/detail-769968.html

到了这里，关于【Java】实现顺序表基本的操作（数据结构）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包