Никак не сортирует список, подскажите, где ошибка.
Я создал 2 односвязных списка. Один пустой, в который будет помещен отсортированный список, а второй - исходный односвязный список. С каждой итерацией мы удаляем узел из нашего начального списка и вставляем в нужную позицию отсортированного списка. Сортировка реализуется благодаря 2 функциям. Первая функция (SortedInsert) ищет место в отсортированном списке, куда вставить узел. Вторая функция(InsertionSort) - это непосредственно сама сортировка, в которой отбирается узел из исходного списка, который нужно вставить в новый список и вставляется благодаря первой функции. Так же во второй функции мы учитываем случай, когда нужно вставить узел первым в список
Вот сам алгоритм сортировки вставками:
PNode InsertionSort(PNode Head)
{
if(!Head || !Head->next)
return Head;
PNode ptr = Head->next;
PNode result = Head;
result->next = NULL;
while(ptr)
{
PNode temp = ptr;
ptr = ptr->next;
result = SortedInsert(result, temp);
}
return result;
}
С помощью этой функции находит место, куда вставить узел в новом массиве:
PNode SortedInsert(PNode Head, PNode NewNode)
{
if(Head == NULL || Head->data >= NewNode->data)
{
NewNode->next = Head;
Head = NewNode;
return Head;
}
PNode ptr = Head;
PNode prev = NULL;
while(ptr != NULL && ptr->data < NewNode->data)
{
prev = ptr;
ptr = ptr->next;
}
NewNode->next = ptr;
prev->next = NewNode;
return Head;
}
Весь код с добавлением и отображением списка:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
typedef Node *PNode;
void AddNode(PNode &Head, int data);
void ShowList(PNode &Head);
int main()
{
PNode Head = NULL;
int node;
cout << "Enter 5 members of the linked list!" << endl;
for(int i = 0; i < 5; i++)
{
cin >> node;
AddNode(Head, node);
}
ShowList(Head);
cout << endl;
InsertionSort(Head);
ShowList(Head);
return 0;
}
void AddNode(PNode &Head, int data)
{
PNode NewNode = new Node;
NewNode->data = data;
NewNode->next = Head;
Head = NewNode;
cout << "Done!" << endl;
}
void ShowList(PNode &Head)
{
PNode q = Head;
while(q)
{
cout << q->data << " ";
q = q->next;
}
}