Попробуем реализовать набор самостоятельно. Начнем мы с простейшей структуры — массива. Количество элементов набора будет храниться в переменной п нашего класса, а сами числа — в массиве х.
р г 1vate- int n, *х;
Полный текст реализации всех классов приводится в приложении 5. Приведенная в листинге версия конструктора на псевдокоде выделяет памяти под массив (с одним добавочным элементом-маркером) и устанавливает количество элементов равным нулю.
Листинг 13.5. Конструктор класса IntSetArray
IntSetArray(maxelements, maxval) x = new lnt[1 + maxelements] n = 0
x[0] = maxval
Поскольку нам необходимо возвращать элементы в порядке возрастания, мы будем все время поддерживать этот порядок их хранения (в некоторых других приложениях выгодней использовать неотсортированные массивы). В конце множества упорядоченных элементов мы будем хранить элемент-маркер со значением maxval, превышающим любое возможное значение элементов набора. Теперь проверку на достижение конца списка можно будет заменить на проверку наличия большего элемента (которая нам и так нужна). Это упростит и ускорит код функции вставки элемента, приведенный в листинге 13.6.
void insert(t)
for (i = 0. х[i] < t, i + + )
if x[i] == t retu rn
for (j “ n. j >= i : j--) x[j + 13 = X[J3 x [ i 3 = t a+ +
В первом цикле просматриваются элементы массива меньше значения вставляемого элемента t. Если такой элемент уже есть, можно немедленно выходить из функции. В противном случае мы сдвигаем элементы, большие данного, вправо на одну позицию (эта процедура применяется и к маркеру), вставляем элемент t в освободившуюся позицию и увеличиваем п на единицу. Эта функция выполняется за время О(п).
Функция size во всех наших реализациях будет выглядеть одинаково.
Листинг 13.7. Функция size
int s i ze() return n.
Функция report копирует все элементы, за исключением маркера, в выходной массив за время 0(п).
Листинг 13.8. Функция report в реализации IntSetArray
void report(v) for i = [0, n) v [ 13 - x С13
Массивы отлично подходят для реализации наборов, когда количество элементов известно заранее. Поскольку массив изначально упорядочен, для определения принадлежности элемента набору можно использовать двоичный поиск, работающий за время 0(log п). Дополнительные сведения о времени работы этой программы вы найдете в конце раздела.
Если размер набора заранее неизвестен, для его представления лучше всего использовать связные списки (рис. 13.1). При этом не требуется тратить время на сдвиг элементов при добавлении нового.
Опубликовал vovan666
April 17 2013 00:03:20 ·
0 Комментариев ·
3475 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
