Уровни описания структур данных: от математики до байтов

Модуль "Объекты и ссылки" • урок 4 из 7 • ~7 минут

Для чего введены уровни описания структур данных

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

Три уровня

1. Функциональная спецификация - внешнее, формальное математическое определение типа: множество возможных значений, допустимые операции и отношения. Ни слова о языке программирования или машине. Пример: вектор - упорядоченный набор элементов с операциями доступа по индексу.
2. Логическое описание - отображение спецификации на средства выбранного языка. Есть в языке готовый подходящий тип (int, массив) - используем его; нет - конструируем свой из базовых (struct в C).
3. Физическое представление - конкретное размещение данных в оперативной памяти. Два основных вида:
   • Сплошное (непрерывное) - данные лежат друг за другом одним блоком. Адрес элемента вычисляется по формуле, доступ - O(1). Подходит, когда размер известен заранее (массивы).
   • Цепное (связное) - данные разбиты на части, разбросанные по памяти и связанные указателями. Размер меняется легко, но доступ медленнее (списки, деревья).

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

Пример: "Сотрудник" двумя способами

Логическое описание - конструируем тип из базовых через struct; физическое представление - на выбор, сплошное или цепное:

#include <stdlib.h>

/* Логическое описание: новый тип из базовых */
typedef struct {
    int id;
    double salary;
} Employee;

int main(void) {
    /* Физическое СПЛОШНОЕ представление:
       100 сотрудников лежат в памяти подряд */
    Employee array[100];
    array[0].id = 1;
    array[0].salary = 50000.0;

    /* Физическое ЦЕПНОЕ представление:
       узлы разбросаны по куче и связаны указателями */
    typedef struct Node {
        Employee data;
        struct Node* next; /* ссылка на следующий узел */
    } Node;

    Node* head = (Node*)malloc(sizeof(Node));
    head->data.id = 2;
    head->data.salary = 60000.0;
    head->next = NULL;

    free(head);
    return 0;
}