Файл: Лекция 10.doc

Лекция 10

6.4. Простейшие алгоритмы

6.4.1. Поиск

6.4.1.1. Линейный поиск

В массиве A: array[iMin..iMax] of ТИП найти элемент равный B.

Листинг. Алгоритм линейного поиска

i:=iMin;

while (i<iMax) and (A[i]<>B) do i:=i+1;

Цикл while завершит свою работу либо при нахождении элемента равного B, либо при переборе всех элементов массива.

На каждом шаге цикла выполняется две проверки. Для упрощения проверок в конец массива A: array[iMin..iMax+1] of ТИП добавляется барьер - элемент равный B.

Листинг. Алгоритм линейного поиска с барьером

i:=iMin; A[iMax+1]:=B;

while A[i]<>B do i:=i+1;

Завершение работы цикла гарантировано, т.к. элемент B в массиве всегда есть. Ожидаемое число шагов – N/2.

6.4.1.2. Поиск делением пополам

В упорядоченном массиве A: array[iMin..iMax] of ТИП найти элемент равный B.

Листинг. Алгоритм поиска деления пополам

A1:=iMin; A2:=iMax; Ok:=false;

while (A1<=A2) and not Ok do

begin

m:=(A1+A2) div 2;

if A[m]=B then Ok:=true

else

if A[m]<B then A1:=m+1 else A2:=m-1;

end;

Листинг. Упрощенный алгоритм поиска деления пополам

A1:=iMin; A2:=iMax;

while A1<A2 do begin

m:=(A1+A2) div 2;

if A[m]=B then begin

A1:=m; A2:=m;

end

else

if A[m]<B then A1:=m+1 else A2:=m;

end;

Завершение работы цикла гарантировано, т.к. A1<m<A2, A1 – увеличивается, A2 - уменьшается. Ожидаемое число шагов – logN.

6.4.1.3. Поиск в массиве строк

В массиве упорядоченных строк AStr: array[iMin..iMax] of string найти строку St: string.

Воспользуемся поиском деления пополам:

Листинг. Поиск в массиве строк

A1:=iMin; A2:=iMax;

while A1<A2 do

begin

m:=(A1+A2) div 2; i:=0;

