Динамические структуры данных. Алексеев А.Ю - 43 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Требуется:
а) вычислить как целое число значение выражения (без переменных), запи-
санного в постфиксной форме в заданном текстовом файле postfix;
б) то же для выражения в префиксной форме (задан текстовый файл prefix);
в) перевести выражение, записанное в обычной (инфиксной) форме в за-
данном текстовом файле infix, в постфиксную форму и в таком виде записать
его в текстовый файл postfix;
г) то же, но в префиксную форму (записать в файл prefix);
д) вывести в обычной (инфиксной) форме выражение, записанное в пост-
фиксной форме в заданном текстовом файле postfix (рекурсивные процедуры
не использовать и лишние скобки не выводить);
е) то же, но при заданной префиксной форме (в файле prefix).
3. ДЕРЕВЬЯ
Наиболее полезной нелинейной структурой данных является дерево (или лес).
3.1. Определения дерева, леса, бинарного дерева.
Скобочное представление
Дадим формальное определение дерева, следуя [10].
Дерево – конечное множество Т, состоящее из одного или более узлов, та-
ких, что
а) имеется один специально обозначенный узел, называемый корнем дан-
ного дерева;
б) остальные узлы (исключая корень) содержатся в m ≥ 0 попарно не пере-
секающихся множествах Т
1
, Т
2
, ... , Т
m
, каждое из которых, в свою очередь,
является деревом. Деревья Т
1
, Т
2
, ... , Т
m
называются поддеревьями данного
дерева.
При программировании и разработке вычислительных алгоритмов удобно
использовать именно такое рекурсивное определение, поскольку рекурсив-
ность является естественной характеристикой этой структуры данных.
Каждый узел дерева является корнем некоторого поддерева. В том случае,
когда множество поддеревьев такого корня пусто, этот узел называется конце-
вым узлом, или листом. Уровень узла определяется рекурсивно следующим
образом: 1) корень имеет уровень 1; 2) другие узлы имеют уровень, на едини-
цу больший их уровня в содержащем их поддереве этого корня. Используя
для уровня узла «а» дереве T обозначение уровень ( a , T ), можно записать это
43
   Требуется:
   а) вычислить как целое число значение выражения (без переменных), запи-
санного в постфиксной форме в заданном текстовом файле postfix;
   б) то же для выражения в префиксной форме (задан текстовый файл prefix);
   в) перевести выражение, записанное в обычной (инфиксной) форме в за-
данном текстовом файле infix, в постфиксную форму и в таком виде записать
его в текстовый файл postfix;
   г) то же, но в префиксную форму (записать в файл prefix);
   д) вывести в обычной (инфиксной) форме выражение, записанное в пост-
фиксной форме в заданном текстовом файле postfix (рекурсивные процедуры
не использовать и лишние скобки не выводить);
   е) то же, но при заданной префиксной форме (в файле prefix).




                                3. ДЕРЕВЬЯ

   Наиболее полезной нелинейной структурой данных является дерево (или лес).


             3.1. Определения дерева, леса, бинарного дерева.
                        Скобочное представление

   Дадим формальное определение дерева, следуя [10].
   Дерево – конечное множество Т, состоящее из одного или более узлов, та-
ких, что
   а) имеется один специально обозначенный узел, называемый корнем дан-
ного дерева;
   б) остальные узлы (исключая корень) содержатся в m ≥ 0 попарно не пере-
секающихся множествах Т1 , Т2 , ... , Тm, каждое из которых, в свою очередь,
является деревом. Деревья Т1 , Т2 , ... , Тm называются поддеревьями данного
дерева.
   При программировании и разработке вычислительных алгоритмов удобно
использовать именно такое рекурсивное определение, поскольку рекурсив-
ность является естественной характеристикой этой структуры данных.
   Каждый узел дерева является корнем некоторого поддерева. В том случае,
когда множество поддеревьев такого корня пусто, этот узел называется конце-
вым узлом, или листом. Уровень узла определяется рекурсивно следующим
образом: 1) корень имеет уровень 1; 2) другие узлы имеют уровень, на едини-
цу больший их уровня в содержащем их поддереве этого корня. Используя
для уровня узла «а» дереве T обозначение уровень ( a , T ), можно записать это

                                     43

Страницы