0

请帮助我插入方法。我想在双向链表中插入一个值大于该 int 的 int。然后新的 int 将替换双向链表中更大的值（我得到了很好的工作）。但现在我希望更大的 int 出现在列表中并在适当的地方插入。

如果我说 insert 2 4 6 8 ，它会起作用（结果：2 4 6 8）如果我然后插入 1（小于 2）

结果将是 1 4 6 8 2

问题是，当我插入让我们说 7（大于 6，但小于 8）时，我不知道如何向下行并在适当的地方插入。

enter code here

public void insert(int newInt) { Cell newCell = new Cell (newInt);

  if (this.size() == 0){
      smallest = newCell;
  } 

  for (Cell i = smallest; i != null; i = i.right){

      // if newCell is the larger than all in row, then add it to the end. 
      if (newCell.value > i.value && i.right == null){
          i.right = newCell; 
      }

      // if newCell is smaller than smallest, then add it to smallest and old smallest will go down the list (compare and put it where appropriate). 
      if (newCell.value < smallest.value){
          newCell.below = smallest; 
          newCell.right = smallest.right; 
          smallest.right = null; 
          smallest = newCell; 

      }

      // if newCell is smallest than any element, then replace that cell with newCell, and send that cell to below row
      // do again untill all below rows are sorted. hence this could be a while loop. 
      if (newCell.value > i.value && newCell.value < i.right.value){
          System.out.println("newCell is " + newCell);
          Cell largerRight = i.right; 
          newCell.right = largerRight.right;
          largerRight.right = null; 
          i.right = newCell; 


          temp = smallest.below; 


          while (temp != null){
              System.out.println(temp); 

              for (Cell k = temp; k != null; k = k.right){

                  if (largerRight.value > temp.value && temp.right == null){
                      temp.right = largerRight;
                      temp = null; 
                  }



              }


              temp =temp.below; 
          }

      }

  }










}//end insert
4

1 回答 1

0

插入双向链表时，您几乎总是有一个第一个和最后一个指针。您还需要在列表中插入一个新节点，但还没有指针信息。

我会用伪代码来做这件事，这样你就可以把它翻译成你想要的任何语言（因为它可能是家庭作业）。

首先，检测一个空列表。如果是这种情况，只需构建一个新的单元素列表：

if first == NULL:
    newNode->next = NULL  # one element pointing nowhere.
    newNode->prev = NULL
    first = newNode       # first and last are that element.
    last = newNode
    return

否则，找到大于当前节点的第一个节点，这就是您要在之前插入的位置：

insertPoint = first                              # scan list until end.
while insertPoint != NULL:
    if insertPoint->payload > newNode->payload:  # stop if found one greater.
        break;
    insertPoint = insertPoint->next              # move to next.

现在，这里有三种不同的可能性：

  1. insertPoint是第一个节点，这意味着您必须在前面插入；
  2. insertPointis NULL，这意味着您必须附加到列表中；或者
  3. insertPoint是第一个以外的有效节点。

首先，处理两种特殊情况。这些被认为是特殊的，因为它们更改了列表 (first和last) 的控制信息，而不仅仅是节点本身内的指针：

if insertPoint == first:      # inserting at front.
    newNode->next = first     # new node points forwards to current first
    newNode->prev = NULL      #   and backwards to nowhere.
    first = newNode           # and update first.
    return

if insertPoint = NULL:        # appending to end.
    newNode->next = NULL      # new node points forwards to nowhere
    newNode->prev = last      #   and backwards to current last.
    last = newNode            # and update last.
    return

如果你已经到了这里，你只需要插入，知道你有一个有效的当前和前一个节点：

newNode->next = insertPoint        # set new node to point to correct nodes.
newNode->prev = insertPoint->prev
insertPoint->prev->next = newNode  # update those nodes to point to new node.
insertPoint->prev = newNode
return
于 2012-05-15T02:21:40.440 回答