вставка сортировать двусвязный список

Question

Я пытаюсь выполнить сортировку вставки в двусвязном списке в C. В этом состоянии мой код застревает в бесконечном цикле, выплевывая 8 и 9.

Может кто-нибудь, пожалуйстабудьте любезны объяснить, как должен быть разработан метод "inserttionSort"?

мой связанный список разработан с заголовком, предыдущим, следующим и некоторыми данными.

Вот мой код на данный момент

Я надеюсь, что NULL.пожалуйста, помогите.

#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

Может быть, кто-нибудь проявит любезность и объяснит, как должен быть разработан метод "inserttionSort"?

Во-первых, я предлагаю избавиться от переменной lengthили, по крайней мере, не использовать его в своей рутине.Это не нужно, и полагаться на это может отвлечь ваше мышление в сторону реализации в стиле массива.Вы знаете, что достигли конца списка, когда обнаружили узел, указатель next которого равен NULL.

Во-вторых, я повторяю мой комментарий о том, что вы неправильно выполняете перестановки узлов для двусвязного списка.,Замена узла в любом связанном списке, независимо от того, является ли он одно- или двусвязным, эквивалентна извлечению второго узла из списка в целом, а затем повторной вставке его перед первым.В односвязном списке, который затрагивает, как правило, три узла: в дополнение к двум обмениваемым, предшественник к первому.В двусвязном списке это также влияет на преемника второго.Это достаточно запутанно в случае с двойной связью, и я предлагаю явно структурировать его как исключение с последующей вставкой.

Но я также предлагаю вам сделать шаг назад и посмотреть на алгоритм с высокого уровня.Он работает, рассматривая каждый узел по очереди, начиная со второго, и, если необходимо, удаляя его и вставляя его в правильную позицию в (отсортированном) подсписке, предшествующем ему.Так что же тогда с этим связано парным обменом? Nothing .Это деталь, удобная для реализации такой сортировки в массиве, но она делает ненужную работу при сортировке связанного списка.

Для связанного списка, особенно двусвязного, я предлагаю реализацию, которая более непосредственно относится кабстрактное описание алгоритма:

1. Сохранение указателя S на последний узел отсортированного ведущего подсписка.Первоначально это будет указывать на заголовок списка.
2. Если S указывает на последний узел (который можно судить по S->next), то остановитесь.
3. В противном случае проверьте, *N, преемник *S, правильно упорядочен относительно * S.
   • Если это так, тогда установите S (указатель, а не его референт) равным N.
   • Если нет, тогда
     • вырежьте *N изсписок (обновляя как своего предшественника, так и его преемника, если таковой имеется, соответственно) и
     • шаг назад через отсортированный подсписок, пока вы не достигнете либо первого узла, либо узла, предшественник которого должен предшествовать *N, в зависимости от того, что встречаетсяfirst.
     • Вставьте *N перед узлом, который вы обнаружили.
     • Если это делает *N заголовком списка (о чем вы можете судить по новому значению указателя previous), затем установите указатель головы (не его референт), равный N.
4. , повторите с точки 2

фактический код оставлен как упражнение, которому он предназначен.