正文
Java数据结构与算法(1) - ch02有序表(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();
}
}
