《java数据结构和算法》---第二章数组，编程作业

// orderedArray.java
// demonstrates ordered array class
// to run this program: C>java OrderedApp
////////////////////////////////////////////////////////////////
class OrdArray
   {
   private long[] a; // ref to array a
   private int nElems; // number of data items
   //-----------------------------------------------------------
   public OrdArray(int max) // constructor
      {
      a = new long[max]; // create array
      nElems = 0;
      }
   //-----------------------------------------------------------
   public int size()
      { return nElems; }
   //-----------------------------------------------------------
   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 // divide range
            {
            if(a[curIn] < searchKey)
               lowerBound = curIn + 1; // it's in upper half
            else
               upperBound = curIn - 1; // it's in lower half
            } // end else divide range
         } // end while
      } // end find()
   //-----------------------------------------------------------
   public void insert(long value) // put element into array
      {
      int j;
      for(j=0; j<nElems; j++) // find where it goes
         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; // insert it
      nElems++; // increment size
      } // end insert()

   //采用二分查找法，进行数据插入操作 递增排序  程晓鹏 2016.08.18 add 编程作业2.4
   public void insert2(long value){
      int j; //要插入数据的位置
      int bIdx = 0; // 二分查找开始索引号码
      int eIdx = nElems - 1; //二分查找终止编码
      int curIdx = 0; //中间索引编码
      while(true){
     curIdx = (bIdx + eIdx) / 2;
         if(bIdx > eIdx){ //当不含任何元素时
             j = nElems;
     break;
     }else if(bIdx == curIdx && nElems > 0){
     if(value >= a[bIdx] && value >= a[eIdx]){
        j = eIdx+1;
     }else if (value >= a[bIdx]){
        j = eIdx;
     }
     else{
        j =bIdx;
     }
     break;
     }else if (a[curIdx] < value){
         bIdx = curIdx + 1;
     }else{
             eIdx = curIdx - 1;
     }
      }
      System.out.println("value = " + value + ",insert idx = " + j + ", bIdx=" + bIdx + ", eIdx=" + eIdx + ", mIdx = " +curIdx);
       for(int k=nElems; k>j; k--) // move bigger ones up
         a[k] = a[k-1];
      a[j] = value; // insert it
      nElems++; // increment size

   }
   //-----------------------------------------------------------
   public boolean delete(long value)
      {
      int j = find(value);
      if(j==nElems) // can't find it
         return false;
      else // found it
         {
         for(int k=j; k<nElems; k++) // move bigger ones down
            a[k] = a[k+1];
         nElems--; // decrement size
         return true;
         }
      } // end delete()
   //-----------------------------------------------------------
   public void display() // displays array contents
      {
      for(int j=0; j<nElems; j++) // for each element,
         System.out.print(a[j] + " "); // display it
      System.out.println("");
      }
   //-----------------------------------------------------------
   } // end class OrdArray
////////////////////////////////////////////////////////////////
class OrderedApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100; // array size
      OrdArray arr; // reference to array
      arr = new OrdArray(maxSize); // create the array

      arr.insert2(77); //编程作业 2.4
      arr.insert2(99);
      arr.insert2(44);
      arr.insert2(11);
      arr.insert2(55);
      arr.insert2(22);
      arr.insert2(88);
      arr.insert2(00);
      arr.insert2(66);
      arr.insert2(33);

      System.out.println("insert data result is");
      arr.display();
      int searchKey = 55; // search for item
      if( arr.find(searchKey) != arr.size() )
         System.out.println("Found " + searchKey);
      else
         System.out.println("Can't find " + searchKey);

      arr.display(); // display items

      arr.delete(00); // delete 3 items
      arr.delete(55);
      arr.delete(99);

      arr.display(); // display items again
      } // end main()
   }

执行结果

