animated.java

Java经典例程 从外国一大学计算机教授出版物下载的代码 经典

  import javagently.*;
  import java.io.*;

  class Animated {

    /* The animated binary search program  by J M Bishop   Jan 1997
     * ==================================  Java 1.1
     *                                     improved August 2000
     * searches a sorted sequence for a given value
     * and shows the workings of binary sort.
     *
     * Illustrates recursion and user defined exceptions
     */

    static item a [] = new item [10];
    static int counter;

    static int binarySearch (item a [], item x, int left, int right)
    //---------------------
                             throws ItemNotFoundException {
      display(a,left,right);
      if (left==right)
        if (x.equals(a[left])) return left;
        else throw new ItemNotFoundException ();
     else {
       int mid = (int) ((left+right) / 2);
       if (x.equals(a[mid]))
         return mid;
       else
         if (x.less(a[mid]))
       return binarySearch (a, x, left, mid);
         else
       return binarySearch (a, x, mid+1, right);
     }
    }
  }

    public static void main (String args [])
      			   throws IOException {

      BufferedReader in = new Stream(System.in);
      System.out.println("**** Testing the binary search ****");
      System.out.println("Type in 10 sorted characters "+
            "separated by spaces");
      for (int i=0; i<a.length;i++)
        a[i] = new item (Stream.readChar(in));

      // Loop to try several searches
      while (true)
        try {
          counter = 0;
          Text.prompt("Find what value?");
          item x = new item(Stream.readChar(in));
          System.out.println("The array is:");
          System.out.println("0  1  2  3  4  5  6  7  8  9");

          try {
            int found = BinarySearch (a, x, 0, a.length-1);
            // do what ever is necessary with a[found]
            System.out.println((char) x.data+
                   " was found at position "+found
                   +" in "+counter+" probes.");
          }
          catch (ItemNotFoundException e ) {
            // react to x not being there
            System.out.println((char) x.data+" was not found in "
              +counter+" probes.");
          }
        }
      catch (EOFException e) {break;}
    }

    static void display (item [] a, int left, int right) {
      for (int j = 0; j < left; j++)
        System.out.print("   ");
      for (int j = left; j <= right; j++)
        System.out.print((char) a[j].data+"  ");
      System.out.println();
      counter++;
    }

  }

    class item {
    // ---------
    // the objects being sorted

      item (char i) {
        data = i;
      }

      boolean equals (item x) {
        return data==x.data;
      }

      boolean less (item x) {
        return data < x.data;
      }

      char data;
    }
  class ItemNotFoundException extends Exception { }