0

我在这个网站上查询了搜索引擎，但我没有看到任何与我正在寻找的东西相匹配的东西，所以我希望这个问题还没有在其他地方得到回答。我正在尝试完善我对有序 LinkedList 的添加方法。程序的其余部分运行良好，虽然列表按照测试工具中的指定打印出来，但我希望对名称进行排序。

在多次调用从线束中添加和删除之后，我的输出是这样的：

Sue, Bill, Michael, Someguy, Michael, Carl, Steve, Carl, Sue
Sue, Bill, Someguy, Michael, Steve, Carl, Sue
Sue, Bill, Someguy, Michael, Steve, Carl, Sue, Sue, Bill

我想要的是：Sue、Sue、Bill、Michael、Michael、Carl、Carl、Steve 等……

我的添加方法：

 public boolean add(Comparable obj)
{
    OrderedListNode newNode = new OrderedListNode(obj, null, null);
    if( tail == null) {
    tail = newNode;
    head = tail;
    modCount++;
    return true;

    }
    if(((Comparable)(head.theItem)).equals(obj)){
        tail.previous = newNode;
        modCount++;
        return true;
    }else{


    tail.previous.next = newNode;
    newNode.previous = tail.previous;
    newNode.next = tail;
    tail.previous = newNode;
    modCount++;
    return true;
    }
}

整个代码，因为它被要求：

package dataStructures;


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 newNode = new OrderedListNode(obj, null, null);
    if( tail == null) {
    tail = newNode;
    head = tail;
    modCount++;
    return true;

    }
    if(((Comparable)(head.theItem)).compareTo(obj) > 0){
        ////////////////////////////////////////
        //here is where my problem lies, I believe
        /////////////////////////////////////////
        modCount++;
        return true;
    }else{


    tail.previous.next = newNode;
    newNode.previous = tail.previous;
    newNode.next = tail;
    tail.previous = newNode;
    modCount++;
    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)
{
    if(head == null) return false;
    if(((Comparable)(head.theItem)).compareTo(obj) == 0) {
    if(head == tail) {
        head = tail = null;
        return true;
    }
    head = head.next;
    return true;
    }

    if(head == tail)return false;
    OrderedListNode ref = head;
    while( ref.next != tail) {
        if(((Comparable)(ref.next.theItem)).compareTo(obj) == 0) {
            ref.next = ref.next.next;
            return true;
        }
        ref = ref.next;
    }
    if(((Comparable)(tail.theItem)).compareTo(obj) == 0 ) {
        tail = ref;
        tail.next = null;
        return true;
    }

    return false;

}


/**
 *  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;
}

private static class OrderedListNode<Comparable> {

    Comparable theItem;
    OrderedListNode<Comparable> next;
    OrderedListNode<Comparable> previous;

    public OrderedListNode(Comparable theItem, OrderedListNode<Comparable> previous, OrderedListNode<Comparable> next) {
        this.theItem = theItem;
        this.next = next;
        this.previous = previous;
    }

}

}

4

1 回答 1

0

这条线肯定是错的

if(((Comparable)(head.theItem)).equals(obj)) {

你应该使用 Comparable.compareTo，除了你应该总是从头开始，直到你找到一个大于或等于 obj 的元素并在它之前插入 obj，像这样

public boolean add(Comparable obj) {
    modCount++;
    if (head == null) {
        head = new OrderedListNode(obj, null, null);
        return true;
    }
    for (OrderedListNode current = head; current != null; current = current.next) {
        if (((Comparable) (current.theItem)).compareTo(obj) >= 0) {
            current.prev = new OrderedListNode(obj, current.prev, current);
            return true;
        }
    }
    tail.next = new OrderedListNode(obj, tail, null);
    return true;
}
于 2013-04-05T03:28:02.323 回答