Язык программирования C++ для профессионалов
является стандартной библиотечной функцией, преобразующей
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() - для получения следующего элемента:
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий