Хорошими упражнениями на выработку понимания работы с указателями являются задания по построению различных списков (односвязных, двусвязных, двухсторонних и.т.д.) и по выполнению операций с ними.
Одно из таких заданий можно найти на сайте
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
Ради любопытства попросите своих коллег выполнить данное задание и посмотрите, что они вам предоставят в результате. Я уверен, что многие не справятся с заданием, или представленный код будет страдать многими недостатками или багами.