0

我有一个来自 https://hotfile.com/dl/253309046/133284f/4_SinglyLinkedList.rar.html的项目

该函数insertOrdered()按顺序插入分数。

我的问题是：可以在不使用“先前”变量的情况下重写此循环吗？

SinglyNode* current = head;
SinglyNode* previous= NULL;
while (current != NULL)
{
    if(newNode->score >= current->score)
        previous = current; 
    else
        break;
    current = current->next;
}

newNode->next   = previous->next;
previous->next  = newNode;
4

5 回答 5

0

在另一个变量（比如 x）中获取前一个变量（比如 p）的值，并使用 x 而不是 p。

于 2013-11-02T15:15:16.250 回答
0

一个简单的解决方案是首先检查它是否应该插入到头部之前。如果不是，则使用类似于您的循环但比较current->next（如果不是NULL），那么当循环结束时，新节点应插入到 and 之间current，current->next即在您现在拥有的代码current中使用previous。如果current->next是NULL则在末尾插入。

于 2013-11-02T15:17:13.143 回答
0

无法对此进行测试，但将新的节点设置代码移动到 if 块中应该允许您删除以前的变量。

SinglyNode* current = head;
while (current != NULL)
{
    if(newNode->score >= current->score) {
        newNode->next  = current->next;
        current->next  = newNode; 
    }
    else break;
    current     = current->next;
}
if(current == NULL) { // got to end of list
    current->next  = newNode;
    newNode->next  = NULL;
}
于 2013-11-02T15:17:33.253 回答
0

这应该有效：

SinglyNode* current = head;
if(current == NULL) {
    head = newNode;
}
else if(newNode->score < current->score) {
    newNode->next  = current;
    head  = newNode;  
}
else {
    while (current->next != NULL)
    {
        if(newNode->score < current->next->score)
          break;
        current = current->next;
    }

    newNode->next  = current->next;
    current->next  = newNode;  
}
于 2013-11-02T15:18:32.260 回答
0

您无法消除“先前”变量，但可以伪装它；此外，您可以构造循环，使其成为唯一的迭代变量。

当然要插入新的，您需要更新前一个节点以指向它。

您可以通过在列表中向前查看并处理各种情况来从当前节点执行此操作。

另一种方法是在前一个节点中保留指向指针字段的指针。

node **ppnode;

for (ppnode = &head;
     *ppnode != NULL && (*ppnode)->value >= newnode->value;
     ppnode = &(*ppnode)->next) 
   ; /* empty body */

newnode->next = (*ppnode) ? (*ppnode)->next : NULL;
*ppnode = newnode;

在这里，current我们不使用指向当前节点的ppnode指针，而是使用间接指向当前节点的指针。它不是指向该节点，而是指向指向该节点的指针（因此必须适当地键入：它是指向指针的指针：双星）。

指向第一个节点的指针是列表head变量，因此最初ppnode指向该head变量。之后指向每个其他节点的指针是next前一个节点的字段：这些字段中的每一个next都非常像head列表其余部分的一个。因此，使用这个ppnode变量，我们跟踪必须更新的前一个节点中的位置，而不跟踪前一个节点本身。这让我们可以处理没有前一个节点的列表前面的情况。

让我们追踪为空的情况head（列表为空）。

ppnode指向head. 但是*ppnode为空，因此循环体永远不会执行。

由于ppnode指向head，这些行：

newnode->next = (*ppnode) ? (*ppnode)->next : NULL;
*ppnode = newnode;

含义相同：

newnode->next = head ? head->next : NULL;
head = newnode;

这些行中的条件检查处理将新节点添加到空列表或非空列表尾部的情况。如果列表为空或其中的所有值都小于新值，则循环以ppnode指向列表的空终止符（head如果列表为空，否则next为尾节点的字段）终止。由于*ppnode为空，我们不能服从(*ppnode)->next。没有下一个；新节点是最后一个节点，它next必须为空。

现在让我们看看在有头节点的情况下会发生什么，并且它的值更大，因此必须将新节点插入到最前面。在这种情况下ppnode指向head，和以前一样，并且*ppnode != NULL条件为真。但是(*ppnode)->value >= newnode->value条件失败，因此循环永远不会执行。

现在，我们再次执行此代码的等价物：

newnode->next = head ? head->next : NULL;
head = newnode;

但这一次head不是空的，所以newnode->next = head->next, 和以前一样，newnode变成了新的head。

所有其他情况都从这两个开始：除了不是head，动作使用next前一个节点的指针来执行，这就像列表其余部分的头部。

于 2013-11-02T15:26:04.430 回答