Списки общего вида. Примеры: ортосписки

Модуль "Линейные списки" • урок 6 из 9 • ~7 минут

Списки общего вида. Примеры: что это такое

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

К таким структурам относятся ортосписки (ортогональные списки) и суперсписки.

Разреженные матрицы (Ортосписки)

Одной из практически значимых разновидностей являются разреженные матрицы. Это огромные двумерные таблицы, где подавляющее большинство элементов равны нулю. Хранить их в виде обычного двумерного массива (например, int A[10000][10000]) крайне неэффективно по памяти.

Вместо этого используется структура ортосписка:

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

Получается "ортогональная" сеть указателей, которая хранит только полезные (ненулевые) данные, игнорируя пустоты.

Реализация на C (Объединения)

Так как элемент списка общего вида может быть либо значением (атомом), либо указателем на вложенный подсписок, для реализации такого узла на C обычно применяется объединение (union) вместе с флагом типа:

typedef enum { ATOM, SUBLIST } NodeType;

typedef struct ListNode {
    NodeType type;            /* Флаг: что хранится в данном узле? */
    union {
        int data;             /* Если это ATOM, храним данные */
        struct ListNode* sub; /* Если SUBLIST - указатель на подсписок */
    } value;
    struct ListNode* next;    /* Указатель на следующий элемент на текущем уровне */
} ListNode;

Благодаря union узел занимает в памяти ровно столько места, сколько требуется большему из полей data или sub, избегая лишних затрат.