按字母顺序排序双向链表

Question

任务是按字母顺序对列表进行排序。这将通过更改指针变量来完成，而不仅仅是切换节点的内容。

我首先想实现一个交换功能。该功能应交换 2 个节点。之后我想实现一个排序算法。我的问题是，交换功能并没有真正发挥应有的作用，算法也没有（ofc，因为交换功能甚至不起作用）。

    struct student {
      char Vorname[51];
      char Nachname[51];
      int MatNr;
      char Adresse[51];
      int Kurse;
      struct student *next;
      struct student *previous;
    };

    struct student *first = NULL;
    struct student *last = NULL;  

    void swap(struct student *pointer) {
      struct student *pointer1, *pointer3, *pointer4;
      pointer1 = pointer->previous;
      pointer3 = pointer->next;
      pointer4 = pointer->next->next;

      pointer4->previous = pointer;
      pointer->next = pointer4;
      pointer1->next = pointer3;
      pointer3->previous = pointer1;
      pointer->previous = pointer3;
      pointer3->next = pointer;
    }

这是未完成的排序功能。我还没有正确实现它，因为交换功能首先引起了我的注意。

void sort(void) {
  struct student *pointer1, *pointer2, *pointer3, *pointer4;
  pointer1 = first->previous;
  pointer2 = pointer1->next;
  pointer3 = pointer2->next;
  pointer4 = pointer3->next;

  while(pointer2 != NULL){
    if((strcmp(pointer2->Nachname, pointer3->Nachname)) > 0) {
           swap(pointer2);
    }
    pointer1 = pointer1->next;
    printList();
  }
}

当我运行 swap(first); 时，第一个元素不会显示，因为指针 first 现在指向第二个节点。嗯，这很容易用 first = pointer3;

当我运行 swap(first->next); 有一个类似的问题，因为它也遗漏了列表的一个节点。

我不太确定如何正确使用此函数，因为 first 不应该参与交换列表的第二个和第三个节点。

如果能帮助我解决这个问题，我将不胜感激，也许我只是忽略了一些小错误，但我无法真正解决这个问题。谢谢！

Answer 1

通过交换双向链接节点对列表进行排序似乎效率很低，因为您不能使用像归并排序这样的快速算法。

您可以在递归合并排序函数中仅使用 next 链接，并在结果列表中重建反向链接。

操作方法如下：

struct student {
    char Vorname[51];
    char Nachname[51];
    int MatNr;
    char Adresse[51];
    int Kurse;
    struct student *next;
    struct student *previous;
};

struct student *first = NULL;
struct student *last = NULL;

/* Merge two sorted lists. p1 and p2 are != NULL */
struct student *merge(struct student *p1, struct student *p2) {
    struct student *head, **pp;
    pp = &head;
    for (;;) {
        if (strcmp(p1->Nachname, p2->Nachname) <= 0) {
            *pp = p1;
            pp = &p1->next;
            p1 = p1->next;
            if (p1 == NULL) {
                *pp = p2;
                break;
            }
        } else {
            *pp = p2;
            pp = &p2->next;
            p2 = p2->next;
            if (p2 == NULL) {
                *pp = p1;
                break;
            }
        }
    }
    return head;
}

/* Recursive top-down merge sort */
struct student *msort(struct student *np) {
    struct student *p1, *p2;
    /* trivial lists are sorted */
    if (np == NULL || np->next == NULL)
        return np;
    /* locate mid-point using 2 finger method */
    for (p1 = np, p2 = np->next; p2 && p2->next; p2 = p2->next->next)
        p1 = p1->next;
    /* split the list at mid-point */
    p2 = p1->next;
    p1->next = NULL;
    p1 = np;
    /* sort the sublists recursively */
    p1 = msort(p1);
    p2 = msort(p2);
    return merge(p1, p2);
}

void sort(void) {
    struct student *p1, *p2;
    /* sort the list as a singly linked list */
    first = msort(first);
    /* reconstruct the backlinks */
    p1 = NULL;
    for (p2 = first; p2; p2 = p2->next) {
        p2->last = p1;
        p1 = p2;
    }
    last = p1;
}

正如 rcgldr 所建议的那样，使用自下而上的合并排序可能更有效，以避免重复扫描列表。这是备用代码：

/* bottom-up merge sort with sublist array */
struct student *msort(struct student *head) {
    struct student *array[32] = { NULL };
    int i;

    /* handle trivial lists */
    if (head == NULL || head->next == NULL)
        return head;

    i = 0;  /* avoid warning */
    p1 = head;
    /* merge nodes into pending lists of increasing lengths */
    while (head != NULL) {
        struct student *next = head->next;
        head->next = NULL;
        for (i = 0; i < 32 && array[i] != NULL; i++) {
            head = merge(array[i], head);
            array[i] = NULL;
        }
        /* do not go past end of array */
        if (i == 32)
            i--;
        array[i] = head;
        head = next;
    }
    /* merge pending lists into single list:
     * the last element stored into the array is at offset i and
     * all entries before it are NULL pointers. */
    for (head = array[i++]; i < 32; i++) {
        if (array[i] != NULL)
            head = merge(array[i], head);
    }
    return head;
}

按字母顺序排序双向链表

Sorting doubly linked list alphabetical

c

sorting

doubly-linked-list