#数组 --- ``` /** * 普通数组的Java代码 * @author dream * */ public class GeneralArray { private int[] a; private int size; //数组的大小 private int nElem; //数组中有多少项 public GeneralArray(int max){ this.a = new int[max]; this.size = max; this.nElem = 0; } public boolean find(int searchNum){ //查找某个值 int j; for(j = 0; j < nElem; j++){ if(a[j] == searchNum){ break; } } if(j == nElem){ return false; }else { return true; } } public boolean insert(int value){ //插入某个值 if(nElem == size){ System.out.println("数组已满"); return false; } a[nElem] = value; nElem++; return true; } public boolean delete(int value){ //删除某个值 int j; for(j = 0; j < nElem; j++){ if(a[j] == value){ break; } } if(j == nElem){ return false; } if(nElem == size){ for(int k = j; k < nElem - 1; k++){ a[k] = a[k+1]; } }else { for(int k = j; k < nElem; k++){ a[k] = a[k+1]; } } nElem--; return true; } public void display(){ //打印整个数组 for(int i = 0; i < nElem; i++){ System.out.println(a[i] + " "); } System.out.println(""); } } ``` ``` /** * 有序数组的Java代码 * @author dream * */ /** * 对于数组这种数据结构， * 线性查找的话，时间复杂度为O(N)， * 二分查找的话时间为O(longN)， * 无序数组插入的时间复杂度为O(1)， * 有序数组插入的时间复杂度为O(N)， * 删除操作的时间复杂度均为O(N)。 * @author dream * */ public class OrderedArray { private long[] a; private int size; //数组的大小 private int nElem; //数组中有多少项 public OrderedArray(int max){ //初始化数组 this.a = new long[max]; this.size = max; this.nElem = 0; } public int size(){ //返回数组实际有多少值 return this.nElem; } /** * 二分查找 * @param searchNum * @return */ public int find(long searchNum){ int lower = 0; int upper = nElem - 1; int curr; while (true) { curr = (lower + upper) / 2; if(a[curr] == searchNum){ return curr; }else if(lower > upper){ return -1; }else { if(a[curr] < searchNum){ lower = curr + 1; }else { upper = curr - 1; } } } } public boolean insert(long value){ //插入某个值 if(nElem == size){ System.out.println("数组已满!"); return false; } int j; for(j = 0; j < nElem; j++){ if(a[j] > value){ break; } } for(int k = nElem; k > j; k++){ a[k] = a[k-1]; } a[j] = value; nElem++; return true; } public boolean delete(long value){ //删除某个值 int j = find(value); if(j == -1){ System.out.println("没有该元素!"); return false; } if(nElem == size){ for(int k = j; k < nElem - 1; k++){ a[k] = a[k+1]; } a[nElem-1] = 0; }else { for(int k = j; k < nElem; k++){ a[k] = a[k+1]; } } nElem--; return true; } public void display(){ //打印整个数组 for(int i = 0; i < nElem; i++){ System.out.println(a[i] + " "); } System.out.println(""); } } ```