Язык программирования C++ для профессионалов



           

Законченный пример класса - часть 2


extern "C" int atoi(const char*)

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

extern "C" int rand(); // будьте осторожны: // числа не совсем случайные int randint(int u) // диапазон 1..u { int r = rand(); if (r < 0) r = -r; return 1 + r%u; }

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

intset::intset(int m, int n) // не более m целых в 1..n { if (m<1 || n<m) error("недопустимый размер intset"); cursize = 0; maxsize = m; x = new int[maxsize]; }

intset::~intset() { delete x; }

Целые добавляются таким образом, что они хранятся во множестве в возрастающем порядке:

void intset::insert(int t) { if (++cursize > maxsize) error("слишком много элементов"); int i = cursize-1; x[i] = t;

while (i>0 && x[i-1]>x[i]) { int t = x[i]; // поменять местами x[i] и x[i-1] x[i] = x[i-1]; x[i-1] = t; i--; } }

Чтобы найти элемент, используется простой двоичный поиск:

int intset::member(int t) const // двоичный поиск { int l = 0; int u = cursize-1;

while (l <= u) { int m = (l+u)/2; if (t < x[m]) u = m-1; else if (t > x[m]) l = m+1; else return 1; // найден } return 0; // не найден }

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

Пользователь получает три функции: start() - для инициализации итерации, ok() - для проверки, есть ли следующий элемент, и next() - для получения следующего элемента:




Содержание  Назад  Вперед