On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 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

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

Спасибо: 0 
ПрофильЦитата Ответить
Новых ответов нет


Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 31
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет