数据结构-数组1

这一部分先简单描述一下数组的特性以及对数组的增删查等操作。

数组的大小固定，所以对于增加元素，只要数组空间中有空的位置就可以将要添加的元素添加进去。

对于数组元素的删除，删除对应位置的元素后，要将删除位用后面的元素填充。

 一、无序数组

无序数组是只在数组空间中，元素是按照插入顺序排列的，而不是按照元素之间的大小来排列。无序数组相对于有序数组而言，在插入的效率上要高，但是在查找的效率上要低。

代码如下：

 1 public class LowArray {
 2     private static final double BASIC_VALUE = 0;
 3     private double[] basicArray;
 4 
 5     public LowArray(int initialCapacity) {
 6         this.basicArray = new double[Math.max(initialCapacity, 0)];
 7     }
 8 
 9     public void setElements(int index, double value) {
10         this.checkIndex(index);
11         this.basicArray[index] = value;
12     }
13 
14     public double getElements(int index) {
15         this.checkIndex(index);
16         return this.basicArray[index];
17     }
18 
19     public boolean deleteElementsByIndex(int index) {
20         this.checkIndex(index);
21         int len = this.basicArray.length - 1;
22         for (int i = index; i < len; i++) {
23             this.basicArray[i] = this.basicArray[i + 1];
24         }
25         this.basicArray[len] = BASIC_VALUE;
26         return true;
27     }
28 
29     public boolean deleteElements(double value) {
30         boolean result = false;
31         int len = this.basicArray.length;
32         for (int i = 0; i < len; i++) {
33             if (Double.compare(this.basicArray[i], value) == 0) {
34                 result = this.deleteElementsByIndex(i);
35                 if (result) {
36                     break;
37                 }
38             }
39         }
40 
41         if (result) {
42             this.deleteElements(value);
43         }
44         return false;
45     }
46 
47     public void show() {
48         System.out.println(Arrays.toString(this.basicArray));
49     }
50 
51     private void checkIndex(int index) {
52         if (index > this.basicArray.length) {
53             throw new IllegalArgumentException("index is error,index:=" + index + ", length:=" + this.basicArray.length);
54         }
55     }
56 }
View Code

使用上述代码的样列如下：

 1 class LowArrayApp {
 2     public static void main(String[] args) {
 3         LowArray array = new LowArray(10);
 4 
 5         array.setElements(0, 12);
 6         array.setElements(1, 25);
 7         array.setElements(2, 1);
 8         array.setElements(3, -2);
 9         array.setElements(4, 12.21);
10         array.setElements(5, 1);
11 
12         array.show();
13 
14         array.deleteElements(12.21);
15         array.show();
16         array.deleteElements(1);
17         array.show();
18         array.deleteElementsByIndex(2);
19         array.show();
20     }
21 }
View Code

我们可以发现我们在调用上面的代码的时候需要指定你插入元素的位置，我们参考java中的ArrayList的实现（内部也是使用数组来保存数据的），我们重新将LowArray这个类重新实现一遍，代码如下所示：

  1 public class HightArray {
  2     private static final int BASIC_ARRAY_LENGTH = 16;
  3     private double[] basicArray;
  4     private int size;
  5     private int length;
  6 
  7     public HightArray() {
  8         this(BASIC_ARRAY_LENGTH);
  9     }
 10 
 11     public HightArray(int initialCapacity) {
 12         if (initialCapacity < 0) {
 13             initialCapacity = 0;
 14         }
 15         basicArray = new double[initialCapacity];
 16         this.length = initialCapacity;
 17         this.size = 0;
 18     }
 19 
 20     public void add(double value) {
 21         this.checkIndex(this.size + 1);
 22         this.basicArray[this.size++] = value;
 23     }
 24 
 25     public double get(int index) {
 26         this.checkIndex(index);
 27         return this.basicArray[index];
 28     }
 29 
 30     public boolean find(double value) {
 31         for (int i = 0; i < size; i++) {
 32             if (Double.compare(this.basicArray[i], value) == 0) {
 33                 return true;
 34             }
 35         }
 36         return false;
 37     }
 38 
 39     public void display() {
 40         for (int i = 0; i < size; i++) {
 41             System.out.print(this.basicArray[i] + "	");
 42             // System.out.print(i + ":" + this.basicArray[i] + "	");
 43         }
 44         System.out.println("");
 45         System.out.println("总数据有:" + this.size + "个");
 46     }
 47 
 48     public boolean deleteValue(double value) {
 49         boolean result = false;
 50         for (int i = 0; i < size; i++) {
 51             if (Double.compare(this.basicArray[i], value) == 0) {
 52                 result = this.deleteIndex(i);
 53                 if (result) {
 54                     break;
 55                 }
 56             }
 57         }
 58 
 59         if (result) {
 60             this.deleteValue(value);
 61         }
 62         return result;
 63     }
 64 
 65     public boolean deleteIndex(int index) {
 66         if (index >= size) {
 67             return false;
 68         }
 69 
 70         for (int i = index; i < size; i++) {
 71             this.basicArray[i] = this.basicArray[i + 1];
 72         }
 73         this.size--;
 74         return true;
 75     }
 76 
 77     public double getMax() {
 78         if (this.size == 0) {
 79             throw new NullPointerException();
 80         }
 81 
 82         double result = 0;
 83         for (int i = 0; i < size; i++) {
 84             if (Double.compare(this.basicArray[i], result) > 0) {
 85                 result = this.basicArray[i];
 86             }
 87         }
 88         return result;
 89     }
 90 
 91     public double removeMax() {
 92         if (this.size == 0) {
 93             throw new NullPointerException();
 94         }
 95 
 96         int maxindex = 0;
 97         double maxvalue = 0.0;
 98         for (int i = 0; i < size; i++) {
 99             if (Double.compare(this.basicArray[i], maxvalue) > 0) {
100                 maxindex = i;
101                 maxvalue = this.basicArray[i];
102             }
103         }
104         this.deleteIndex(maxindex);
105         return maxvalue;
106     }
107 
108     public int size() {
109         return this.size;
110     }
111 
112     private void checkIndex(int index) {
113         if (index >= this.length) {
114             throw new IllegalArgumentException("index is error,index:=" + index + ", length:=" + this.length);
115         }
116     }
117 }
View Code

那么我们将LowArray的代码改成HightArray后，对应的使用该类的代码也要进行改变，如下：

 1 class HightArrayApp {
 2     public static void main(String[] args) {
 3         HightArray array = new HightArray(10);
 4         array.add(1);
 5         array.add(12);
 6         array.add(111);
 7         array.add(12);
 8         array.add(11);
 9         array.add(14);
10         array.add(15);
11         array.add(17);
12         array.add(15);
13 
14         // ----------sort
15         double[] sortresult = new double[array.size()];
16         for (int i = 0; i < sortresult.length; i++) {
17             sortresult[i] = array.removeMax();
18         }
19         System.out.println(Arrays.toString(sortresult));
20 
21         System.out.println(array.getMax());
22         System.out.println(array.removeMax());
23 
24         array.display();
25 
26         System.out.println(array.find(111));
27         System.out.println(array.find(22));
28 
29         array.deleteIndex(2);
30         array.display();
31         array.deleteValue(14);
32         array.display();
33         array.deleteValue(15);
34         array.display();
35         array.deleteValue(12);
36         array.display();
37     }
38 }
View Code

二、有序数组

