c - 我的排序功能出了什么问题

Question

我很难理解为什么这个排序功能不起作用。它确实将节点按排序顺序排列，但第一个节点总是在此过程中丢失。这是我的代码(head 变量是全局的):

void medianscore() {
   int i, j=0;
   int counter=0;
   struct student *curr=head;
   struct student *trail=head;
   struct student *temp=NULL;

   while (curr !=NULL)
   {
      curr=curr->next;    //couting the number of items I have in my list.
      counter++;          //this works fine.
   }

   curr=head->next;          // reseting the curr value for the 2nd position.

   for (i=0; i<counter; i++)
   {
      while (curr != NULL)
      {
          if (trail->grade > curr->grade)
          {
             temp=curr->next;      //bubble sort for the pointers.
             curr->next=trail;
             trail->next=temp;

             temp=curr;         //reseting trail and curr. curr gets back to be infront.
             curr=trail;
             trail=temp;

             if (j==0)   //i'm using j to determine the start of the loop so i won't loose the head pointer.
             {
                head=trail;
             }
          }
          j++;
          trail=curr;
          curr=curr->next;   //traversing thru the list. nested loop.
      }

      trail=head;
      curr=trail->next;
      curr->next=trail->next->next;  //traversing thru the list. outer loop.
      j=0;
   }
}

我做错了什么？

Answer 1

您的节点计数以及使用变量 i 和 j 来控制排序的代码味道很糟糕。这些应该不是必需的。

稍后我将讨论 j 和您的头列表处理。对于 i 上的外部循环，您可以为外部循环的每次迭代维护一个标志，以便确定在该迭代结束时是否进行了任何交换。如果不是，则无需执行另一次迭代。这种方法永远不会执行比您当前技术执行的迭代更多的迭代，并且对于大多数输入，它执行的迭代次数会更少。

但是，我在您的代码中看到的主要问题是它无法正确执行节点交换。假设你从这种情况开始......

prev --> trail --> curr --> Z

.... 您询问 trail 和 curr 是否必须交换的问题，并假设您确定它们必须交换。在这种情况下，您更新 trail 的 next 指针和 curr 指针，但不更新 prev 指针，结束链接如下:

prev ----V
       trail --> Z
curr ----^

此时，curr 实际上已丢失 - 从列表头到 Z 的链接链不再通过它，并且您无法执行任何其他操作来修复那个。

我想您可能会遇到这个问题，部分原因是您的头节点是一个特殊情况，没有任何链接到它。但事实并非如此。在不更改代码中其他地方如何使用链表的任何内容的情况下，您可以创建一个指向 head 的 medianscore() 本地虚拟节点:

struct student dummy;

dummy->next = head;

然后您可以使用 ... 开始外循环的每次迭代

trail = &dummy;

...并在内循环中测试 trail->next 是否应与 trail->next->next 交换。当然，您的循环终止条件和交换需要稍有不同，但您始终需要有一个指向要交换的第一个节点之前的节点的指针，如此提供的，以便您可以更新其 下一个指针。

这样做还有另一个好处:头节点不再需要在排序循环中进行任何特殊处理。相反，最后您只需设置 head = dummy->next;。