Часть 2-Основы программирования (Delphi)

ею как одна длинная строка, содержащая текстовые представления чисел. В сочетании с проверкой конца файла функцией eof процедура Read позволяет организовать простой ввод массивов данных, например, так:

const

N = 1000; // Максимальная длина ввода

var

F : TextFile;

М : array [1..N] of Real; i : Integer;

begin

AssignFile(F, 'prog.dat'); Reset(F);

i := 1;

while not EOF(f) and (i <= N) do begin

Read(F, M[i]); inc (i)

end;

CloseFile(F);

end;

Процедура ReadLn идентична процедуре Read за исключением того, что после считывания последней переменной оставшаяся часть строки до маркера EOLN пропускается, поэтому следующее обращение к ReadLn начинается с первого символа новой строки. Кроме того, эту процедуру можно вызвать без параметров Vi, что приведет к пропуску всех символов текущей строки вплоть до EOLN.

Процедура Write обеспечивает вывод в текстовый файл группы переменных. Любой элемент списка вывода может иметь форму

OutExpr[ : MinWidth [ : DecPlaces ] ]

Здесь OutExpr - выводимое выражение; MinWidth, DecPlaces - выражения типа Integer (квадратные скобки означают возможность отсутствия заключенных в них параметров). Параметр MinWidth, если он присутствует, указывает минимальную ширину поля, в которое будет записываться символьное представление значения OutExpr. Если символьное представление имеет меньшую длину, чем MinWidth, оно будет дополнено слева пробелами, если большую длину, то MinWidth игнорируется и в файл помещается необходимое число символов. Параметр DecPlaces задает количество десятичных знаков в дробной части вещественного числа. Он может использоваться только совместно с MinWidth и только по отношению к выводимому выражению одного из вещественных типов.

Если ширина поля вывода не указана, соответствующий параметр выводится вслед за предыдущим без какого-либо их разделения. Символы и строки передаются выводному файлу без изменений, но снабжаются ведущими пробелами, если задана ширина поля вывода и эта ширина больше требуемой для вывода.

При выводе логических выражений в зависимости от их значения выводятся слова True или False. (Ввод логических констант процедурами Read или ReadLn не предусмотрен.)

Вещественные числа выводятся в экспоненциальном формате, если не указан параметр DecPlaces, в противном случае выбирается формат представления числа с фиксированной точкой. Если подпараметр MinWidth опущен, принимается его значение по умолчанию (23). Если MinWidth меньше 10, считается, что он равен 10.

Если подпараметр DecPlaces равен нулю, ни дробная часть числа, ни десятичная точка не выводятся. Если значение DecPlaces больше 18, принимается значение 18. Следует учесть, что при указании подпараметра DecPlaces вещественное число всегда будет выводиться в формате с фиксированной точкой и требуемым количеством знаков в дробной части, даже если значение подпараметра MinWidth окажется недостаточным для размещения целой части: в этом случае значение MinWidth автоматически увеличивается.

Процедура WriteLn полностью идентична процедуре Write за исключением того, что выводимая последовательность символов автоматически завершается маркером EOLN (свое название процедура получила от Write Line - писать строку). При вызове WriteLn можно опускать параметры Vi - в этом случае в файл передается пустая строка.

Типизированные файлы

Длина любого компонента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому из них (т. е. доступ к компоненту по его порядковому номеру).

Перед первым обращением к процедурам ввода-вывода указатель файла стоит в его начале и указывает на первый компонент с номером 0. После каждого чтения или записи указатель сдвигается к следующему компоненту файла. Переменные в списках ввода-вывода должны иметь тот же тип, что и компоненты файла. Если этих переменных в списке несколько, указатель будет смещаться после каждой операции обмена данными между переменными и дисковым файлом.

Рассмотрим некоторые подпрограммы для работы с типизированными файлами.

Function FILEPOS Возвращает текущую позицию в файле, т. е. номер компонента, (var F): Longint; который будет обрабатываться следующей операцией ввода-

вывода

Function FILESIZE Возвращает количество компонентов файла

(var F): Longint;

Procedure SEEK (var Смещает указатель файла F к требуемому компоненту файла с F; N: Longint); номером N (первый компонент файла имеет номер 0)

Procedure READ (var Читает данные из типизированного файла F; Vi – переменные F, V1,..., Vn); такого же типа, что и компоненты файла

Procedure WRITE Записывает данные в типизированный файл F; Pi - выражения (var F, P1, ..., Pn); такого же типа, что и компоненты файла

Чтобы переместить указатель в конец типизированного файла, можно написать:

Seek (FileVar, FileSize(FileVar));

Нетипизированные файлы

Нетипизированные файлы объявляются как файловые переменные типа File и отличаются тем, что для них не указан тип компонентов. Отсутствие типа делает эти файлы, с одной стороны, совместимыми с любыми другими файлами, а с другой - позволяет организовать высокоскоростной обмен данными между диском и памятью.

