数据结构——java如何实现顺序表中增删查改操作

亦凉 2023-10-05 23:36 31阅读 0赞

#### 文章目录 ####

*  什么是顺序表
 *   *  1 在顺序表的尾部插入一个新元素
     *  2 在顺序表的指定位置插入一个新元素
     *  3 删除第一次出现的key元素
     *  4 清空顺序表
     *  5 查找顺序表中是否包含toFind的值
     *  6 查找某个对应元素的位置
     *  7 获取pos元素的位置
     *  8 将pos位置的元素更新为value

## 什么是顺序表 ##

顺序表属于线性表的一种，是一种用一段**地址连续的存储单元依次存储线性表的数据元素**。

我们是使用一维数组来实现顺序表的，它需要三个属性：

*  **存储空间的起始位置**：数组elem。
 *  **顺序表的最大储存量**：数组的长度
 *  **顺序表当前的长度**

![d54162833eee42a28cd4da0de37080fa.png][]

因为数组的下标是从0开始的，如果要获取5元素的位置，  
就要拿它的值减1，它的下标就是4。

要把顺序表的第一个数据元素存放到数组的第一个下标当中，其它的数据紧接着存放。

数组的第一个位置就是顺序表的起始位置。

### 1 在顺序表的尾部插入一个新元素 ###

*  要保证数组的空间没满，这样才可以插入一个新的元素。
 *  如果顺序表的数据元素个数大于或者等于数组的长度就说明空间已满，则就要开始扩容了。
 *  在扩容的时候，使用**Array.copyof**来实现扩容。

**插入前：** \- 有效数据个数是4

![4e0c8c57ad444843870cfec3b96139ac.png][]

**插入后：** \- 有效数据个数是5

![4cab69ed830f4d31afdba13787813a0c.png][]  
  
**顺序表满了的情况：** \- 有效数据个数是7

![26dceb20d74a41f1bfa61806cfc5c61a.png][]

代码实现：

