Claw.ru | Рефераты по информатике, программированию | Двоичные деревья поиска Двоичные деревья поиска | Категория реферата: Рефераты по информатике, программированию | Теги реферата: отчет о прохождении практики, шпоры на экзамен | Добавил(а) на сайт: Dvoreckov. Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата     node.key = del.key; // Скопировать ключ     { копирование дополнительных данных }   End   Return del; End

NIL, NULL и маленькие хитрости

Нередко алгоритмы, просто выглядящие на бумаге, становятся нагромождением сплошных конструкций if в реальной программе. Почему? Ответ очевиден: многие алгоритмы для работы с деревьями предполагают, что (NIL).parent == (NIL).left == (NIL).right == NIL. Вроде всё ясно и даже логично, но ведь во многих языках программирования NIL/NULL – это ноль. А обращение по нулевому адресу памяти чревато нехорошими вещами. Что же делать? Ведь мало того, что все эти if тормозят программу, в них легко запутаться! Решение просто: мы не будем использовать NIL! Действительно, алгоритмам совершенно всё равно, какое численное значение имеет NIL, главное, чтобы адрес любой реальной вершины в дереве не был ему равен. Поэтому вместо NIL мы будем использовать адрес переменной, проинициализированной особым образом. Я покажу это на языке С++, но думаю, этот пример можно будет перевести и на другие языки, хотя там, скорее всего, нет шаблонов, и придется пожертвовать типобезопасностью.