При инициации нетипизированного файла процедурами Reset или Rewrite можно указать длину записи нетипизированного файла в байтах. Например, так:

var

F: File; begin

AssignFile(F,'myfile.dat');

Reset(f,512);

end;

Длина записи нетипизированного файла указывается вторым параметром при обращении к процедурам Reset или Rewrite, в качестве которого может использоваться выражение типа Longint. Если длина записи не указана, она принимается равной 128 байтам.

Object Pascal не накладывает каких-либо ограничений на длину записи нетипизированного файла, за исключением требования положительности и ограничения максимальной длины 2 Гбайт. Для обеспечения максимальной скорости обмена данными рекомендуется задавать длину, которая была бы кратна длине физического сектора дискового носителя информации (512 байт). Однако операции обмена данными с дисковыми устройствами в среде Windows кэшируются, т. е. осуществляются через промежуточный буфер памяти, поэтому обычно задают длину записи = 1, что позволяет обмениваться с файлом блоками любой длины, начиная с одного байта.

При работе с нетипизированными файлами могут применяться все процедуры и функции, доступные типизированным файлам, за исключением Read и Write, которые заменяются соответственно высокоскоростными процедурами BlockRead и BlockWrite:

Procedure BlockRead(var F: File; var Buf, Count: Integer [;var AmtTransferred: Integer]);

Procedure BlockWrite(var F: File; var Buf, Count: Integer [;var AmtTransferred: Integer]);

Здесь Buf – буфер – имя переменной, которая будет участвовать в обмене данными с дисками; Count - количество записей, которые должны быть прочитаны или записаны за одно обращение к диску; AmtTransferred - необязательный параметр, содержащий при выходе из процедуры количество фактически обработанных записей.

За одно обращение к процедурам может быть передано до Count*RecSize байт, где RecSize - длина записи нетипизированного файла. Передача идет начиная с первого байта переменной Buf. Программист должен позаботиться о том, чтобы длина внутреннего представления переменной Buf была достаточной для размещения всех Count*RecSize байт при чтении информации с диска. Если при чтении указана переменная недостаточной длины или если в процессе записи на диск не окажется нужного свободного пространства, возникнет ошибка вводавывода, которую можно заблокировать, указав необязательный параметр

AmtTransferred.

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

•Глава . СОРТИРОВКА МАССИВОВ

При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя: количество присваиваний, количество сравнений.

Все методы сортировки можно разделить на две большие группы: прямые методы сортировки, улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе метода, разделяются на три подгруппы:

1)сортировка вставкой (включением);

2)сортировка выбором (выделением);

3)сортировка обменом («пузырьковая» сортировка).

Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы.

Сортировка вставкой

Принцип метода: массив разделяется на две части – отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные элементы.

Таким образом, алгоритм будет состоять из n-1-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:

–взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;

–поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

–сдвиг элементов массива от j-го до i-1-го вправо, чтобы освободить найденную позицию вставки;

–вставка взятого элемента в найденную j-ю позицию.

Запишем одну из возможных программных реализаций метода сортировки вставкой:

For i:=2 to n do Begin

b:=a[i];

j:=1;

While (b>a[j]) do j:=j+1;

For k:=i-1 downto j do a[k+1]:=a[k]; a[j]:=b;

End;

Улучшением метода сортировки вставками является сортировка Шелла

– сортировка с убывающим шагом. В этом методе сначала сортируются элементы, отстоящие друг от друга на расстоянии K. Значение K называется шагом. Первый проход в этом методе упорядочивает элементы каждой получающейся части массива. После этого выбирается некоторое новое меньшее значение K, и данный массив снова разделяется на новый набор частей массива. Каждая из этих частей сортируется, и процесс повторяется с еще меньшим значением K. В конце концов K становится равным 1, и тогда сортируется весь массив.

Например, первоначальный массив имеет вид: 24 58 42 37 11 89 76 32

Выбрана последовательность шагов (5, 3, 1). При первом проходе сортируются следующие части:

a[1], a[6]; a[2], a[7]; a[3], a[8]; a[4]; a[5]

При втором проходе (шаг = 3):

a[1], a[4], a[7]; a[2], a[5], a[8]; a[3], a[6]

При третьем проходе (шаг =1):

a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8]

Поскольку первый шаг является достаточно большим, то отдельные части массива становятся малыми, и сортировка вставками над этими частями работает быстро. При каждом просмотре массив становится все более отсортированным, поэтому сортировка вставками становится достаточно эффективной. Необходимо отметить, что частично отсортированный массив с шагом K не будет нарушаться последующими сортировками с более малыми шагами. Желательно, чтобы все шаги в сортировке были взаимно простыми числами. Это гарантирует то, что последующие частичные сортировки перемешивают части массива так, что при шаге, равном 1, весь массив является почти отсортированным.

