1

我正在为一项作业编写一个有序的链表。我们正在使用可比较的,我正在努力让布尔加法正常工作。我已经为这个代码工作了两个星期,现在我正盯着代码看。我真的很感激对我的代码有新的看法。

该代码应该适用于 Comparable 数据 - 整数和字符串(虽然没有混合)。我可以接近完成每一项工作,但没有一个代码可以代表所有人。请帮我解决这个问题,因此代码适用于字符串或整数。

我只能更改 add()、remove() 和 OrderedListNode 类

更新感谢 parkydr,我能够解决我的一些问题,但是,我仍然收到一个空点错误。我正在测试int和Strings。如果 String 循环在 while 部分中有一个“<”,则元素以相反的顺序返回。不过,对于整数来说,我将是一个错误。如果我有 >=,就像 parkydr 说的那样,那么我会以正确的顺序取回整数,但字符串会出现空指针错误。我如何让两者一起工作?

Update2整数需要按顺序排列,就像 AmitG 的代码一样。

编辑有没有人有任何想法?

package dataStructures;

/**
*   Class OrderedLinkedList.
*
*   This class functions as a linked list, but ensures items are stored in ascending     
    order.
*
*/
public class OrderedLinkedList
{

/**************************************************************************
 * Constants
 *************************************************************************/

/** return value for unsuccessful searches */
private static final OrderedListNode NOT_FOUND = null;


/**************************************************************************
 * Attributes
 *************************************************************************/

/** current number of items in list */
private int theSize;

/** reference to list header node */
private OrderedListNode head;

/** reference to list tail node */
private OrderedListNode tail;

/** current number of modifications to list */
private int modCount;


/**************************************************************************
 * Constructors
 *************************************************************************/


/**
 *  Create an instance of OrderedLinkedList.
 *
 */
public OrderedLinkedList()
{
    // empty this OrderedLinkedList
    clear();

}


/**************************************************************************
 * Methods
 *************************************************************************/


/*
 *  Add the specified item to this OrderedLinkedList.
 *
 *  @param  obj     the item to be added
 */
public boolean add(Comparable obj){
   OrderedListNode node = new OrderedListNode(obj);
   OrderedListNode head2 = new OrderedListNode(obj);
   OrderedListNode tail2 = new OrderedListNode(obj);
       if (head2 == null)
       {
           head2 = node;
           tail2 = node;
           return true;
       }


       // When the element to be added is less than the first element in the list
       if (obj.compareTo(head2.theItem) < 0)
       {
           node.next = head2;
           head2 = node;
           return true;
       }

       // When the element to be added is greater than every element in in list
       // and has to be added at end of the list
       if (obj.compareTo(tail2.theItem) > 0)
       {
           tail2.next = node;
           tail2 = node;
           return true;
       }

       //When the element to be added lies between other elements in the list
       if (obj.compareTo(head2.theItem) >= 0 && obj.compareTo(tail2.theItem) <= 0)
       {
          OrderedListNode current = head.next;
          OrderedListNode previous = head;
          while (obj.compareTo(current.theItem) >= 0)
          {
              previous = current;
              current = current.next;
          }
          previous.next = node;
          node.next = current;

       }

       return true;
   }  

/*
 *  Remove the first occurrence of the specified item from this   
            OrderedLinkedList.
 *
 *  @param  obj     the item to be removed
 */
public boolean remove(Comparable obj)
{
   OrderedListNode curr = head;
       OrderedListNode prev = head;

       while(curr != null && ! (curr.theItem.compareTo(obj) == 0)){
       prev = curr;
       curr = curr.next;
       }
       if(curr == null)
      return false;
       else{
          prev.next = curr.next;
          curr = null;
          return true;
     }  
  }



/**
 *  Empty this OrderedLinkedList.
 */
public void clear()
{
    // reset header node
    head = new OrderedListNode("HEAD", null, null);

        // reset tail node
        tail = new OrderedListNode("TAIL", head, null);

        // header references tail in an empty LinkedList
        head.next = tail;

        // reset size to 0
    theSize = 0;

    // emptying list counts as a modification
    modCount++;
}


/**
 *  Return true if this OrderedLinkedList contains 0 items.
 */
public boolean isEmpty()
{
    return theSize == 0;
}


/**
 *  Return the number of items in this OrderedLinkedList.
 */
public int size()
{
    return theSize;
}


/*  
 *  Return a String representation of this OrderedLinkedList.
 *
 *  (non-Javadoc)
 *  @see java.lang.Object#toString()
 */
@Override
public String toString()
{
    String s = "";

    OrderedListNode currentNode = head.next;

    while (currentNode != tail)
    {
        s += currentNode.theItem.toString();

        if (currentNode.next != tail)
        {
            s += ", ";
        }

        currentNode = currentNode.next;
    }

    return s;
}


/**************************************************************************
 * Inner Classes
 *************************************************************************/


/**
 *  Nested class OrderedListNode.
 *
 *  Encapsulates the fundamental building block of an OrderedLinkedList
 *  contains a data item, and references to both the next and previous nodes
 *  in the list
 */


// TODO: Implement the nested class OrderedListNode (5 points).  This nested class
// should be similar to the nested class ListNode of the class LinkedList, but
// should store a data item of type Comparable rather than Object.
    public static class OrderedListNode {


