插入排序双链表

Question

我试图在C中的双向链表上做插入排序。在这种状态下，我的代码让我陷入了一个没有结束的循环，吐出了8和9。

有人能好心解释一下“插入排序”方法是如何设计的吗？

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

到目前为止这是我的代码

我的希望破灭了。请帮忙。

#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

有人能好心解释一下“插入排序”方法是如何设计的吗？

首先，我建议去掉长度变量，或者至少不要在排序例程中使用它。它是不需要的，依赖它可能会将您的想法过多地转移到数组风格的实现上。当您发现下一个指针为NULL的节点时，您知道您已经到达了列表的末尾。

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

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

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

• 维护一个指针，S，指向排序的前导子列表的最后一个节点。最初，这将指向列表头。
• 如果S指向最后一个节点（可以通过S-判断

实际的代码保留为它想要的练习。