插入排序双向链表

Question

我正在尝试对 C 中的双向链表进行插入排序。在这种状态下，我的代码让我陷入了一个无休止的循环，吐出 8 和 9。

有人可以解释一下 "insertionSort" 方法应该如何设计吗？

我的链表设计为包含头、上一个、下一个和一些数据。

到目前为止，这是我的代码

我的希望是空的。请帮忙

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int data;
struct Node* next;
struct Node* previous;

}Node;

struct Node* head = NULL;
struct Node* current = NULL;
struct Node* headsorted = NULL;
int l = 0;
int empty = 1;
int length = 0;
int change = 0;

void InsertSort(){

Node* temp = (Node*)malloc(sizeof(struct Node));

temp = head;
current = head->next;

printf("\nInsert Sort begins...\n");

if (head != NULL && head->next != NULL)
{
   for (int i = 1; i < length; i++)
   {
        while(current->data > current->next->data && current->next != NULL && current != NULL)
        {
            temp = current;
            current = current->next;
            current->next = temp;
        }
   }
}
else
{
printf("\nList Error!\n");
}

temp = NULL;

}

void Insert(int x)
{
    Node* temp = (Node*)malloc(sizeof(struct Node));

    temp->data = x;
    temp->next = head;
    temp->previous = NULL;

   if (head != NULL)
   {
       head->previous = temp;
   }
    head = temp;
}

void Print(){

    struct Node* temp = head;
    printf("List is: ");
    while(temp != NULL)
    {
        printf(" %d", temp->data);
        temp = temp->next;
    }
}

int main()
{
    head = NULL;
    FILE * file = fopen("List.txt", "r");

    fscanf(file, "%d", &l);
    while (!feof (file))
    {
        Insert(l);
        fscanf(file, "%d", &l);
        length++;
    }
    fclose(file);

    Print();

    printf("\n\n\n");

    printf("data: %d next: %d   " , head->data, head->next->data);

    InsertSort();

    Print();

    return 0;
}

Answer 1

can someone please be kind enough to explain how the "insertionSort" method is supposed to be designed?

首先，我建议去掉 length 变量，或者至少不要在排序例程中使用它。它不是必需的，依赖它可能会使您的想法过多地转向数组样式的实现。当您发现 next 指针为 NULL 的节点时，您知道您已经到达列表的末尾。

其次，我重申我的意见，即您没有正确执行双向链表的节点交换。任何链表上的节点交换，无论是单链还是双链，都等同于从链表中完全提取第二个节点，然后将其重新插入到第一个节点之前。在一个单向链表中，通常影响三个节点：除了交换的两个节点之外，还有第一个节点的前任节点。在双向链表中，它还会影响第二个的后继者。在双向链接的情况下，这已经够混乱了，我建议将其明确地构造为先切除后插入。

但我也建议你退一步，从高层次上看算法。它的工作原理是依次考虑每个节点，从第二个开始，如果有必要，将其删除并将其重新插入到它前面的（已排序）子列表中的正确位置。那么，成对交换与它有什么关系呢？无。在数组上实现这样的排序时，这是一个很方便的细节，但在对链表进行排序时，它会做一些不必要的工作。

对于链表，尤其是双向链表，我建议更直接地切入算法的抽象描述的实现：

维护一个指针，S，指向已排序的前导子列表的最后一个节点。最初，这将指向列表头。
如果S指向最后一个节点（可以通过S->next判断）则停止
否则，检查 *S 的后继 *N 是否相对于 *S 正确排序。
- 如果是这样，则将 S（指针，而不是其引用对象）设置为 N。
- 如果没有，那么
  - 从列表中删除 *N（适当更新其前身和后继，如果有的话），以及
  - 向后遍历已排序的子列表，直到到达第一个节点或其前导节点应在 *N 之前，以先遇到者为准。
  - 在您发现的节点前插入 *N。
  - 如果这使得 *N 成为列表头（你可以通过它的 previous 指针的新值来判断），然后将头指针（不是它的引用）设置为 N.
从点 2 开始重复

实际代码留作练习。

插入排序双向链表

insertion sort doubly linked list

c

insertion-sort

doubly-linked-list