不想说话,自闭中..

数据结构之数组

数组作为最为基础的数据结构,以线性结构来存储固定大小、相同类型的数据。
Java中已经为我们封装好了ArrayList来描述各种操作,下面将自定义类分装并描述数组的操作。

  • 数组操作之增删改查

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    package Array;

    public class MyArray {
    private long[] arr;
    //表示有效数据的长度

    private int elements;

    public MyArray() {
    arr = new long[50];
    }

    public MyArray(int maxsize) {
    arr = new long[maxsize];
    }

    /**
    * 添加数据
    * @param value
    */
    public void insert(long value) {
    arr[elements] = value;
    elements++;
    }

    /**
    * 显示数据
    */
    public void display() {
    System.out.print("[ ");
    for(int i = 0; i < elements; i++) {
    System.out.print(arr[i] + " ");
    }
    System.out.println("]");
    }

    /**
    * 查找数据,根据值来查询
    * 线性查找,从头到尾的查
    * @param value
    */
    public int search(long value) {
    int i;
    for(i = 0; i < elements; i++) {
    if(value == arr[i]){
    break;
    }
    }
    if(i == elements) {
    return -1;
    } else {
    return i;
    }
    }

    /**
    * 查询数据,根据索引来查询
    * @param index
    * @return
    */
    public long get(int index) {
    if(index >= elements || index < 0) {
    throw new ArrayIndexOutOfBoundsException();
    } else {
    return arr[index];
    }
    }

    /**
    * 删除数据
    * @param index
    */
    public void delete(int index) {
    if(index >= elements || index < 0) {
    throw new ArrayIndexOutOfBoundsException();
    } else {
    for(int i = index; i < elements; i++) {
    arr[index] = arr[index+1];
    }
    elements--;
    }
    }

    /**
    * 更新数据
    * @param index
    * @param newvalue
    */
    public void change(int index, int newvalue) {
    if(index >= elements || index < 0) {
    throw new ArrayIndexOutOfBoundsException();
    } else {
    arr[index] = newvalue;
    }
    }
    }
  • 构建有序数组

    构建有序的数组,需要注意的点是在添加元素的时候需要进行值得判断,并从后向前的进行值的交换。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /**
    * 添加数据
    * @param value
    */
    public void insert(long value) {
    int i;
    for(i = 0; i < elements; i++) {
    if(arr[i] > value) {
    break;
    }
    }
    for(int j = elements; j > i; j--) {
    arr[j] = arr[j-1];
    }
    arr[i] = value;
    elements++;
    }
  • 二分法查找数据

    二分法顾名思义即将数组切为两部分,通过比较查询值与中间值,来判断查询值所处范围,来进一步缩小查询范围,直到查询值等于中间值为止。
    二分法查找的使用前提是为有序的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 二分法查找
* @param value
* @return
*/
public int binarySearch(long value) {
int middle = 0;
int low = 0;
int pow = elements;

while(true) {
middle = (pow + low) / 2;
if(value == arr[middle]) {
return middle;
} else if(low > pow) {
return -1;
} else {
if(value < arr[middle]) {
pow = middle - 1;
} else {
low = middle + 1;
}
}
}
}
  • 测试类
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    package Array;

    public class TestMyArray {
    public static void main(String[] args) {
    /* MyArray arr = new MyArray();
    arr.insert(13);
    arr.insert(23);
    arr.insert(54);

    arr.display();
    System.out.println(arr.search(23));

    System.out.println(arr.get(1));

    arr.delete(1);
    arr.display();

    arr.change(0,22);
    arr.display();*/

    MyOrderArray arr = new MyOrderArray();
    arr.insert(76);
    arr.insert(45);
    arr.insert(96);
    arr.insert(31);
    arr.display();

    System.out.println(arr.binarySearch(96));
    }
    }