IPB

> Лекция №12.1: Алгоритмы на графах и деревьях
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4 5 6

Примеры алгоритмов обработки деревьев и графов. Сравнение рекурсивных и итеративных алгоритмов, решающих некоторые классические задачи теории графов.

Содержание

В этой лекции мы рассмотрим некоторые классические алгоритмы, использующие графы и деревья, приведём и сравним рекурсивные и итеративные их варианты.

Используемая здесь терминология полностью совпадает с терминологией, введённой в предыдущей лекции.

Генерация дерева синтаксического анализа

Одно и то же арифметическое выражение может быть записано трёмя способами:

  1. Инфиксный способ записи (знак операции находится между операндами):

    ((a / (b + c)) + (x * (y - z))) 

    Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.

  2. Префиксный способ записи (знак операции находится перед операндами):

    +( /(a, +(b, c)), *(x, -(y, z))) 

    Из знакомых всем нам функций префиксный способ записи используется, например, для sin(x), tg(x), f(x, y, z) и т. п.

  3. Постфиксный способ записи (знак операции находится после операндов):

    ((a, (b, c)+ )/ ,(x, (y, z)- )* )+

    Этот способ записи менее распространён, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).

Разумеется, вид дерева синтаксического анализа (ДСА)1 арифметического выражения не зависит от способа записи этого выражения (см. рис. 12.1), поскольку определяет его не форма записи, а порядок выполнения операций. Но процесс построения дерева, конечно же, зависит от способа записи выражения. Далее мы разберём все три варианта алгоритма построения ДСА.

Дерево синтаксического анализа и способ описания его элементов

Рис. 12.1.  Дерево синтаксического анализа и способ описания его элементов

type ukaz = ^tree;
     tree = record
       symbol : Char;
       left : ukaz;
       right : ukaz;
    end;

Построение из инфиксной записи

Для простоты мы будем считать, что правильное арифметическое выражение подаётся в одной строке, без пробелов, а каждый операнд записан одной буквой. Приоритет операций определяется расставленными скобками: ими должна быть снабжена каждая операция.

Алгоритм Infix

Если не достигнут конец строки ввода, прочитать очередной символ.

Если этот символ — открывающая скобка, то:

  1. создать новую вершину дерева;
  2. вызвать алгоритм Infix для её левого поддерева;
  3. прочитать символ операции и занести его в текущую вершину;
  4. вызвать алгоритм Infix для правого поддерева;
  5. прочитать символ закрывающей скобки (и ничего с ним не делать).

Иначе:

  1. создать новую вершину дерева;
  2. занести в неё этот символ.
Реализация

Мы воспользуемся здесь описанием типа данных ukaz, приведённым на рис. 12.1:

procedure infix(var p : ukaz);
var c : Char;
begin
 Read(c);
 if c = '(' then
 begin
   New(p);
    infix(p^.left);
   Read(p^.symbol); {'+', '-', '*', '/'}
    infix(p^.right);
   Read(c);  {')'}
 end
 else
 begin   {'a' .. 'z', 'A' .. 'Z'}
   New(p);
    p^.symbol := c;
    p^.right := nil;
    p^.left := nil
 end;
end;

begin
 {...}
  infix(root);
 {...}
end.

Построение из префиксной записи

Для простоты предположим, что правильное арифметическое выражение подаётся в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, будем считать, что из записи удалены все скобки: это вполне допустимо, так как операция всегда предшествует своим операндам, следовательно, путаница в порядке выполнения невозможна.

Алгоритм Prefix
  1. Если не достигнут конец строки ввода, прочитать очередной символ.
  2. Создать новую вершину дерева, записать в неё этот символ.
  3. Если символ — операция, то:
    1. вызвать алгоритм Prefix для левого поддерева;
    2. вызвать алгоритм Prefix для правого поддерева.
Реализация

Вновь воспользуемся описанием типа данных ukaz, приведённым на рис. 12.1:

procedure prefix(var p : ukaz);
begin
 New(p);
 Read(p^.symbol);
 if p^.symbol in ['+', '-', '*', '/'] then
 begin
    prefix(p^.left);
    prefix(p^.right);
 end
 else
 begin
    p^.left := nil;
    p^.right := nil;
 end
end;

begin
 {...}
  prefix(root);
 {...}
end.

страницы: 1 2 3 4 5 6

Примечания

  1. ^ См. лекцию 11.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"