    Comparable theItem;   
        OrderedListNode next;
        OrderedListNode prev;


        OrderedListNode( Comparable theItem ) { this( theItem, null, null ); }

        OrderedListNode( Comparable theItem, OrderedListNode prev, OrderedListNode next)
        {
           this.theItem = theItem;         
           this.next = next;        
           this.prev = prev;
        }

        Comparable getData() { return theItem; }

        OrderedListNode getNext() { return next; }

        OrderedListNode getPrev() { return prev; }

        }
  // Remove - for testing only
   public static void main (String[] args)
   {
     OrderedLinkedList list = new OrderedLinkedList();
     list.add("1");
     list.add("4");
     list.add("3");
     list.add("33");
     list.add("4");
     System.out.println(list.toString());

   }

 }

上面的代码在大多数情况下都适用于整数,除了项目按词法存储为字符串。所以我需要帮助解决这个问题。我还需要使此代码也可以与字符串一起使用。现在下面的代码适用于字符串但不适用于整数,它也以相反的顺序存储,因为 <= 在 while 语句中发生了变化。帮助!

请注意,符号的更改将使字符串起作用(尽管顺序相反):

  while (obj.compareTo(current.theItem) <= 0)
4

3 回答 3

1

这是我最新版本的添加。它没有设置 prev 链接(我将把它作为“读者练习”)。

   public boolean add(Comparable obj){
       OrderedListNode node = new OrderedListNode(obj);

       // When the list is empty
       if (head.next == tail)
       {
           head.next = node;
           node.next = tail;
           tail.prev = node;
           return true;
       }


       // When the element to be added is less than the first element in the list
       if (obj.compareTo(head.next.theItem) < 0)
       {
           node.next = head.next;
           head.next = node;
           return true;
       }

       //When there is an element in the list

       OrderedListNode current = head.next;
       OrderedListNode previous = head;
       while (current != tail && node.theItem.compareTo(current.theItem) >= 0)
       {
          previous = current;
          current = current.next;
       }

       previous.next = node;
       node.next = current;

       return true;
   }
于 2013-04-04T10:42:21.267 回答
0

修改后的程序,输出将是1,3,33,4,4
如果您想要输出,然后从以下程序1,3,4,4,33 中删除line 1并粘贴以下代码。和方法被修改。line 2AddtoString

int currentValue = Integer.parseInt(freshNode.theItem.toString());  
int tempValue = Integer.parseInt(nodeToTraverse.theItem.toString());
if(currentValue>tempValue)  


完整代码

/**
 * Class OrderedLinkedList.
 * 
 * This class functions as a linked list, but ensures items are stored in
 * ascending order.
 * 
 */
public class OrderedLinkedList {

    /**************************************************************************
     * Constants
     *************************************************************************/

    /** return value for unsuccessful searches */
    private static final OrderedListNode NOT_FOUND = null;

    /**************************************************************************
     * Attributes
     *************************************************************************/

    /** current number of items in list */
    private int theSize;

    /** reference to list header node */
    private OrderedListNode head;

    /** reference to list tail node */
    private OrderedListNode tail;

    /** current number of modifications to list */
    private int modCount;

    /**************************************************************************
     * Constructors
     *************************************************************************/

    /**
     * Create an instance of OrderedLinkedList.
     * 
     */
    public OrderedLinkedList() {
        // empty this OrderedLinkedList
//       clear();  //work around with this method. Removed temporarily.

    }

    /**************************************************************************
     * Methods
     *************************************************************************/

    /*
     * Add the specified item to this OrderedLinkedList.
     * 
     * @param obj the item to be added
     */
    public void add(Comparable obj) {
        OrderedListNode freshNode = new OrderedListNode(obj);
        if (head == null) {
            head = freshNode;
            tail = freshNode;
            return;
        }
        OrderedListNode nodeToTraverse = head;
        while(nodeToTraverse!=null)
        {
            int result = freshNode.theItem.compareTo(nodeToTraverse.theItem);  // line 1
            if(result>0)   // line 2
            {
                if(nodeToTraverse.next==null)
                {
                    nodeToTraverse.next=freshNode;
                    freshNode.prev =nodeToTraverse;
                    break;
                }
                else
                {
                    nodeToTraverse=nodeToTraverse.next;
                    continue;
                }
            }
            else
            {
                nodeToTraverse.prev.next = freshNode;
                freshNode.prev = nodeToTraverse.prev;
                freshNode.next= nodeToTraverse;
                nodeToTraverse.prev=freshNode;
                break;
            }
        }
    }

    /*
     * Remove the first occurrence of the specified item from this
     * OrderedLinkedList.
     * 
     * @param obj the item to be removed
     */
    public boolean remove(Comparable obj) {
        OrderedListNode curr = head;
        OrderedListNode prev = head;

        while (curr != null && !(curr.theItem.compareTo(obj) == 0)) {
            prev = curr;
            curr = curr.next;
        }
        if (curr == null)
            return false;
        else {
            prev.next = curr.next;
            curr = null;
            return true;
        }
    }

