Основные понятия структур данных

Прежде чем приступить к формальному изучению различных структур данных, вам необходимо освоить методы классификации структур данных, понятие абстрактных типов данных и повторить ключевые моменты языка C, тесно связанные со структурами данных.


Классификация структур данных

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

数据结构分类全景图

На рисунке выше показана полная система классификации структур данных, которая поясняется ниже по порядку.

Классификация по логической структуре

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

TypeСвязь элементовТипичный примерПрименимый сценарий
Линейная структураПоследовательная связь «один к одному»Массивы, связные списки, стеки, очередиДанные имеют очевидный порядок, например списки дел и история просмотров
Древовидная структураИерархическое отношение «один ко многим»Бинарные деревья, BST, кучиДанные имеют иерархическую принадлежность, например каталоги файловой системы и организационные структуры
Графовая структураСетевое отношение «многие ко многим»Ориентированные графы, неориентированные графы, взвешенные графыСвязи между данными сложны, например социальные сети и навигация по картам

Классификация по способу хранения

Способ хранения описывает фактическую организацию данных в памяти.

TypeХарактеристикиТипичный примерКомпромисс
Последовательное хранениеЭлементы хранятся один за другим в непрерывном пространстве памятиМассивы, стеки/очереди, реализованные на массивахБыстрый доступ (O(1)), но медленная вставка и удаление, фиксированный размер
Связное хранениеЭлементы могут храниться вразброс и соединяться с помощью указателейСвязные списки, деревья, графы (список смежности)Быстрая вставка и удаление, но не поддерживается произвольный доступ, дополнительные накладные расходы на указатели
Индексное хранениеСоздание дополнительной индексной таблицы для поиска данныхХеш-таблицы (индексируются с помощью хеш-функций)Чрезвычайно быстрый поиск, но требует дополнительного пространства для хранения индексной структуры

Одну и ту же логическую структуру можно реализовать разными способами хранения. Например, стек (логически линейная структура) можно реализовать либо с помощью массива (последовательное хранение), либо с помощью связного списка (связное хранение). От конкретных требований приложения к скорости доступа, эффективности вставки/удаления и использованию памяти зависит, какая реализация будет выбрана.


Абстрактный тип данных (АТД)

Абстрактный тип данных (АТД)— ключевое понятие в изучении структур данных.

Он означает абстрактное описание набора данных и набора операций, определённых над этими данными, при этом важно только «что делать», а не «как это делать».

Рассмотрим «стек» как пример для понимания АТД:

Уровень АТД (что делать)Уровень реализации (как это делать)
Определить операции: push, pop, peekРеализовать с помощью массива: поддерживать массив + указатель top
Определите поведение: последним вошёл — первым вышел (LIFO)Реализуйте с помощью связанного списка: используйте голову связанного списка как вершину стека
Задайте ограничения: операции можно выполнять только на одном концеОбе реализации удовлетворяют определению АТД, но имеют разные характеристики производительности

Эта идея "разделения интерфейса и реализации" — краеугольный камень модульного проектирования в современной программной инженерии.

Когда вы используете стек, вам нужно знать только, как использовать такие операции, как push и pop, и не нужно заботиться о том, является ли базовая реализация массивом или связанным списком — в этом и заключается ценность АТД.


Повторение основ языка C

Прежде чем изучать структуры данных, вам нужно освоить следующие три ключевых понятия языка C, которые встречаются почти во всех главах этого руководства.

Указатель

Указатель — одна из самых важных и гибких возможностей языка C. Он хранит адрес памяти другой переменной, позволяя косвенно обращаться к целевой переменной и манипулировать ею.

Пример

#include <stdio.h>

int main() {
    int num = 42;        /* обычная целочисленная переменная */
    int *ptr = &num;   /* 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 <stdio.h>
#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 <stdio.h>
#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.

Другие расширения