2

我正在尝试在链表上实现 Shell 排序。我将原始链表划分为子链表，其中包含关于 shell 排序算法的“k”间隙的节点。我想通过操作“下一个”指针而不是更改其数据字段来对子链表进行排序。所以我有一个sortList函数可以遍历链表并在swapNodes遇到任何无序节点时交换节点。

当我将带有两个元素的无序列表传递给时，sortList我不断丢失列表中的一个节点。例如，我的列表中有 50 和 -84，我将其传递给sortList. 在sortList它们无序的数字之后，它调用swapNodes，但一旦swapNodes终止，结果列表只有 50 个。

我尝试 gdb 并发现当我在swapNodes范围内时，列表会成功排序而不会丢失节点，但是当它终止并返回sortList范围时，headandcurr都只指向 50，并且它们的“下一个”字段为 NULL。

我的职能：

void sortList(Node * head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = head; curr -> next != NULL; ) {
                *n_comp += 1; //number of comparison
                if(curr->value > curr->next->value) {
                    swapNodes(curr, curr->next, &head);
                    didSwap = 1;
                } 
                curr = curr -> next;
                if (!curr) break;
            }
    }
}

void swapNodes(Node * p1, Node * p2, Node ** start) 
{
    Node *p1pre = NULL;
    Node *p1curr = *start;
    while (p1curr && p1curr!=p1)
    {
        p1pre = p1curr;
        p1curr = p1curr->next;
    }
    Node *p2pre = NULL;
    Node *p2curr = *start;
    while (p2curr && p2curr != p2)
    {
        p2pre = p2curr;
        p2curr = p2curr->next;
    }

    if (p1pre != NULL)
    {
        p1pre->next = p2curr;
    }
    else
    {
        *start = p2curr;
    }
    if (p2pre != NULL)
    {
        p2pre->next = p1curr;
    }
    else
    {
        *start = p1curr;
    }
    Node *temp = p2curr->next;
    p2curr->next = p1curr->next;
    p1curr->next = temp;
    return;
}  
``
4

1 回答 1

1

发生这种情况的原因与您首先给出start类型Node**的原因相同：您的节点 [50] 正在移动并head随之移动，而不是停留在列表的开头。您需要更改您的 sortList 方法，以便参数head也具有类型Node**：

void sortList(Node ** head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = *head; curr -> next != NULL; ) {
            std::cout<< "It: " << *n_comp<< std::endl;
            *n_comp += 1; //number of comparison
            if(curr->value > curr->next->value) {
                swapNodes(curr, curr->next, head);
                didSwap = 1;
            }
            curr = curr -> next;
            if (!curr) break;
        }
    }
}

现在你的头将停留在列表的开头。

注意：这是哨兵节点成为事物的原因之一。

于 2020-05-02T14:23:59.413 回答