Java数据结构与算法(1) - 有序表(OrderedArray)

浏览数：22 / 时间：2015年06月08日

有序表需要掌握的插入方法，删除方法和二分法查找方法。

插入方法：从前往后找到比要插入的值大的数组项，将该数组项及之后的项均后移一位（从最后一项起依次后移），最后将要插入的值插入当前数组项。

删除方法：从前往后找到要删除的项，将该数组项之后的项均前移一位（从该数组项后一项起依次往前移）；

二分法查找：通过将数组数据项范围不断对半分割来查找特定的数据项。

示例代码：

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();                  
    }   
}