Неделя 7 · Foundation

Структуры данных

На прошлой неделе мы изучили указатели. Теперь, используя их, мы будем умно организовывать данные. Группировка связанных данных с помощью struct, связанный список, стек и очередь — всё это мы увидим в живых диаграммах. Именно здесь раскрывается, почему указатели настолько важны.

Что вы узнаете на этом уроке

Поймёте, что такое структура данных и зачем она нужна

Объедините связанные поля в один тип с помощью struct

Увидите, как связанный список строится из узлов

Понаблюдаете, как соединяются указатели при добавлении узла в список

Поработаете со стеком (LIFO) и очередью (FIFO)

Выберете правильную структуру в зависимости от задачи

7.1 Что такое структура?

Под структурой данных (data structure) понимается способ удобно хранить данные и управлять ими. Одну мы уже знаем: массив. Но массив подходит не для всякой задачи.

Например, если вы хотите вставить элемент в середину массива, придётся сдвигать все остальные. Или размер массива задаётся заранее, и потом его непросто увеличить. Для разных задач лучше подходят разные структуры.

На этом уроке мы рассмотрим несколько: struct (группировка связанных данных), связанный список (легко растущий список), стек и очередь (списки с особым порядком). Большинство из них построены поверх указателей с прошлой недели.

Правильный выбор структуры может резко ускорить программу. Поэтому хороший программист не просто пишет код, но и тщательно продумывает, как хранить данные.

7.2 struct: группировка данных

У одного ученика есть имя, возраст и оценка. Их можно хранить в трёх отдельных переменных, но они связаны между собой. struct как раз объединяет эти связанные поля в один новый тип.

student.c

1struct Student {

2 char ism[20];

3 int yosh;

4 int baho;

5};

К полям мы обращаемся через точку: student.yosh. Введите значения ниже и посмотрите, как заполняется struct:

Конструктор struct заполните поля

ism yosh baho

7.3 Массив struct

struct, как и обычный тип, позволяет создать массив. struct Student sinf[3]; означает: полные данные трёх учеников в одном массиве. Теперь к каждому ученику мы обращаемся по индексу, а к каждому полю — через точку: sinf[1].baho.

Таблица ниже — это три struct учеников. Нажмите на строку и посмотрите, как к ней обращаться:

Массив struct нажмите на строку

#	ism	yosh	baho

Нажмите на любого ученика в таблице.

7.4 Связанный список

Теперь на помощь приходят указатели. Связанный список (linked list) состоит из узлов (node). Каждый узел хранит две вещи: своё значение и указатель на следующий узел. Так узлы соединяются в цепочку, а последний указывает на NULL (список закончился).

node.c

1struct Node {

2 int data; // значение

3 struct Node *next; // следующий узел

4};

На диаграмме ниже каждый прямоугольник — это один узел: слева значение, справа стрелка к следующему. Зелёная голова указывает на первый узел:

Связанный список узел

В каждом узле есть значение и стрелка на следующий узел. Последний указывает на NULL. А голова — это указатель на первый узел.

7.5 Добавление и удаление

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

Введите значение ниже и поработайте со списком. Новый узел вспыхивает зелёным:

Операции со списком добавляйте и удаляйте

значение:

7.6 Массив vs связанный список

Оба хранят данные последовательно, но у каждого есть сильные и слабые стороны. Выбор зависит от задачи:

Свойство	Массив	Связанный список
Обращение по индексу	быстро (`O(1)`)	медленно (проход с начала)
Добавление в начало	медленно (нужно сдвигать)	быстро (`O(1)`)
Размер	задан заранее	растёт динамически
Память	компактно	в каждом узле есть надбавка на указатель

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

7.7 Стек (LIFO)

Стек (stack) — это особый список, работающий только с одного конца. Добавление элемента называется push, удаление — pop, и оба происходят сверху. Правило: LIFO, то есть последний вошедший выходит первым. Как сложенные друг на друга тарелки.

Попробуйте ниже. Внимание: pop всегда берёт самый верхний:

Стек (push / pop) LIFO

вершина (top)

Сделайте прогноз

В пустой стек мы сделали push 1, затем 2, затем 3. Если потом сделать один pop, что выйдет?

1 (вошедший первым)

2 (средний)

3 (вошедший последним)

7.8 Очередь (FIFO)

Очередь (queue) похожа на стек, но с обратным правилом. Элемент добавляется с одного конца (enqueue), а берётся с другого (dequeue). Правило: FIFO, то есть первый вошедший выходит первым. Прямо как настоящая очередь в магазине.

Попробуйте ниже. Внимание: dequeue всегда берёт передний (вошедший первым):

Очередь (enqueue / dequeue) FIFO

7.9 Практика: какую структуру выбрать?

Выбор структуры зависит от характера задачи. Вот повседневные примеры:

Нужно быстрое обращение по индексу (например таблица): массив
Размер неизвестен, вы часто добавляете и удаляете: связанный список
Отмена последнего действия (кнопка «назад»): стек (LIFO)
Обслуживание по очереди (принтер, сообщения): очередь (FIFO)
Хранить вместе несколько связанных полей: struct

Во многих случаях структуры используются вместе. Например, связанный список из struct или массив struct. Как их комбинировать — зависит от мастерства программиста.

7.10 Глубже advanced

Кратко познакомимся ещё с двумя мощными структурами. Их глубокое изучение — для следующих этапов, а сейчас получим общее представление.

Хеш-таблица

Хеш-таблица (hash table) — одна из самых быстрых структур для поиска. Она с помощью специальной функции напрямую превращает ключ (например имя) в место в памяти. Поэтому поиск элемента занимает почти один шаг (O(1)). Идеальна для словаря или телефонной книги.

Дерево

Дерево (tree) — ветвящаяся иерархическая структура. Каждый узел может иметь несколько «дочерних» узлов. Используется для папок в файловой системе, семейного древа или быстрого поиска (binary tree). Оно тоже, по сути, построено поверх узлов и указателей.

Обратите внимание: почти все сложные структуры (список, дерево, хеш-таблица) строятся поверх идей, изученных на этом уроке: struct, указатели и связывание узлов. Именно поэтому основы так важны.

Словарь терминов

structобъединяет несколько связанных полей в один тип.

узел (node)элемент, хранящий значение и указатель на следующий.

связанный списокцепочка узлов, конец указывает на NULL.

стексписок LIFO: последний вошедший выходит первым.

очередьсписок FIFO: первый вошедший выходит первым.

хеш-таблицаструктура, ищущая по ключу почти за один шаг.

7.11 Тест знаний

16 вопросов. Чтобы завершить неделю, ответьте правильно как минимум на 11 из них.

Поздравляем! Неделя 7 завершена

Теперь вы умеете умно организовывать данные: вы познакомились со struct, связанным списком, стеком и очередью. Эти структуры лежат в сердце почти каждой серьёзной программы.

Следующая неделя: Рекурсия и файлы (функции, вызывающие сами себя, стек вызовов и работа с файлами).

Перейти к следующему модулю