重新温习数据结构一:数组

我对java基础和数据结构,算法学得好的人很佩服,毕竟无论什么时候,基础的学习才是最重要的.以前学过数据结构,现在重新温习一下.
数组分为有序数组与无序的数组,在一个无序数组中可以很快进行插入,花费O(1)时间,但查找与删除都速度比较慢O(n)时间;有序数组,查找很快O(1)时间花费,但插入却花费O(n)时间.
(本文的例子是摘<<Data Structures & Algorithms in Java>>这一本书的)

下面看一个无序数组的例子
package org.h2;

/**
 * 这一个类是为说明数组在数据结构中的运用
 *
 * @author light
 *
 */
class HighArray {
 private long[] a; // 定义一个数组a

 private int nElems; // 定义数组里面有多少项

 // -----------------------------------------------------------

 public HighArray(int max) // 构造方法
 {
  a = new long[max]; // 创建一个数组
  nElems = 0; // 刚开始数组元素为空
 }

 // -----------------------------------------------------------
 public boolean find(long searchKey) { // 寻找指定的值
  int j;
  for (j = 0; j < nElems; j++)
   if (a[j] == searchKey) // 找到元素?
    break;            // 退出循环
  if (j == nElems)
   return false;         // 没有在数组中找到元素
  else
   return true;          // 在数组中找到元素
 }

 // -----------------------------------------------------------

 public void insert(long value) // 增加一个元素到数组中去
 {
  a[nElems] = value;
  nElems++;
 }

 // -----------------------------------------------------------
 public boolean delete(long value) {// 删除一个元素,先查找,找到则删除
  int j;
  for (j = 0; j < nElems; j++)
   if (value == a[j])
    break;
  if (j == nElems)
   return false;
  else {
   for (int k = j; k < nElems; k++)
    a[k] = a[k + 1];
   nElems--;
   return true;
  }
 }

 // -----------------------------------------------------------

 public void display() // 打印出数组的内容
 {
  for (int j = 0; j < nElems; j++)
   System.out.print(a[j] + " ");
  System.out.println("");
 }
}
注:find方法中的如下语句:  if (j == nElems)
   return false;         // 没有在数组中找到元素
  else
   return true;          // 在数组中找到元素
可以用这一条语句来替代return (j!=nElems);

再写一个类:
package org.h2;

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

   arr.display();                // display items

   int searchKey = 35;           // search for item
   if( arr.find(searchKey) )
      System.out.println("找到 " + searchKey);
   else
      System.out.println("不能找到" + searchKey);

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

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

运行结果如下:
77 99 44 55 22 88 11 0 66 37
不能找到35
77 44 22 88 11 66 37

下面看一个有序数组的例子,比较上面的,看一下两者的不同之处
package org.h2;

class OrderArray {
 private long[] a; // ref to array a

 private int nElems; // number of data items

 public OrderArray(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
   }
  } 
 }

 public void insert(long value) // put element into array
 {
  int j;
  for (j = 0; j < nElems; j++)
   if (a[j] > value)      // (linear search)
    break;
  for (int k = nElems; k > j; k--)
   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++)
    a[k] = a[k + 1];
   nElems--;  // decrement size
   return true;
  }
 }

 public void display() // displays array contents
 {
  for (int j = 0; j < nElems; j++)
   System.out.print(a[j] + " ");
  System.out.println("");
 }
}
再写一个实现类,测试一下
package org.h2;

class OrderArrayApp
{
public static void main(String[] args)
   {
   int maxSize = 100;             // array size
   OrderArray arr;                  // reference to array
   arr = new OrderArray(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(33);

   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()
}  // end class OrderedApp

测试结果如下:
Found 55
0 11 22 33 44 55 66 77 88 99
11 22 33 44 66 77 88