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

На каждом шаге цикла выполняется две проверки. Для упрощения проверок в конец массива 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

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. Шейкерная сортировка

Отсортировать массив 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;

6.5. Файлы

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

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

описать файловый указатель;
связать файловый указатель с именем файла;
объявить новый файл или существующий;
записывать данные или читать их;
закрыть файл.

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

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

№	Назначе-ние	Текстовые	Типизирован-ные	Нетипизирован-ные
1	Указатель	F: textfile	F: file of ТИП X: ТИП	F: file
2	Связать	AssignFile(f,name)	AssignFile(f, name)	AssignFile(f,name)
3	Объявить Существу-ющий	Reset(f), Append(f)	Reset(f)	Reset(f,1)
3	Объявить новый	Rewrite(f)	Rewrite(f)	Rewrite(f,1)
4	Чтение	Read(f,список) Readln(f,список)	Read(f,x)	BlockRead (f,buf,SizeOf(buf), NumRead)
4	Запись	Write(f,список) Writeln(f,список)	Write(f,x)	BlockWrite (f,buf,SizeOf(buf), NumWrite)
5	Закрыть	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)	Возвращает текущий размер файла; не использовать для текстовых файлов.
Flush (var F: Text)	Сбрасывает буфер выходного текстового файла.
GetDir (D: Byte; var S: string)	Возвращает текущий директорий указанного логического диска.
IOResult: Integer	Возвращает целую величину, которая является статусом последней выполненной функции ввода/вывода.
MkDir (S: string)	Создает поддиректорий.
Read (F , V1 [, V2,...,Vn ] )	Читает одну или более величин из файла в одну или более переменных.
Readln ([ var F: Text; ] V1 [, V2, ...,Vn ])	Выполняет Read и затем переходит к началу следующей строки в текстовом файле.
Rename (var F; Newname)	Переименовывает файл.
Reset (var F [: File; RecSize: Word ] )	Открывает существующий файл.
Rewrite (var F [: File; RecSize: Word ] )	Создает и открывает новый файл.
RmDir (S: string)	Удаляет пустую папку.
Seek (var F; N: Longint)	Перемещает текущую позицию типизированного или нетипизированного файла. Не используется для текстовых файлов.
SeekEof [ (var F: Text) ]	Возвращает статус конца текстового файла.
SeekEoln [ (var F: Text) ]	Возвращает статус конца строки текстового файла.
SetTextBuf (var F: Text; var Buf [ ; Size: Integer] )	Назначает буфер I/O для текстового файла.
Truncate (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-}.