java数据结构与算法--数组

痛定思痛。 2022-05-26 11:20 249阅读 0赞

1.数组基础

package com.evior.demo1;
    
    /** * 数组 * * 1 数组的创建 * 2 访问数组的数据项 * */ public class Array {
    
        public static void main(String[] args) {
            //1 数组的创建
            int[] arr=new int[5];
            int [] arr2=new  int[]{
      2,3,2};//3 数组的初始化
            int [] arr3={
      1,2,3};//3 数组的初始化
            //3 数组的初始化
            arr[0]=1;
    
           //2 访问数组的数据项
            System.out.println(arr[0]);
            System.out.println(arr2[0]);
            System.out.println(arr3[0]);
    
        }
    
    }

2.无序数组

package com.evior.demo2;
    
    /** * 无序数组 */ public class Array {
    
        //定义数组的有效长度
        private int realLength=0;
        private int[] arr;
        private int length;
    
    
        public Array(int maxLength) {
           arr=new int[maxLength];
           length=maxLength;
        }
    
        public Array() {
            arr=new int[50];
            length=50;
        }
    
        //插入
        public void insert(int value){
            if (realLength<length){
                arr[realLength]=value;
                realLength++;
            }else {
                throw new RuntimeException("有效长度到达最大值,无法继续插入");
            }
        }
    
    
        //查询
        public Integer find(int value){
            Integer flag=null;
            for (int i=0;i<arr.length;i++){
                if (arr[i]==value){
                    flag=i;
                    break;
                }
            }
            return flag;
    
        }
    
    
        //删除
        public void delete(int value){
    
            //查询
            if (find(value)!=null){
                //清除
                arr[find(value)]=0;
            }
        }
    
        //修改第一次遇到的
        public void updateOne(int oldValue,int newValue){
            for (int i=0;i<arr.length;i++){
                if (arr[i]==oldValue){
                    arr[i]=newValue;
                    break;
                }
            }
        }
    
    
        //修改所有遇到的
        public void updateAll(int oldValue,int newValue){
            for (int i=0;i<arr.length;i++){
                if (arr[i]==oldValue){
                    arr[i]=newValue;
                }
            }
        }
    
    
        //显示所有的数据
        public void display(){
            System.out.print("[");
            for (int i=0;i<arr.length-1;i++){
                System.out.print(arr[i]+",");
            }
            System.out.print(arr[arr.length-1]+"]");
            System.out.println();
        }
    }

测试

package com.evior.demo2;
    
    public class test {
    
        public static void main(String[] args) {
    
            Array array=new Array(3);
            array.insert(1);
            array.insert(2);
            array.insert(3);
            //array.insert(4);
            System.out.println(array.find(3));
            System.out.println(array.find(5));
            array.delete(3);
            array.delete(5);
            array.display();
            array.updateOne(1,2);
            array.display();
            array.updateAll(2,3);
            array.display();
        }
    }

结果

![70][]

3、有序数组

