Рекурсия
|t_| Доброго времени суток!
|go| Готов с вниманием внимать,
все то, что ты, zz сказать.
(переменная zz пока не определена).
|t_| Давай присвоим zz := 'хотел'.
Напомню, сегодня, наша тема - рекурсия.
|go| Я посмотрел, что говорит на эту тему википедия - что-то уж очень закручено... но вообще-то мы такое проходили... Фотография: мужик смотрит на фотографию на ней он же смотрит на туже фотографию, на ней...
|t_| Уже легче. Давай использовать облегченное определение. Рекурсия, это когда внутри процедуры (функции) есть вызов ее самой:
procedure МояПроцедура(параметры);
begin
...
что-то там делается
...
if условие потребности в рекурсии
then МояПроцедура(параметры);
...
и еще что ни будь сделаем
...
end;
Условие потребности в рекурсии, рано или поздно должно стать false иначе она станет бесконечной и программа зависнет. Возможен и такой вариант:
function МояФункция(параметры):boolean;
begin
...
что-то там делается
...
if МояФункция(параметры)
then exit;
...
result := условие выхода из рекурсии
...
end;
Конечно же, возможны сотни других вариантов...
Надеюсь, что не очень напряг тебя теорией, теперь к практике.
|go| Да нет, все нормально. Поехали.
:(
Yes no,
all OK.
Let's go.
:)
|t_| Сегодня у тебя поэтическое настроение, это хорошо...
Рекурсия очень хорошо подходит для обхода дерева, например дерева файловой системы.
Задача.
Написать программку удаляющую все пустые папки в заданной папке ( устройстве ).
(готовый исходник можно извлечь из этой книги, и имя его del_empty_dir.zip1 )
Давай сделаем простенькую форму с одной только кнопочкой.
При нажатии должен появляться диалог выбора папки, и после этого просмотрим все входящие папки и удалим пустые. Да еще, посчитаем удаленные и сообщим результат.
|go| Ну, что делаем новый проект в новой папке?
|t_| Да, как всегда.
На форме одну кнопочку, и вот обработчик ее клика и все остальное.
Давай, попробуй выполнить программку, создай пустую папку и попробуй ее удалить.
А потом обсудим.
// начало кода
{ 0 } var
{ 1 } Form1: TForm1;
{ 2 } Path : AnsiString; // путь к папке с программой
{ 3 } count : integer; // счетчик удалений
{ 4 }
{ 5 } implementation
{ 6 }
{ 7 } {$R *.dfm}
{ 8 }
{ 9 } function DelEmtyDir(Target : AnsiString):boolean;
{ 10 } var
{ 11 } Found : integer; // результат поиска ( 0 - файл найден )
{ 12 } SR : TSearchRec; // запись с параметрами файла
{ 13 } begin
{ 14 } Found := FindFirst(Target + '\*.*',$3F,SR);
{ 15 } result := true; // предположим что папка пуста.
{ 16 } WHILE Found = 0 DO
{ 17 } BEGIN
{ 18 } if (SR.Name <> '.')
{ 19 } and (SR.Name <> '..')
{ 20 } then
{ 21 } begin
{ 22 } // если это папка
{ 23 } if ((SR.Attr and $10) = $10 ) then
{ 24 } begin // рекурсивный вызов функции
{ 25 } if DelEmtyDir( Target+'\'+ SR.Name)
{ 26 } then
{ 27 } begin // удаление пустой папки
{ 28 } RmDir(Target+'\'+ SR.Name);
{ 29 } inc(count); // + 1 в счетчик
{ 30 } end;
{ 31 } end
{ 32 } else
{ 33 } begin // найден какой то файл
{ 34 } result := false; // значит папка не пуста.
{ 35 } FindClose(SR);
{ 36 } exit;
{ 37 } end;
{ 38 } end;
{ 39 } Found := FindNext(SR);
{ 40 } END;{DosError = 0}
{ 41 } FindClose(SR);
{ 42 } end;
{ 43 }
{ 44 } procedure TForm1.Button1Click(Sender: TObject);
{ 45 } var
{ 46 } Dir : AnsiString;
{ 47 } begin
{ 48 } Dir := Path; count := 0;
{ 49 } if SelectDirectory(Dir, [sdAllowCreate, sdPerformCreate, sdPrompt],0)
{ 50 } then
{ 51 } begin
{ 52 } if Dir[length(Dir)]='\'
{ 53 } then delete(Dir, length(Dir),1);
{ 54 } DelEmtyDir(Dir);
{ 55 } ShowMessage('Deleted ' + IntToStr(count) +' folders.');
{ 56 } end;
{ 57 } end;
{ 58 }
{ 59 } procedure TForm1.FormCreate(Sender: TObject);
{ 60 } begin
{ 61 } Path := ExtractFileDir(ParamStr(0)) + '\';
{ 62 } end;
// конец кода
|go| Не работает. Delphi не знает кто такое SelectDirectory.
|t_| Ничего, потихоньку научишься работать, поставь курсор на слово - ошибку и нажми F1.
|go| Получил help. Ну и что дальше.
|t_| В help найди к какому unit относился функция SelectDirectory и вставь это название в uses своей программы. Так поступай и в дальнейшем, больше старайся использовать help и умеренно, советы из интернета, к сожалению в этой "всемирной свалке" надо хорошо покопаться чтобы найти алмазы, а по пути можно и замазаться...
|go| Как сказал кот Матроскин - "Заработало!!!"
|t_| Хорошо, ну а теперь найди в программе ошибку. Подсказка, тоже цитата "Хотели как лучше, а получилось... "
|go| Нашел, каждый раз при нажатии кнопки выбор папки начинается из папки программы, а это неудобно.
|t_| Ну, ты даешь! Нашел не запланированную мною ошибку. Ты совершенно прав. Давай исправлять.
{ 46 } Dir : AnsiString; - определение переменной сделай глобальным
{ 0 } var
{ 1 } Form1: TForm1;
Dir : AnsiString;
{ 2 } Path : AnsiString; // путь к папке с программой
а строчку 46 удали
теперь:
{ 48 } Dir := Path; - это присваивание отсюда забери и вставь в:
{ 61 } Path := ExtractFileDir(ParamStr(0)) + '\';
Dir := Path;
{ 62 } end;
Ну, а теперь, ищи дальше.
|go| Не понял смысла в строках
{ 52 } if Dir[length(Dir)]='\'
{ 53 } then delete(Dir, length(Dir),1);
Dir и так возвращается без конечного слеша.
|t_| Не совсем так. Если ты будешь искать в корневом каталоге, то там будет слеш (например: с:\ ). Ищи дальше.
|go| Наверно это строки
{ 33 } begin // найден какой то файл
{ 34 } result := false; // значит папка не пуста.
{ 35 } FindClose(SR);
{ 36 } exit;
{ 37 } end;
не знаю в чем ошибка, хотя бы потому, что я не понимаю их смысла.
|t_| Да, это ошибка и есть. Подразумевалось такое рассуждение: если в папки найден какой то файл, значит папка не пуста, а значит и искать дальше нечего, и давай сэкономим время.
Это бы работало правильно, если бы вложенные папки были бы гарантированно просмотрены первыми... Удали строки 35, 36.
|go| Слушай, что то странное. Удаляю из одной папки, пишет "Удалено 8 папок", опять удаляю оттуда, опять пишет "Удалено 8 папок", третий раз удаляю, опять тоже самое.
|t_| Интересно. Поставь курсор на 28 строку и нажми F4. Посмотри содержимое Target и SR.Name в момент удаления папки.
|go| Не понял, как посмотреть?
|t_| Знаешь, мне не хочется отвлекаться на описание возможностей Delphi по отладке программ, информацию об этом найдешь в любом учебнике, поэтому пока простейшее, в режиме отладки, наведи курсор мыши на нужную переменную и через пару секунд всплывет ее значение в этот момент ( есть и более удобные способы - читай учебники ).
Возвращаемся к нашей программе. Посмотри содержимое указанных переменных и проверь, что есть в этих папках.
|go| В этих папках есть другие папки, т.е. они не пустые.
|t_| Минуточку, сам попробую.
Через 6 минут.
|t_| Все, разобрался. Достаточно грубая ошибка. У нас result := false - признак не пустой папки вырабатывался только при нахождении файла, а при нахождении папки функция все равно оставалась истинной. Функция RmDir пыталась удалить папку, но т.к. она не пуста ей это не удавалось, а результат удаления мы не анализируем. Вот и имеем, что имеем.
Давай переделаем этот фрагмент.
Кстати, надо учитывать, что папку функции RmDir может не удастся удалить т.к. у нее будет стоять атрибут Только чтение. Можно конечно снять этот атрибут программным путем, но давай сделаем проще и безопаснее, программа будет сообщать о невозможности удаления.
{ 21 } begin
{ 34 } result := false; // значит папка не пуста.
{ 22 } // если это папка
{ 23 } if ((SR.Attr and $10) = $10 ) then
{ 24 } begin // рекурсивный вызов функции
{ 25 } if DelEmtyDir( Target+'\'+ SR.Name)
{ 26 } then
{ 27 } begin // удаление пустой папки
{ 28 } RmDir(Target+'\'+ SR.Name);
if IOResult = 0
{ 29 } then inc(count) // + 1 в счетчик
else ShowMessage('Не могу удалить папку '+Target+'\'+ SR.Name);
{ 30 } end;
{ 31 } end;
{ 38 } end;
|go| Все. Теперь работает. Претензий нет.
|t_| Да? А мне вот, не нравится. Программа удаляет с компьютера, что-то не спросив разрешения, а может эта папка и пустая необходима.
Давай переделаем программу.
Вместо одной кнопки - две: Сканирование и Удаление.
И CheckListBox для хранения найденных пустых папок.
|go| Как опять все сначала?
|t_| Ну, не совсем сначала. Кстати вот один из критериев оценки качества программы - легкость ее модификации...
Вот, что у меня получилось:
// начало кода
{ 0 } unit Unit1;
{ 1 }
{ 2 } interface
{ 3 }
{ 4 } uses
{ 5 } Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
{ 6 } Dialogs, StdCtrls, FileCtrl, CheckLst, ExtCtrls;
{ 7 }
{ 8 } type
{ 9 } TForm1 = class(TForm)
{ 10 } Panel1: TPanel;
{ 11 } Button1: TButton;
{ 12 } Button2: TButton;
{ 13 } CheckListBox1: TCheckListBox;
{ 14 } Label1: TLabel;
{ 15 } procedure Button1Click(Sender: TObject);
{ 16 } procedure FormCreate(Sender: TObject);
{ 17 } procedure Button2Click(Sender: TObject);
{ 18 } private
{ 19 } { Private declarations }
{ 20 } public
{ 21 } { Public declarations }
{ 22 } end;
{ 23 }
{ 24 } var
{ 25 } Form1: TForm1;
{ 26 } Path : AnsiString; // путь к папке с программой
{ 27 } Dir : AnsiString;
{ 28 } CCount : integer; // счетчик удалений
{ 29 }
{ 30 } implementation
{ 31 }
{ 32 } {$R *.dfm}
{ 33 }
{ 34 } function ScanEmtyDir(Target : AnsiString):boolean;
{ 35 } var
{ 36 } Found : integer; // результат поиска ( 0 - файл найден )
{ 37 } SR : TSearchRec; // запись с параметрами файла
{ 38 } begin
{ 39 } Found := FindFirst(Target + '\*.*',$3F,SR);
{ 40 } result := true; // предположим что папка пуста.
{ 41 } WHILE Found = 0 DO
{ 42 } BEGIN
{ 43 } if (SR.Name <> '.')
{ 44 } and (SR.Name <> '..')
{ 45 } then
{ 46 } begin
{ 47 } result := false; // значит папка не пуста.
{ 48 } // если это папка
{ 49 } if ((SR.Attr and $10) = $10 ) then
{ 50 } begin // рекурсивный вызов функции
{ 51 } if ScanEmtyDir( Target+'\'+ SR.Name)
{ 52 } then // удаление пустой папки
{ 53 } begin
{ 54 } with Form1.CheckListBox1 do
{ 55 } Checked[Items.Add(Target+'\'+ SR.Name)] := true;
{ 56 } end;
{ 57 } end;
{ 58 } end;
{ 59 } Found := FindNext(SR);
{ 60 } END;{DosError = 0}
{ 61 } FindClose(SR);
{ 62 } end;
{ 63 }
{ 64 } procedure TForm1.Button1Click(Sender: TObject);
{ 65 } begin
{ 66 } if SelectDirectory(Dir, [sdAllowCreate, sdPerformCreate, sdPrompt],0)
{ 67 } then
{ 68 } begin
{ 69 } if Dir[length(Dir)]='\'
{ 70 } then delete(Dir, length(Dir),1);
{ 71 } CheckListBox1.Items.Clear;
{ 72 } ScanEmtyDir(Dir);
{ 73 } Label1.Caption := 'Найдено '+ IntToStr(CheckListBox1.Items.Count)
{ 74 } +' пустых папок.';
{ 75 } end;
{ 76 } end;
{ 77 }
{ 78 } procedure TForm1.FormCreate(Sender: TObject);
{ 79 } begin
{ 80 } Path := ExtractFileDir(ParamStr(0)) + '\';
{ 81 } Dir := Path;
{ 82 } end;
{ 83 }
{ 84 } procedure TForm1.Button2Click(Sender: TObject);
{ 85 } var
{ 86 } i : integer;
{ 87 } begin
{ 88 } CCount := 0;
{ 89 } with Form1.CheckListBox1 do
{ 90 } begin
{ 91 } for i := Items.Count - 1 downto 0 do
{ 92 } if Checked[i] then
{ 93 } begin
{ 94 } RmDir(Items[i]);
{ 95 } if IOResult = 0
{ 96 } then
{ 97 } begin
{ 98 } inc(CCount); // + 1 в счетчик
{ 99 } Items.Delete(i);
{ 100 } end;
{ 101 } end;
{ 102 } if Items.Count = 0
{ 103 } then ShowMessage('Удалено ' + IntToStr(CCount) +' папок.')
{ 104 } else ShowMessage('Не могу удалить '+intToStr(Items.Count)+' папок');
{ 105 } end;
{ 106 } end;
{ 107 }
{ 108 } end.
// конец кода
Скопируй сей текст в какой либо файл и давай на него посмотрим.
|go| Готово.
У матросов есть вопросов.
Я понял, почему ты переназвал функцию ScanEmtyDir, но почему наименование счетчика сменилось на Ccount
|t_| Сменил, чтобы не было конфликта имен с списком CheckListBox1, тут я немного схалтурил, рекомендуется давать осмысленные имена, ну бывает, поленился.
|go| Я не понял эти строки:
{ 54 } with Form1.CheckListBox1 do
{ 55 } Checked[Items.Add(Target+'\'+ SR.Name)] := true;
|t_| Это можно было бы написать более подробно (и более понятно)
var n : integer; // номер строки в списке
...
n := Form1.CheckListBox1. Items.Add(Target+'\'+ SR.Name);
Form1.CheckListBox1.Checked[n] := true;
Но мне не хотелось вводить совершенно лишнюю переменную.
|go| Хорошо, а что это за загадочные точки в строках 43 и 44
{ 43 } if (SR.Name <> '.')
{ 44 } and (SR.Name <> '..')
|t_| Это особенности операционной системы, две точки это обращение к родительской папке, а одна это обращение к текущей папке.
Давай сделаем маленький эксперимент.
В любой папке создай текстовый файл.
Скопируй в него следующий текст
rem начало кода
cd ..
dir
pause
rem конец кода
сохрани изменения.
теперь переименуй файл, ну например proba.bat
Вся соль тут в расширении.
Запусти файл на исполнение.
В окошке с заголовком cmd.exe ты увидишь распечатку содержимого родительского (для текущего каталога) каталога { кстати, обрати внимание я сразу сбился на досовскую терминологию, напомню, каталог это папка }
И вот смотри, вверху, те самые точки. Т.е. операционная система при поиске всегда выдает ссылки на текущую и родительские папки, но нам они абсолютно не нужны и посему мы исключаем их из рассмотрения.
Do you understand?
|go|Oh! Yes, yes!
А как насчет строчки 49
{ 49 } if ((SR.Attr and $10) = $10 ) then
|t_| Ты возможно заметил что в предыдущей строке комментария, дается расшифровка этой строки
{ 48 } // если это папка
Но все таки давай разберемся подробнее.
Во первых, открою тебе великую тайну. Папка (folder, каталог, директорий) на самом деле это файл.
Да, это просто файл, и отличается он от других только атрибутом. Вот теперь мы добрались до атрибутов.
Вызови help на слове TsearchRec и ты увидишь(кроме всего прочего) :
faReadOnly $00000001 Read-only files
faHidden $00000002 Hidden files
faSysFile $00000004 System files
faVolumeID $00000008 Volume ID files
faDirectory $00000010 Directory files
faArchive $00000020 Archive files
faAnyFile $0000003F Any file
Нас интересует faDirectory но у папки могут быть установлены и другие атрибуты, а устанавливаются они сложением соответствующих значений.
Значит для определения, что рассматриваемый файл является папкой сказать
if SR.Attr = $10
будет неправильно, т.к. $11, $12, $13, $14, $15 ... - это тоже папки.
Поэтому лучше сначала обрезать значение с помощью &
В результате операции SR.Attr and $10 останется или 0 или $10, и это мы проконтролируем.
|go| Чёто сложновато.
|t_| Ну, я тут немножко повыёживался, не очень подробно объясняю.
Но, я хотел подвести к морали: программист должен очень много знать. В том числе работу операционной системы, и, а это святое - алгебру логики.
|go| Намек понял, не дурак. Надо подучить.
|t_| Ну, что ж, давай на этой оптимистичной ноте, заканчивать сегодняшнее занятие.
Сегодня мы сделали полезную, но, не очень необходимую утилитку.
В следующий раз мы будем продолжать тему "Рекурсия", я предлагаю сделать программку имитирующую windows Поиск, но с бОльшими возможностями:
Поиск регулярных выражений
Поиск в найденном
Сохранение и Загрузка списка найденных файлов
See you later.
|go| До связи.
Примечания
1
Как получить исходник из этой книги, описано в "Извлекаем архив из fb2"
(обратно)
Комментарии к книге «Рекурсия», Юрий Карпов
Всего 0 комментариев