Динамические структуры данных в C

Структуры одинакового типа можно не только группировать в массивы, но и связывать их между собой, создавая так называемые динамические структуры данных. Такие связи можно организовать по-разному, что позволяет выделять среди динамических структур списки, стеки, очереди, деревья, графы и другие. Обзор всех типов мы делать не будем. Наша цель на этом уроке — понять концепцию динамических данных и способы их создания в языке программирования C.

Динамическим данным память выделяется непосредственно в процессе выполнения программы, а не на этапе ее запуска. Например, при объявлении массива на 100 элементов, система сразу резервирует память для всех ста, даже если по ходу работы программы потребуется лишь 10. С динамическими же структурами, память выделяется по мере необходимости — специальная функция выделяет пространство по мере поступления новых данных.

Но возникает другая сложность. Как управлять такими данными, когда их местоположение заранее неизвестно? Переменные для динамических структур не объявляются, так как это сразу бы резервировало память. Очевидным решением кажется использование указателей: выделяя память, мы записываем ее адрес в указатель. Но сколько таких указателей нужно вводить, не зная объема требуемой памяти?

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

Подход следующий:

1. В программе задается структура с особенностью — она включает указатель на структуру своего типа. Создаем указатель на нее, и при запуске программы память выделяется только для этого указателя.
2. По необходимости, в процессе выполнения программы, выделяем память для новой структуры с помощью специальной функции.
3. Указателю присваивается адрес новой структуры.
4. Снова вызываем функцию для новой структуры, и обновляем указатель ее адресом.
5. Особенность структурного типа в том, что одно из его полей — указатель на такую же структуру.
6. Этот указатель хранит адрес предыдущей созданной структуры.

Так формируется цепочка связанных структур. Первая структура не ссылается ни на какую другую, и ее указатель равен NULL. Вторая ссылается на первую, и так далее. Главный указатель хранится в переменной, заданной программистом.

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

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

В C выделять память динамически можно через malloc() и calloc(), а освобождать — через free(). Эти функции содержатся в stdlib.h и malloc.h, которые можно подключить к коду.

Функция malloc() формирует указатель на выделенную память согласно запрашиваемому объему. Если память доступна, она возвращает ее адрес. Указатель необходимо привести к требуемому типу.

Функция free() освобождает память по переданному адресу.

#include <stdio.h>
#include <stdlib.h>
 
struct stack {
       int data;
       struct stack *next;
};
 
struct stack *create(struct stack *, int); // добавление элемента к головному элементу, возвращение адреса головного элемента
void list(struct stack *); // просмотр состава стека
 
main() {
       int i, n;
       struct stack *head; // указатель на головной элемент стека
       head = NULL;
 
       scanf("%d", &n);
       for (i=0; i <= n; i+=5) {
           head = create(head,i);
           printf("%d<--", head->data);
       }
       printf("\n");
       list(head);
       free(head);
}
 
struct stack *create(struct stack *head, int x) {
       struct stack *element; // новый указатель на структуру
       element = (struct stack *)malloc(sizeof(struct stack)); // резервирование памяти
       element->next = head;
       element->data = x;
       return element;
}
 
void list(struct stack *p){
     while (p != NULL) { // до конца стека
           printf("%d-->", p->data);
           p = p->next; // перемещение по списку
     }
     printf("\n");
}

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

60
0<--5<--10<--15<--20<--25<--30<--35<--40<--45<--50<--55<--60<--
60-->55-->50-->45-->40-->35-->30-->25-->20-->15-->10-->5-->0-->

Почему это так?

1. Задается тип данных struct stack с полем-указателем, указывающим на эту же структуру.
2. В main() создается головной указатель на struct stack и изначально инициализируется как NULL.
3. В цикле несколько раз вызывается create(), передающая текущее значение указателя (адрес) и число.
4. В create() создается новый указатель (element) на struct stack.
5. С помощью malloc() выделяется память для одной структуры. Объем определяется с помощью sizeof(). Возвращаемый malloc() указатель преобразуется к struct stack.
6. Выделенной памяти присваивается элемент element.
7. В поле next новой структуры записывается адрес из аргумента, переданного функции. При первом вызове это NULL, в дальнейшем — адрес предыдущей структуры.
8. В поле data заносится существенное для программы число.
9. Возвращается указатель на новую память с новой структурой. Это значение присваивается head, который всегда указывает на последнюю структуру.
10. На экран выводится значение элемента data из текущей структуры, на которую указывает head.
11. Функция list() позволяет просматривать стек с последнего добавленного элемента. При вызове head копируется в переменную p. Изменения p внутри list() не затрагивают head в функции main().
12. В p = p->next сначала извлекается значение из next, что дает адрес предыдущей структуры. Этот адрес передается p. Так p движется по стеку от последних элементов к первым. Поле next первой структуры содержит NULL, что завершает цикл.
13. В конце освобождается память с помощью free() по адресу указателя head. Но не вся память, а только последней структуры.

Основное преимущество заключается в динамическом выделении памяти под необходимое количество структур. Минус — расходы на указатели. Если в структуре только одно значимое поле, такие затраты, возможно, излишни. В таком случае оправдано создание массива с запасом. Но для сложных структур такой подход несомненно выгоден.