sortedarray.java

《Java2程序设计实用教程(第2版)》课件

//【例4.5】  设计一个已排序的对象数组类，实现查找算法。

public class SortedArray<T>                  //泛型类  
{
    private Comparable table[];              //存放实现Comparable接口的对象
    private int count;
    
    public SortedArray(int n)
    {
        if (n<=0)  n=10;
        this.table = new Comparable[n];
        this.count=0;
    }
    
    public void print()                      //输出数组元素
    {
        System.out.print("table: ");
        for (int i=0;i<this.count;i++)
            System.out.print("  "+table[i].toString());
        System.out.println();
    }

    public int search(T tobj)                //顺序查找
    {                                        //查找成功时返回元素的序号，查找失败时时返回-1
        int i=0;
        while (i<this.count && !this.table[i].equals(tobj)) //比较两个对象是否相等
            i++;

        if (i<this.count)                    //查找成功
            return i+1;                      //下标转换成序号
        else        
            return -1;                       //查找失败
    }  

    public boolean insert(T tobj)            //将元素按升序插入数组，直接插入排序算法的一趟
    {
        if (this.count<this.table.length && tobj instanceof Comparable)
        {                                    //数组未满且tobj是实现Comparable接口对象时
            int i=0;
            Comparable cmpobj = (Comparable) tobj;
            while (i<this.count && cmpobj.compareTo(this.table[i])>=0)//比较两个对象的大小
            {
                i++;
            }
                 
            for(int j=this.count-1;j>=i;j--) //若干数组元素向后移动
            {
                table[j+1]=table[j];
            }   
            this.table[i] = cmpobj;          //插入
            this.count++;
            return true;                     //插入成功
        }
        else
            return false;                    //插入未成功
    }
}

class SortedArray_ex
{
    public static void main(String args[]) 
    {
        SortedArray<Integer> sa1 = new SortedArray<Integer>(10);
        Integer intobj = new Integer(2);
        sa1.insert(intobj);

        intobj = new Integer(3);
        sa1.insert(intobj);

        intobj = new Integer(1);
        sa1.insert(intobj);

        sa1.print();


        SortedArray<String> sa2 = new SortedArray<String>(10);
        String strobj = new String("xyz");
        sa2.insert(strobj);
        
        strobj = new String("aaa");
        sa2.insert(strobj);
       
        strobj = new String("abc");
        sa2.insert(strobj);

        sa2.print();

        System.out.println("search "+strobj.toString()+" : "+sa2.search(strobj));


    }
}

/* 



程序运行结果如下：
table:  1 2 3
table:  aaa  abc  xyz
search abc : 2

*/