Реализация АВЛ–деревьев через классы объектно–ориентированного программирования
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Министерство образования и науки Украины
Запорожская государственная инженерная академия
Кафедра программного обеспечения автоматизированных систем
КУРСОВАЯ РАБОТА
По дисциплине Объектно ориентированное программирование
На тему: Реализация АВЛ деревьев через классы объектно ориентированного программирования
Выполнил: ст. гр. СП 07 1з Воронько О.А.
Проверил: Попивщий В.И.
Запорожье, 2009г.
ПЛАН
Введение
1. Основные термины
2. Основные операции с АВЛ - деревьями
3. Алгоритм реализации АВЛ деревьев через классы объектно ориентированного программирования
Список литературы
ВВЕДЕНИЕ
Язык программирования С++ является одним из наиболее популярных средств объектно ориентированного программирования, позволяющим разрабатывать программы, эффективные по объему кода и скорости выполнения. С++ включает большое число операций и типов данных, средства управления вычислительными процессами, механизмы модификации типов данных и методы их обработки и, как следствие, является мощным языком программирования. Он позволяет описывать процессы обработки информации, начиная с уровня отдельных разрядов, видов и адресов памяти, переходя на основе механизмов объектно ориентированного программирования к близким конкретным предметным областям понятиям.
Первые программы для цифровых вычислительных машин редко превышали объем 1 кбайт. Объемы используемых программ и программных систем измеряются не только десятками килобайтов, но и сотнями мегабайтов. Вместе с тем удельная стоимость создания программ (нормированная объемом программы) до последнего времени менялась мало. Более того, с ростом объема программы удельная стоимость ее создания могла нелинейно возрастать. Поэтому не удивительно, что одним из основных факторов, определяющих развитие технологии программирования, является снижение стоимости проектирования и создания программных продуктов (ПП), или борьба со сложностью программирования.
Другими важнейшими факторами, влияющими на эволюцию методов проектирования и создания ПП, являются:
- изменение архитектур вычислительных средств (ВС) в интересах повышения производительности, надежности и коммуникативности;
- упрощение взаимодействия пользователей с ВС и интеллектуализация ВС.
Действие двух последних факторов, как правило, сопряжено с ростом сложности программного обеспечения ВС. Сложность представляет неотъемлемое свойство программирования и программ, которое проявляется во времени и стоимости создания программ, в объеме или длине текста программы, характеристиках ее логической структуры, задаваемой операторами передачи управления (ветвления, циклы, вызовы подпрограмм и др.).
Можно выделить 5 следующих источников сложности программирования:
1) решаемая задача;
2) язык программирования;
3) среда выполнения программы;
4) технологический процесс коллективной разработки и создания ПП;
5) стремление к универсальности и эффективности алгоритмов и типов данных.
От свойства сложности нельзя избавиться, но можно изменять характеристики его проявления путем управления или организации.
В программировании широко используется фундаментальный принцип управления сложными системами, который известен человеку с глубокой древности devide et impera (разделяй и властвуй, лат.) и широко им применяется при разработке и проектировании любых сложных технических систем.
В настоящее время объектно ориентированное программирование (ООП) является доминирующим стилем при создании больших программ.
1. ОСНОВНЫЕ ТЕРМИНЫ
Так исторически сложилось, что у этих деревьев есть два альтернативных названия: АВЛ - деревья и сбалансированные деревья. АВЛ произошло от фамилий изобретателей.
Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать.
В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому Г.М. Адельсон - Вельский и Е.М. Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.
Дерево считается сбалансированным по АВЛ (в дальнейшем просто сбалансированным), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится. Рассмотрим модифицированный класс деревьев, обладающих всеми преимуществами бинарных деревьев поиска и никогда не вырождающихся. Они называются сбалансированны