list.java

八数码问题,可以实现将九个空格里的八个数进行排列

  class ListNode{
    public Eight data;
    public ListNode next;
    public ListNode()
    {
    	next=null;
    }
    public ListNode(Eight o)
    {
        data=o;
        next=null;
    }
    public ListNode(Eight o,ListNode nextNode)
    {
        data=o;
        next=nextNode;
    }
    
    // Return the Eight in this node
    public Eight getEight()
    {
        return data;
    }
    
    public ListNode getnext()
    {
        return next;
    }
}    
 public class List{
    public ListNode firstNode;
    public ListNode lastNode;
    public int length;
    private String name;         //    String like "list" used in printing
        
    public List(String s)
    {
        name=s;
        firstNode=lastNode=null;
        length=0;
    }
        
    //Constructor: Constructor an empty List with "List" as the name
    public List(){
        this("list");
    }
    public  Eight getFirstNode(){
    	return firstNode.data;
    
    }

    
    //Insert an Eight at the front of the List If List is empty, firstNode
    //and lastNode refer to same Eight. Otherwise,firstNode refers to new node.
    public void insertAtFront(Eight insertItem)
    {
        if(isEmpty())//如果链表为空,返回true,否则返回false.
            firstNode=lastNode=new ListNode(insertItem);
        else
            firstNode=new ListNode(insertItem,firstNode);
        length++;
    }
    
    
    //Insert an Eight at the end of the List If List is empty, firstNode and
    //lastNode refer to same Eight. Otherwise, lastNode's next instance variable refers to new node.
    public void insertAtBack(Eight insertItem)
    {
        if(isEmpty())
            firstNode=lastNode=new ListNode(insertItem);
        else
            lastNode=lastNode.next=new ListNode(insertItem);
        length++;
    }
    
    // Remove the first node from the List.
    public Eight removeFromFront() throws EmptyListException
    {
        Eight removeItem=null;
        if(isEmpty())
            throw new EmptyListException(name);
        
        removeItem=firstNode.data;   //retrieve the data reset the firstNode and lastNode references
        
        if(firstNode.equals(lastNode))
            firstNode=lastNode=null;
        else
            firstNode=firstNode.next;
        length--;
        return removeItem;
    }
    
    //Remove the last node from the List
    public Eight removeFromBack() throws EmptyListException
    {
        Eight removeItem=null;
        
        if(isEmpty())
            throw new EmptyListException(name);
        
        removeItem=lastNode.data; //retrieve the data reset the firstNode and lastNode references
        if(firstNode.equals(lastNode))
            firstNode=lastNode=null;
        else
        {
            ListNode current=firstNode;
        
            while(current.next !=lastNode){
                current=current.next;
            }
        
            lastNode=current;
            current.next=null;
        }
        length--;
        return removeItem;
    }
    
    //Return true if the List is empty.
    public boolean isEmpty(){
        return firstNode==null;
    }
    
    //Output the List contents
    public void print()
    {
    	if(isEmpty()){
            System.out.println("Empty ");
            return;
        }
    	ListNode current=firstNode;
    	do
    	{
            current.data.print();
            System.out.println("fֵΪ:"+current.data.f());
            System.out.println("=====");
            current=current.next;
        }while(current !=null);
        
    }




 }  
   // Class EmptyListException definition
class EmptyListException extends RuntimeException{
    public EmptyListException(String name)
    {
        super("The " + name + " is empty");
    }
}