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!!");
  }
  
 }

}

就是這么簡單!!相信順序表也可以輕松高頂了.

原文轉自：http://www.anti-gravitydesign.com

評論列表（網友評論僅供網友表達個人看法，并不表明本站同意其觀點或證實其描述）