// highArray.java
// demonstrates array class with high-level interface
// to run this program: C>java HighArrayApp
////////////////////////////////////////////////////////////////
class HighArray
   {
   private long[] a; // ref to array a
   private int nElems; // number of data items
   //-----------------------------------------------------------
   public HighArray(int max) // constructor
      {
      a = new long[max]; // create the array
      nElems = 0; // no items yet
      }
   //-----------------------------------------------------------
   public boolean find(long searchKey)
      { // find specified value
      int j;
      for(j=0; j<nElems; j++) // for each element,
         if(a[j] == searchKey) // found item?
            break; // exit loop before end
      if(j == nElems) // gone to end?
         return false; // yes, can't find it
      else
         return true; // no, found it
      } // end find()
   //-----------------------------------------------------------
   //获取最大值函数 编程作业2.1 程晓鹏 2016.08.17 add
   public long getMax(){
      long result = -1;
      for(int i=0; i<nElems; i++){
     if(a[i] > result){
             result = a[i];
     }
      }
      return result;
   }

   //删除最大值 编程作业2.2  程晓鹏 2016.08.17 add
   public long removeMax(){
      long result = -1;
      int i=-1; // 最大值索引值
      for(int ii=0; ii<nElems; ii++){
     if(a[ii] > result){
             result = a[ii];
             i = ii;
     }
      }

      if(i !=nElems && i != -1){
     for(int j=i; j<nElems; j++){
         a[j] = a[j+1];
     }
     nElems--;
      }
      return result;
   }

   //选择排序 编程作业2.3 程晓鹏 2016.08.17 add
   public void xuanzeSort(){
     for (int i=0; i<nElems; i++){
     long max=a[i];
     int index = i;
     for(int j=i+1; j<nElems; j++){
            if(a[j]>max){
         max=a[j];
         index = j;
     }
     }

     if(index != i){
     long temp=a[i];
        a[i]=a[index];
        a[index]=temp;
     }

     }
   }

   //删除重复项 编程作业2.6 程晓鹏 2016.08.18 add
   public void noDup(){
      for(int i=0; i<nElems; i++){
         long tmp = a[i];
     for(int j=i+1; j<nElems; j++){
     if(tmp == a[j]){ //当出现重复数据时，进行
         for(int k=j; k<nElems; k++){
            a[k] = a[k+1];
         }

         nElems--;
         j--; //减一，防止两个连续的重复的出现
     }
     }
      }
   }

   //-----------------------------------------------------------
   public void insert(long value) // put element into array
      {
      a[nElems] = value; // insert it
      nElems++; // increment size
      }
   //-----------------------------------------------------------
   public boolean delete(long value)
      {
      int j;
      for(j=0; j<nElems; j++) // look for it
         if( value == a[j] )
            break;
      if(j==nElems) // can't find it
         return false;
      else // found it
         {
         for(int k=j; k<nElems; k++) // move higher ones down
            a[k] = a[k+1];
         nElems--; // decrement size
         return true;
         }
      } // end delete()
   //-----------------------------------------------------------
   public void display() // displays array contents
      {
      for(int j=0; j<nElems; j++) // for each element,
         System.out.print(a[j] + " "); // display it
      System.out.println("");
      }
   //-----------------------------------------------------------
   } // end class HighArray
////////////////////////////////////////////////////////////////
class HighArrayApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100; // array size
      HighArray arr; // reference to array
      arr = new HighArray(maxSize); // create the array

      arr.insert(77); // insert 10 items
      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(22);
      arr.insert(33);
      arr.insert(15);
      arr.insert(22);
      arr.insert(14);

      arr.display(); // display items

      int searchKey = 35; // search for item
      if( arr.find(searchKey) )
         System.out.println("Found " + searchKey);
      else
         System.out.println("Can't find " + searchKey);

      arr.delete(00); // delete 3 items
      arr.delete(55);
      arr.delete(33);

      arr.display(); // display items again
      arr.noDup(); //编程作业2.6
      System.out.println("delete dup data result");
      arr.display();
      long iMax = arr.getMax(); //编程作业 2.1
      System.out.println("the max is " + iMax);
      long reMax = arr.removeMax(); //编程作业2.2
      System.out.println("remove max is " + reMax);
      arr.display();
      System.out.println("xuanze sort result");
      arr.xuanzeSort(); //编程作业2.3
      arr.display();
      } // end main()
   }

执行结果：

Array.rar