Абстрактные типы данных

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


struct rational
{
    int p;
    int q;
};

Тогда атрибут p - это числитель, а q - знаменатель. В этом случае создание рационального числа в программе могло бы выглядеть так:


rational a = {1, 2};
rational b;
b.p = 5;
b.q = 6;
rational c;

Все три способа являются правильными с точки зрения компилятора (в данном примере используется GNU g++[1]). Но даже самый невнимательный читатель может заметить, что тут есть проблемы. Во-первых, в качестве числителя и знаменателя можно передавать любые значения, в том числе 0. Это, конечно, противоречит правилам работы с рациональными числами, так как 0 в числителе должен обнулять все число, а в знаменателе 0 недопустим. Во-вторых, и числитель, и знаменатель можно свободно менять уже после создания переменной, что чревато всеми проблемами, перечисленными выше. В-третьих, оба атрибута можно оставить без значений, что делает такую переменную бесполезной, а поведение программы, которая ее использует, непредсказуемым.

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


#include <assert.h>

rational cons(const int x, const int y)
{
    assert(y != 0);
    if (x == 0) return {0, 0};
    rational r;
    if (y < 0)
    {
        r.p = -x;
        r.q = -y;
    }
    else
    {
        r.p = x;
        r.q = y;
    }
    return r;
}
    
rational a = cons(1, 2);

Функция проверяет: числитель на нулевое значение (тогда вся дробь обнуляется), знаменатель на нулевое значение (тогда даже нет смысла продолжать, и работа программы прерывается, чуть ниже посмотрим на более элегантный способ справляться с этой ситуацией), знаменатель на отрицательное значение (тогда отрицание переносится на числитель). Конечно, те, кто более-менее разбирается в нюансах создания переменных в C, понимают, что эта функция никак не решает проблемы изменения значений числителя и знаменателя в последствии. В целом, “ограничения”, которые эта функция накладывает, довольно условны. Никак не запрещается создавать переменные такого типа без использования этой функции. Другими словами, она рассчитана на то, что разработчики будут руководствоваться здравым смыслом при работе с нашими рациональными числами. Тем не менее, компилятор позволяет установить более жесткие ограничения, которые полностью контролируют создание переменных и изменение атрибутов каждого создаваемого объекта типа rational. Чуть позже мы рассмотрим примеры такого подхода.

Тут интересно другое. Когда мы решили создать функцию, задача которой - заботиться о правильности создания рациональных чисел, мы абстрагировались от деталей реализации рациональных чисел в нашей программе. Как пользователям нам не очень интересно, что творится в самой структуре, нам интересно только то, как мы можем использовать объекты такого типа в наших программах. Аналогичные функции можно написать для всех операций, в которых наши объекты могут участвовать. Так получается “абстрактный тип данных” (не путать с “абстрактными типами”, о которых речь пойдет в других разделах). Еще раз стоит подчеркнуть, такой тип данных абстрагирует работу с данными (это не надо делать напрямую), которые хранятся в объектах такого типа, отсюда и название.

Упражнения

Абстрактные типы данных будут составлять основу большинства концепций, обсуждаемых в этом тексте, поэтому с ними нужно освоиться как можно быстрее. Для этого читателю предлагается дополнить тип данных, описанный выше, несколькими операциями. Во-первых, было бы неплохо поддерживать сокращенную форму всех создаваемых в программе рациональных чисел (т.е., при заданных числителе и знаменателе, которые кратны одному и тому же числу, делить их на это число по умолчанию: 5⁄10 превращать в 1⁄2, 9⁄6 - в 3⁄2). Во-вторых, было бы удобно отображать такие числа в текстовом виде как дроби, а не пару целых чисел.

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

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

Один из возможных вариантов решения может быть выполнен с помощью лямбда-выражения[2]. Такая функция определяет цифры, составляющие числитель и знаменатель, с помощью остатка от деления на 10 и записывает эти цифры в виде печатных символов в предоставленный для этого массив. Сами печатные символы получаются прибавлением ASCII-кода[3] символа “0” к числовому значению, что даст ASCII-код искомой цифры (так как все коды в таблице идут по порядку, начиная с нуля).

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

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

Во-вторых, функция возвращает строку, которая передается в нее изначально, что может показаться бесполезным. Причина состоит в том, что строки в С и С++ являются указателями, что подразумевает отсутствие процесса “конструирования” объекта внутри функции. Это значит, что данная функция не создает новых объектов, а только лишь дублирует адрес строки, в которой были произведены необходимые манипуляции с данными. Другими словами, можно считать, что у функции нет возвращаемого значения:


rational a = cons(10, 20);
reduce(a);
char tmp[100] {};
rstr(a, tmp)
assert(!strcmp("1/2", tmp));

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


char  tmp[100] {};
assert(!strcmp(“1/2”, rstr(a, tmp)));

То есть, результат работы этой функции можно передавать как аргумент в другие функции, ожидающие указатель на строку в качестве аргумента. Из этого следует, что в идеале наша функция должна возвращать не адрес той строки, которую мы в нее передали, а непосредственно символы, составляющие такую строку, которые можно скопировать в новую переменную типа char*: tmp = rstr(a);. В одной из следующих глав мы посмотрим как это можно сделать. Но самые сообразительные читатели уже, наверное, догадались, что это будет сделано с помощью абстрактного типа данных.


#include <assert.h>
#include <string.h>

int main(int argc, char const *argv[])
{
    rational a = cons(10, 20);
    assert(a.p == 10 && a.q == 20);

    reduce(a);
    assert(a.p == 1 && a.q == 2);

    char tmp1[100]{};
    assert(!strcmp("1/2", rstr(a, tmp1)));

    rational b = cons(100, 20);
    assert(b.p == 100 && b.q == 20);

    reduce(b);
    assert(b.p == 5 && b.q == 1);

    char tmp2[100]{};
    assert(!strcmp("5", rstr(b, tmp2)));

    rational c = cons(9, 6);
    assert(c.p == 9 && c.q == 6);

    reduce(c);
    assert(c.p == 3 && c.q == 2);

    char tmp3[100]{};
    assert(!strcmp("3/2", rstr(c, tmp3)));

    rational d = cons(12, 37);
    assert(d.p == 12 && d.q == 37);

    reduce(d);
    assert(d.p == 12 && d.q == 37);

    char tmp4[100]{};
    assert(!strcmp("12/37", rstr(d, tmp4)));
}

Сноски

^*Действительное число, которое можно представить как пару целых чисел, записанных одно над другим через прочерк, в виде дроби.

Источники

GCC, the GNU Compiler Collection, gcc.gnu.org
“Лямбда-исчисление”, Вики-конспекты, Университет ИТМО, neerc.ifmo.ru/wiki/
“ISO-IR-6: ASCII Graphic Character Set”, ANSI, 1975.