Java 中的双链表问题

Question

我正在制作一个双链表，它将 "boxes" 存储在一个有 5 个货架的仓库中。每个架子都不能包含一个链表，该链表包含该架子上的 "boxes"。我遇到一个问题，当我尝试移动其中一个盒子时，我会将盒子添加到不同的架子上，但是当我尝试从旧架子上移除盒子时，我的程序只会移除我刚刚添加到新架子上的盒子架子。下面是我的 shelf class 代码，它设置列表和我的仓库代码，其中存在我遇到问题的 moveOneBox 方法。

    package assignment2;

public class Warehouse{

protected Shelf[] storage;
protected int nbShelves;
public Box toShip;
public UrgentBox toShipUrgently;
static String problem = "problem encountered while performing the operation";
static String noProblem = "operation was successfully carried out";

public Warehouse(int n, int[] heights, int[] lengths){
    this.nbShelves = n;
    this.storage = new Shelf[n];
    for (int i = 0; i < n; i++){
        this.storage[i]= new Shelf(heights[i], lengths[i]);
    }
    this.toShip = null;
    this.toShipUrgently = null;
}

public String printShipping(){
    Box b = toShip;
    String result = "not urgent : ";
    while(b != null){
        result += b.id + ", ";
        b = b.next;
    }
    result += "\n" + "should be already gone : ";
    b = toShipUrgently;
    while(b != null){
        result += b.id + ", ";
        b = b.next;
    }
    result += "\n";
    return result;
}

public String print(){
    String result = "";
    for (int i = 0; i < nbShelves; i++){
        result += i + "-th shelf " + storage[i].print();
    }
    System.out.println(result);
    return result;
}

public void clear(){
    toShip = null;
    toShipUrgently = null;
    for (int i = 0; i < nbShelves ; i++){
        storage[i].clear();
    }
}

/**
 * initiate the merge sort algorithm
 */
public void sort(){
    mergeSort(0, nbShelves -1);
}

/**
 * performs the induction step of the merge sort algorithm
 * @param start
 * @param end
 */
protected void mergeSort(int start, int end) {
    int middle;

    if (start < end) {
        middle = (start + end) / 2;

        mergeSort(start, middle);
        mergeSort(middle + 1, end);

        merge(start, middle, end);
    }
}

/**
 * performs the merge part of the merge sort algorithm
 * @param start
 * @param mid
 * @param end
 */
protected void merge(int start, int mid, int end){
    int sizeOfLeft = mid - start + 1;
    int sizeOfRight = end - mid;

    Shelf left_Array[] = new Shelf[sizeOfLeft];
    Shelf right_Array[] = new Shelf[sizeOfRight];

    for(int i = 0; i < sizeOfLeft; i++) {
        left_Array[i] = storage[start + i];
    }

    for(int j = 0; j < sizeOfRight; j++) {
        right_Array[j] = storage[mid+1+j];
    }

    int i = 0;
    int j = 0;
    int k = start;

    while(i < sizeOfLeft && j < sizeOfRight) {
        if(left_Array[i].height <= right_Array[j].height) {
            storage[k] = left_Array[i];
            i++;
        }
        else {
            storage[k] = right_Array[j];
            j++;
        }
    k++;    
    }

    while(i < sizeOfLeft) {
        storage[k] = left_Array[i];
        i++;
        k++;
    }

    while(j < sizeOfRight) {
        storage[k] = right_Array[j];
        j++;
        k++;
    }
}

/**
 * Adds a box is the smallest possible shelf where there is room available.
 * Here we assume that there is at least one shelf (i.e. nbShelves >0)
 * @param b
 * @return problem or noProblem
 */
public String addBox (Box b){
    int i = 0, shelf_Space_Available = 0, lowest_Shelf = 1001, index_Lowest_Shelf = -1;
    while(i < nbShelves) {
        if(b.height <= storage[i].height && b.length <= storage[i].availableLength) {
            shelf_Space_Available = storage[i].height - b.height;
            if(shelf_Space_Available < lowest_Shelf) {
                lowest_Shelf = shelf_Space_Available;
                index_Lowest_Shelf = i;
            }
        }
        i++;
    }
    if(index_Lowest_Shelf >= 0) {
        System.out.println(b.id+" adding to shelf"+index_Lowest_Shelf);
        storage[index_Lowest_Shelf].addBox(b);
        System.out.println(index_Lowest_Shelf);
        print();
        return noProblem;
    }
    else {
        return problem;
    }
}

/**
 * Adds a box to its corresponding shipping list and updates all the fields
 * @param b
 * @return problem or noProblem
 */
public String addToShip (Box b){
    //System.out.println("Add to ship has box: "+b.id);
    if(b instanceof UrgentBox) {
        if(toShipUrgently == null) {
            toShipUrgently = (UrgentBox)b;
            return noProblem;
        }
        else {
            Box temp = toShipUrgently;
            while(temp != null) {
                temp = temp.next;
            }
            temp = b;
            temp.next = null;
            return noProblem;
        }
    }
    else if(b instanceof Box) {
        if(toShip == null) {
            toShip = b;
            return noProblem;
        }
        else {
            //System.out.println(b.id+" is an instance of box. Adding to box list");
            b.next = toShip;
            toShip.previous = b;
            toShip = b;
        }
    }
    //System.out.println(b.id+" did not work");
    return problem;
}

/**
 * Find a box with the identifier (if it exists)
 * Remove the box from its corresponding shelf
 * Add it to its corresponding shipping list
 * @param identifier
 * @return problem or noProblem
 */
public String shipBox (String identifier){
    Box grabber = null;
    int i = 0;
    while((grabber = storage[i].removeBox(identifier)) == null) {
        i++;
        if(i >= nbShelves) {
            break;
        }
    }
    if(grabber != null) {
        addToShip(grabber);
        return noProblem;
    }
    return problem;
}

/**
 * if there is a better shelf for the box, moves the box to the optimal shelf.
 * If there are none, do not do anything
 * @param b
 * @param position
 */
public void moveOneBox (Box b, int position){
    /*Box check;
    System.out.println("Removing "+b.id+" from shelf #"+position);
    check = storage[position].removeBox(b.id);
    System.out.println(check.id);
    print();
    if(check.id.equals(b.id)){
        addBox(b);
    }
    else{
        System.out.println("Box not moved -- not found.");
    }*/
    String problemOrNoProblem = addBox(b);
    System.out.println("Removing "+b.id+" from shelf #"+position);
    if(problemOrNoProblem.contentEquals(noProblem)){
        Box check = storage[position].removeBox(b.id);
        System.out.println(check.id+" removed from shelf "+position);

    }
}

/**
 * reorganize the entire warehouse : start with smaller shelves and first box on each shelf.
 */
public void reorganize (){
    Box compare;
    print();
    for(int i = 0; i < nbShelves; i++) {
        compare = storage[i].firstBox;
        while(compare != null) {
            moveOneBox(compare, i);
            compare = compare.next;
        }
    }
}

}

