Java 实现在顺序表指定位置插入一个元素

心已赠人 2023-10-12 00:22 78阅读 0赞

**一、思路**

> 1.定义一个pos变量来记录要插入的位置.  
> 2.定义一个usedSize变量来记录元素个数.  
> 3.定义一个data变量来记录要插入的元素值.  
> 4.要保证pos位置合法，也就是不是负数，因为是要保证pos位置前是要有元素，因此也不能大于元素个数.  
> 5.也需要考虑顺序表满了需要扩容的问题.  
> 6.在开始插入之前，要将pos位置和它之后的所有元素向后位移一个位置，要注意的是是从末尾开始移动.  
> 7.插入元素的时候直接将data赋值给pos下标.  
> 8.插入成功后元素个数加1.

**二、图解**  
  
![97f7f9cc427d4a9cb1af8ac5eac144a8.png_pic_center][]  
当前 pos 指向的是 3 下标的位置，即要插入的位置是 3 下标的位置；data 是要插入的元素的值。  
  
如果要在当前的 pos 位置插入一个元素，则需要将 4、5 这两个元素各向后移动一个位置。  
需要注意的是要先移动 5，再移动 4，即先移动后面的位置，再移动前面的位置。

移动完成如下图。  
  
![e0298e9b5c5c46fe9af4c2646783c758.png_pic_center][]  
接下来只需要将 data 元素的值赋值给 pos 下标即可。  
  
插入完成的如下图。  
  
![932ab0ddb6c0406ab6e6168f97f57702.png_pic_center][]

**位置不合法的情况**  
  
![fe8adc9ee1e740ab9a654efa125cec1d.png_pic_center][]  
可以看到当前的 pos 位置不属于数组的范围，也就不可以插入到数组中。  
  
![92f46a4898234847b34769508b25c98f.png_pic_center][]  
因为要保证 pos 位置前是要有元素的，因此此时的情况也是不合法的一种。  
在上述这种情况下如果插入元素，将 4、5 两个元素向后移动，在 pos 位置插入之后，pos 位置前的那一个位置(3 下标)就浪费掉了。  
  
如果在移动元素的时候不是从末尾开始移动的比较不合理。  
  
![4d0d58a82069426e9673715eaee18f95.png_pic_center][]  
可以看到如果是在当前的 pos 位置插入元素，若此时不是从末尾位置移动，而是直接从 4 下标开始移动，会一次移动两个位置。效果如下图。  
  
![0da57826573246ea86472ce82d27bf18.png_pic_center][]  
可以看到此时在 pos 位置插入一个元素后，会浪费掉一个空间；并且是每一次插入就会浪费掉一个空间。

**三、代码**

// 2.在顺序表指定位置插入一个元素
        public void add(int pos, int data) {
        
            // 先判断顺序表是不是满的
            if (isFull()) {
        
                // 满了 - 扩容
                System.out.println("顺序表满了!!!");
                this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            }
    
            // pos 位置要合法
            if (pos < 0 || pos > this.usedSize) {
        
                // 此时为不合法
                System.out.println("插入位置不合法!!!");
                throw new PosWrongfulException("位置不合法！！！");
            }
    
            // 开始插入前要将 pos 位置和他后面的元素向后移
            for (int i = this.usedSize - 1; i >= pos ; i--) {
        
                // 将前一个元素赋值给后一个
                this.elem[i + 1] = this.elem[i];
            }
    
            // 开始插入
            this.elem[pos] = data;
            // 元素个数加1
            this.usedSize++;
        }

![28feab2584c144dda08e185f27dcdd67.png_pic_center][]  
上述图片是插入之前的顺序表元素，接下来在 1(元素2) 下标位置插入一个元素 10。  
  
![0d1a81f842424425a1fd1c84bc856c2b.png_pic_center][]  
可以看到此时 10 元素就出现到了 1 下标的位置，并且顺序表的结构也没有乱。

[97f7f9cc427d4a9cb1af8ac5eac144a8.png_pic_center]: https://img-blog.csdnimg.cn/97f7f9cc427d4a9cb1af8ac5eac144a8.png#pic_center
[e0298e9b5c5c46fe9af4c2646783c758.png_pic_center]: https://img-blog.csdnimg.cn/e0298e9b5c5c46fe9af4c2646783c758.png#pic_center
[932ab0ddb6c0406ab6e6168f97f57702.png_pic_center]: https://img-blog.csdnimg.cn/932ab0ddb6c0406ab6e6168f97f57702.png#pic_center
[fe8adc9ee1e740ab9a654efa125cec1d.png_pic_center]: https://img-blog.csdnimg.cn/fe8adc9ee1e740ab9a654efa125cec1d.png#pic_center
[92f46a4898234847b34769508b25c98f.png_pic_center]: https://img-blog.csdnimg.cn/92f46a4898234847b34769508b25c98f.png#pic_center
[4d0d58a82069426e9673715eaee18f95.png_pic_center]: https://img-blog.csdnimg.cn/4d0d58a82069426e9673715eaee18f95.png#pic_center
[0da57826573246ea86472ce82d27bf18.png_pic_center]: https://img-blog.csdnimg.cn/0da57826573246ea86472ce82d27bf18.png#pic_center
[28feab2584c144dda08e185f27dcdd67.png_pic_center]: https://img-blog.csdnimg.cn/28feab2584c144dda08e185f27dcdd67.png#pic_center
[0d1a81f842424425a1fd1c84bc856c2b.png_pic_center]: https://img-blog.csdnimg.cn/0d1a81f842424425a1fd1c84bc856c2b.png#pic_center