Основные понятия структур данных
Прежде чем приступить к формальному изучению различных структур данных, вам необходимо освоить методы классификации структур данных, понятие абстрактных типов данных и повторить ключевые моменты языка C, тесно связанные со структурами данных.
Классификация структур данных
Структуры данных можно классифицировать по двум измерениям: логическая структура и способ хранения. Понимание этих двух способов классификации помогает быстро определить, какой тип структуры данных следует выбрать при решении конкретных задач.
На рисунке выше показана полная система классификации структур данных, которая поясняется ниже по порядку.
Классификация по логической структуре
Логическая структура описывает абстрактные отношения между элементами данных, не затрагивая фактический способ хранения данных в памяти.
| Type | Связь элементов | Типичный пример | Применимый сценарий |
|---|---|---|---|
| Линейная структура | Последовательная связь «один к одному» | Массивы, связные списки, стеки, очереди | Данные имеют очевидный порядок, например списки дел и история просмотров |
| Древовидная структура | Иерархическое отношение «один ко многим» | Бинарные деревья, BST, кучи | Данные имеют иерархическую принадлежность, например каталоги файловой системы и организационные структуры |
| Графовая структура | Сетевое отношение «многие ко многим» | Ориентированные графы, неориентированные графы, взвешенные графы | Связи между данными сложны, например социальные сети и навигация по картам |
Классификация по способу хранения
Способ хранения описывает фактическую организацию данных в памяти.
| Type | Характеристики | Типичный пример | Компромисс |
|---|---|---|---|
| Последовательное хранение | Элементы хранятся один за другим в непрерывном пространстве памяти | Массивы, стеки/очереди, реализованные на массивах | Быстрый доступ (O(1)), но медленная вставка и удаление, фиксированный размер |
| Связное хранение | Элементы могут храниться вразброс и соединяться с помощью указателей | Связные списки, деревья, графы (список смежности) | Быстрая вставка и удаление, но не поддерживается произвольный доступ, дополнительные накладные расходы на указатели |
| Индексное хранение | Создание дополнительной индексной таблицы для поиска данных | Хеш-таблицы (индексируются с помощью хеш-функций) | Чрезвычайно быстрый поиск, но требует дополнительного пространства для хранения индексной структуры |
Одну и ту же логическую структуру можно реализовать разными способами хранения. Например, стек (логически линейная структура) можно реализовать либо с помощью массива (последовательное хранение), либо с помощью связного списка (связное хранение). От конкретных требований приложения к скорости доступа, эффективности вставки/удаления и использованию памяти зависит, какая реализация будет выбрана.
Абстрактный тип данных (АТД)
Абстрактный тип данных (АТД)— ключевое понятие в изучении структур данных.
Он означает абстрактное описание набора данных и набора операций, определённых над этими данными, при этом важно только «что делать», а не «как это делать».
Рассмотрим «стек» как пример для понимания АТД:
| Уровень АТД (что делать) | Уровень реализации (как это делать) |
|---|---|
| Определить операции: push, pop, peek | Реализовать с помощью массива: поддерживать массив + указатель top |
| Определите поведение: последним вошёл — первым вышел (LIFO) | Реализуйте с помощью связанного списка: используйте голову связанного списка как вершину стека |
| Задайте ограничения: операции можно выполнять только на одном конце | Обе реализации удовлетворяют определению АТД, но имеют разные характеристики производительности |
Эта идея "разделения интерфейса и реализации" — краеугольный камень модульного проектирования в современной программной инженерии.
Когда вы используете стек, вам нужно знать только, как использовать такие операции, как push и pop, и не нужно заботиться о том, является ли базовая реализация массивом или связанным списком — в этом и заключается ценность АТД.
Повторение основ языка C
Прежде чем изучать структуры данных, вам нужно освоить следующие три ключевых понятия языка C, которые встречаются почти во всех главах этого руководства.
Указатель
Указатель — одна из самых важных и гибких возможностей языка C. Он хранит адрес памяти другой переменной, позволяя косвенно обращаться к целевой переменной и манипулировать ею.
Пример
int main() {
int num = 42; /* обычная целочисленная переменная */
int *ptr = # /* ptr — указатель на int, хранящий адрес num */
printf("значение num: %d\n", num); /* Вывод: 42 */
printf("адрес num: %p\n", &num); /* Вывод: 0x16d2f2f38 (пример адреса) */
printf("адрес, хранящийся в ptr: %p\n", ptr); /* Вывод: такой же, как выше */
printf("значение, разыменованное через *ptr: %d\n", *ptr); /* Вывод: 42, * — оператор разыменования */
*ptr = 100; /* Изменить значение num через указатель */
printf("после изменения, num = %d\n", num); /* Вывод: 100 */
return 0;
}
Основные применения указателей в структурах данных:
| Используйте | Пример |
|---|---|
| Устанавливать связи между динамическими узлами | В узлах связного списка,nextуказатели; в узлах дерева,left/rightуказатели |
| Косвенно получать доступ к данным и изменять их | Используйте параметры-указатели, чтобы функции могли изменять значения внешних переменных |
| Динамическое управление памятью | mallocВозвращает начальный адрес выделенной памяти, который должен быть получен с помощью указателя |
| Избегание копирования больших объёмов данных | При передаче больших структур в функции передача указателей эффективнее, чем передача по значению |
Что начинающие чаще всего путают — это
*и&использование * и &: в объявлениях,int *p* указывает, что p имеет тип указателя; при использовании,*p* обозначает разыменование (получение значения);&x& обозначает взятие адреса. Это два совершенно разных оператора, и понимание этой разницы — предпосылка для умелого использования указателей.
Структура (struct)
Структура позволяет объединять несколько элементов данных разных типов в пользовательский тип и является базовой единицей для построения составных структур данных, таких как узлы связного списка и узлы дерева.
Пример
#include <string.h> /* заголовочный файл для strcpy */
/* Определение структуры узла связного списка */
struct Node {
int data; /* Поле данных: хранит фактические данные */
struct Node* next; /* Поле указателя: указывает на следующий узел */
};
/* Определение структуры информации о студенте */
struct Student {
int id; /* Идентификатор студента */
char name[50]; /* Имя, массив символов */
float score; /* Балл */
};
int main() {
/* Создать узел */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL означает, что следующего узла сейчас нет */
printf("node1.data = %d\n", node1.data); /* Вывод: 10 */
/* Создать запись студента */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "EXAMPLE"); /* strcpy: копирует строку в массив символов */
stu.score = 95.5;
printf("ID: %d, Name: %s, Score: %.1f\n",
stu.id, stu.name, stu.score);
/* Вывод: ID: 1001, Name: EXAMPLE, Score: 95.5 */
return 0;
}
Структуры в сочетании с указателями позволяют создавать гибкие динамические структуры данных. Например, самоссылающаяся структура узла связного списка (struct Node* nextуказывает на следующий узел того же типа) — это именно основа реализации связных списков.
Динамическое распределение памяти
Динамическое распределение памяти позволяет программе запрашивать и освобождать память в куче во время выполнения по мере необходимости и является ключом к созданию структур данных переменного размера (таких как связанные списки и деревья).
C предоставляет четыре основные функции:
| Функция | Функциональность | Пример |
|---|---|---|
| malloc | Выделяет память указанного размера в байтах, содержимое не инициализировано | int* p = malloc(10 * sizeof(int)); |
| calloc | Выделяет память и инициализирует её нулями | int* p = calloc(10, sizeof(int)); |
| realloc | Изменяет размер уже выделенной памяти | p = realloc(p, 20 * sizeof(int)); |
| free | Освобождает выделенную память и возвращает её системе | free(p); |
Пример
#include <stdlib.h> /* заголовочный файл для malloc, free */
int main() {
int n = 5;
/* malloc: выделить непрерывную область для n int в куче */
int* arr = (int*)malloc(n * sizeof(int));
/* Проверить, успешно ли выделение памяти; malloc возвращает NULL при ошибке */
if (arr == NULL) {
printf("Ошибка выделения памяти!"\n");
return 1; /* Аварийный выход */
}
/* Использовать динамически выделенную память как обычный массив */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* Присвоить: 10, 20, 30, 40, 50 */
}
printf("Содержимое динамического массива: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Вывод: Содержимое динамического массива: 10 20 30 40 50 */
free(arr); /* Освободить память, чтобы предотвратить утечки памяти */
arr = NULL; /* Хорошая практика: установите указатель в NULL, чтобы предотвратить дикие указатели */
return 0;
}
Другие расширенияЯзык C не освобождает автоматически динамически выделенную память. Каждый раз
malloc(илиcalloc) должен иметь соответствующийfree, иначе это приведёт к утечкам памяти. В реальных проектах утечки памяти постепенно исчерпывают системные ресурсы и в конечном итоге приводят к сбою программы. Это одна из самых распространённых ошибок начинающих программистов на C.