Java数据结构和算法笔记_参考教材：Java数据结构和算法（第二版），[美] Robert lafore-数组

╰+哭是因爲堅強的太久メ 2022-06-09 11:37 63阅读 0赞

参考教材：Java数据结构和算法（第二版），\[美\] Robert lafore

## 1、数据结构的特性 ##

![这里写图片描述][SouthEast]

## 2、 经典算法总结 ##

查找算法：线性查找和二分查找  
排序算法：  
用表展示：

## 第一讲 数组 ##

# 1. Java中数组的基础知识 #

1）创建数组

> 在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：  
> `int[] intArr = new int[10];`  
> 一旦创建数组，数组大小便不可改变。

2）访问数组数据项
    数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：

intArr[0] = 123;

3）数组的初始化
    当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。

int[] intArr = {1, 2, 3, 4, 5};

等效于下面使用new来创建数组并初始化：

int[] intArr = new int[5];
            intArr[0] = 1;
            intArr[1] = 2;
            intArr[2] = 3;
            intArr[3] = 4;
            intArr[4] = 5;

# 2、面向对象编程方式 #

## 1）使用自定义的类封装数组 ##

MyArray类：

public class MyArray {
        private long[] arr;
        private int size;   //记录数组的有效长度 
    
        public MyArray() {
            arr = new long[10];
        }
        public MyArray(int maxSize) {
            arr = new long[maxSize];
        }
    
        //向数组中插入数据
        public void insert(long element) {
            arr[size] = element;
            size++;
        }
    
        //显示数组中的数据
        public void show() {
            for(int i=0; i<size; i++) {
                if(i==0) {
                    System.out.print("[" + arr[i] + ", ");
                } else if(i==size-1) {
                    System.out.println(arr[i] + "]");
                } else {
                    System.out.print(arr[i] + ", ");
                }
            }
        }
    
        //根据值查找索引（出现该值的第一个位置）：线性查找
        public int queryByValue(long element) {
            int i;
            for(i=0; i<size; i++) {  // linear search 
                if(arr[i] == element) break;
            }
            if(i == size) {
                return -1;
            } else {
                return i;
            }
        }
    
        //根据索引查找值
        public long queryByIndex(int index) {
            if(index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                return arr[index];
            }
        }
    
        //删除数据
        public void delete(int index) {
            if(index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                //当size=maxSize，删除最后一个数时，不会执行for
                for(int i=index; i<size-1; i++) {
                    arr[index] = arr[index + 1];       
                    System.out.println("for");  
                }
                size--;
            }
        }
    
        //更新数据
        public void update(int index, long value) {
            if(index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                arr[index] = value;
            }
        }
    }

## 2）添加类方法实现数据操作 ##

测试MyArray类方法：

public void testMyArray() throws Exception {
            MyArray myArray = new MyArray();
            myArray.insert(123);
            myArray.insert(456);
            myArray.insert(789);
            myArray.show(); //[123, 456, 789]   
            System.out.println(myArray.queryByValue(111));  //-1
            System.out.println(myArray.queryByIndex(2));    //789
            myArray.delete(2);
            myArray.show(); //[123, 456]
            myArray.update(0, 0);
            myArray.show(); //[0, 456]
        }

# 3、有序数组 #

## 1）有序数组简介以及其优点 ##

> 有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。

## 2）构建有序数组 ##

将2.1中自定义的类封装数组MyArray的insert方法改为如下：

//向有序数组中插入数据，按大小从前往后排列
        public void insert(long element) {
            int i;
            for(i=0; i<size; i++) {  // find where it goes
                if(element<arr[i]) break;
            }
            for(int j=size; j>i; j--) {  // move bigger ones up
                arr[j] = arr[j-1];
            }
            arr[i] = element;
            size++;
        }

得到有序数组的类封装MyOrderedArray类，测试该类中的insert方法：

public void testMyOrderedArray() throws Exception {
            MyOrderedArray myOrderedArray = new MyOrderedArray();
            myOrderedArray.insert(999);
            myOrderedArray.insert(555);
            myOrderedArray.insert(777);
            myOrderedArray.show();  //[555, 777, 999]
        }

# 4、 查找算法 #

## 1）线性查找 ##

> 在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。

## 2）二分查找 ##

> 二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数<中间数，则表明要查的数在数组的前半段；如果要查的数>中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。

在有序数组的类封装类MyOrderedArray中添加binarySearch方法

//根据值二分查找索引（前提：有序）
        public int binarySearch(long value) {
            int middle = 0;
            int left = 0;
            int right = size - 1;
    
            while(true) {
                middle = (left + right) / 2;
                if(arr[middle] == value) {
                    return middle;  // found it
                } else if(left > right) {
                    return -1;  // can't found it
                } else {    // divide range
                    if(arr[middle] > value) {
                        right = middle - 1; //in lower half
                    } else {
                        left = middle + 1;  // in upper half
                    }
                }
            }
        }

测试该二分查找方法：

[SouthEast]: /images/20220609/0ab9463a4d5a4d02a1cd4526586b5aec.png