Java数据结构——代码实现顺序表的操作

骑猪看日落 2023-10-10 15:01 17阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

![e2a43e3ae2e74c2ea15117f5deba26f9.png][]

**文章目录**

顺序表

1.获取顺序表长度

2.打印顺序表中的所有元素

3.新增一个元素，默认在最后新增

4.在 pos 位置新增元素

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

6.查找某个元素对应的位置

7.获取 pos 位置的元素

8.给 pos 位置的元素更新为 value

9.删除第一次出现的关键字key

10.清空顺序表

--------------------

## 顺序表 ##

> 顺序表是用一段**物理地址连续**的，**存储单元依次存储数据**的**线性结构**。是在数组上完成数据的增删查改

接下来我们自己实现一些接口对数组进行增删查改的操作

创建一个类：

public class MyArrayList {
        public int[] elem;//数组
        public int usedSize;//记录有效数据的个数
        public static final int DEFAULT_SIZE = 10;
        public MyArrayList(int[] elem){
            this.elem = new int[DEFAULT_SIZE];
        }

### 1.获取顺序表长度 ###

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

### 2.打印顺序表中的所有元素 ###

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

### 3.新增一个元素，默认在最后新增 ###

步骤：检查当前顺序表是否满了；如果满了进行扩容；然后将元素放进去；usedSize++；

判满：

public boolean isFull(int[] elem){
            if(size()>=this.usedSize){
                return true;
            }
            else return false;
    }

扩容：

public void add(int data){
            if(isFull()){
                this.elem = 
                        Arrays.copyOf(this.elem,2*this.elem.length);
            }
            //添加数据
            this.elem[this.usedSize] = data;
            //有效数据加一
            this.usedSize++;
    
    }

测试：

public class TestList {
        public static void main(String[] args) {
            MyArrayList myArrayList = new MyArrayList();
            myArrayList.add(1);
            myArrayList.add(2);
            myArrayList.add(3);
            myArrayList.disPlay();
        }
    }

![045f9190cffb41e696c5838df6b14496.png][]

### 4.在 pos 位置新增元素 ###

注意：负数下标不能当Pos；不能超过数组长度插入；不能间隔着插入，即插入的位置前面一定有元素；

还是先判断数组是否满，满了扩容；然后判断pos位置是否合法；不合法抛出异常；插入后将其他元素后移

public void add(int pos, int data) {
            if(isFull()){
                System.out.println("满了");
                this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            }
            if(pos<0||pos>this.usedSize){
                System.out.println("pos位置不合法");
                throw new PosworongfulException("pos位置不合法");
            }
            //pos一定合法
            // 挪动数据
            for (int i = this.usedSize-1; i>=pos  ; i--) {
                this.elem[i+1] = this.elem[i];
            }
            //插入数据
            this.elem[pos] = data;
            //usedSize++
            this.usedSize++;
    }

添加10到1位置

try {
                    myArrayList.add(1,10);
            }
            catch (PosworongfulException e){
                    e.printStackTrace();
            }
                    myArrayList.disPlay();

![e25462ba785b4cfe8d4cb7ae14636877.png][]

在10位置添加数据

try {
                    myArrayList.add(10,10);
            }
            catch (PosworongfulException e){
                    e.printStackTrace();
            }
                    myArrayList.disPlay();

![f5e72cc660e4425dabbdca4321612dc5.png][]

### 5. 判定是否包含某个元素 ###

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

System.out.println("-------------");
        System.out.println(myArrayList.contains(10));
        System.out.println(myArrayList.contains(100));

![d71f1f75c37a422d896701dc976bdbc2.png][]

### 6.查找某个元素对应的位置 ###

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

System.out.println("-------------");
            System.out.println(myArrayList.indexOf(3));

![fd4065d9798940928c42e226f909f21c.png][]

### 7.获取 pos 位置的元素 ###

//判断为空
        public boolean isEmpty(){
            return size()==0;
        }
        // 获取 pos 位置的元素
        public int get(int pos) {
            if(isEmpty()){
                throw new EmptyException("当前顺序表为空");
            }
            if(pos<0||pos>=this.usedSize){
                throw new PosworongfulException("pos位置不合法");
            }
            return this.elem[pos];
        }

System.out.println("------------");
        System.out.println(myArrayList.get(0));
         try {
              myArrayList.get(10);
         }catch (PosworongfulException e){
               e.printStackTrace();
         }

![7b3c8d9dcb5b4d169bedd9954df7728d.png][]

### 8.给 pos 位置的元素更新为 value ###

public void set(int pos, int value) {
            if(isEmpty()){
                throw new EmptyException("顺序表为空");
            }
            if(pos<0||pos>=this.usedSize){
                throw new PosworongfulException("pos位置不合法");
            }
            this.elem[pos] = value;
    
        }

System.out.println("---------");
          myArrayList.set(0,100);
          myArrayList.disPlay();

![e30ea8d3ffb24fdea72b89590fbad2b2.png][]

### 9.删除第一次出现的关键字key ###

> 空表没有key
> 
> 先找到key，找到下标
> 
> 挪动数据
> 
> usedSize--

public void remove(int key) {
            if(isEmpty()){
                throw new EmptyException("顺序表为空");
            }
            int index = this.indexOf(key);
            if(index==-1){
                System.out.println("没有这个数字");
            }
            for (int i = index; i < size()-1; i++) {
                    this.elem[i] = this.elem[i+1];
            }
            this.usedSize--;
        }

System.out.println("---------");
            myArrayList.remove(3);
            myArrayList.disPlay();

![7c762922caa64d3e91484b819ffa5cba.png][]

### 10.清空顺序表 ###

此处顺序表元素不是引用类型，可直接将usedSize变为0来清空顺序表，如果是引用类型，则必须全部置空，否则会造成内存泄漏，空间无法回收

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

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[e2a43e3ae2e74c2ea15117f5deba26f9.png]: https://img-blog.csdnimg.cn/e2a43e3ae2e74c2ea15117f5deba26f9.png
[045f9190cffb41e696c5838df6b14496.png]: https://img-blog.csdnimg.cn/045f9190cffb41e696c5838df6b14496.png
[e25462ba785b4cfe8d4cb7ae14636877.png]: https://img-blog.csdnimg.cn/e25462ba785b4cfe8d4cb7ae14636877.png
[f5e72cc660e4425dabbdca4321612dc5.png]: https://img-blog.csdnimg.cn/f5e72cc660e4425dabbdca4321612dc5.png
[d71f1f75c37a422d896701dc976bdbc2.png]: https://img-blog.csdnimg.cn/d71f1f75c37a422d896701dc976bdbc2.png
[fd4065d9798940928c42e226f909f21c.png]: https://img-blog.csdnimg.cn/fd4065d9798940928c42e226f909f21c.png
[7b3c8d9dcb5b4d169bedd9954df7728d.png]: https://img-blog.csdnimg.cn/7b3c8d9dcb5b4d169bedd9954df7728d.png
[e30ea8d3ffb24fdea72b89590fbad2b2.png]: https://img-blog.csdnimg.cn/e30ea8d3ffb24fdea72b89590fbad2b2.png
[7c762922caa64d3e91484b819ffa5cba.png]: https://img-blog.csdnimg.cn/7c762922caa64d3e91484b819ffa5cba.png