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

Структуры одного типа можно объединять не только в массивы. Их можно связывать между собой, создавая так называемые динамические структуры данных. Связь между отдельными структурами может быть организована по-разному, и именно поэтому среди динамических данных выделяют списки, стеки, очереди, деревья, графы и др. Мы не будем рассматривать каждый тип. Цель этого урока — понять, что такое динамические данные, и как они создаются на языке программирования C.

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

Тут появляется проблема. Для динамических типов данных не объявляются переменные, иначе память бы выделялась под переменные. Как тогда обращаться к данным, записанным неизвестно где в памяти? Можно ввести переменные-указатели и при выделении памяти записывать адрес этой памяти в указатели. Но мы же не знаем, сколько памяти потребуется в процессе выполнения. Сколько вводить указателей?

Проблема решается путем использования структур. Допустим, мы пишем программу, позволяющую вводить данные на сотрудников организации. Количество сотрудников неизвестно. Можно было бы создать массив записей с запасом. Однако, если данных о каждом сотруднике много, то каждая запись занимает много памяти; получается, что мы будем расходовать много памяти в пустую, если сотрудников мало.

Идея заключается примерно в следующем:

  1. В программе определяем структурный тип данных с "кое-какой изюминкой" и создаем переменную указатель на него. В итоге при запуске программы память выделяется только под указатель.
  2. В процессе выполнения программы, в случае возникновения необходимости в создании структуры, с помощью специальной функции выделяем память под хранение данных (полей структуры).
  3. Присваиваем указателю адрес, по которому расположена только что созданная структура.
  4. Когда поступает команда на создание следующей структуры, снова с помощью функции выделяется память, а указателю присваивается адрес этой новой структуры.
  5. "Изюминка" определенного ранее структурного типа данных заключается в том, что одним из его полей является указатель на структуру этого же типа.
  6. В это поле-указатель записывается адрес на структуру, которая была создана перед данной структурой.

Таким образом получается цепочка взаимосвязанных структур. Самая первая созданная структура не имеет ссылки на другую структуру. Ее поле-указатель имеет значение NULL. Вторая созданная структура ссылается на первую, третья на вторую и т.д. Адрес последней созданной структуры хранится в переменной-указателе, которая была объявлена в программе программистом.

Чтобы извлечь данные из такого агломерата данных, надо пройтись по ссылкам начиная с переменной-указателя. Т.е. первой мы извлечем последнюю записанную структуру. Потом предпоследнюю и постепенно будем двигаться к структуре, которая была создана первой во времени. Такой динамический тип данных называется стеком. Объекты извлекаются из стека таким образом, что первым выбирается тот, который был помещен последним.

Стек — это не единственный способ организации динамических данных, но наиболее простой.

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

В языке программирования C выделение памяти в процессе выполнения программы можно организовать с помощью функций malloc() и calloc(), освобождение памяти с помощью free(). Объявление этих функций находится в заголовочных файлах stdlib.h и malloc.h. К исходному коду можно подключить любой из них.

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

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

Рассмотрим программу:

#include <stdio.h>
#include <stdlib.h>
#define N 3
 
struct person {
    char name[10];
    char lastname[15];
    struct person *before;
};
 
int main() {
    struct person *head, *p;
    head = NULL;
 
    for (int i = 0; i < N; i++) {
        p = (struct person *) malloc(sizeof(struct person));
        scanf("%s %s", p->name, p->lastname);        
        p->before = head;
        head = p;
    }
 
    printf("\n");
    for (int i = 0; i < N; i++) {
        printf("%s %s\n", p->name, p->lastname);
        p = p->before;
    }
 
    while (head != NULL) {
        p = head->before;
        free(head);
        head = p;
    }
    printf("\n%p %p\n", p, head);
}

В ней создается структурный тип данных person, объявляется два указателя на структуру такого типа и одному из них присваивается NULL.

В цикле for выделяется память размером со структуру, приводится к соответствующему типу, и указатель на эту область памяти присваивается переменной p. Далее в память записываются значения двух полей структуры.

Третьему полю присваивается то, что содержится в указателе head (на первой итерации это NULL), а сам он начинает указывать на область только что выделенной памяти.

После первого цикла указатели head и p указывают на одну и ту же область памяти. Во втором цикле при последовательном прохождении по элементам стека мы пользуемся одним указателем, а в другом сохраняется ссылка на последнюю добавленную структуру.

В цикле while происходит освобождение памяти. Первой удаляется структура, которая была добавлена последней. Перед этим мы сохраняем значение ее поля before, чтобы знать какой участок памяти надо будет высвобождать при следующем проходе цикла.

Пример выполнения программы:

Tom Box
Alice Circle
John Brown        

John Brown
Alice Circle
Tom Box

(nil) (nil)

Рассмотрим более сложный вариант. Здесь каждая структура создается с помощью вызова функции. Также отдельная функция предусмотрена для вывода стека на экран:

#include <stdio.h>
#include <stdlib.h>
 
struct stack {
    int data;
    struct stack *before;
};
 
/* присоединение элемента к голове, возврат адреса головы */
struct stack *create(struct stack *, int); 
 
void list(struct stack *); // просмотр стека
 
int 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);
}
 
struct stack *create(struct stack *head, int x) {
 
    struct stack *element; // указатель на новую структуру
 
     // выделяем память
    element = (struct stack *)malloc(sizeof(struct stack));
    element->before = head;
    element->data = x;
    return element;
}
 
void list(struct stack *p) {    
    while (p != NULL) {  // пока не конец стека   
      printf("%d-->", p->data);
      p = p->before; // продвижение по списку
    }
    printf("\n");
}

В процессе выполнения эта программа запрашивает целое число и сначала выводит числа от 0 до указанного числа, а затем выводит их же в обратном порядке — от указанного число до нуля:

40
0<--5<--10<--15<--20<--25<--30<--35<--40<--
40-->35-->30-->25-->20-->15-->10-->5-->0-->

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

Курс с решением задач:
pdf-версия


Основы языка C. Курс

Все разделы сайта