首页 > 代码库 > Java数据结构与算法(1) - 有序表(OrderedArray)
Java数据结构与算法(1) - 有序表(OrderedArray)
有序表需要掌握的插入方法，删除方法和二分法查找方法。
插入方法： 从前往后找到比要插入的值大的数组项，将该数组项及之后的项均后移一位（从最后一项起依次后移），最后将要插入的值插入当前数组项。
删除方法： 从前往后找到要删除的项，将该数组项之后的项均前移一位（从该数组项后一项起依次往前移）；
二分法查找： 通过将数组数据项范围不断对半分割来查找特定的数据项。
示例代码：
package chap02.OrderedArray;class OrdArray { private long[] a; private int nElems; public OrdArray(int max) { a = new long[max]; nElems = 0; } public int size() { return nElems; } // 插入方法 public void insert(long value) { int j; for(j=0; j<nElems; j++) { if(a[j] > value) { // (linear search) break; } } for(int k=nElems; k>j; k--) { // move bigger ones up a[k] = a[k-1]; } a[j] = value; nElems++; } // 删除方法 public boolean delete(long value) { int j = find(value); if(j==nElems) { return false; } else { for(int k=j; k<nElems; k++) { a[k] = a[k+1]; } nElems--; return true; } } // 二分法查找 public int find(long searchKey) { int lowerBound = 0; int upperBound = nElems-1; int curIn; while(true) { curIn = (lowerBound + upperBound ) / 2; if(a[curIn]==searchKey) { return curIn; // found it } else if(lowerBound > upperBound) { return nElems; // can‘t find it } else { if(a[curIn] < searchKey) { lowerBound = curIn + 1; // it‘s in upper half } else { upperBound = curIn - 1; // it‘s in lower half } } } } public void display() { for(int j=0; j<nElems; j++) { System.out.print(a[j] + " "); } System.out.println(""); } } class OrderedApp{ public static void main(String[] args) { int maxSize = 100; OrdArray arr; arr = new OrdArray(maxSize); arr.insert(77); arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); int searchKey = 55; if(arr.find(searchKey) != arr.size()) { System.out.println("Found " + searchKey); } else { System.out.println("Can‘t find " + searchKey); } arr.display(); arr.delete(00); arr.delete(55); arr.delete(99); arr.display(); } }
Java数据结构与算法(1) - 有序表(OrderedArray)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。