有序数组中的元素一般是按照某种规定的排序方式排列的，这个排序方式可以通过实现Comparable<T>接口(compareTo(T)方法)或者实现接口Comparator<T>(compare(T,T)方法)，亦或者是基本类型中的直接比较。

 代码如下：

  1 public class SortArray {
  2     private static final int BASIC_ARRAY_LENGTH = 16;
  3     private double[] basicArray;
  4     private int size;
  5     private int length;
  6 
  7     public SortArray() {
  8         this(BASIC_ARRAY_LENGTH);
  9     }
 10 
 11     public SortArray(int initialCapacity) {
 12         if (initialCapacity < 0) {
 13             initialCapacity = 0;
 14         }
 15         this.basicArray = new double[initialCapacity];
 16         this.length = initialCapacity;
 17         this.size = 0;
 18     }
 19 
 20     public int size() {
 21         return this.size;
 22     }
 23 
 24     public void add(double value) {
 25         checkSize(this.size + 1);
 26 
 27         int index = 0;
 28         for (; index < size; index++) {
 29             if (Double.compare(this.basicArray[index], value) > 0) {
 30                 break;
 31             }
 32         }
 33 
 34         this.moveAfterArray(index, index + 1, this.size - index);
 35         this.basicArray[index] = value;
 36         this.size++;
 37     }
 38 
 39     public double get(int index) {
 40         this.checkIndex(index);
 41         return this.basicArray[index];
 42     }
 43 
 44     public boolean find(double value) {
 45         return findIndex(this.basicArray, 0, this.size - 1, value) > -1;
 46     }
 47 
 48     public static int findIndex(double[] array, int left, int right, double value) {
 49         if (array == null || left > right || right+1 > array.length) {
 50             return -1;
 51         }
 52 
 53         int mid = -1;
 54         while (left <= right) {
 55             mid = (left + right) / 2;
 56             int compareResult = Double.compare(array[mid], value);
 57             if (compareResult == 0) {
 58                 return mid;
 59             } else if (compareResult < 0) {
 60                 // array[mid] < value
 61                 left = mid + 1;
 62             } else {
 63                 right = mid - 1;
 64             }
 65         }
 66         return -1;
 67     }
 68 
 69     public void display() {
 70         for (int i = 0; i < size; i++) {
 71             System.out.print(this.basicArray[i] + "	");
 72         }
 73         System.out.println("");
 74         System.out.println("总数据有:" + this.size + "个");
 75     }
 76 
 77     public boolean deleteValue(double value) {
 78         int index = findIndex(this.basicArray, 0, this.size - 1, value);
 79         if (index > -1) {
 80             this.deleteIndex(index);
 81             this.deleteValue(value);
 82             return true;
 83         } else {
 84             return false;
 85         }
 86     }
 87 
 88     public boolean deleteIndex(int index) {
 89         if (index >= size) {
 90             return false;
 91         }
 92         this.moveBeforeArray(index + 1, index, this.size - index - 1);
 93         this.size--;
 94         return true;
 95     }
 96 
 97     public double getMax() {
 98         if (this.size == 0) {
 99             throw new NullPointerException();
100         }
101 
102         return this.basicArray[this.size - 1];
103     }
104 
105     public double removeMax() {
106         if (this.size == 0) {
107             throw new NullPointerException();
108         }
109 
110         return this.basicArray[--this.size];
111     }
112 
113     private void moveAfterArray(int startIndex, int newStartIndex, int size) {
114         for (int i = size - 1; i >= 0; i--) {
115             this.basicArray[newStartIndex + i] = this.basicArray[startIndex + i];
116         }
117     }
118 
119     private void moveBeforeArray(int startIndex, int newStartIndex, int size) {
120         for (int i = 0; i < size; i++) {
121             this.basicArray[newStartIndex + i] = this.basicArray[startIndex + i];
122         }
123     }
124 
125     private void checkSize(int size) {
126         if (size > this.length) {
127             throw new IllegalArgumentException("array size is error,size:=" + size + ", array length:=" + this.length);
128         }
129     }
130 
131     private void checkIndex(int index) {
132         if (index >= this.size) {
133             throw new IllegalArgumentException("index is error,index:=" + index + ", size:=" + this.size);
134         }
135     }
136 }
View Code

对应的调用代码如下所示，调用代码和普通无序数组一样。

 1 class SortArrayApp {
 2     public static void main(String[] args) {
 3         SortArray array = new SortArray(10);
 4         array.add(1);
 5         array.add(12);
 6         array.add(111);
 7         array.add(12);
 8         array.add(11);
 9         array.add(14);
10         array.add(15);
11         array.add(17);
12         array.add(15);
13 
14         array.display();
15 
16         // delete by index
17         array.deleteIndex(4); // delete 14.0
18         array.display();
19 
20         // delete by value
21         array.deleteValue(17); // delete 17 one
22         array.deleteValue(12); // delete 12 two
23         array.display();
24     }
25 }
View Code

 

三、总结

通过上面的代码，我们可以看到，数组的添加是很方便的，但是删除和查找就比较麻烦了，从时间复杂度上面来说的话，数组有如下特性：

算法 运行时间
有序数组的插入  O(N) 
无序数组的插入 O(1)
有序数组的删除 O(N)
无序数组的删除 O(N)
有序数组的查找 O(logN)
无序数组的查找 O(N)
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/liuming1992/p/4194239.html