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

2230阅读　0评论2016-08-18　chengxiaopeng
分类：Java



点击(此处)折叠或打开

  1. // orderedArray.java
  2. // demonstrates ordered array class
  3. // to run this program: C>java OrderedApp
  4. ////////////////////////////////////////////////////////////////
  5. class OrdArray
  6.    {
  7.    private long[] a; // ref to array a
  8.    private int nElems; // number of data items
  9.    //-----------------------------------------------------------
  10.    public OrdArray(int max) // constructor
  11.       {
  12.       a = new long[max]; // create array
  13.       nElems = 0;
  14.       }
  15.    //-----------------------------------------------------------
  16.    public int size()
  17.       { return nElems; }
  18.    //-----------------------------------------------------------
  19.    public int find(long searchKey)
  20.       {
  21.       int lowerBound = 0;
  22.       int upperBound = nElems-1;
  23.       int curIn;

  25.       while(true)
  26.          {
  27.          curIn = (lowerBound + upperBound ) / 2;
  28.          if(a[curIn]==searchKey)
  29.             return curIn; // found it
  30.          else if(lowerBound > upperBound)
  31.             return nElems; // can't find it
  32.          else // divide range
  33.             {
  34.             if(a[curIn] < searchKey)
  35.                lowerBound = curIn + 1; // it's in upper half
  36.             else
  37.                upperBound = curIn - 1; // it's in lower half
  38.             } // end else divide range
  39.          } // end while
  40.       } // end find()
  41.    //-----------------------------------------------------------
  42.    public void insert(long value) // put element into array
  43.       {
  44.       int j;
  45.       for(j=0; j<nElems; j++) // find where it goes
  46.          if(a[j] > value) // (linear search)
  47.             break;
  48.       for(int k=nElems; k>j; k--) // move bigger ones up
  49.          a[k] = a[k-1];
  50.       a[j] = value; // insert it
  51.       nElems++; // increment size
  52.       } // end insert()

  54.    //采用二分查找法，进行数据插入操作 递增排序 程晓鹏 2016.08.18 add 编程作业2.4
  55.    public void insert2(long value){
  56.       int j; //要插入数据的位置
  57.       int bIdx = 0; // 二分查找开始索引号码
  58.       int eIdx = nElems - 1; //二分查找终止编码
  59.       int curIdx = 0; //中间索引编码
  60.       while(true){
  61.      curIdx = (bIdx + eIdx) / 2;
  62.          if(bIdx > eIdx){ //当不含任何元素时
  63.              j = nElems;
  64.      break;
  65.      }else if(bIdx == curIdx && nElems > 0){
  66.      if(value >= a[bIdx] && value >= a[eIdx]){
  67.         j = eIdx+1;
  68.      }else if (value >= a[bIdx]){
  69.         j = eIdx;
  70.      }
  71.      else{
  72.         j =bIdx;
  73.      }
  74.      break;
  75.      }else if (a[curIdx] < value){
  76.      bIdx = curIdx + 1;
  77.      }else{
  78.              eIdx = curIdx - 1;
  79.      }
  80.       }
  81.       System.out.println("value = " + value + ",insert idx = " + j + ", bIdx=" + bIdx + ", eIdx=" + eIdx + ", mIdx = " +curIdx);
  82.        for(int k=nElems; k>j; k--) // move bigger ones up
  83.          a[k] = a[k-1];
  84.       a[j] = value; // insert it
  85.       nElems++; // increment size
  86.      
  87.    }
  88.    //-----------------------------------------------------------
  89.    public boolean delete(long value)
  90.       {
  91.       int j = find(value);
  92.       if(j==nElems) // can't find it
  93.          return false;
  94.       else // found it
  95.          {
  96.          for(int k=j; k<nElems; k++) // move bigger ones down
  97.             a[k] = a[k+1];
  98.          nElems--; // decrement size
  99.          return true;
  100.          }
  101.       } // end delete()
  102.    //-----------------------------------------------------------
  103.    public void display() // displays array contents
  104.       {
  105.       for(int j=0; j<nElems; j++) // for each element,
  106.          System.out.print(a[j] + " "); // display it
  107.       System.out.println("");
  108.       }
  109.    //-----------------------------------------------------------
  110.    } // end class OrdArray
  111. ////////////////////////////////////////////////////////////////
  112. class OrderedApp
  113.    {
  114.    public static void main(String[] args)
  115.       {
  116.       int maxSize = 100; // array size
  117.       OrdArray arr; // reference to array
  118.       arr = new OrdArray(maxSize); // create the array

  120.       arr.insert2(77); //编程作业 2.4
  121.       arr.insert2(99);
  122.       arr.insert2(44);
  123.       arr.insert2(11);
  124.       arr.insert2(55);
  125.       arr.insert2(22);
  126.       arr.insert2(88);
  127.       arr.insert2(00);
  128.       arr.insert2(66);
  129.       arr.insert2(33);

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

  139.       arr.display(); // display items

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

  145.       arr.display(); // display items again
  146.       } // end main()
  147.    }
执行结果



