Отправлено: 16.11.18 18:18. Заголовок: -Сортировка односвязного списка с помощью метода пузырьковой сортировки на C.

Хорошими упражнениями на выработку понимания работы с указателями являются задания по построению различных списков (односвязных, двусвязных, двухсторонних и.т.д.) и по выполнению операций с ними.

Одно из таких заданий можно найти на сайте Stackoverflow по ссылке
char (contain words) array buble sort problem (c)

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

Как показала тема Как выполнить инверсию отдельных слов в объекте класса std::string в этом разделе форума, такое задание может оказаться не по зубам даже программистам со стажем.

Сначала отметим некоторые существенные недостатки кода, представленного в исходном вопросе на сайте Stackoverflow.

Начнем с того, что согласно стандарту C функция main без параметров должна быть объявлена как

 
 int main( void ) 
 

В исходном вопросе она объявляется как

 
 void main()

Второе важное замечание касается того, что в программе объявляется глобальная переменная на начало списка. В связи с этим все функции, объявленные в этой программе, имеют дело с этой глобальной переменной и, соответственно, не могут работать с другими списками в программе.
То есть, фактически, код не является переносимым.

Член структуры с именем data имеет неверный тип char вместо типа char *. Но даже если этот член структуры имел бы правильный тип char * ( или const char *), тем не менее для хранения данных необходимо выделять динамически память под строки. Нельзя просто хранить указатели на строковые литералы, так как в общем случае пользователь может в качестве данных передать не строковый литерал. В этом случае программа будет иметь неопределенное поведение, если строки не имеют статическую память.

Для метода пузырьковой сортировки при работе с односвязным списком совершенно нет никакой необходимости знать число элементов в списке. Например, в C++ стандартный класс std::forward_list не имеет такого метода, который возвращает число элементов в односвязном списке. Такой метод не эффективный и имеет сложность O( n ).

Кроме того автор вопроса в функции, выполняющей сортировку, обменивает значения членов узла списка вместо того, чтобы обменивать сами узлы. Почему требуется обменивать сами узлы? Потому что в общем случае в программе могут быть переменные, которые ссылаются на узлы списка. После обмена значений узлов списка такие переменные будут ссылаться на переписанные узлы, а не на узлы с исходными значениями.

Итак, имеется структура вида

 
 struct node  
 {  
     char *data;  
     unsigned int key;  
     struct node *next;  
 };  
 

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

Как известно, этот метод основывается на перестановки смежных элементов последовательности. Поэтому самое сложное, что требуется в задании, это написать корректно перестановку смежных узлов списка.

Как может выглядеть соответствующая функция?

Она может выглядеть следующим образом

 
 void swap( struct node **current )  
 {  
     struct node *tmp = ( *current )->next->next;  
  
     ( *current )->next->next = *current;  
  
  
     *current = ( *current )->next;  
  
     ( *current )->next->next = tmp;  
 }  
 

Эта функция низкого уровня, а потому она не делает проверку на то, является ли указатель на следующий узел, то есть ( *current )->next, равным NULL. Это задача клиента функции выполнить такую проверку перед вызовом функции.

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

Теперь, имея данную функцию, не сложно написать функцию сортировки.

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

В ниже приведенной программе сначала созданный список сортируется по значению члена структуры key, а затем по значению поля структуры data.

Важно также не забыть удалить список, когда он больше не требуется в программе.

 
 #include <stdlib.h>  
 #include <stdio.h>  
 #include <string.h>  
  
 struct node  
 {  
     char *data;  
     unsigned int key;  
     struct node *next;  
 };  
  
 void printList( struct node **head )  
 {  
     for ( struct node *current = *head; current != NULL; current = current->next )  
     {  
         printf( "%u -> %s\n", current->key, current->data );  
     }  
 }  
  
 int insertList( struct node **head, unsigned int key, const char *data )  
 {  
     struct node *new_node = malloc( sizeof( struct node ) );  
     int success = new_node != NULL;  
  
     if ( success )  
     {  
         size_t n = strlen( data );  
  
         new_node->data = malloc( n + 1 );  
         success = new_node->data != NULL;  
  
         if ( success )  
         {  
             strcpy( new_node->data, data );  
             new_node->key = key;  
             new_node->next = *head;  
  
             *head = new_node;  
         }  
         else  
         {  
             free( new_node );  
         }  
     }  
  
     return success;  
 }  
  
 void clearList( struct node **head )  
 {  
     while ( *head != NULL )  
     {  
         struct node *tmp = *head;  
  
         *head = ( *head )->next;  
  
         free( tmp->data );  
         free( tmp );  
     }  
 }  
  
 void swap( struct node **current )  
 {  
     struct node *tmp = ( *current )->next->next;  
  
     ( *current )->next->next = *current;  
  
  
     *current = ( *current )->next;  
  
     ( *current )->next->next = tmp;  
 }  
  
 void bubbleSortList( struct node **head, int cmp( const void *left, const void *right ) )  
 {  
     if ( *head )  
     {  
         for ( struct node **first = head, *sorted = NULL, *last = sorted;  
               ( *first )->next != last;  
               last = sorted )  
         {  
             sorted = ( *first )->next; 
             for ( struct node **current = first; ( *current )->next != last; current = &( *current )->next )  
             {  
                 if ( cmp( current, &( *current )->next ) > 0 )  
                 {  
                     swap( current );  
  
                     sorted = ( *current )->next;  
                 }  
             }  
         }  
     }  
 }  
  
 int cmpByKey( const void *left, const void *right )  
 {  
     const struct node *a = *( const struct node ** )left;  
     const struct node *b = *( const struct node ** )right;  
  
     return ( b->key < a->key ) - ( a->key < b->key );  
 }  
  
 int cmpByData( const void *left, const void *right ) 
 { 
     const struct node *a = *( const struct node ** )left;  
     const struct node *b = *( const struct node ** )right;  
  
     return strcmp( a->data, b->data ); 
 } 
  
 int main( void )  
 {  
     struct node *head = NULL;  
  
     insertList( &head, 1, "Papatya" );  
     insertList( &head, 2, "DortKardes" );  
     insertList( &head, 3, "Toroslu" );  
     insertList( &head, 4, "PostEdu" );  
     insertList( &head, 5, "Adana" );  
  
     printList( &head );  
  
     putchar( '\n' );  
  
     bubbleSortList( &head, cmpByKey );  
  
     printList( &head );  
     putchar( '\n' );  
  
     bubbleSortList( &head, cmpByData );  
  
     printList( &head );  
     putchar( '\n' );  
  
     clearList( &head );  
 } 
 

Вывод программы на консоль будет следующим

 
 5 -> Adana 
 4 -> PostEdu 
 3 -> Toroslu 
 2 -> DortKardes 
 1 -> Papatya 
  
 1 -> Papatya 
 2 -> DortKardes 
 3 -> Toroslu 
 4 -> PostEdu 
 5 -> Adana 
  
 5 -> Adana 
 2 -> DortKardes 
 1 -> Papatya 
 4 -> PostEdu 
 3 -> Toroslu

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