c - 如何对链表进行排序

Question

我正在尝试按姓氏对线性链表进行排序，但它崩溃了，而且我也不知道我的算法是否正常工作。

谁能帮我阻止它崩溃，看看我的列表排序算法是否有效？

void sort(NODEPTR *employees, int maxEmployees)
{
  int i = 0, j = 0, k = 0;
  NODEPTR p, q, pTrail = NULL, qTrail, temp;
  temp = (NODEPTR) calloc(1, sizeof(node));

  qTrail = *employees;
  q = (*employees)->next;
  for (i = 0; i < maxEmployees; i++)
  {

    p = *employees;

    while (p != q)
    {

      if (strcmp(p->lastName, q->lastName))
      {
        temp = q;
        qTrail = q->next;
        q = pTrail->next;

        temp = pTrail->next;
        pTrail = temp;

        p = q;
      }
      else
      {
        pTrail = p;
        p = p->next;
      }

    }
    qTrail = q;
    q = q->next;

    pTrail = NULL;
  }
  printf("%10s %10ss\n", "First", "Last");
  printf("%10s %10s\n", "-----", "----");

  for (i = 0; i < maxEmployees; i++)
  {
    printf("%10s %10ss\n", (*employees)->firstName, (*employees)->lastName);
  }
}

链表:

typedef struct node
{
  char firstName[11];
  char lastName[16];
  char gender;
  int tenure;
  char rate;
  float salary;
  struct node *next;
} node, *NODEPTR;

Answer 1

你的逻辑似乎是错误的:

strcmp() 将返回三个 值。

• 1 如果第一个参数的值为 >
• -1 如果第二个参数的值为 >
• 0 如果两个参数的值相同。

所以基于strcmp(p->lastName,q->lastName)你不能排序。

您应该仅在 strcmp() 返回 1 时更改位置。对于 -1 和 0 它应该放在 else 部分。