Форум » C/C++ для начинающих (C/C++ for beginners) » -Сортировка односвязного списка с помощью метода пузырьковой сортировки на C. » Ответить
-Сортировка односвязного списка с помощью метода пузырьковой сортировки на C.
Сыроежка: Хорошими упражнениями на выработку понимания работы с указателями являются задания по построению различных списков (односвязных, двусвязных, двухсторонних и.т.д.) и по выполнению операций с ними. Одно из таких заданий можно найти на сайте Stackoverflow по ссылке char (contain words) array buble sort problem (c) Требуется создать односвязный список и выполнить его сортировку с помощью метода пузырьковой сортировки. Как показала тема Как выполнить инверсию отдельных слов в объекте класса std::string в этом разделе форума, такое задание может оказаться не по зубам даже программистам со стажем. Сначала отметим некоторые существенные недостатки кода, представленного в исходном вопросе на сайте Stackoverflow. Начнем с того, что согласно стандарту C функция main без параметров должна быть объявлена как [pre2] int main( void ) [/pre2] В исходном вопросе она объявляется как [pre2] void main()[/pre2] Второе важное замечание касается того, что в программе объявляется глобальная переменная на начало списка. В связи с этим все функции, объявленные в этой программе, имеют дело с этой глобальной переменной и, соответственно, не могут работать с другими списками в программе. То есть, фактически, код не является переносимым. Член структуры с именем data имеет неверный тип char вместо типа char *. Но даже если этот член структуры имел бы правильный тип char * ( или const char *), тем не менее для хранения данных необходимо выделять динамически память под строки. Нельзя просто хранить указатели на строковые литералы, так как в общем случае пользователь может в качестве данных передать не строковый литерал. В этом случае программа будет иметь неопределенное поведение, если строки не имеют статическую память. Для метода пузырьковой сортировки при работе с односвязным списком совершенно нет никакой необходимости знать число элементов в списке. Например, в C++ стандартный класс std::forward_list не имеет такого метода, который возвращает число элементов в односвязном списке. Такой метод не эффективный и имеет сложность O( n ). Кроме того автор вопроса в функции, выполняющей сортировку, обменивает значения членов узла списка вместо того, чтобы обменивать сами узлы. Почему требуется обменивать сами узлы? Потому что в общем случае в программе могут быть переменные, которые ссылаются на узлы списка. После обмена значений узлов списка такие переменные будут ссылаться на переписанные узлы, а не на узлы с исходными значениями. Итак, имеется структура вида [pre2] struct node { char *data; unsigned int key; struct node *next; }; [/pre2] Требуется создать на ее основе список и выполнить его сортировку методом пузырьковой сортировки. Как известно, этот метод основывается на перестановки смежных элементов последовательности. Поэтому самое сложное, что требуется в задании, это написать корректно перестановку смежных узлов списка. Как может выглядеть соответствующая функция? Она может выглядеть следующим образом [pre2] void swap( struct node **current ) { struct node *tmp = ( *current )->next->next; ( *current )->next->next = *current; *current = ( *current )->next; ( *current )->next->next = tmp; } [/pre2] Эта функция низкого уровня, а потому она не делает проверку на то, является ли указатель на следующий узел, то есть ( *current )->next, равным NULL. Это задача клиента функции выполнить такую проверку перед вызовом функции. Именно написание этой функция вызывает наибольшую трудность у начинающих и, порой, программистов со стажем. Теперь, имея данную функцию, не сложно написать функцию сортировки. Отметим, что функция сортировки должна принимать в качестве параметра функцию сравнения, с помощью которой можно производить сортировку по любому полю односвязного списка. В ниже приведенной программе сначала созданный список сортируется по значению члена структуры key, а затем по значению поля структуры data. Важно также не забыть удалить список, когда он больше не требуется в программе. [pre2] #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 ); } [/pre2] Вывод программы на консоль будет следующим [pre2] 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[/pre2] Ради любопытства попросите своих коллег выполнить данное задание и посмотрите, что они вам предоставят в результате. Я уверен, что многие не справятся с заданием, или представленный код будет страдать многими недостатками или багами.
Ответов - 0
полная версия страницы