H5W3
当前位置:H5W3 > 其他技术问题 > 正文

Java数据结构—基于数组的表

    我没看过 其他语言版的数据结构,但觉得java的实现方法很巧妙–用类和对象来实现.基于数组的表,思想很简单就是定义一个类用来存储一组数据,我定义的是ArrayListClass类,在类中定义用来操作数组的方法.其实就是 这么简单,但具体操作起来就会遇到很多麻烦了!     我们这个ArrayListClass类中首先应该包括一个数组型的域list,用来存放数据,这样放在同一数组中数据之间就产生了位置上的联系,使对数据的操作便的简单.然而这个数组到底是什么数据类型的,我们期望这个表能用于所有的数据类型,我们不能将他单纯的固定成某一种.所以我们必须将这个数据普通化,解决的办法就是定义一个类,作为所有数据类型的超类.看这个DataElement:  public abstract class DataElement {  public abstract boolean equals(DataElement otherElement);  public abstract int compareTo(DataElement otherElement);  public abstract void makeCopy(DataElement otherElement);  public abstract DataElement getCopy(); } 将他定义成为抽象的,再在定义其他数据类型时继承并实现它,我定义了两个数据类型IntElement和StringElement: IntElement: public  class IntElement extends DataElement {  protected int num;    //constructors  public IntElement(){   num=0;  }  public IntElement(int number){   num=number;  }  public IntElement(IntElement otherElement){   num=otherElement.num;  }    ///get-set Methods  public void setNum(int number){   num=number;  }  public int getNum(){   return num;  }    /* (non-Javadoc)   * @see DataElement#equals(DataElement)   */  public boolean equals(DataElement otherElement) {   // TODO Auto-generated method stub   IntElement newe=(IntElement)otherElement;   return (this.num==newe.num);  }  /* (non-Javadoc)   * @see DataElement#compareTo(DataElement)   */  public int compareTo(DataElement otherElement) {   // TODO Auto-generated method stub   IntElement newe=(IntElement)otherElement;   if(this.num==newe.num)   return 0;   else if(this.num>newe.num)     return 1;   else     return -1;  }  /* (non-Javadoc)   * @see DataElement#makeCopy(DataElement)   */  public void makeCopy(DataElement otherElement) {   // TODO Auto-generated method stub   IntElement newe=(IntElement)otherElement;   this.num=newe.num;     }  /* (non-Javadoc)   * @see DataElement#getCopy()   */  public DataElement getCopy() {   // TODO Auto-generated method stub   IntElement newElement=new IntElement();   newElement.num=this.num;   return newElement;  }  public String toString(){   return String.valueOf(num);  } } StringElement: public class StringElement extends DataElement {  /**   *    */  private String str;    //constructors  public StringElement() {   str=null;     }  public StringElement(String string){   str=string;  }  public StringElement(StringElement otherElement){   str=otherElement.str;  }    //get-set Methods  public void setStr(String string){   str=string;  }  public String getStr(){   return str;  }  /* (non-Javadoc)   * @see DataElement#equals(DataElement)   */  public boolean equals(DataElement otherElement) {   // TODO Auto-generated method stub   StringElement newe=(StringElement)otherElement;   return (str==newe.str);  }  /* (non-Javadoc)   * @see DataElement#compareTo(DataElement)   */  public int compareTo(DataElement otherElement) {   // TODO Auto-generated method stub   StringElement newe=(StringElement)otherElement;  

return (str.compareTo(newe.str));  }  /* (non-Javadoc)   * @see DataElement#makeCopy(DataElement)   */  public void makeCopy(DataElement otherElement) {   // TODO Auto-generated method stub   StringElement newe=(StringElement)otherElement;   str=newe.str;  }  /* (non-Javadoc)   * @see DataElement#getCopy()   */  public DataElement getCopy() {   // TODO Auto-generated method stub      StringElement othere=new StringElement();   othere.str=str;   return othere;     }  public String toString(){   return str;  } } 已经定义好了数据类型,所以list的数据类型我们就可以定义为DateElement[]了,这样就可以包括所以你想要的了,只要你在用的时候定义一个DataElement的子类就行了,这正是java继承的精髓所在.我们接着定义ArrayListClass类:  protected int length;  protected int maxSize;  protected DataElement[] list;这就是它的所有域了. 接下来就是它的方法了,我们对表的操作应该有很多种,比如插入、查询、删减等等,我们要逐个的实现,具体方法不再赘述,且看最后完成代码 public abstract class  ArrayListClass {  //fields  protected int length;  protected int maxSize;  protected DataElement[] list;    //defalt constructors  public ArrayListClass(){   length=0;   maxSize=100;   list=new DataElement[maxSize];  }  //constructors  public ArrayListClass(int size){   if(size<=0){    System.err.println("The arry size must be positive.Creating an array of size 100.");    maxSize=100;   }   else     maxSize=size;   length=0;   list=new DataElement[maxSize];  }  public ArrayListClass(ArrayListClass otherList){   maxSize=otherList.maxSize;   length=otherList.length;   list=new DataElement[maxSize];   for(int i=0;i<length;i++){    list[i]=otherList.list[i].getCopy();   }  }    //methods  public boolean isEmpty(){   return (length==0);  }  public boolean isFull(){   return (length==maxSize);  }  public int listSize(){   return length;  }  public int maxListSize(){   return maxSize;  }  public void print(){   for(int i=0;i<length;i++){    System.out.print(list[i]+" ");   }   System.out.println();  }  public boolean isItemAtEqual(int location,DataElement item){   return(list[location].equals(item));  }  public void insrtAt(int location,DataElement insertItem){   if(location<0||location>+maxSize){    System.out.println("The position of the item to be inserted is out of range!!");   }   else     if(length>=maxSize)     System.err.println("Can’t insert in a full list!!");    else{     for(int i=length;i>location;i–){      list[i]=list[i-1];     }      list[location]=insertItem.getCopy();      length++;    }  }  public void insertEnd(DataElement insertItem){   if(length>=maxSize){    System.err.println("Can’t insert in a full list!!");   }      else{    list[length]=insertItem.getCopy();   length++;   }  }  public void removeAt(int location){   if(location<0||location>=length){    System.err.println("The location you want to remove is out of range!!");   }   else{    for(int i=location;i<length-1;i++){     list[i]=list[i+1];    }    list[length]=null;    length–;   }  }     public DataElement retrieveAt(int location){      if(location<0||location>=length){       System.err.println("The location of item to be retrieved is out of range!!");          return null;      }      else{       return list[location].getCopy();      }     }     public void replacAt(int location,DataElement repItem){      if(location<0||location>=length)       System.out.println("The position of item to be replaced is out of range!!");      else       list[location]=repItem.getCopy();     }     public void clearList(){      for(int i=0;i<length;i++){       list[i]=null;      }      length=0;      System.gc();     }

public void copyList(ArrayListClass otherList){      if(this!=otherList){       for(int i=0;i<length;i++)        list[i]=null;       System.gc();       maxSize=otherList.maxSize;       length=otherList.length;       list=new DataElement[maxSize];              for(int j=0;j<length;j++)        list[j]=otherList.list[j].getCopy();      }     }     public abstract int seqSearch(DataElement seqItem);     public abstract void insert(DataElement insertItem);     public abstract void remove(DataElement removeItem);        }  看到代码的最后你回发现这个类其实是一个抽象类,为什么要这样定义呢?之所以这样我们是为了针对不同是类型:顺序表和非顺序表.不难想象他们的一些方法是存在差异的,先看一下非顺序表: public class UnorderedArrayList extends ArrayListClass{  /**   *    */  public UnorderedArrayList() {   super();   // TODO Auto-generated constructor stub  }  /* (non-Javadoc)   * @see ArrayListClass#seqSearch(DataElement)   */  public int seqSearch(DataElement seqItem) {   // TODO Auto-generated method stub   int loc;   boolean found=false;      for(loc=0;loc<length;loc++)    if(list[loc].equals(seqItem))    {     found=true;     break;    }    if(found)     return loc;    else     return -1;  }  /* (non-Javadoc)   * @see ArrayListClass#insert(DataElement)   */  public void insert(DataElement insertItem) {   // TODO Auto-generated method stub   int loc;   if(length==0)    list[length++]=insertItem.getCopy();   else    if(length==maxSize)     System.err.println("Can’t insert in a  full list!!");    else{     loc=seqSearch(insertItem);          if(loc==-1)      list[length++]=insertItem.getCopy();     else      System.err.println("The item to be inserted is allready in the list!!");         }  }  /* (non-Javadoc)   * @see ArrayListClass#remove(DataElement)   */  public void remove(DataElement removeItem) {   // TODO Auto-generated method stub   int loc;      if(length==0)    System.err.println("Can’t delete from a empty list!!");   else{    loc=seqSearch(removeItem);    if(loc!=-1)     removeAt(loc);    else     System.err.println("The item to be deleted is not in the list!!");   }     } } 就是这么简单!!相信顺序表也可以轻松高顶了.

本文地址:H5W3 » Java数据结构—基于数组的表

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址