Завершение работы цикла гарантировано, т.к. A1<m<A2, A1 – увеличивается, A2 - уменьшается. Ожидаемое число шагов – logN.
В массиве упорядоченных строк 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;
В строке 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);
Отсортировать массив 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;
Отсортировать массив A: array[1..N] of ТИП.
Листинг. Шейкерная сортировка.
L:=2; R:=N; k:=N;
repeat
for j:=R downto L do
if A[j-1]>A[j] then begin
t:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;
end;
L:=k+1;
for j:=L to R do
if A[j-1]>A[j] then begin
T:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;
end;
R:=k-1;
until L>R;
Существует три традиционных способа доступа к информации в файле: файл может быть открыт как текстовый, как типизированный и как нетипизированный. Текстовые файлы могут содержать признак конца строки (символы с кодами #13#10) и признак конца файла (символ с кодом #27). Типизированные файлы допускают запись и чтение данных порциями одинаковой длины. Структура этой порции определяется при объявлении файлового указателя. Нетипизированные файлы используются для быстрой записи и копирования данных.
При работе с любым типом данных необходимо обязательно выполнить 5 действий:
· описать файловый указатель;
· связать файловый указатель с именем файла;
· объявить новый файл или существующий;
· записывать данные или читать их;
· закрыть файл.
Ниже в таблице 6.1 приведены процедуры и функции, позволяющие реализовать эти действия для всех типов файлов.
Таблица 6.1. Основные действия с файлами
№
Назначе-ние
Текстовые
Типизирован-ные
Нетипизирован-ные
Указатель
F: textfile
F: file of ТИП
X: ТИП
F: file
Связать
AssignFile(f,name)
AssignFile(f, name)
AssignFile(f,name)
Объявить
Существу-ющий
Reset(f), Append(f)
Reset(f)
Reset(f,1)
Объявить новый
Rewrite(f)
Rewrite(f)
Rewrite(f,1)
Чтение
Read(f,список)
Readln(f,список)
Read(f,x)
BlockRead (f,buf,SizeOf(buf), NumRead)
Запись
Write(f,список)
Writeln(f,список)
Write(f,x)
BlockWrite (f,buf,SizeOf(buf), NumWrite)
Закрыть
CloseFile(f)
CloseFile(f)
CloseFile(f)
Файловый указатель f – любая переменная файлового типа: текстового, типизированного и нетипизированного.
Перед использованием файловой переменной, она должна быть связана с внешним файлом с помощью процедуры AssignFile. Под внешним файлом понимается файл на диске, но это также может быть устройство, например, клавиатура или дисплей.
Если связь с внешним файлом установлена, файловая переменная должна "быть открыта", чтобы подготовить его для чтения или записи. Существующий файл может открываться с помощью процедуры Reset, которая устанавливает файловый указатель в начало файла. Существующий текстовый файл также может открываться с помощью процедуры Append, которая устанавливает файловый указатель в конец файла. Новый файл может создаваться и открываться процедурой Rewrite. Текстовые файлы, открываемые Reset, предназначены только для чтения, а текстовые файлы открытые Rewrite или Append предназначены только для записи. Типизированные файлы и нетипизированные файлы допускают как чтение, так и запись независимо от того, как они открывались Reset или Rewrite.
Каждый файл – линейная последовательность компонентов, которая имеет тип компонента (или тип записи). Нумерация записей начинается с нуля.
Файлы доступны последовательно. При чтении компонента с помощью процедуры Read и при записи процедурой Write, файловый указатель переходит на следующий компонент. Типизированные файлы и нетипизированные файлы могут быть доступными произвольно с помощью процедуры Seek, которая перемещает файловый указатель на указанный компонент. Функции FilePos и FileSize позволяют определять текущую файловую позицию и размер файла.
Когда программа завершает обработку файла, файл должен быть закрыт процедурой CloseFile. После того, как файл закроется, связанный внешний файл будет скорректирован. Файловая переменная может затем связываться с другим внешним файлом.
Помимо основных процедур, представленных в табл. 6.1, существует достаточно много других процедур и функций, предназначенных для работы с файлами. Некоторые из них представлены в табл. 6.2:
Таблица 6.2. Другие процедуры и функции
Процедуры или функции
Описание
Append (var F: Text)
Открывает существующий текстовый файл для добавления
AssignFile(var F; FileName: string)
Назначает имя файла в файловую переменную
BlockRead (var F: File; var Buf; Count:Integer[;var AmtTransferred: Integer])
Читает одну или более записей из нетипизированного файла.
BlockWrite (var f: File; var Buf; Count: Integer[;var AmtTransferred: Integer])
Пишет одну или более записей в нетипизированный файл.
ChDir (S: string)
Изменяет текущий директорий.
CloseFile (var F)
Закрывает открытый файл.
Eof(var F)
Возвращает статус конца файла
Eoln [(var F: Text) ]
Возвращает статус конца строки текстового файла.
Erase (var F)
Удаляет файл.
FilePos(var F)
Возвращает текущую файловую позицию типизированного или нетипизированного файла
FileSize(var F)
Возвращает текущий размер файла; не использовать для текстовых файлов.
Отсекает типизированный или нетипизированный файл с текущей позиции.
Write (F, V1,...,Vn)
Пишет одну или более величин в файл.
Writeln ([var F: Text;] P1 [,P2, ...,Pn] )
Выполняет Write и затем пишет признак конца строки в текстовый файл.
По умолчанию, все вызовы стандартных процедур и функций ввода/вывода (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-}.
