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一部分。