    /**
     * Empty this OrderedLinkedList.
     */
    public void clear() {
        // reset header node
        head = new OrderedListNode("HEAD", null, null);

        // reset tail node
        tail = new OrderedListNode("TAIL", head, null);

        // header references tail in an empty LinkedList
        head.next = tail;

        // reset size to 0
        theSize = 0;

        // emptying list counts as a modification
        modCount++;
    }

    /**
     * Return true if this OrderedLinkedList contains 0 items.
     */
    public boolean isEmpty() {
        return theSize == 0;
    }

    /**
     * Return the number of items in this OrderedLinkedList.
     */
    public int size() {
        return theSize;
    }

    /*
     * Return a String representation of this OrderedLinkedList.
     * 
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        String s = "";

        OrderedListNode temp = head;
        while (temp != null) {
            s = s + temp.theItem.toString()+",";
            temp = temp.next;
        }

        return s.substring(0,s.lastIndexOf(",")); //this will remove last comma
//      return s; //1,2,3,4,5,25,33, this will not remove last comma(,)
    }

    /**************************************************************************
     * Inner Classes
     *************************************************************************/

    /**
     * Nested class OrderedListNode.
     * 
     * Encapsulates the fundamental building block of an OrderedLinkedList
     * contains a data item, and references to both the next and previous nodes
     * in the list
     */

    // TODO: Implement the nested class OrderedListNode (5 points). This nested
    // class
    // should be similar to the nested class ListNode of the class LinkedList,
    // but
    // should store a data item of type Comparable rather than Object.

    // Remove - for testing only
    public static void main(String[] args) {
        OrderedLinkedList list = new OrderedLinkedList();
        /*list.add("1");
        list.add("4");
        list.add("3");
        list.add("33");
        list.add("5");
        list.add("2");
        list.add("25");*/
        list.add("1");
         list.add("4");
         list.add("3");
         list.add("33");
         list.add("4");

        System.out.println(list.toString());
    }

    private static class OrderedListNode {
        Comparable data;
        Comparable theItem;
        OrderedListNode next;
        OrderedListNode prev;

        OrderedListNode(Comparable data) {
            this(data, null, null);
        }

        OrderedListNode(Comparable data, OrderedListNode prev, OrderedListNode next) {
            this.theItem = data;
            this.next = next;
            this.prev = prev;
        }

        Comparable getData() {
            return data;
        }

        OrderedListNode getNext() {
            return next;
        }

        OrderedListNode getPrev() {
            return prev;
        }
        @Override
        public String toString() {
            return (String)theItem;
        }

    }
}
于 2013-04-04T14:59:27.323 回答
0
import java.util.*;

public class List {

    private Node head;
    private int manyNodes;

    public List() {
        head = null;
        manyNodes = 0;
    }

    public boolean isEmpty() {
        return ((head == null) && (manyNodes == 0));
    }

    public void add(int element) {
        if (head == null) {
            head = new Node(element, null);
            manyNodes++;
        } else {
            head.addNodeAfter(element);
            manyNodes++;
        }
    }

    public boolean remove(int target) {
        boolean removed = false;

        Node cursor = head;
        Node precursor;

        if (head == null) {
            throw new NoSuchElementException("Cannot remove from empty list");
        }

        if (head.getInfo() == target) {
            head = head.getNodeAfter();
            manyNodes--;
            removed = true;
        } else {
            precursor = cursor;
            cursor = cursor.getNodeAfter();

            while ((cursor != null) && (!removed)) {
                if (cursor.getInfo() == target) {
                    precursor.removeNodeAfter();
                    manyNodes--;
                    removed = true;
                } else {
                    precursor = cursor;
                    cursor = cursor.getNodeAfter();
                }
            }
        }

        return removed;
    }

    public Node getFront() {
        return head;
    }

    public int size() {
        return manyNodes;
    }

    public Node listSort(Node source) {
        source = head;

        int largest = Integer.MIN_VALUE;
        int smallest;

        Node front;

        while (source != null) {
            if (source.getInfo() > largest) {
                largest = source.getInfo();
            }

            source = source.getNodeAfter();
        }

        front = new Node(Node.find(head, largest).getInfo(), null);
        remove(largest);

        while (!isEmpty()) {
            source = head;
            smallest = Integer.MAX_VALUE;

            while (source != null) {
                if (source.getInfo() <= smallest) {
                    smallest = source.getInfo();
                }

                source = source.getNodeAfter();
            }

            remove(smallest);
            front.addNodeAfter(smallest);
        }

        head = front.reverse(front);
        source = head;
        return source;
    }

    public void showList() {
        Node cursor = head;

        if (cursor == null) {
            System.out.println("This list contains no items.");
        } else {
            while (cursor != null) {
                System.out.print(cursor.getInfo() + " ");
                cursor = cursor.getNodeAfter();
            }
        }
    }

}//end class List
于 2013-06-28T00:15:10.253 回答