java——顺序表的方法实现

谁借莪１个温暖的怀抱￠ 2022-12-16 03:56 148阅读 0赞

## 顺序表需要有以下几点思考； ##

> 1.  顺序表中间/头部的插入删除，**时间复杂度为O(N)**
> 2.  增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
> 3.  增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间

顺序表的方法实现：

import java.util.Arrays;
    
    public class MyArrayList{
        
        public int[] array;//有效数组
        public int usedSize;//有效数据个数
        public static final int capacity = 10;//有效数据容量
    
        public MyArrayList(){
        
            this.array = new int[capacity];
            this.usedSize = 0;
        }
    
        // 打印顺序表
        public void display() {
        
            System.out.println("顺序表为：");
            System.out.println(Arrays.toString(this.array));
        }
    
        public boolean isFull(){
        
            if (this.usedSize == this.array.length){
        
                return true;
            }
            return false;
        }
    
        // 在 pos 位置新增元素
        public void add(int pos, int data) {
        
            if (isFull()){
        
                //扩容
                this.array = Arrays.copyOf(this.array, 2*this.array.length);
                // return;
            }
            if (pos < 0 || pos > this.usedSize){
        
                //如果位置为负数  或者  位置超过了有效数据个数范围
                return;
            }
            for (int i = this.usedSize-1; i >= pos; i--){
        
                //让pos后面的数依次往后挪
                this.array[i+1] = this.array[i];
            }
            //再把空出来的位置放上data的值
            this.array[pos] = data;
            this.usedSize++;
        }
    
        // 判定是否包含某个元素
        public boolean contains(int toFind) {
        
            for (int i = 0; i < this.usedSize; i++){
        
                if (toFind == this.array[i]){
        
                    return true;
                }
            }
            return false;
        }
    
        // 查找某个元素对应的位置
        public int search(int toFind) {
        
            for (int i = 0; i < this.usedSize; i++){
        
                if (toFind == this.array[i]){
        
                    return i;
                }
            }
            return -1;
        }
    
        public boolean isEmpty(){
        
            return this.usedSize == 0;
        }
    
        // 获取 pos 位置的元素
        public int getPos(int pos) {
        
            if (isEmpty()){
        
                throw new RuntimeException("顺序表为空");
               // return -1;
            }
            if (pos < 0 || pos >= this.usedSize){
        
                //如果位置为负数  或者  位置超过了有效数据个数范围
                //return -1;
                throw new RuntimeException("pos位置不合法");
            }
            return this.array[pos];
        }
    
        // 给 pos 位置的元素设为 value
        public void setPos(int pos, int value) {
        
            if (isEmpty()){
        
                throw new RuntimeException("顺序表为空");
            }
            if (pos < 0 || pos >= this.usedSize){
        
                //如果位置为负数  或者  位置超过了有效数据个数范围
                throw new RuntimeException("pos位置不合法");
            }
            this.array[pos] = value;
        }
    
        //删除第一次出现的关键字key
        public void remove(int toRemove) {
        
            int index = search(toRemove);
            if (index == -1){
        
                System.out.println("没有需要删除的数字！");
                return;
            }
            for (int i = index; i < this.usedSize-1; i++){
        
                this.array[i] = this.array[i+1];
            }
            this.usedSize--;
        }
    
        // 获取顺序表长度
        public int size() {
        
            return this.usedSize;
        }
    
        // 清空顺序表
        public void clear() {
        
            this.usedSize = 0;
        }
    }

主函数：

public class TestDemo1018_1 {
        
        public static void main(String[] args) {
        
            MyArrayList myArrayList = new MyArrayList();
            myArrayList.add(0,0);
            myArrayList.add(1,1);
            myArrayList.add(2,2);
            myArrayList.add(3,3);
            myArrayList.add(4,4);
            myArrayList.add(5,5);
            myArrayList.add(6,6);
    //        也可以这样赋值：
    //        for (int i = 0; i < 10; i++){
        
    //            myArrayList.add(i, i);
    //        }
            myArrayList.add(7,19);
            myArrayList.display();
    
            System.out.println(myArrayList.search(19));
    
            System.out.println(myArrayList.getPos(5));
    
            myArrayList.setPos(2,64);
            myArrayList.display();
    
        }
    }