首页 > 代码库 > 【数据结构与算法01】数组
【数据结构与算法01】数组
数组是应用最广泛的数据存储结构。它被植入到大部分的编程语言中,由于数组十分易懂,所以在这里就不赘述,主要附上两端代码,一个是普通的数组,另一个是有序数组。有序数组是按关键字升序(或降序)排列的,这种排列使快速查找数据项成为可能,即可以使用二分查找。
普通数组的Java代码:
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.print(a[i] + " "); } System.out.println(""); } }
有序数组的java代码:
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; } //--------------二分法查找某个值----------------// 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.print(a[i] + " "); } System.out.println(""); } }
对于数组这种数据结构,线性查找的话,时间复杂度为O(N),二分查找的话时间为O(longN),无序数组插入的时间复杂度为O(1),有序数组插入的时间复杂度为O(N),删除操作的时间复杂度均为O(N)。
【数据结构与算法01】数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。