点击(此处)折叠或打开

  1. // highArray.java
  2. // demonstrates array class with high-level interface
  3. // to run this program: C>java HighArrayApp
  4. ////////////////////////////////////////////////////////////////
  5. class HighArray
  6.    {
  7.    private long[] a; // ref to array a
  8.    private int nElems; // number of data items
  9.    //-----------------------------------------------------------
  10.    public HighArray(int max) // constructor
  11.       {
  12.       a = new long[max]; // create the array
  13.       nElems = 0; // no items yet
  14.       }
  15.    //-----------------------------------------------------------
  16.    public boolean find(long searchKey)
  17.       { // find specified value
  18.       int j;
  19.       for(j=0; j<nElems; j++) // for each element,
  20.          if(a[j] == searchKey) // found item?
  21.             break; // exit loop before end
  22.       if(j == nElems) // gone to end?
  23.          return false; // yes, can't find it
  24.       else
  25.          return true; // no, found it
  26.       } // end find()
  27.    //-----------------------------------------------------------
  28.    //获取最大值函数 编程作业2.1 程晓鹏 2016.08.17 add
  29.    public long getMax(){
  30.       long result = -1;
  31.       for(int i=0; i<nElems; i++){
  32.      if(a[i] > result){
  33.              result = a[i];        
  34.      }
  35.       }
  36.       return result;
  37.    }
  38.   
  39.    //删除最大值 编程作业2.2 程晓鹏 2016.08.17 add
  40.    public long removeMax(){
  41.       long result = -1;
  42.       int i=-1; // 最大值索引值
  43.       for(int ii=0; ii<nElems; ii++){
  44.      if(a[ii] > result){
  45.              result = a[ii];
  46.              i = ii;    
  47.      }
  48.       }

  50.       if(i !=nElems && i != -1){
  51.      for(int j=i; j<nElems; j++){
  52.          a[j] = a[j+1];
  53.      }    
  54.      nElems--;
  55.       }
  56.       return result;
  57.    }

  59.    //选择排序 编程作业2.3 程晓鹏 2016.08.17 add
  60.    public void xuanzeSort(){
  61.      for (int i=0; i<nElems; i++){
  62.      long max=a[i];
  63.      int index = i;
  64.      for(int j=i+1; j<nElems; j++){
  65.             if(a[j]>max){
  66.          max=a[j];
  67.          index = j;
  68.      }
  69.      }

  71.      if(index != i){
  72.      long temp=a[i];
  73.      a[i]=a[index];
  74.      a[index]=temp;
  75.      }

  77.      }
  78.    }

  80.    //删除重复项 编程作业2.6 程晓鹏 2016.08.18 add
  81.    public void noDup(){
  82.       for(int i=0; i<nElems; i++){
  83.          long tmp = a[i];
  84.      for(int j=i+1; j<nElems; j++){
  85.      if(tmp == a[j]){ //当出现重复数据时，进行
  86.          for(int k=j; k<nElems; k++){
  87.          a[k] = a[k+1];
  88.          }
  89.         
  90.          nElems--;
  91.          j--; //减一，防止两个连续的重复的出现
  92.      }
  93.      }
  94.       }
  95.    }

  97.    //-----------------------------------------------------------
  98.    public void insert(long value) // put element into array
  99.       {
  100.       a[nElems] = value; // insert it
  101.       nElems++; // increment size
  102.       }
  103.    //-----------------------------------------------------------
  104.    public boolean delete(long value)
  105.       {
  106.       int j;
  107.       for(j=0; j<nElems; j++) // look for it
  108.          if( value == a[j] )
  109.             break;
  110.       if(j==nElems) // can't find it
  111.          return false;
  112.       else // found it
  113.          {
  114.          for(int k=j; k<nElems; k++) // move higher ones down
  115.             a[k] = a[k+1];
  116.          nElems--; // decrement size
  117.          return true;
  118.          }
  119.       } // end delete()
  120.    //-----------------------------------------------------------
  121.    public void display() // displays array contents
  122.       {
  123.       for(int j=0; j<nElems; j++) // for each element,
  124.          System.out.print(a[j] + " "); // display it
  125.       System.out.println("");
  126.       }
  127.    //-----------------------------------------------------------
  128.    } // end class HighArray
  129. ////////////////////////////////////////////////////////////////
  130. class HighArrayApp
  131.    {
  132.    public static void main(String[] args)
  133.       {
  134.       int maxSize = 100; // array size
  135.       HighArray arr; // reference to array
  136.       arr = new HighArray(maxSize); // create the array

  138.       arr.insert(77); // insert 10 items
  139.       arr.insert(99);
  140.       arr.insert(44);
  141.       arr.insert(55);
  142.       arr.insert(22);
  143.       arr.insert(88);
  144.       arr.insert(11);
  145.       arr.insert(00);
  146.       arr.insert(66);
  147.       arr.insert(22);
  148.       arr.insert(33);
  149.       arr.insert(15);
  150.       arr.insert(22);
  151.       arr.insert(14);

  153.       arr.display(); // display items

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

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

  165.       arr.display(); // display items again
  166.       arr.noDup(); //编程作业2.6
  167.       System.out.println("delete dup data result");
  168.       arr.display();
  169.       long iMax = arr.getMax(); //编程作业 2.1
  170.       System.out.println("the max is " + iMax);
  171.       long reMax = arr.removeMax(); //编程作业2.2
  172.       System.out.println("remove max is " + reMax);
  173.       arr.display();
  174.       System.out.println("xuanze sort result");
  175.       arr.xuanzeSort(); //编程作业2.3
  176.       arr.display();
  177.       } // end main()
  178.    }

执行结果：

Array.rar

上一篇：Java2Xml
下一篇：shell调用oracle存储过程，插入内容含有'&'字符，插入数据异常解决方案