Java数组与数据结构(1)

xinxing

Java数组与数据结构
在Java编程语言中，把数组作为对象来看待，因此在创建数组时必须使用new操作符。
Int[] intArray=new int[100];
[]操作符对于编译器来说是一个标志，它说明正在命名的是一个数组对象而不是普通的变量。
由于数组是一个对象，所以它的名字是数组的一个引用；它并不是数组本身。数组存储在内存中的其它地址中，而intArray仅仅保存着这个地址。
数组有一个length字段，通过它可以得知当前数组的大小：
int arrayLength=intArray.length;
跟大多数编程语言一样，一旦创建数组，数组大小便不可改变。
数组中最基本的操作就是插入、查找、删除。
public class HighArray {
    private long[] a;
    private int nElems;
   
    /** Creates a new instance of HighArray */
    public HighArray(int max) {
        a=new long[max];
        nElems=0;
    }
//    ...........................................................
    public boolean find(long searchKey)
    {
        int j;
        for(j=0;j
            if(a[j]==searchKey)
                break;
        if(j==nElems)
            return false;
        else
            return true;
    }   //end find()
//    ...........................................................
    public void insert(long value){
        a[nElems]=value;
        nElems++;
    }
//    ...........................................................
    public boolean delete(long value)
    {
        int j;
        for(j=0;j
            if(value==a[j])
                break;
        if(j==nElems)
            return false;
        else
        {
            for(int k=j;k
                a[k]=a[k+1];
            nElems--;
            return true;
        }
    }   //end delete()
//    ...........................................................
    public void display()
    {
        for(int j=0;j
            System.out.print(a[j]+" ");
        System.out.println("");
    }   //end display()
}
假设一个数组，其中的数据项按关键字升序或降序排列，称为有序数组。将数组进行排序的好处是可以通过二分查找显著地提高查找速度。不好的方面是在插入操作中由于所有靠后的数据都需移动以腾开空间，所以速度较慢。有序数组和无序数组中的删除操作都很慢。这是因为数据项必须向前移动来填补已删除数据项的洞。
有序数组在查找频繁的情况下非常有用，但若是插入和删除较为频繁时，则无法高效工作。
public class OrdArray {
    private long[] a;
    private int nElems;
    /** Creates a new instance of OrdArray */
    public OrdArray(int max) {
        a=new long[max];
        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;
            else if(lowerBound>upperBound)
                return nElems;
            else
            {
                if(a[curIn]
                    lowerBound=curIn+1;
                else
                    upperBound=curIn-1;
            }
        }
    }
   
    public void insert(long value){
        int j;
        for(j=0;j
            if(a[j]>value)
                break;
        for(int k=nElems;k>j;k--)
            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
                a[k]=a[k+1];
            nElems--;
            return true;
        }
    }
   
    public void display()
    {
        for(int j=0;j
            System.out.print(a[j]+" ");
        System.out.println("");
    }  
   
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/1925/showart_16371.html