void report(int *v)
J * 0
for (p = head, p != sentinel, p = p -> next) v[j + + l = p-> v a 1
Чтобы вставить элемент в упорядоченный связанный список, мы перебираем его элементы до тех пор, пока не находим уже имеющийся элемент с тем же значением (в этом случае мы немедленно возвращаемся из функции) либо находим элемент с большим значением, перед которым вставляем новый. К сожалению, разнообразие возможных ситуаций сильно усложняет код (см. решение задачи 4). Простейшее решение этой задачи, известное мне, представляет собой рекурсивную функцию, вызываемую следующим образом:
Листинг 13.12. Функция insert для класса IntSetList
void i nsert(t)
head = ri nsert(head. t)
Рекурсивная часть проста:
node *rmsert(p. t) if p->va1 < t
p->next = nnsert(p->next. t) else if p->val > t p = new node(t. p) n + + return p
Когда задача усложняется разнообразием возможных случаев, применение подобной функции часто дает возможность сильно упростить код.
Когда один из вариантов реализации наборов применяется для генерации m случайных целых чисел, каждая из m операций поиска выполняется в среднем за время, пропорциональное т. Таким образом, на заполнение всей структуры по
требуется время 0(т2). Я предположил, что версия, использующая список, будет работать несколько быстрее, чем версия с массивом, потому что в ней используется дополнительная память (иод указатели), а это исключает необходимость сдвига верхних элементов. В табл. 13Л приведены данные о времени работы разных реализаций программы при п = 1 ООО ООО и т, меняющемся от 10 ООО до 40 ООО.
Таблица 13.1. Время работы версий программы генерации случайных чисел, с
Структура т=10 ООО т=20 ООО т=40 ООО
Массив 0,6 2,6 11,1
Список (простая версия) 5,7 31,2 170,0
Список (без рекурсии) 1,8 12,6 73,8
Список (групповое 1,2 5,7 25,4
выделение памяти)
Опубликовал vovan666
April 17 2013 00:03:24 ·
0 Комментариев ·
5469 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
