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 %10ssn", "First", "Last");
  printf("%10s %10sn", "-----", "----");
  for (i = 0; i < maxEmployees; i++)
  {
    printf("%10s %10ssn", (*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部分。