- •Тема 16: ссылочные типы. Списки
- •16.33. Пусть l обозначает кольцевой (циклический) двунаправленный список с заглавным звеном (рис. 15) при следующем описании такого списка;
- •Тема 17: очереди, стеки, двоичные деревья
- •17.3. Для работы со стеком, т. Е. Последовательностью элементов, в которой элементы всегда добавляются в конец и удаляются из конца («последним пришел —первым ушел») нужны обычно следующие операции:
- •17.7. Используя очередь или стек (считать уже описанными их типы и операции над ними—см. 17.1 и 17.3), описать процедуру или функцию, которая:
- •17.14. Пусть в дереве-формуле (см. Упр. 17.13) в качестве терминалов используются не только цифры, но и буквы, играющие, роль переменных. Описать процедуру, которая:
17.14. Пусть в дереве-формуле (см. Упр. 17.13) в качестве терминалов используются не только цифры, но и буквы, играющие, роль переменных. Описать процедуру, которая:
а)* упрощает дерево-формулу T, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f),(f—0),
(f*1) и (1*f), на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f*0) и (0*f),—. на вершину с 0;
б) преобразует дерево-формулу Т, заменяя в нем все поддеревья, соответствующие формулам (f1± f2)*f3) и (f1*(f2±f3), на поддеревья, cоответствующие формулам:
((f1* f3) ± (f2* f3)) ((f1* f2) ± (f1* f3))
в) выполняет в дереве-формуле Т преобразования, обратные преобразованиям из п. б;
г) cтроит дерево-формулу Т1 —производную дерева- формулы Т' по переменной, однобуквенное имя которой являет значением литерного параметра v.
17.15. Предложить и описать на Паскале представление в виде двоичного дерева для формул из упр. 17.13, в которых в качестве терминалов используются любые неотрицательные целые числа. Для такого представления реализовать те же операции, что и в упр. 17.13.
17.16. Деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа— с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения); пример такого дерева показан на рис. 21.
Считая описанными тип дерево (см. выше) и тип файл
type файл=file of ТЭД;
определить функцию или процедуру, которая:
а) проверяет, входит ли элемент Е в дерево поиска Т;
б) записывает в файл f элементы дерева поиска Т в порядке их возрастания;
в) добавляет к дереву поиска Т новый элемент Е, если его не было в T;
г) по файлу f, все элементы которого различны, строит соответствующее дерево поиска Т.
17.17. Во внешнем текстовом файле PROG записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и или цифр. Напечатать в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождении в текст программы. (Учесть, что в идентификаторах одноименные прописные и строчные буквы отождествляются, что внутри литерных значений, строк-констант и комментариев последовательности из букв и цифр не являются идентификаторами, и что в записи вещественных чисел может встретиться буква Е или е.)
Для хранения идентификаторов использовать дерево поиска, элементами которого являются пары—идентификаторы и число его вхождений в текст программы.
Решить предыдущую задачу, но вместе с каждым идентификатором печатать в возрастающем порядке номера всех строк текста программы, в которых он встречается.
Решить задачу 17.17 при условии, что максимальная длина идентификаторов заранее не известна.
17.20. Решить задачу 17.18 при условии, что максимальная длина идентификаторов заранее не известна.