Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Т.Н. Ничушкина, А.В. НикитинСтр 1 из 3Следующая ⇒
Имени Н.Э. Баумана (национальный исследовательский университет)» (МГТУ им. Н.Э. Баумана) Т.Н. Ничушкина, А.В. Никитин Динамические структуры данных: бинарные деревья Методические рекомендации к домашнему заданию по теме: «Бинарные деревья» по дисциплине «Информатика»
Москва 2017 Оглавление Введение.. 3 1 Дерево синтаксического разбора.. 4 2 Разбор арифметического выражения.. 5 2.1 Формы записи выражений. 5 2.1.1 Префиксная форма записи. 5 2.1.2 Инфиксная форма записи. 6 2.1.3 Постфиксная форма записи. 6 2.2 Алгоритм построения дерева для разбора арифметического выражения без скобок. 6 2.3 Алгоритм построения дерева для разбора арифметического выражения со скобками. 8 3 Пример вычисления арифметического выражения.. 10 3.1 Порядок синтаксического разбора арифметического выражения через стек 10 3.3 Контрольные вопросы.. 12 4 Требования к выполнению домашнего задания.. 12 4.1 Задание. 12 4.2 Указания к выполнению работы.. 13 4.3 Требования к отчету. 13 4.4 Требования к защите. 14 Заключение.. 15 Список рекомендуемой литературы... 16 Приложение А. Варианты заданий 17
Введение Целью домашнего задания по теме «Бинарные деревья», изучаемой в рамках дисциплины «Информатика» является закрепление материала по динамическим структурам данным и применение этих структур в практике программирования. В домашнем задании изучаются приемы работы с динамическими бинарными деревьями поиска на языке программирования С++. Основное внимание уделяется практическому применению бинарных деревьев, в частности, использование бинарных деревьев для вычисления арифметических выражений. В методических указаниях приводятся краткие теоретические и справочные сведения, необходимые для выполнения домашнего задания. Рассмотрены примеры решения задачи разбора арифметических выражений с применением бинарных деревьев. Методические рекомендации предназначены для студентов первого курса кафедры ФН11 (Математика и компьютерные науки). Разбор арифметического выражения Как транслятор (программа-переводчик, которая преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд) обрабатывает и выполняет арифметические и логические выражения, которые он встречает в программе?
Один из вариантов – представить это выражение в виде двоичного дерева. Например, выражению (a + b) / (c - d + 1) соответствует двоичное дерево разбора, показанное на рисунке 3.
Формы записи выражений
Что получается при прохождении таких двоичных деревьев? В зависимости от варианта обхода такого бинарного дерева можно получить разные формы записи выражения. Префиксная форма записи
Прямое прохождение дерева (корень – левое поддерево – правое поддерево) дает то есть знак операции (корень) предшествует своим операндам. Такая форма записи арифметических выражений называется префиксной. Инфиксная форма записи
Симметричный обход (левое поддерево – корень – правое поддерево) дает запись вида , или инфиксную форму, которая совпадает с обычной записью, но без учета скобок. Поскольку скобок нет, правильный порядок операций невозможно восстановить по инфиксной записи. Постфиксная форма записи
В трансляторах широко используется постфиксная запись выражений, которая получается в результате обратного обхода (левое поддерево - правое поддерево - корень). В такой записи знак операции стоит после обоих операндов: Пример вычисления арифметического выражения Задание
Для заданного арифметического выражения построить дерево арифметического разбора, написать алгоритм подсчета арифметического выражения, организовав ввод переменных с клавиатуры и с помощью датчика случайных чисел в соответствии с заданным вариантом. Вывести дерево и результат расчета на экран. Провести тестирование программы. Примерные варианты заданий приведены в приложении А. Требования к отчету
В отчете по домашнему заданию должны быть сделаны выводы о том, какие достоинства и недостатки имеет метод разбора и расчета арифметического выражения через бинарные деревья (например, в сравнении с разбором и расчетом с помощью стека).
В отчете по домашнему заданию должны быть даны ответы на контрольные вопросы.
Отчет по домашнему заданию должен включать в себя: 1. Титульный лист; 2. Цели домашнего задания; 3. Теоретическая часть с ответами на контрольные вопросы; 4. Задание в соответствии с вариантом; 5. Графическое отображение дерева в соответствии с вариантом; 6. Код программы с комментариями; 7. Тесты программы с пояснениями; 8. Выводы. Требования к защите Для получения зачета по домашнему заданию, студент должен представить отчет, оформленный в соответствие с требованиями, продемонстрировать работающую программу и ответить на вопросы преподавателя по программе. Заключение
В процессе выполнения домашнего задания по теме «Бинарные деревья» студенты получат краткие теоретические и справочные сведения по построению и обработке бинарных деревьев с помощью динамических структур данных. Рассмотрят примеры решения задачи разбора арифметических выражений с применением бинарных деревьев. В результате выполнения домашнего задания студенты освоят приемы работы с динамическими бинарными деревьями поиска на языке программирования С++. Получат практические навыки применения бинарных деревьев для вычисления арифметических выражений. Список рекомендуемой литературы
2. Г.В. Ваныкина, Т.О. Сундукова Структуры и алгоритмы компьютерной обработки данных /– М: Изд-во Интуит, 2011. – 211 с. 3. Михалкович С. С. Основы программирования: Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы. — Ростов н/Д.: УПЛ ЮФУ, 2007. — 48 с. 4. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 392 с. 5. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. М.: Изд-во Вильямс, 2001. – 253 с. 6. Ахо А., Хопкрофт Д.,. Ульман Д. Структуры данных и алгоритмы: Пер. с англ. М.: 7. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и 8. Керниган Б., Пайк Р. Практика программирования: Пер. с англ. СПб.: Невский диалект, 2001. С. 83–90.
Приложение А. Варианты заданий Номер варианта соответствует порядковому номеру студента в алфавитном списке группы.
Имени Н.Э. Баумана (национальный исследовательский университет)» (МГТУ им. Н.Э. Баумана) Т.Н. Ничушкина, А.В. Никитин
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-01-08; просмотров: 253; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.147.61.195 (0.017 с.) |