|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 18 Feb 2002 13:55:13
To : Arseny Slobodjuck
Subject : Re: есть ли название у операции
--------------------------------------------------------------------------------
> From: Arseny Slobodjuck
> <Arseny.Slobodjuck@p16.f41.n5045.z2.fidonet.org>
> Date: Sat, 16 Feb 2002 16:33:22 +0300
>
> Долго думал, что за задачу я решаю, наконец, понял, на что
>это похоже. А есть ли известное название ? Скорее всего, оно
>связано с графами.
>
> Есть данные, организованные в виде разделов и подразделов, со своими
>метками. Hу, чтобы далеко не ходить, возьмём директории на диске.
>Они заданы упорядоченным списком, полученным при поиске в глубину.
>Hапример, так:
>
> C:\A\B
> C:\A\C
> C:\A\D\E
>
>Hужно преобразовать это в менее избыточную структуру - что - то
>типа A( B() C() D(E) ). И вот мне это напоминает дифференцирование,
>т.к. в результате мы имеем изменение данных, а не сами данные -
>мы открываем скобку при входе в директорию и закрываем при выходе.
Hазвание операции - топологическая сортировка направленного графа,
и требуется она для того, чтобы убедиться в древовидности этого графа,
то есть, во-первых, в связности, а во-вторых, в отсутствии циклов.
В этом, собственно, и заключается основная работа по корректной постановке
и решению задачи.
После же правильной сортировки задача становится тривиальной: разбиваем
каждую строку на токены (элементы, ограниченные знаком "\"), печатаем
закрывающие скобки в количестве, равном разности числа токенов в предыдущей
и текущей строках плюс единица (это число всегда неотрицательно), после чего
печатаем последний токен текущей строки и одну открывающую скобку. В конце
печатаем столько закрывающих скобок, сколько было токенов в последней строке.
Вот прмерчик, реализованный с помощью конвейера из sort и awk (полнота и
непротиворечивость исходных данных обеспечена вручную):
$ echo \
'C:\A
C:\A\B
C:
C:\A\B\C
C:\A\D' |
sort |
awk \
'BEGIN{ FS="\\";
ORS="";
l=0;
print "\nHа выходе имеем: "};
{ while(l>=NF){
print ")";
l--};
print $NF "(";
l=NF};
END{ while(l>0){
print ")";
l--};
print "\n"}'
Hа выходе имеем: C:(A(B(C())D()))
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: St. Petersburg State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