Сортировка выбором

Принцип метода: находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Запишем одну из возможных программных реализаций метода сортировки выбором:

For s:=1 to n-1 do Begin min:=a[s]; imin:=s;

For i:= s+1 to n do

If a[i]<min then Begin min:=a[i]; imin:=i; End;

a[imin]:=a[s];

a[s]:=min;

End;

Сортировка обменом («пузырьковая» сортировка)

Принцип метода: слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход.

Запишем одну из возможных программных реализаций метода сортировки обменом (метода «пузырька»):

For k:=n downto 2 do For i:=1 to k-1 do

If a[i]>a[i+1] then Begin b:=a[i]; a[i]:=a[i+1]; a[i+1]:=b; End;

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

направление последовательных просмотров. Такой метод получил название «шейкерной» сортировки. «Шейкерная» сортировка с успехом используется в тех случаях, когда известно, что элементы почти упорядочены.

Сравнение прямых методов сортировки

Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька»).

Поиск

Поиск в неупорядоченном массиве

Если массив неупорядочен, то приходится просматривать в худшем случае весь массив, чтобы найти необходимую информацию, либо убедиться, что ее там нет.

Бинарный поиск в упорядоченном массиве

Алгоритм поиска таков: упорядоченный массив делится пополам, и искомый элемент сравнивается со средним элементом этого массива. Если равенство удовлетворяется, то поиск прекращается, в противном случае искомый элемент сравнивается со средним элементов левого или правого подмассива, в зависимости от того, в какой из них попадает искомый элемент (напомним, что массив упорядочен). Таким образом, либо элемент очень быстро находится, либо исходный массив очень быстро исчерпывается.

i:=1; j:=n; Repeat

k:=(i+j) div 2;

If x<a[k] then j:=k-1 else i:=k+1; Until (i>j) or (x=a[k]);

Сравним скорость поиска в обычном и в упорядоченном массивах. В неупорядоченном массиве, состоящем из 1000 элементов, в среднем надо произвести 500 сравнений, в худшем случае – 1000 сравнений. В упорядоченном массиве искомый элемент находится (если он там есть) максимум за 7 сравнений.

...

Подпрограмма любого уровня имеет обычно множество имен констант, переменных, типов и вложенных в нее подпрограмм низшего уровня. Считается, что все имена, описанные внутри подпрограммы, локализуются в ней, т. е. они как бы “невидимы” снаружи подпрограммы. Таким образом, со стороны операторов; использующих обращение к подпрограмме, она трактуется как “черный ящик”, в котором реализуется тот или иной алгоритм. Все детали этой реализации скрыты от глаз пользователя подпрограммы и потому недоступны ему. Например, в рассмотренном выше примере из основной программы можно обратиться к процедурам A и B, но нельзя вызвать ни одну из вложенных в них процедур A1, А2, В1 и т. д.

Сказанное относится не только к именам самих подпрограмм, но и вообще к любым объявленным в них именам - типам, константам, переменным и меткам. Все имена в пределах подпрограммы, в которой они объявлены, должны быть уникальными и не могут совпадать с именем самой подпрограммы.

При входе в подпрограмму низшего уровня становятся доступными не только объявленные в ней имена, но и сохраняется доступ ко всем именам верхнего уровня. Образно говоря, любая подпрограмма как бы окружена полупрозрачными стенками: снаружи подпрограммы мы не видим ее внутренности, но, попав в подпрограмму, можем наблюдать все, что делается снаружи. Так, например, из подпрограммы В21 мы можем вызвать подпрограмму A, использовать имена, объявленные в основной программе, в подпрограммах B и B2, и даже обратиться к ним. Любая подпрограмма может, наконец, вызвать саму себя - такой способ вызова называется рекурсией.

Пусть имеем такое описание: var V1 : ... ;

Procedure A;

var V2 : ...; end {A};

Procedure В;

var V3 : . . . ;

Procedure B1;

var V4 : . . . ;

Procedure В11;

var V5 : . . . ;

Из процедуры B11 доступны все пять переменных V1, ..., V5, из процедуры B1 доступны переменные V1, ..., V4, из центральной программы – только V1.

При взаимодействии подпрограмм одного уровня иерархии вступает в силу основное правило Object Pascal: любая подпрограмма перед ее использованием должна быть описана. Поэтому из подпрограммы B можно вызвать подпрограмму A, но из A вызвать B невозможно (точнее, такая возможность появляется только с использованием опережающего описания). Продолжая образное сравнение, подпрограмму можно уподобить ящику с непрозрачными стенками и дном и полупрозрачной крышей: из подпрограммы можно смотреть только “вверх” и нельзя “вниз”, т. е. подпрограмме доступны только те объекты верхнего уровня, которые описаны до описания данной подпрограммы. Эти объекты называются глобальными по отношению к подпрограмме.