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
выделение памяти) |
Главная
Каталог файлов