//默认在顺序表最后新增元素 - data是要新增的元素
        public void add(int data) {
        
            //1. 检查当前的顺序表是不是满了
            //isFull()方法中会有一个值来表示当前顺序表是不是满了
            if (isFull()) {
        
                //2. 如果满了 就要进行扩容
                //将elem扩容位原来的2倍
                this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            }
    
            //3.新增元素
            //当前usedSize(有效元素个数)的值就是顺序表末尾的下标 - 要想新增赋值即可
            this.elem[this.usedSize] = data;
    
            //4.有效元素个数加1 - usedSize
            this.usedSize++;

### 2 在顺序表的指定位置插入一个新元素 ###

*  先把要插入的位置的元素以及它后面的元素**后移**。
 *  开始插入到指定位置

需要注意的是，**指定位置的下标不能是负数**，在指定位置插入元素的时候在**指定位置前要有元素**。

下面pos位置前没有元素，所以它的位置不合法。

![1c02b44314394fe6bb2a703dea998d16.png][]

**插入前：**

![65541c3ad69343ca87ce39da93fc3b8c.png][]

**插入后：**  
![6716b3d938b847e38c8f4eed99c57e70.png][]

代码实现：

//在顺序表指定位置新增 - 在pos位置新增元素- data是要新增的元素
        //throws PosWrongfulException可以提示调用者这个地方可能会有一个异常
        public void add(int pos, int data) throws PosWrongfulException{
        
            //1.负数下标不可以
            //2.要存储的位置pos前面一定是有元素的
            //usedSize在这里指的是顺序表末尾的位置下标
            if (pos < 0 || pos > this.usedSize) {
         //pos是指定新增位置的下标
                System.out.println("位置不合法！！！");
    
                //抛一个异常
                throw new PosWrongfulException("位置不合法！！！");
            }
            if (isFull()) {
        
                //3.超过数组长度不可以
                //满了就扩容
                System.out.println("顺序表满了");
                this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            }
    
            //程序执行到这里就可以插入一个元素了
            //1.开始挪动数据
            //从顺序表末位位置开始向后移动，直到遇到 pos 位置
            for (int i = this.usedSize - 1; i >= pos; i--) {
         //usedSize-1指的是顺序表末位位置的下标
                this.elem[i + 1] =  this.elem[i];
            }
    
            //2.在顺序表中插入一个元素
            this.elem[pos] = data; //data是要插入个元素
    
            //3.顺序表元素加1 - usedSize
            this.usedSize++; //顺序表有效元素个数加一个
        }

### 3 删除第一次出现的key元素 ###

删除前：

![10976c5abedf442b92d4fa380c2102ed.png][]  
  
删除后：

![a0576108584046a394325bd063ed61ba.png][]

删除过程：

![a8d58f7c2d9d4146a23204dfe91de13a.png][]  
删除本质上就是将删除的元素覆盖掉。

实现思路：

*  先要找到key的位置，空的表中没有key。
 *  得到了key的下标。
 *  开始覆盖key，key后面的向前覆盖。
 *  表的有效数据个数减1。

代码实现：

//删除第一次出现的关键字 Key - Key是多次出现的元素
        public void remove (int Key) {
        
            //1.空的顺序表没有 Key
            if (isEmpty()) {
        
                //因为作用是删除，即使是空表也不需要扩容
                throw new EmptyException("顺序表为空！！！");
            }
            int index = indexOf(Key);//查找Key位置的下标
            if (index == -1) {
        
                System.out.println("没有这个数字！！！");
                return;
            }
    
            //2.要先找到key，才能知道下标
            //数组是从要删除的元素开始遍历，直到遇到在数组末尾的有效数据元素结束
            for (int i = index; i < usedSize - 1; i++) {
        
                //3.挪动数据
                this.elem[i] = this.elem[i + 1];//将顺序表后一个元素向前一个元素的位置覆盖
            }
    
            //4，顺序表长度减1
            this.usedSize--;//顺序表长度减1
        }

### 4 清空顺序表 ###

在顺序表中的元素分为**普通类型**和**引用类型**两种。

*  如果是普通类型直接将顺序表的有效数据个数置为0即可。
 *  如果是引用类型则要将每一个空间都置为空。

实现思路：

*  写一个循环将顺序表的每块空间都置为null。
 *  直接把有效数据个数（usedSize）改成0即可。

引用类型代码示例：

//0表示的是表的第一个元素，遍历完整个表结束
     for (int i = 0; i < usedSize; i++) {
        
          this.elem[i] = null;//将每一个元素都置为空
     }

普通类型代码示例：

this.usedSize = 0;

### 5 查找顺序表中是否包含toFind的值 ###

![8231a62560a243e0bb733f58882fe467.png][]  
  
实现思路

*  遍历顺序表与toFind的值比较
 *  找到返回true
 *  若遍历结束还没找到就返回false

public boolean contains(int toFind) {
        
        //size()方法求的是顺序表的长度
        for (int i = 0; i < this.size(); i++) {
        
             if (this.elem[i] == toFind) {
        
                 return true;//找到了
             }
        }
        return false;///没找到
    }

找不到的情况

![62a00ac33b124aecb2e9b68379d6c531.png][]

上面的图中即使是将顺序表遍历完也无法查找出来，因为表中根本就没有4。

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

![6da076ea8a184dedb6cf2d58c091d8f1.png][]

实现思路

*  遍历顺序表查找是否存在toFind这个元素
 *  若找到返回toFind的下标
 *  若遍历结束扔未找到则返回-1

public int indexOf (int toFind) {
        
         //size()方法求的是顺序表的长度
         for (int i = 0; i < this.size(); i++) {
        
              //若顺序表存储的是引用数据类型，该怎么比较？要使用 equals()来比较
              if (this.elem[i] == toFind) {
        
                  return i;//找到了 - 返回下标
              }
         }
         return -1;//没找到 - 返回-1
    }

找不到的情况

![570f3c5280d242fd94205a72c9d3ddf2.png][]

顺序表中没有这个元素

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

![在这里插入图片描述][bbba51c183b742269cf1ee1b83366d18.png]

实现思路：

*  pos的位置不能是负数并且不能超过数组的长度
 *  顺序表不能空的
 *  若不是空的就返回pos的下标

//获取 pos 元素的位置
    public int get(int pos) {
        
        if (isEmpty()) {
        
            //顺序表有可能是空的 - 抛异常来提示
            throw new EmptyException("当前顺序表为空！！！");
        }
        if (pos < 0 || pos >= usedSize) {
        
            //查找位置的下标可能是负数 - 也可能超过了顺序表的长度 - 抛异常来提示
            throw new PosWrongfulException("get获取元素的时候，pos位置不合法！！！");
        }
        return this.elem[pos];//此时pos下标就是要找的位置
    }

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

![f46d5c1ee4eb42b09cd9ff98f84cc0b0.png][]  
  
实现思路：

*  顺序表不能是空的，并且位置要合法
 *  直接将数组中pos下标的值改为value值
 *  因为只需要更改，即使是空间满了也不需要考虑扩容

//给 pos 位置的元素更新为 value
        public void set(int pos, int value) {
        
            //1.顺序表不是空的
            if (isEmpty()) {
        
                //顺序表有可能是空的 - 抛异常来提示
                //这里要注意的是此方法是用来更新的，即使是空间满了也不需要扩容
                throw new EmptyException("当前顺序表为空！！！");
            }
    
            //2.pos位置要合法 - 下标不为负数，不超过数组长度
            if (pos < 0 || pos >= usedSize) {
        
                //查找位置的下标可能是负数 - 也可能超过了顺序表的长度 - 抛异常来提示
                throw new PosWrongfulException("set获取元素的时候，pos位置不合法！！！");
            }
    
            //开始更新
            this.elem[pos] = value;//value是更新后的值
        }

[d54162833eee42a28cd4da0de37080fa.png]: https://img-blog.csdnimg.cn/d54162833eee42a28cd4da0de37080fa.png
[4e0c8c57ad444843870cfec3b96139ac.png]: https://img-blog.csdnimg.cn/4e0c8c57ad444843870cfec3b96139ac.png
[4cab69ed830f4d31afdba13787813a0c.png]: https://img-blog.csdnimg.cn/4cab69ed830f4d31afdba13787813a0c.png
[26dceb20d74a41f1bfa61806cfc5c61a.png]: https://img-blog.csdnimg.cn/26dceb20d74a41f1bfa61806cfc5c61a.png
[1c02b44314394fe6bb2a703dea998d16.png]: https://img-blog.csdnimg.cn/1c02b44314394fe6bb2a703dea998d16.png
[65541c3ad69343ca87ce39da93fc3b8c.png]: https://img-blog.csdnimg.cn/65541c3ad69343ca87ce39da93fc3b8c.png
[6716b3d938b847e38c8f4eed99c57e70.png]: https://img-blog.csdnimg.cn/6716b3d938b847e38c8f4eed99c57e70.png
[10976c5abedf442b92d4fa380c2102ed.png]: https://img-blog.csdnimg.cn/10976c5abedf442b92d4fa380c2102ed.png
[a0576108584046a394325bd063ed61ba.png]: https://img-blog.csdnimg.cn/a0576108584046a394325bd063ed61ba.png
[a8d58f7c2d9d4146a23204dfe91de13a.png]: https://img-blog.csdnimg.cn/a8d58f7c2d9d4146a23204dfe91de13a.png
[8231a62560a243e0bb733f58882fe467.png]: https://img-blog.csdnimg.cn/8231a62560a243e0bb733f58882fe467.png
[62a00ac33b124aecb2e9b68379d6c531.png]: https://img-blog.csdnimg.cn/62a00ac33b124aecb2e9b68379d6c531.png
[6da076ea8a184dedb6cf2d58c091d8f1.png]: https://img-blog.csdnimg.cn/6da076ea8a184dedb6cf2d58c091d8f1.png
[570f3c5280d242fd94205a72c9d3ddf2.png]: https://img-blog.csdnimg.cn/570f3c5280d242fd94205a72c9d3ddf2.png
[bbba51c183b742269cf1ee1b83366d18.png]: https://img-blog.csdnimg.cn/bbba51c183b742269cf1ee1b83366d18.png
[f46d5c1ee4eb42b09cd9ff98f84cc0b0.png]: https://img-blog.csdnimg.cn/f46d5c1ee4eb42b09cd9ff98f84cc0b0.png