c - 链表功能？

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

让我们从我认为您应该做的不同的事情开始：


函数的名称为connecting。在给出了您希望函数执行的操作的描述之后，这不是一个好名字。
我可以从用法中推断出linkk是类型定义的指针。大多数情况下，以这种方式隐藏指针不是一个好主意。
您的函数返回一个int。总是0。为什么？这没有任何意义。
因为linkk可能是指向节点的指针，并且您按值（即它的副本）将头指针传递给函数，所以您无法处理列表的头最小的情况。返回“新”头指针，或将指针传递到头指针以能够修改头指针。
正如已经建议的那样，您对sizeof的使用是完全错误的。 sizeof(L)将为您提供指针的大小（以char s为单位），因此在64位系统上可能为8，在32位系统上可能为4。
您不是在更改节点，而是在节点之间移动值。如果您要执行此操作，则可以，但是算法说明建议您改为移动节点。
IMO，您的功能做得太多。这可能很难拆分，但是更好的方法是分离查找/提取最小值并将其放在列表的末尾。
您所做的修改超出了原先的意图。考虑类似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个指针：

结构节点*前任*最小*后继

在将 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的项目。 （因此，我们也可以测试 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!

最后，要考虑的一件事：如您所见，移动节点（而不是项目）更加复杂。为了达到我们想要的目的，我们至少需要修改2个指针。相比之下：移动项目值需要对项目值进行两次修改（并且迭代更容易）。因此，仅当指针分配比项目分配快时，才移动节点而不是项目。由于项目的类型为 int，因此这里不是这种情况。

移动项目而不是包含项目的节点要容易得多。首先，我们需要跟踪最小值（值和节点）：

struct node * minimum;
int currentMinimum;

为了进行迭代，我们将再次使用两个指针。可以只用一个完成，但是这样可以使代码更具可读性：

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;

好的，现在有点长了，但是希望它很容易理解！