package com.evior.demo2;
    
    /** * 有序数组 * 1 使用自定义的类封装数组 * 2 添加类方法来实现数据操作 */ public class Array2 {
    
        //定义数组
        private long[] arr;
    
        private int realLength;
    
    
        //构造器
        public Array2(){
            //该类的默认初始化长度为50
            arr=new long[50];
        }
    
    
        //有参的构造器
        public Array2(int maxLength){
            arr=new long[maxLength];
        }
    
    
    
    
        //显示所有的数据
        public void display(){
            System.out.print("[");
            for (int i=0;i<arr.length-1;i++){
                System.out.print(arr[i]+",");
            }
            System.out.print(arr[arr.length-1]+"]");
            System.out.println();
        }
    
        //指定位置插入
        public void insert(int index,int value){
            if (arr.length-1<index){
                throw new RuntimeException("索引位置"+index+"不合理,插入失败");
            }
            if (index<0){
                throw new RuntimeException("索引位置"+index+"不合理,插入失败");
            }
            arr[index]=value;
    
        }
    
    
        //删除指定位置元素
        public void deleteByIndex(int index){
            if (arr.length-1<index){
                throw new RuntimeException("索引位置"+index+"不合理,删除失败");
            }
            if (index<0){
                throw new RuntimeException("索引位置"+index+"不合理,删除失败");
            }
            arr[index]=0;
            System.out.println();
        }
    
    
        //查找 根据值查索引 查询到返回索引 查询不到返回-1
        public long search(long value){
            int index=-1;
            for (int i=0;i<arr.length;i++){
                if (arr[i]==value){
                    index=i;
                    break;
                }
            }
            return index;
        }
    
    
        //通过索引查询数据  索引位置不合理返回0  索引位置合理返回对应的值
        public long serarchByIndex(int index){
            int value=0;
            if (arr.length-1<index){
                throw new RuntimeException("索引位置"+index+"不合理,查询失败");
            }
            if (index<0){
                throw new RuntimeException("索引位置"+index+"不合理,查询失败");
            }
            return arr[index];
        }
    
    
        //更新数据
        public void  update(int index,int value){
            if (arr.length-1<index){
                throw new RuntimeException("索引位置"+index+"不合理,查询失败");
            }
            if (index<0){
                throw new RuntimeException("索引位置"+index+"不合理,查询失败");
            }
    
            arr[index]=value;
    
        }
    
    
        /** *排序 从小到大 */ public void orderByDesc(){
            for (int i=0;i<arr.length-1;i++){
                for (int j=i+1;j<arr.length;j++){
                    //比较
                    if (arr[i]>arr[j]){
                        //换位子
                        long temp;
                        temp=arr[i];
                        arr[i]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
    
    
        }
    
        /** *排序 从大到小 */ public void orderByAsc(){
    
            for (int i=0;i<arr.length-1;i++){
                for (int j=i+1;j<arr.length;j++){
                    //比较
                    if (arr[i]<arr[j]){
                        //换位子
                        long temp;
                        temp=arr[i];
                        arr[i]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
        }
    
    
        /** * 完全二分法 */ public int binarySerarch(int value){
            //排序
            orderByDesc();
            //二分法
            //中间数
            int href=arr.length/2;
            int index=arr.length-href;
            long centerNum=  arr[index];
            int flag=0;
    
            while (true){
                if (centerNum==value){
                    return 1;
                }else if (centerNum>value){
                    href=href/2;
                    index=index-href;
                    if (href==0){
                        if (value==arr[0]){
                            return 1;
                        }else {
                            return -1;
                        }
                    }
                    centerNum=arr[index];
                    if (index<=0){
                        return -1;
                    }
    
                    if (flag==0)
                    {
                        flag=1;
                    }
                    if (flag==2){
                        return -1;
                    }
                }else if (centerNum<value){
                    href=href/2;
                    if (href==0){
                       if (value==arr.length){
                           return 1;
                       }else {
                           return -1;
                       }
                    }else {
                        index=href+index;
                    }
                    if (index>arr.length){
                        return -1;
                    }
                    centerNum=arr[index];
                    if (flag==0)
                    {
                        flag=2;
                    }
    
                    if (flag==1){
                        return -1;
                    }
                }
    
            }
    
        }
    
    
        //普通二分法
        public int binarySerarch2(int value){
            orderByDesc();
            //中间数的值
            int middle=0;
            //最小索引
            int low=0;
            //最大索引
            int pow=arr.length;
            while (true){
                middle=(low+pow)/2;
                if (low>=pow){
                    return -1;
                }else if(arr[middle]==value) {
                    return 1;
                }else {
                    if (arr[middle]>value){
                        pow=middle-1;
                    }else {
                        low=middle+1;
                    }
                }
            }
        }
    }

测试

package com.evior.demo2;
    
    public class Test2 {
    
    
        public static void main(String[] args) {
            Array2 array2=new Array2(5);
            array2.insert(0,20);
            array2.insert(1,10);
            array2.insert(2,30);
            array2.insert(3,0);
            array2.insert(4,10);
    
            array2.orderByDesc();
            array2.display();
            array2.orderByAsc();
            array2.display();
    
            System.out.println(array2.binarySerarch2(-500));
        }
    
    
    
    }

结果

![70 1][]

[70]: /images/20220526/a158ae70a4a845ea999ca2e37da461ee.png
[70 1]: /images/20220526/b2b17098215e445e85677a060351dae7.png