while (AStr[m,i]=St[i]) and (St[i]<>#0) do i:=i+1;

if AStr[m,i]<St[i] then A1:=m+1 else A2:=m;

end;

if A2<iMax then begin

i:=0;

while (AStr[A2,i]=St[i]) and (St[i]<>#0) do i:=i+1;

end;

6.4.1.4. Прямой поиск строки

В строке s: string[N] найти строку s0: string[M].

Листинг. Прямой поиск строки

i:=0;

repeat

i:=i+1; j:=1;

while (j<M) and (s[i+j-1]=s0[j]) do j:=j+1;

until (j=M) or (i=N-M);

6.4.2. Сортировка

6.4.2.1. Пузырьковая сортировка

Отсортировать массив A: array[iMin..iMax] of ТИП.

Листинг. Пузурьковая сортировка.

for i:=iMin+1 to iMax do

for j:=iMax downto i do

if A[j-1]<A[j] then

begin

t:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;

end;

6.4.2.2. Шейкерная сортировка

Оптимизация предыдущего алгоритма включает в себя следующее:

• массив можно считать уже упорядоченным, если на последнем проходе не было ни одной перестановки элементов;

• сравнение пар элементов можно производить только до места последней перестановки: раз не было перестановок, значит – дальше элементы упорядочены;

• при прохождении массива слева направо (снизу вверх) поднимается легкий пузырек. Почему бы не двигаться по массиву в обратном направлении – сверху вниз, опуская тяжелый пузырек?

Эти моменты учтены в шейкер-сортировке (от англ. shake – трясти), приведенной в листинге 7.6.

Листинг. Шейкерная сортировка.

procedure SortShaker;

var

j,L,left,right: integer;

tmp : integer;

last : integer; // место последней перестановки

begin

L:=Length(A);

left:=1; right:=L-1; last:=L-1;

repeat

for j:=right downto left do //поднимаются легкие пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

left:=last+1; // запомнили место последней перестановки

for j:=left to right do //опускаются тяжелые пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

right:=last-1; // запомнили место последней перестановки

until left>right;

end; //Shaker

6.5. Файлы

Существует три традиционных способа доступа к информации в файле: файл может быть открыт как текстовый, как типизированный и как нетипизированный. Текстовые файлы могут содержать признак конца строки (символы с кодами #13#10) и признак конца файла (символ с кодом #26). Типизированные файлы допускают запись и чтение данных порциями одинаковой длины. Структура этой порции определяется при объявлении файлового указателя. Нетипизированные файлы используются для быстрой записи и копирования данных.

При работе с любым типом данных необходимо обязательно выполнить 5 действий:

• описать файловый указатель;

• связать файловый указатель с именем файла;

• объявить новый файл или существующий;

• записывать данные или читать их;

• закрыть файл.

Ниже в таблице 6.1 приведены процедуры и функции, позволяющие реализовать эти действия для всех типов файлов.

Таблица 6.1. Основные действия с файлами

Файловый указатель f – любая переменная файлового типа: текстового, типизированного и нетипизированного.

Перед использованием файловой переменной, она должна быть связана с внешним файлом с помощью процедуры AssignFile. Под внешним файлом понимается файл на диске, но это также может быть устройство, например, клавиатура или дисплей.

Если связь с внешним файлом установлена, файловая переменная должна "быть открыта", чтобы подготовить его для чтения или записи. Существующий файл может открываться с помощью процедуры Reset, которая устанавливает файловый указатель в начало файла. Существующий текстовый файл также может открываться с помощью процедуры Append, которая устанавливает файловый указатель в конец файла. Новый файл может создаваться и открываться процедурой Rewrite. Текстовые файлы, открываемые Reset, предназначены только для чтения, а текстовые файлы открытые Rewrite или Append предназначены только для записи. Типизированные файлы и нетипизированные файлы допускают как чтение, так и запись независимо от того, как они открывались Reset или Rewrite.

Каждый файл – линейная последовательность компонентов, которая имеет тип компонента (или тип записи). Нумерация записей начинается с нуля.

Файлы доступны последовательно. При чтении компонента с помощью процедуры Read и при записи процедурой Write, файловый указатель переходит на следующий компонент. Типизированные файлы и нетипизированные файлы могут быть доступными произвольно с помощью процедуры Seek, которая перемещает файловый указатель на указанный компонент. Функции FilePos и FileSize позволяют определять текущую файловую позицию и размер файла.

Когда программа завершает обработку файла, файл должен быть закрыт процедурой CloseFile. После того, как файл закроется, связанный внешний файл будет скорректирован. Файловая переменная может затем связываться с другим внешним файлом.

Помимо основных процедур, представленных в табл. 6.1, существует достаточно много других процедур и функций, предназначенных для работы с файлами. Некоторые из них представлены в табл. 6.2:

Таблица 6.2. Другие процедуры и функции

По умолчанию, все вызовы стандартных процедур и функций ввода/вывода (I/O) автоматически проверяются на ошибки, и если возникает ошибка, то происходит исключение (или программа прекращает свою работу, если не допускается исключительная обработка). Эта автоматически проверка может включаться и выключаться директивами компилятора {$I+} и {$I-}. Если проверка I/O выключена {$I-}, то при возникновении ошибки I/O исключительная обработка не вызывается и необходимо использовать стандартную функцию IOResult.

{$I-}

Reset(f);

{$I+}

if IoResult<>0 then Rewrite(f);

Необходимо вызвать функцию IOResult, для того чтобы очистить ошибку, даже если IOResult не используется. Иначе в состоянии {$I+} вызов следующей функции I/O потерпит неудачу с предыдущей ошибкой IOResult.

В таблице 6.3 приведены коды ошибок, возникающих при работе с файлами. Эти коды присваиваются свойству errorcode, если действует директива компилятору {$I+}, или возвращаются функцией IoResult, если действует директива компилятору {$I-}.

Таблица 6.3. Коды ошибок ввода/вывода

Контроль ошибок ввода/вывода необходим при создании приложений, работающих в локальной сети, когда необходимо обеспечить корректный доступ к одному файлу нескольких пользователей. При этом возникает проблема создания очереди, т.к. одновременный доступ к файлу нескольких приложений невозможен. Наиболее простой способ заключается в использовании цикла repeat:

{$I-}

repeat

Reset(f);

Until IoResult=0;

{$I+}

Этот цикл будет работать до тех пор, пока файл не освободится. Мы будем использовать эту технологию в примере, рассмотренном в пункте 6.5.5.

6.5.1. Текстовые файлы

Если текстовый файл открыт с файловым указателем типа FileText, внешний файл интерпретируется специальным образом: считается, что он представляет последовательность символов сформатированную в строки, где каждая строка заканчивается признаком конца строки (символ возврата каретки, возможно сопровождаемый символом перевода строки #13#10). Тип FileText в каком-то смысле соответствует типу file of Char.

Для текстовых файлов, есть специальные процедуры Read и Write, которые позволяют читать и записывать величины неcимвольного типа. Такие величины автоматически интерпретируются из их символьного представления. Например, Read(F,I), где I – переменная целого типа, читает последовательность цифр, интерпретирует эту последовательность как десятичное целое, и загружает это значение в переменную I.

Есть две стандартные текстфайловые переменные: Input и Output. Стандартная файловая переменная Input указывает на файл только для чтения, связываемый с операционным системным вводом (обычно клавиатурой). Стандартная файловая переменная Output указывает на файл только для записи, связываемый с операционным системным стандартным выводом (обычно дисплеем). Прежде, чем приложение начнет выполняться, файлы Input и Output автоматически открываются, как при выполнении следующих команд:

AssignFile(Input, '');

Reset(Input);

AssignFile(Output, '');

Rewrite(Output);

Примечание:

Текстовый ввод/вывод доступен только в консольных приложениях.

Некоторым стандартным процедурам I/O, работающим с текстовыми файлами, не нужно иметь файловую переменную, явно указанную как параметр. Если файловый параметр опускается, то по умолчанию принимаются Input или Output. Например, Read(X) соответствует Read(Input, X) и Write(X) соответствует Write(Output, X).

Принтер тоже может выступать как текстовый файл для записи. В этом случае вместо процедуры AssignFile(f,FileName) необходимо использовать AssignPrn. Например,

AssignPrn(f); Rewrite(f);

Writeln(f, 'Напечатана одна строка');

CloseFile(f);

Любой принтер управляется с помощью кодов символов и команд, отправляемых на принтер процедурой Write. Первые 32 кода таблицы кодов ASCII называются управляющими кодами. Так как этого количества не хватает для всех команд, то многие команды состоят из двух и более кодов. В этом случае последовательность управляющих кодов для принтера всегда начинается с кода 27. В системе ASCII для этого кода используется аббревиатура ESC, а сами команды называются ESC-последовательностями. Система команд зависит от типа принтера, но во многом эти команды совпадают. Ниже приводится система некоторых команд для принтера Epson FX-800.

Таблица 6.4. Команды для принтера Epson FX-800