链接列表函数？

Question

所以我写这个函数，使最小的节点在链表的末尾。到目前为止，它的工作除了最后一个元素。如果链表被创建为包含0〜9项的节点，则该函数之后的列表为{1,2,3,4,5,6,7,8,0,9}，零不成为结束。

任何想法为什么？

我的功能;

int connecting(linkk A) 
{ 
    linkk L = A; 
    for (int i = 0; i<sizeof(L);i++) 
    { 
     if (L->item < L->next->item) 
     { 
      int a = L->item; 
      L->item = L->next->item; 
      L->next->item = a; 
      L = L->next; 
     } 
     else{L=L->next;} 
    } 
    return 0; 
} 

Answer 1

让我们先从什么，我认为你应该做的是不同的：

1. 你的函数的名称为connecting。鉴于你想要的功能的描述，这是而不是一个很好的名字。
2. 我可以从使用中推断出linkk是一个typedef指针。在大多数情况下，隐藏指针并不是一个好主意。
3. 你的函数返回一个int。它总是0。为什么？这没有任何意义。
4. 因为linkk可能是一个指向节点的指针，并且您将头指针按值（即它的副本）传递给该函数，所以无法处理列表头部最小的情况。返回“新”头指针，或将指针传递给头指针以便能够修改头指针。
5. 您已经暗示您使用sizeof是完全错误的。 sizeof(L)会给你指针的大小（在char s），因此可能是8位在64位系统或4位在32位系统上。
6. 您并未更改节点，而是移动节点之间的值。如果它是你想要做的，这是可以的，但是你的算法的描述表明你想要移动节点。
7. 您的功能太多了，IMO。这可能很难分开，但更好的方法是分开查找/提取最小值并将其放在列表的末尾。
8. 您的修改比您原来想要的要多得多。考虑一个列表，如1, 2, 3, 0, 4。使用您的算法，该列表将更改为2, 3, 1, 4, 0。这样做不仅对性能不利，而且对于呼叫者来说也是非常令人惊讶的。当谈到编程时，惊喜并不好！

所以，让我们的希望良好的实施，分步实施：

struct node { 
    int item; 
    struct node * next; 
}; 

我假设你要移动的节点包含的最低值到列表的末尾，如您描述。为了保持与原始代码更接近，我也将这个函数保存为一个函数，接收struct node * head指针，尽管我的观点如上所述。让我们先来看一下特殊/基本情况：移动空列表的最小元素以及单个元素列表是微不足道的：不做任何事情。

if (head == NULL || head->next == NULL) { 
    return head; 
} 

我返回列表的“新”头允许调用者更新它自己的头指针。（正如已经说过的，head只是调用者头指针的副本，修改它在调用站点不会有任何影响）。

因为我们在这里处理单向链表，并且实现不应该在列表中不必要地迭代，所以我们应该记住我们以前访问过的节点。否则，我们不能轻易从列表中提取一个节点：直接

struct node * follow, * point; 

follow遵循point后面。

最初，我们将该点放在列表的第二个节点（我们已经检查了列表中至少有2个节点）。因此follow将指向头：

point = head->next; 
follow = head; 

因为我们想找到最低的项目，我们需要保持最小的已经搜索列表的一部分的轨道。我们用头节点的值初始化它：

int currentMinimum = head->item; 

现在我们准备遍历列表，以便找到包含最小值的节点。但是我们不仅需要找到包含最小值的节点，还需要找到它之前的节点和之后的节点，以便能够轻松地提取它。所以，3个指针：

struct node * predecessor，* minimum，* successor;

我们设置currentMinimum到head小号的项目，我们也应该相应地设置指针：

predecessor = NULL; // Nothing preceding the head 
minimum = head; 
successor = head->next; 

现在让我们重复，完全动点在列表中，直到它在最后脱落：

while (point != NULL) { 
    // to be continued 
    follow = point; 
    point = point->next; 
} 
// when we're here, follow will point to the last node 

在每次迭代中，我们需要检查，如果发现比目前的最低较小的值，并最终记住的节点包含它：

if (point->item < currentMinimum) { 
    predecessor = follow; 
    minimum = point; 
    successor = point->next; 
    currentMinimum = point->item; 
} 

现在，当我们走出循环，下面的状态应该达到：

• minimum指向包含最小的节点。
• follow指向列表的最后一个节点。
• 上面两个可能是相同的，这是一个特例！
• predecessor仍然可能是NULL，这是另一种特殊情况！

首先考虑minimum = follow的特殊情况：在这种情况下，最小值已经在列表的末尾，所以赢利！否则，我们需要minimum“开刀”的节点淘汰之列，并追加到最后一个节点，指向follow：

if (follow != minimum) { 
    if (predecessor != NULL) { 
    predecessor->next = successor; // Cut out 
    minimum->next = NULL; // will be the last node 
    follow->next = minimum; // append at end 
    } else { 
    // to be continued 
    } 
} 

正如你所看到的，还有要考虑第二个特殊情况：如果predecessor仍然是NULL，那么没有项目小于head s项目。（因此，我们也可以测试minimum == head）因此，列表的第一个节点将移动到最后。我们需要通知来电者！

head = head->next; // Second node is now the first one, though this is not all we need to do, see further down! 
minimum->next = NULL; // Will be the last node 
follow->next = minimum; // Append at end 

由于分配给head不仅改变了功能参数（这是与该功能被称为指针的拷贝），我们需要返回（可能修改！）头指针，给发话更新了自己的头指针的能力：

return head; 

来电者将因此使用此功能，像这样：

struct node * head = get_a_fancy_list(); 
head = move_minimum_to_end(head); // This is our function being called! 

最后，要考虑的：为y你可以看到，移动节点（而不是项目）更复杂。我们需要修改至少2个指针才能实现我们想要的。相反：移动项目值需要对项目值进行两次修改（并且迭代更容易）。因此，当指针分配比项目分配快时，移动节点而不是项目。由于项目是int这是而不是这里的情况。

移动项目而不是包含项目的节点相当容易。首先，我们需要跟踪最小的（价值以及节点）：

要迭代，我们再次将使用两个指针。它可以用一个一个来完成，但代码将是更具可读性这样：

struct node * point, * follow; 

我们开始用相同的初始状态：

minimum = head; 
currentMinimum = head->item; 
follow = head; 
point = head->next; 

迭代类似于其他实施，是迭代步骤：

while (point != NULL) { 
    if (point->item < currentMinimum) { 
    minimum = point; 
    currentMinimum = point->item; 
    } 
    follow = point; 
    point = point->next; 
} 
// follow points to the last node now 

现在，做一样的以前的实现，我们可以交换的最后一个节点的项目和最小的节点：

minimum->item = follow->item; 
follow->item = currentMinimum; // contains minimum->item 

有在检查follow != minimum像以前的做法是没有意义的：你可以这样做，但交换节点的项目有自己的项目不会做任何伤害。 OTOH添加if将增加一个分支，因此可能会导致性能损失。

由于我们没有更改列表结构（节点之间的链接），因此没有更多需要考虑的事项。我们甚至不需要告诉来电者一个新的头像，因为它永远不会有任何改变。出于风格的目的，我会添加它：

return head; 

好吧，这有点长，但希望它很容易理解！

Answer 2

试试这个功能

int connecting(linkk A) 
{ 
linkk L = A; 
    while(L->next!=NULL) 
    { 
    if (L->item < L->next->item) 
    { 
     int a = L->item; 
     L->item = L->next->item; 
     L->next->item = a; 

    } 

    L=L->next; 
    } 
    return 0; 
}