Сортировка однонаправленных списков

Для ускорения поиска информации в списке, обычно при выводе данных список упорядочивают (сортируют) по ключу.

Проще всего использовать метод сортировки, основанный на перестановке местами двух соседних элементов, если это необходимо. Существует два способа перестановки элементов: обмен адресов и обмен информацией.

1. Первый способ – перестановка адресов двух соседних элементов, следующих за элементом с известным указателем. Первый элемент стека в этом случае не сортируется. Для того чтобы и первый элемент оказался отсортированным, следует перед обращением к функции сортировки добавить один (любой) элемент в стек, а после сортировки – удалить его.

Функция сортировки для этого случая имеет вид:

void Sort_p(Stack **p) {

Stack *t = NULL, *t1, *r;

if ((*p) -> next -> next == NULL) return;

do {

for (t1=*p; t1-> next->next!= t; t1=t1-> next)

if (t1->next->info > t1-> next-> next-> info){

r = t1->next->next;

t1 -> next -> next = r -> next;

r-> next =t1-> next;

t1-> next = r;

}

t= t1-> next;

} while ((*p)-> next -> next!= t);

}

Обращение к этой функции Sort_p(&begin);

2. Второй способ – обмен информации между текущим и следующим элементами. Функция сортировки для этого случая будет иметь вид:

void Sort_info(Stack *p) {

Stack *t = NULL, *t1;

int r;

do {

for (t1=p; t1 -> next!= t; t1 = t1-> next)

if (t1-> info > t1-> next -> info) {

r = t1-> info;

t1-> info = t1-> next -> info;

t1-> next -> info = r;

}

t = t1;

} while (p -> next!= t);

}

Пример выполнения задания

Написать программу, содержащую основные функции обработки однонаправленного списка, организованного в виде стека, информационная часть которого представляет собой случайные целые числа от 0 до 20.