Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
{ insert(data,root); } Важно! Для правильной работы алгоритма, значение info добавляемого элемента должно иметь уникальное значение! 96 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ БИНАРНОГО ДЕРЕВА При удалении элементов из бинарного дерева рассматривается 3 (три) различных случая: 1. Удаляется «ЛИСТ». Оба указателя left и right равны NULL.
tree 4 ДО УДАЛЕНИЯ 9 10 2 1 7 5 8 ДЕРЕВО ПОСЛЕ УДАЛЕНИЯ 7 5 97 2. Удаляется элемент с ОДНИМ «ребёнком». Один из указателей left или right элемента равен NULL. tree ДО УДАЛЕНИЯ 4 2 9 1 7 10 5 8 tree ПОСЛЕ УДАЛЕНИЯ 4 1 9 7 10 5 8 98 3. Удаляется элемент с ДВУМЯ «детьми». Оба указателя left и right не равны NULL. Возможно 2 варианта удаления.
tree ВАРИАНТ 1-ый 4 ДО УДАЛЕНИЯ 2 9 1 7 10 5 8 6 ДЕРЕВО 9 ПОСЛЕ УДАЛЕНИЯ 6 10 5 8 99 ВАРИАНТ 2-ой tree ДО УДАЛЕНИЯ 4 2 9 1 7 10 5 8 6 ДЕРЕВО 9 ПОСЛЕ УДАЛЕНИЯ 8 10 5 6 100 Важно! При удалении из дерева элемента, у которого оба указателя left и rightне равны NULL, фактически происходит перезапись информационной части этого элемента, а не его удаление из структуры данных. Удаляется при этом другой элемент. Для этого 1. ищется предыдущий или следующий относительно «удаляемого» элемент, обозначим его А; 2. информационная часть элемента Азаписывается вместо информационной части «удаляемого» элемента; 3. после этого элемент А удаляется из структуры дерева.
В силу самой структуры дерева, предыдущий или следующий относительно данного элемент ВСЕГДА будет либо «листом», либо узлом с одним «ребёнком». Поэтому удаление такого узла сводится к случаю 1 или 2.
A дерево дерево A дерево дерево дерево дерево дерево дерево B C дерево дерево Элемент B – «наибольший» среди «меньших», то есть предшествующий.
Элемент C – «наименьший» среди «больших», то есть следующий.
Правила удаления элементов из дерева в случаях 1 или 2: при удаленни «листа» соответствующий указатель родительского элемента перенаправляется на любой из указателей удаляемого элемента (NULL);
101
при удаленни узла с одним дочерним элементом, соответствующий указатель родительского элемента перенаправляется на тот из указателей удаляемого узла, который не равен NULL.
указатель родительского элемента. Для реализации указанного алгоритма можно применить 2 функции: 1. первая принимает в качестве аргумента указатель на элемент дерева и «удаляет» его в зависимости от количества дочерних элементов («лист», один дочерний элемент, два дочерних элемента) соответствующим образом; 2. вторая принимает в качестве аргумента данные (значение поля info), которые требуется удалить, и, если находит их в дереве, передаёт указатель на соответствующий узел дерева первой функции.
Вариант функции №1, реализующей удаление данного узла дерева в зависимости от количества дочерних элементов. template void deleteNode(Node { Node temp = tree; if(tree->left == nullptr ) // Один или ни одного дочернего узла { tree = tree->right; delete temp; } elseif( tree->right == nullptr ) // Один или ни одного дочернего узла { tree = tree->left; delete temp; } else // Ровно два дочерних узла { Node 102 // Находит «предыдущий» элемент tree->info = pred->info; // Записывает данные в «удаляемый» узел deleteNode(pred); //Удаляет «предыдущий» элемент } Вариант функции №2 (рекурсия), которая ищет узел с данными, которые требуется удалить, и передаёт указатель на этот узел функции №1.
template void delete(Node { if(data < tree->info ) // Если данные «меньше», чем у текущего узла ... delete(tree->left, data); // Идём налево elseif( data > tree->info ) // Если данные «больше», чем у текущего узла ... delete(tree->right, data); // Идём направо else // Узел найден, вызываем ф-цию №1 deleteNode(tree); }
Функция GetPredecessor()возвращает указатель на «предыдущий» элемент. template Node { if(tree == nullptr ) {...} // Проверка... Node // Идём направо, пока есть узлы... while(curr->right != nullptr ) curr = curr->right; return curr; //Получаем указатель }
103 ОБХОД БИНАРНОГО ДЕРЕВА(tree traversal) Существует три распространённых способа обхода или, другими словами, перемещения между узлами бинарного дерева. 1. Симметричный обход (inorder traversal). 1.1. Обход левого поддерева данного узла. 1.2. Посещение данного узла. 1.3. Обход правого поддерева данного узла. 2. Обход в прямом порядке или обход в ширину (preorder traversal). 2.1. Посещение данного узла. 2.2. Обход левого поддерева данного узла. 2.3. Обход правого поддерева данного узла. 3. Обход в обратном порядке или обход в глубину (postorder traversal). 3.1. Обход левого поддерева данного узла. 3.2. Обход правого поддерева данного узла. 3.3. Посещение данного узла.
СИММЕТРИЧНЫЙ ОБХОД(inorder traversal) LA B 5 A RA C D H 1 E F I 4 6 7 8 G 9 2 3 Маршрут симметричного обхода: DHBEAFCIG. 104 ОБХОД В ШИРИНУ(preorder traversal) 2 LA B 3 6 A 1 RA C 8 7 D H 4 E F I G 5 9 Маршрут обхода в ширину: ABDHECFGI. ОБХОД В ГЛУБИНУ(postorder traversal) 9 LA B 3 4 A RA C 5 8 D H 1 E F I 2 6 G 7 Маршрут обхода в глубину: HDEBFIGCA. 105 При выборе того или иного маршрута обхода дерева, информационные части узлов могут, например, быть записаны в соответствующую очередь или стэк , которые затем и будут использоваться для вывода данных.
Рекурсивный алгоритм обхода бинарного дерева Пример private-функции, реализующей рекурсивный алгоритм обхода бинарного дерева в симметричном (inorder) порядке: template void BinaryTree tree) const { if(tree != nullptr )//Только если дерево не пусто { inorder(tree->left );//Рекурсивный вызов cout << tree->info << " ";
//Или добавление в очередь или стэк... inorder(tree->right ); //Рекурсивный вызов }; } Пример public-функции, члена класса BinaryTree: template void BinaryTree { inorder(root); } Аналогично реализовываются другие маршруты обхода бинарного дерева. Поддерживаемые операции 1. 2. 3. 4. 5. 6. 7. 8.
добавить элемент; удалить элемент; удалитьдерево; проверить, пусто ли дерево; найти и извлечь данные; копировать дерево; обойти дерево по трёмразличным маршрутам; вывести в консоль (или файл) все элементы дерева. 106 Пример интерфейса классов BinaryTree и Node template class Node { public:
// Конструктор по умолчанию. Node() { left = right = nullptr;} // Конструктор с параметрами. Node(const T& d, Node Node { info = d; left = l; right = r; } T info;// Информационная часть. Node узлы. }; template class BinaryTree { public:
BinaryTree(); // Конструктор по умолчанию. Создаёт Пустое дерево. ~BinaryTree(); // Деструктор const BinaryTree BinaryTree // Перегрузка оператора присваивания. BinaryTree(const BinaryTree // Копирующий конструктор bool isEmpty() const;// Отвечает на вопрос содержит дерево элементы или нет. Возвращает true, если дерево не пусто и false в противном случае. void print() const;// Выводит данные издерева. int nodeCount() const;// Возвращает количество 107 узлов в дереве. void destroy() { clear(root); }; // Удаляет все узлы дерева. В результате дерево
пусто и root == NULL; void inorderTree()const{ inorder(root); };// Симметричный обход дерева. void preorderTree()const{ preorder(root); }; // Обход дерева в ширину. void postorderTree()const{ postorder(root); }; // Обход дерева в глубину. T* retriveItem(const T& item) const{ return search(root, item); };// Возвращает указатель на item, если найдено void deleteItem(const T& item){ return delete(root, item); };
// Удаляет узел с данными item из дерева. void insertItem(const T& item){ return insert(root, item); }; // Добавляет узел с данными item в дерево. private:
Node copyTree(BinaryTree // Функция, создающая копию дерева otherTree. Node T* search(Node // Ищет и возвращает данные. void void
void void
inorder(Node preorder(Node postorder(Node clear(Node и устанавливает указатель root в NULL. void delete(Node 108 void deleteNode(Node void insert(Node };
Контрольные вопросы 1. Что такое абстрактная структура данных? 2. Что такое бинарное поисковое дерево? 3. Основные свойства и способы построения структуры данных бинарное поисковое дерево? 4. Напишите алгоритм основных операций для структуры данных бинарное поисковое дерево? 5. В каком порядке посещаются узлы бинарного дерева в случае: симметричного обхода – inorder traversal; обхода в прямом порядке (в ширину)– preorder traversal; обхода в обратном порядке (в глубину)– postorder traversal. ПРАКТИЧЕСКИЕ ЗАДАНИЯ Задание 1 Используя абстрактную структуру данных БИНАРНОЕ ДЕРЕВО, реализовать свой вариант Задания №1 из Лабораторной работы №3. Приложение должно обеспечивать диалог с помощью меню и контроль ошибок при вводе. Определить ключевое поле, по которому будет происходить упорядочивание бинарного дерева. Обеспечить возможность ПОИСКА данных по ключевому полю. Задание 2 Используя абстрактную структуру данных БИНАРНОЕ ДЕРЕВО, разработать и реализовать ДЕРЕВО РЕШЕНИЙ для какой-либо задачи из повседневной жизни (выдача кредита, страхование имущества, диагностика заболевания и т.п.) по следующему принципу: 109 ДА
Вопрос ? НЕТ Вопрос ? НЕТ ДА Вопрос ? Решение1 ДА Вопрос ? ДА НЕТ НЕТ Требования: 1. дерево должно иметь не менее 4-х уровней; 2. программа должна обеспечить диалог, с помощью которого пользователь может отвечать на вопросы; 3. после окончания опроса (достижения какого-либо решения), программа выводит в консоль решение и ответы, данные пользователем во время опроса. Задание 3 Используя абстрактную структуру данных БИНАРНОЕ ДЕРЕВО, разработать калькулятор, вычисляющий арифметические выражения из 4-х основных действий и скобок, записанные в постфиксной форме (postfix notation), используя подходящий порядок обхода и следующие правила: 1. дерево состоит только из узлов, у которых ровно 2 ребёнка и листьев; 2. листьям дерева соответствуют операнды – числа; 3. остальным узлам соответствуют бинарные операции – действия над 2-мя числами. Например,выражению3 13 / 9 52 3 7 4 6 соответствует дерево 110 —
/ * + 3 1 3 — + 2 3 * — + 6 9 5 7 4 111 ПРИЛОЖЕНИЕ 2 Белорусский государственный университет УТВЕРЖДАЮ Декан гуманитарного факультета ________________ В.Е. Гурский (подпись) ____________________ (дата утверждения) Регистрационный № УД-______/р. Алгоритмы и структуры данных Учебная программа учреждения высшего образования по учебной дисциплине:1-31 03 07-03 для специальности: Прикладная информатика Факультет Гуманитарный Кафедра Информационных технологий Курс (курсы) 1 Семестр (семестры) 2 Лекции 34
занятия
Лабораторные занятия 34 Аудиторных часов по учебной дисциплине 68 Всего часов по учебной дисциплине 158 Экзамен 2 Зачет Курсовая работа (проект) Форма получения высшего образования очное Составил(а) А.В. Овсянников, кандидат технических наук, доцент 2013 г. 112 Учебная программа составлена на основе типовой учебной программы «Алгоритмы и структуры данных» Регистрационный номер №ТД – G 278/тип, дата утверждения 16.06.2010
Рассмотрена и рекомендована к утверждению кафедрой Информационных технологий ____________________ (дата, номер протокола) Заведующий кафедрой ________________ В.А. Нифагин (подпись) Одобрена и рекомендована к утверждению Научно-методическим советом1 Гуманитарного факультета БГУ 28.06.2013 г. №9 Председатель ________________ О.В.Немкович (подпись) Учебная программа может быть рекомендована к утверждению Советом факультета или методической комиссией факультета, или общеуниверситетской (общеакадемической) кафедрой. 1 113 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Учебная программа «Алгоритмы и структуры данных» разработана для специальности 1-31 03 07-03 «Прикладная информатика» высших учебных заведений. Дисциплина «Алгоритмы и структуры данных» знакомит студентов с фундаментальными понятиями, используемыми при разработке алгоритмов и оценке их трудоемкости. Цель дисциплины - изучение подходов к разработке эффективных алгоритмов для разнообразных задач дискретной и комбинаторной оптимизации. Задачи дисциплины - выработать навыки по оценке трудоемкости алгоритмов и по применению современных структур данных для эффективной реализации различных базовых операций. В курсе рассматриваются такие фундаментальные понятия как информация, размерность задачи и трудоемкость алгоритмов. Особое внимание уделено способам определения трудоемкости алгоритмов с помощью таких методов, как составление и решение рекуррентных уравнений. Наряду с классическим подходом оценки трудоемкости рассматриваются также способы определения усредненной оценки трудоемкости алгоритма для группы операций. Основой для дисциплины «Алгоритмы и структуры данных» являются следующие дисциплины: «Дискретная математика и математическая логика», «Теория вероятностей и математическая статистика», «Программирование». Изучение курса позволяет дать студентам базу, необходимую для успешного усвоения материала, а также получить знания, необходимые им в дальнейшем для успешной работы при разработке эффективных алгоритмов, В результате изучения дисциплины студент должен знать: понятие размерности задачи и трудоемкости алгорнма; основные приемы разработки эффективных алгоритмов: динамическое программирование и метод «разделяй и властвуй»; основные структуры данных и трудоемкость базовых операций для них;
виды поисковых деревьев: основные алгоритмы поиска на графах и их трудоемкость; уметь: определять трудоемкость основных алгоритмов поиска и внутренней сортировки. используя технику рекуррентных соотношений: осуществлять выбор структуры данных для разработки эффективного алгоритма решения задачи; реализовывать поисковые деревья: реализовывать основные алгоритмы поиска на графах. уметь: определять трудоемкость основных алгоритмов поиска и внутренней сортировки, используя технику рекуррентных соотношений; 114 осуществлять выбор структуры данных для разработки эффективного алгоритма решения задачи; реализовывать поисковые деревья; реализовывать основные алгоритмы поиска на графах. Учебная программа предусматривает для изучения дисциплины 158 часов, в том числе 68 аудиторных часов: лекции - 34 часа, лабораторные занятия - 34 часа.
СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА Тема 1 Понятие структуры данных и алгоритмов. Определение алгоритма. Формальные свойства алгоритмов. Понятие структуры данных. Классификация структур данных. Операции над структурами данных. Структурность данных и технология программирования.
Тема 2 Абстрактные вычислительные машины. МашинаПоста.Маши́наТьюринга,детерминированнаяи ́ недетерминированная машина Тьюринга. Вероятностная машина Тьюринга. Тема 3 Анализ алгоритмов. жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|