还有我的书架class代码。

package assignment2;

public class Shelf {

protected int height;
protected int availableLength;
protected int totalLength;
protected Box firstBox;
protected Box lastBox;

public Shelf(int height, int totalLength){
    this.height = height;
    this.availableLength = totalLength;
    this.totalLength = totalLength;
    this.firstBox = null;
    this.lastBox = null;
}

protected void clear(){
    availableLength = totalLength;
    firstBox = null;
    lastBox = null;
}

public String print(){
    String result = "( " + height + " - " + availableLength + " ) : ";
    Box b = firstBox;
    while(b != null){
        result += b.id + ", ";
        b = b.next;
    }
    result += "\n";
    return result;
}

/**
 * Adds a box on the shelf. Here we assume that the box fits in height and length on the shelf.
 * @param b
 */
public void addBox(Box b){
    if(firstBox == null) {
        b.next = null;
        b.previous = null;
        firstBox = b;
        lastBox = b; 
    }
    else {
        lastBox.next = b;
        b.previous = lastBox;
        b.next = null;
        lastBox = b;
    }
    System.out.println(b.id+" added");
    availableLength = availableLength - lastBox.length;
}

/**
 * If the box with the identifier is on the shelf, remove the box from the shelf and return that box.
 * If not, do not do anything to the Shelf and return null.
 * @param identifier
 * @return
 */
public Box removeBox(String identifier){
    Box temp = firstBox;
    while(temp != null) {
        if(temp.id.equals(identifier)) {
            if(temp.next != null && temp.previous != null) {
                temp.previous.next = temp.next;
                temp.next.previous = temp.previous;
                temp.next = null;
                temp.previous = null;
                System.out.println("Running normal removal "+identifier);
            }
            else if(temp.next == null && temp.previous == null) {
                firstBox = null;
                lastBox = null;
                System.out.println("Running only 1 box "+identifier);
            }
            else if(temp.next == null && temp.previous != null) {
                lastBox = temp.previous;
                temp.previous = null;
                lastBox.next = null;
                System.out.println("Running last box "+identifier+" previous box is "+lastBox.id);
            }
            else if(temp.next != null && temp.previous == null) {
                firstBox = temp.next;
                temp.next = null;
                firstBox.previous = null;
                System.out.println("Running first box "+identifier);
            }
            availableLength = availableLength + temp.length;
            return temp;
        }
        //System.out.println("Next box");
        temp = temp.next;
    }
    System.out.println("No box "+identifier);
    return null;
}

}

任何 help/tips 任何人都可以给我，我将不胜感激，谢谢。

Answer 1

你的moveOneBox应该是这样的：

public void moveOneBox (Box b, int position){    
    Box check;
    System.out.println("Removing "+b.id+" from shelf #"+position);
    check = storage[position].removeBox(b.id);
    System.out.println(check.id);

    for(int i = 0; i< nbShelves ; i++) {
      if(storage[i].height >= b.height && storage[i].availableLength >= b.length) {
        storage[i].addBox(b);
        break;
      }
    }
}

你的reorganize应该是这样的：

public void reorganize (){   
    Box compare;
    print();
    for(int i = 0; i < nbShelves; i++) {
      compare = storage[i].firstBox;

      while(compare != null) {
        Box nextCompare = compare.next;
        moveOneBox(compare, i);
        compare = nextCompare;

       }
    }
}

Java 中的双链表问题

Problems with Double Linked List in Java

java

linked-list

doubly-linked-list