Энциклопедия Turbo Pascal. Главы 1-4
ОГЛАВЛЕНИЕ
Эта книга поможет вам раскрыть на конкретных примерах большие возможности системы Турбо Паскаль. В каждой главе рассматривается определенная тема программирования и разрабатываются программы, относящиеся к этой теме. В ходе этого процесса вы увидите какие преимущества дает Турбо Паскаль при решении некоторых обычных задач программирования. В то же время вы сможете усовершенствовать свои программистские способности.
Глава 1 посвящена сортировке массивов и дисковых файлов. В главе 2 рассматриваются стеки, очереди, связанные списки и двоичные деревья. Такой диапазон вопросов, рассматриваемых в одной главе, может показаться слишком широким, однако предмет обсуждения обладает достаточной однородностью.
В главе 3 рассматриваются методы динамического управления памятью, а в главе 4 дается обзор принципов связи с операционной системой и с языком ассемблера. .
Поскольку Турбо Паскаль всегда отличался особенно высокой скоростью компиляции и эффективностью получаемого кода трудно было ожидать, что его можно будет каким-либо способом заметно улучшить. Однако с выходом Турбо Паскаля версии 4 значительно расширяется область применения Турбо Паскаля. Теперь и впервые программисты, использующие Турбо Паскаль, не ограничены 64К в отношении размера кода программы. Поскольку в версии 4.0 обеспечена раздельная компиляция и связь блоков размер программ ограничивается размером имеющейся памяти. В результате использования этих дополнительных возможностей некоторые программы, которые разрабатывались с применением первых версий системы Турбо Паскаль, не будут компилироваться в версии 4.0. Соответственно, некоторые программы, написанные для версии 4, не будут компилироваться в первых версиях системы Турбо Паскаль. Из-за важности использованных в Турбо Паскале версии 4 усовершенствований приводимые в этой книге примеры соответствуют версии 4. Таким образом, если вы используете первые версии системы Турбо Паскаль, то вам придется выполнить небольшие изменения в некоторых примерах. /Однако наилучшим выходом из положения является переход на более совершенную версию 4 Турбо Паскаля.
Глава 1. Сортировка и поиск
В информатике, по-видимому, нет более глубоко исследованных задач, чем задачи сортировки и поиска. Подпрограммы сортировки и поиска используются фактически во всех программах, работающих с базами данных, а также в компиляторах, интерпретаторах и в операционных системах. В этой главе рассматриваются основные вопросы сортировки и поиска. Сортировка рассматривается первой, поскольку она обычно делает поиск данных более простым и быстрым.
Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если
i <= i <= ... <= i
Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах. В этой главе рассматривается в основном сортировка первого вида, поскольку она представляет наибольший интерес для пользователей микрокомпьютеров. Однако в конце главы делается общий метод сортировки последовательных файлов.
Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляются полное имя и адрес. Для простоты в примерах, иллюстрирующих методы сортировки, используются символьные массивы. Затем будет показано, как эти методы можно адаптировать к любым структурам данных.
Классы алгоритмов сортировки
Имеется три способа сортировки массивов:
- сортировка обменом;
- сортировка выбором;
- сортировка вставкой.
Представьте, что перед вами лежит колода карт. Для сортировки карт обменом вы должны разложить карты на столе лицевой стороной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором вы должны разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем вы должны из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже имеется у вас в руке. Этот процесс вы должны продолжать до тех пор, пока все карты не окажутся у вас в руках. Поскольку каждый раз вы выбираете наименьшую по значению карту из оставшихся на столе, по завершению такого процесса карты у вас в руке будут отсортированы.
Для сортировки вставкой вы должны держать карты в своей руке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соответствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты.
Оценка алгоритмов сортировки
Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от ответов, которые будут получены на следующие вопросы:
- с какой средней скоростью этот алгоритм сортирует информацию?;
- какова скорость для лучшего случая и для худшего случсая?;
- поведение алгоритма является естественным или является неестественным?;
- выполняется ли перестановка элементов для одинаковых ключей.
Для конкретного алгоритма большое значение имеет скорость сортировки. Скорость, с которой массив может быть упорядочен, прямо зависит от числа сравнений и числа необходимых операций обмена, причем операции обмена занимают большее время. Ниже в этой главе будет показано, что для некоторых алгоритмов время сортировки зависит экспоненциально от числа элементов, а для других алгоритмов это время находится в логарифмической зависимости от числа элементов сортировки.
Время работы алгоритма для лучшего и худшего случаев важно учитывать, когда ожидается их частое появление. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худшего случая, и наоборот.
Считается поведение алгоритма сортировки естественным, если время сортировки наименьшее при упорядоченном списке элементов, время сортировки увеличивается при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. Время сортировки зависит от числа операций сравнения и операций обмена.
Для того, чтобы понять важность перегруппировки элементов с одинаковыми ключами сортировки, представим базу данных, которая упорядочена по основному ключу и дополнительному ключу. /Например, список почтовых отправлений с почтовым индексом в качестве основного ключа и фамилией в качестве дополнительного ключа в рамках одного почтового индекса/. Когда новый адрес добавляется в список и список вновь сортируется, вам не требуется перестановка дополнительных ключей. Для обеспечения этого сортировка не должна выполнять операции обмена для основных ключей с одинаковыми значениями.
В следующих разделах приводятся алгоритмы сортировки каждого класса и анализируется их эффективность. Каждая программа сортировки использует два типа данных, определенных пользователем, которые определяются следующим образом:
type
DataItem = char;
DataArray = array [1..80] of DataItem;
Следовательно, для изменения используемых в сортировках типов данных требуется изменить только эти два определения типов.
Размерность массива выбрана произвольно и вы можете при необходимости их изменить.
Сортировка пузырьковым методом
Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.
Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:
{ сортировка пузырьковым методом}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]>item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end; {конец сортировки пузырьковым методом}В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.
Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена.
Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Например, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки, которые приводятся в этой главе.
program SortDriver;
{эта программа будет считывать 80 или меньше символов
дискового файла "test.dat", отсортирует их и
выдаст pезультат на экран дисплея }type
DataItem = char;
DataArray = array [1..80] of char;
var
test: DataArray;
t, t2: integer;
testfile: file of char;
{ сортировка пузырьковым методом}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]>item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end;
begin
Assign(testfile, 'test.dat');
Reset(testfile);
t := 1;
{ считывание символов,которые будут сортироваться.}
while not Eof(testfile) do begin
read(testfile, test[t]);
t := t+1;
end;
t := t-2; {скорректировать число считанных элементов }
Bubble(test, t); { сортировать массив }
{ выдать отсортированный массив символов }
for t2 := 1 to t do write(test[t2]);
WriteLn;
end.
Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":
- исходное положение: d c a b;
- первый проход: a d c b;
- второй проход: a b d c;
- третий проход: a b c d.
При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n**2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу.
Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n**2-n), а для наихудшего случая будет равно 3/2 (n**2-n) раз. Вывод этих формул выходит за пределы этой книги. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива.
Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет пять секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5000000 секунд или около 1400 часов (т.е. два месяца непрерывной работы).
Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab")
достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.
Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
{ челночная сортировка является улучшенной версией сортировки пузырьковым методом }
procedure Shaker(var item: DataArray; count:integer);
var
j, k, l, r: integer;
x: DataItem;
begin
l := 2; r := count; k := count;
repeat
for j := r downto l do
if item[j-1] then
begin { обмен }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
l := k+1;
for j := l to r do
if item[j-1]>item[j] then
begin { обмен }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
r := k-1;
until l>r
end; { конец челночной сортировки }ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
Сортировка выбором
При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:
- исходное состояние: b d a c;
- первый проход: a d b c;
- второй проход: a b b c;
- третий проход: a b c d.
Ниже приводится простой алгоритм сортировки выбором /см. следующую страницу/.
К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
Это значит, что число сравнений для сортировки выбором равно 1/2
(n** 2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3 (n-1), а в худшем случае равно n**2/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1элементов,а каждая операция обмена требует три операции пересылки.
{ сортировка выбором }
procedure Selekt(var item: DataArray; count:integer);
var
i, j, k: integer;
x: DataItem;
begin
for i := i to count-1 do
begin
k := i;
x := item[i];
for j := i+1 to count do { найти элемент с наименьшим
значением }
if item[j]<x then
begin
k := j;
x := item[j];
end;
item[k] := item[i]; { обмен }
item[i] := x;
end;
end; { конец сортировки выбором }Вывод числа операций обмена для среднего случая выходит за рамки этой книги. Это число равно n(ln+y), где "y" является константой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.
Сортировка вставкой
Сортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом:
- исходное состояние: d c a b;
- первый проход: c d a b;
- второй проход: a c d b;
- третий проход: a b c d.
Ниже приводится алгоритм сортировки вставкой:
{ сортировка вставкой }
procedure Inser(var item: DataArray; count:integer);
var
i, l: integer;
x: DataItem;
begin
for i := 2 to count do
begin
x := item[i];
j := i-1;
while (x<item[j]) and (j>0) do
begin
item[j+1] := item[j];
j := j-1;
end;
item[j+1] := x;
end;
end; { конец сортировки вставкой }В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1. Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n**2 +n)-1,давая в среднем значение 1/4 (n**2+n-2).
Число операций обмена будет следующим:
- для лучшего случая: 2 (n-1);
- в среднем: 1/4 (n**2+9n-10);
- для худшего случая: 1/2 (n**2+3n-4).
Таким образом, число операций обмена для худшего случая будет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т.
е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.
Несмотря на то, что число сравнений может быть довольно небольшим для определенных наборов данных, постоянные сдвиги массива требуют выполнения большого числа операций пересылок. Однако, сортировка вставкой имеет естественное поведение, требуя наименьшее число операций обмена для почти упорядоченного списка и наибольшее число операций обмена, когда массив упорядочен в обратном направлении.
Усовершенствованные алгоритмы сортировки
Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины они будут слишком медленными, чтобы их можно было использовать на практике. Каждый программист слышал или рассказывал "страшные"
истории о "сортировке, которая выполнялась три дня". К сожалению эти истории часто не являлись выдумкой.
Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Однако, первая реакция на такое поведение сортировки выражается словами: "Давай напишем программу на ассемблере". Хотя использование ассемблера почти всегда позволяет повысить быстродействие программы в некоторое число раз с постоянным коэффициентом, но если выбранный алгоритм не является достаточно хорошим, то сортировка вне зависимости от оптимальности кода по-прежнему будет выполняться долго. Следует помнить, что при квадратичной зависимости времени выполнения программы от числа элементов массива повышение оптимальности кода или повышение быстродействия ЭВМ приведет лишь к незначительному улучшению, поскольку время выполнения программы будет увеличиваться по экспоненте. /Кривая, показанная на рис.1 лишь слегка сместится вправо, однако ее вид не изменится/. Следует помнить, что если какаялибо программа, написанная на языке Турбо Паскаль, выполняется недостаточно быстро, то она не станет выполняться достаточно быстро, если ее написать на ассемблере. Решение лежит в использовании лучшего алгоритма сортировки.
В этой главе будут рассмотрены две очень хорошие сортировки. Первая носит название сортировки Шелла, а вторая называется быстрой сортировкой, алгоритм которой признан наилучшим. Эти сортировки выполняются очень быстро.
Сортировка Шелла
Сортировка Шелла получила свое название по имени ее создателя Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга. ("Ракушка" - одно из значений слова
shell - Примеч. пер.)
Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. На рис.2 показана схема выполнения сортировки Шелла для массива "оасве". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
проход 1 f d a c b e
проход 2 c b a f d e
проход 3 a b c e d f
полученный результат a b c d e .
Сортировка Шелла:
{ сортировка Шелла }
procedure Shell(var item: DataArray; count:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (x<item[j]) and (j<count) do
begin
item[j+k] := item[j];
j := j-k;
end;
item[j+k] := x;
end;
end;
end; { конец сортировки Шелла }
При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно/.
Внутренний цикл имеет два условия проверки. Условие "х<item[j]" необходимо для упорядочения элементов. Условия "j>0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.
Анализ сортировки Шелла требует решения некоторых сложных математических задач, которые выходят за рамки этой книги. Время выполнения сортировки Шелла пропорционально n**1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.
Быстрая сортировка
Метод быстрой сортировки был разработан Ч.Ф.Р.Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.
В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива "fedacb" при использовании в качестве значения разбиения "d" будут получены следующие проходы при выполнении быстрой сортировки:
- исходное состояние: f e d a c b;
- первый проход: d c a d e f;
- второй проход: a b c d e f.
Этот процесс продолжается для каждой части "вса" и def". Фактически этот процесс имеет рекурсивную природу. И действтительно, наиболее "аккуратно" быстрая сортировка реализуется посредством рекурсивного алгоритма.
Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов. Однако, для большинства наборов данных это сделать нелегко. Однако, даже в худшем случае, когда выбирается одно из экстремальных значений, быстрая сортировка работает достаточно хорошо.
В приводимом ниже алгоритме быстрой сортировки в качестве значения разбиения используется среднее значение. Хотя такой подход не всегда является наилучшим, он достаточно прост и сортировка будет выполняться правильно.
{ быстрая сортировка }
procedure QuickSort(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it: DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i:=l; j:=r;
x:=it[(l+r) div 2];
repeat
while it[i]<x do i := i+1;
while x<it[j] do j := j-1;
if y<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end; { конец быстрой сортировки }В данном примере процедура быстрой сортировки обращается к основной процедуре сортировки с именем "qs". Это обеспечивает доступ к данным "item" и "count" при всех вызовах "qs".
Вывод числа операций сравнения и числа операций обмена для быстрой сортировки выходит за рамки данной книги. Можно считать, что число операций сравнения равно n log n, а число операций обмена равно приблизительно n/6 log n. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок.
Равенство
N = a**x
можно представить в виде
x = loga n.
Это, например, будет означать, чо при сортировке ста элементов методом быстрой сортировки потребуется в среднем 100*2, т.е. 200 операций сравнений, так как log 100 равен 2. Это значение является вполне хорошим по сравнению со значением 990 для сортировки пузырьковым методом.
Однако, следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n. Однако, на практике этот случай не встречается.
Необходимо тщательно выбирать метод определения значения разбиения. Часто это значение определяется по фактическим данным, которые сортируются. Для больших списков почтовых отправлений, когда сортировка часто делается по коду почтового индекса, значение для разбиения выбрать не сложно, так как коды почтовых индексов распределены достаточно равномерно и требуемое значение можно определить с помощью простой алгебраической процедуры. Однако, определенные базы данных могут иметь ключи сортировки с очень близкими значениями и поэтому наилучшим методом часто оказывается случайный выбор значения. Распространенный и достаточно эффективный метод заключается в выборке трех элементов из соответствующей области и вычисление их среднего значения.
Сортировка данных других типов
До сих пор рассматривались сортировки для символьных массивов. Это позволяло представлять алгоритмы сортировки в более простом виде. Как указывалось ранее, при сортировке могут использоваться массивы любых встроенных типов данных. Для этого достаточно изменить определение типа данного "DataItem". Однако, часто приходится сортировать сложные типы данных, например, символьные строки или сгруппированные в записи данные. (Напомним, что в большинстве сортировках упорядочиваются элементы, имеющие ключ, с которым связаны другие данные). Для того, чтобы настроить алгоритмы сортировки на другие структуры данных достаточно изменить блок сравнений, блок обмена или оба эти блока. Основа алгоритма остается неизменной.
Поскольку быстрая сортировка является одной из самых лучших, имеющихся в настоящее время сортировок, она будет использоваться в последующих примерах. Те же методы, однако, можно применять для любых ранее описанных сортировок.
Сортировка символьных строк
Для сортировки символьных строк проще всего создать массив символьных строк, используя предусмотренный в языке TURBOПаскаль тип данных "string". Это дает вам простой способ индексирования и выполнения операций обмена при сохранении основного алгоритма сортировки неизменным. Приводимая ниже версия алгоритма быстрой сортировки позволяет упорядочивать символьные строки в алфавитном порядке:
type
DataItem = string[80];
DataArray = array [1..80] of DataItem;
{ алгоритм быстрой сортировки для символьных строк }
procedure QsString(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it:DataArray);
var
i, l: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i] < x do i := i+1;
while x < it[j] do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it);
end;
begin
qs(1, count, item);
end; { конец быстрой сортировки }
Следует отметить, что потребовалось изменить только определение типа данного "DataItem" для того, чтобы настроить алгоритм быстрой сортировки на упорядочивание символьных строк. Это оказывается возможным благодаря превосходной работе, проделанной фирмой Borland по обеспечению использования в Паскале данных типа символьных строк. На стандартном Паскале запись алгоритма сортировки символьных строк была бы значительно длинее.
Следует учитывать, что операции сравнения символьных строк выполняются больше времени, чем операции сравнения символов, так как в первом случае каждый раз делается проверка нескольких элементов.
Сортировка записей
По-видимому в большинстве прикладных программ, где используется сортировка, требуется сортировать группы данных. Хорошим примером этого является список почтовых корреспонденций, поскольку в этом случае фамилия, улица, город, страна и почтовый индекс составляют связанную группу данных. При сортировке таких групп данных используется ключ сортировки в операциях сравнения, но в операциях обмена участвует вся запись целиком. Для того, чтобы лучше понять этот процесс сначала создадим запись, которая будет содержать необходимую информацию. Если в качестве примера использовать почтовый адрес, то запись может иметь следующий вид:
type
address = record
name: string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
end;
После описания адреса необходимо изменить следующим образом определение данного "DataItem":
DataItem = address;
После выполнения этих изменений нужно скорректировать блок сравнений в алгоритме быстрой сортировки, используя то поле, которое применяется в качестве ключа сортировки. В приводимой ниже версии быстрой сортировки в качестве ключа используется поле фамилии "name". Это означает, что список почтовых корреспонденций сортируется в алфавитном порядке фамилий.
{ быстрая сортировка записей с почтовым адресом }
procedure QsRecord(var item: DataArray; count:integer);
procedure qs(l, r:integer; var it:DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i].name < x.name do i := i+1;
while x.name < it[j].name do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end; {конец быстрой сортировки записей}
Сортировка дисковых файлов
Имеется два типа дисковых файлов: файлы с последовательным доступом и файлы с произвольным доступом. Если файл достаточно небольшой, то он может быть считан в оперативную память и тогда могут использоваться для наиболее эффективной сортировки те программы, которые рассматривались ранее для сортировки массивов. Однако многие дисковые файлы имеют слишком большой размер и не могут просто считываться в оперативную память для сортировки. Для этого требуется применить специальные методы.
Сортировка дисковых файлов произвольного доступа
Дисковые файлы с произвольным доступом, которые используются в большинстве баз данных на микро-ЭВМ, обладают двумя основными преимуществами над последовательными дисковыми файлами. Во-первых, их легко поддерживать. Обновление информации может производиться без копирования всего списка. Во-вторых, их можно рассматривать как большие массивы, расположенные на диске, что в значительной мере упрощает сортировку.
Последнее преимущество позволяет использовать алгоритм быстрой сортировки в некоторыми его модификациями для поиска различных записей на диске аналогично индексированию массива. В отличие от сортировки последовательного файла при сортировке дискового файла с произвольным доступом не требуется иметь на диске пространство одновременно как для отсортированного, так и для неотсортированного массива.
В каждом конкретном случае алгоритм сортировки должен модифицироваться в соответствии со структурой сортируемых данных и выбранным ключом сортировки. Однако основные принципы сортировки дисковых файлов произвольного доступа можно понять, изучая программу сортировки записей с адресами почтовых корреспонденций /запись "address" определялась раньше/. В приводимом ниже примере, предполагается, что число элементов фиксированно и равно восьмидесяти. На практике счетчик записей должен поддерживаться динамически
{ пример программы сортировки списка почтовых адресов }
programm MlistSort;
type
address = record
name: string[30];
street: string[40];
sity: string[20];
state: string[2];
zip: string[9];
end;
str80 = string[80];
DataItem = addres;
DataArray = array [1..80] of DataItem
recfil = file of DataItem
var
test: DataItem;
t, t2:integer;
testfile: recfil;
{ найти запись в файле }
function Find(var fp:recfil; i:integer): str80
var
t:address;
begin
i := i-1;
Seek(fp, i)
Read(fp, t)
Find := t.name;
end;
procedure QsRand(var var fp:recfil; count:integer)
procedure Qs(l, r:integer)
var
i, j, s:integer ;
x, y, z:DataItem;
begin
i := l; j := r;
s := (l+r) div 2;
Seek(fp,s-1); { получить запись }
Reed(fp,x);
repeat
while Find(fp, i) < x.name do i := i+1;
while x.name < Find(fp, j) do j := j-1;
if i<=j then
begin
Seek(fp,i-1); Reed(fp,y);
Seek(fp,j-1); Reed(fp,z);
Seek(fp,j-1); Write(fp,y);
Seek(fp,i-1); Write(fp,z);
i := i+1; j := j-1;
end;
until i>y;
if l<j then qs(l, j)
if l<r then qs(i, r)
end;
begin
qs(1,count);
end; { конец быстрой сортировки файла произвольного
доступа }
begin
Assign(testfile, 'rectest.dat');
Reset(testfile);
t := 1;
while not EOF(testfile) do begin
Read(testfile,test); { подсчет числа записей в
файле}
t := t+1;
end;
t := t-1;
QsRand(testfile,t)
end.Функция Find используется для того, чтобы оставить в основном неизменным программу быстрой сортировки. Результатом этой функции является символьная строка "name" из записи, расположенной на диске. Необходимо постоянно вычитать единицу из аргументов функций Seek и Find, так как записи дискового файла нумеруются начиная с нуля, а массивы нумеруются с единицы.
Сортировка последовательных файлов
В отличие от файлов с прямым доступом последовательные файлы обычно не используют записи фиксированной длины и могут размещаться на устройствах памяти, на которых трудно организовать прямой доступ. Поэтому последовательные файлы на дисках используются в тех случаях, когда для решения конкретной задачи удобнее использовать записи переменной длины или когда устройство памяти ориентировано на последовательный доступ. Например, большинство текстовых файлов имеют последовательную организацию.
Несмотря на то, что такой подход к сортировке, когда дисковый файл рассматривается как массив, имеет ряд преимуществ, его нельзя применить к последовательным файлам - быстрый доступ к произвольному элементу в этом случае невозможен. Например, нельзя быстро прочитать произвольную запись из последовательного файла, расположенного на магнитной ленте. По этой причине возникают трудности по применению любого ранее описанного метода сортировки массивов к сортировке последовательных файлов.
Имеется два подхода к сортировке последовательных файлов. Первый подход предусматривает считывание информации в оперативную память и сортировку при помощи одного из стандартных методов сортировки массивов. Несмотря на то, что при таком подходе сортировка будет выполняться быстро, размеры оперативной памяти накладывают сильное ограничение на размер сортируемого файла.
При использовании второго подхода, получившего название сортировки слиянием, весь файл делиться на две равные части. В процессе сортировки из каждого файла считывается по одному элементу, эта пара элементов упорядочивается и делается запись элементов в третий файл, расположенный на диске. Новый файл затем снова делится на два файла и упорядоченные пары элементов объединяются в упорядоченные группы элементов по четыре элемента в каждой. Затем полученный файл снова разделяется на два файла и вся процедура повторяется до тех пор, пока файл не будет отсортирован. Эту сортировку-слияние называют трехленточным слиянием, поскольку в этом случае одновременно требуется иметь три файла /т.е. три накопителя на магнитной ленте, если файл располагается на ленте/.
Для того, чтобы лучше понять работу сортировки-слияние, рассмотрим следующую последовательность числе:
1 4 3 8 6 7 2 5.
В результате разбиения получаться следующие последовательности:
1 4 3 8
6 7 2 5.
Затем производится слияние пар элементов:
1 6 - 4 7 - 2 3 - 5 8.
Новое разбиение дает следующие последовательности:
1 6 - 4 7
2 3 - 5 8.
Результат следующего слияния:
1 2 3 6 - 4 5 7 8.
Последнее разбиение будет следующим:
1 2 3 6
4 5 7 8.
И в результате получаем:
1 2 3 4 5 6 7 8.
При сортировке методом слияния, как возможно вы уже заметили, требуется выполнить log n операций доступа к каждому файлу, где "n" является числом сортируемых элементов.
Ниже дается простая версия алгоритма сортировки методом слияния. Предполагается, что размер входного файла в два раза превышает объем содержащейся в нем информации. Поэтому в действтительности требуется иметь лишь один файл. Однако, по-существу, метод сортировки слиянием не изменяется. В этом примере данное
"filtype" определяется как файл типа "DataItem". Функция "Find" используется для считывания конкретной записи из файла.
{ функция "Find" используется в сортировке методо.
слияния для считывания из файла конкретной записи.}
function Find(var fp:filtype; i:integer):DataItem;
var
t:DataItem;
begin
Seek(fp, i-1);
Read(fp, t);
Find := t;
end;
procedure Mergesort(var fp: filetype; count:integer);
var
i, j, k, l, t, h, m, p, q, r: integer;
ch1, ch2:DataItem
up: Boolean;
begin
up := TRUE;
p := 1;
repeat
h := 1; m := count;
if up then
begin
i := 1; j := count; k := count+1; l := 2*count;
end else
begin
k := 1; l := count; i := count+1; j := 2*count;
end;
repeat
if m>=p then q := p else q := m;
m := m-q;
if m>=p then r := p else r := m;
m := m-r;
while (q<>0) and (r<>0) do
begin
if Find(fp,i) < Find(fp,j) then
begin
Seek(fp, i-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; i := i+1; q := q-1;
end else
begin
Seek(fp, j-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; j := j-1; r := r-1;
end;
end;
while r<>0 do
begin
Seek(fp, j-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; j := j-1; r := r-1;
end;
while q<>0 do
begin
Seek(fp, i-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; i := i+1; q := q-1;
end;
h := -1; t := k;
k := l;
l := t;
until m = 0:
up := not up;
p := p*2;
until p >= count;
if not up then
for i := 1 to count do
begin
Seek(fp, i-1+count); Read(fp,ch2);
Seek(fp, i-1); Write(fp,ch2);
end;
end; { кoнец сортировки методом слияния }
Поиск
В настоящее время имеются базы данных, где информация храниться таким образом, что пользователь время от времени может получить требуемые данные из соответствующих записей, когда ему известны их ключи. Для неупорядоченных файлов или массивов используются одни методы поиска, а для упорядоченных файлов или массивов используются другие методы поиска.
Поиск информации в неотсортированном массиве требует проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива. Этот метод должен использоваться для неотсортированных данных, но он также может использоваться для отсортированных данных. Если данные отсортированы, то может использоваться двоичный поиск, который выполняется значительно быстрее.
Последовательный поиск
Алгоритм последовательного поиска имеет очень простой вид.
Ниже представлена функция, которая выполняет поиск в символьном массиве заданной длины элемента с заданным значением ключа:
function SeqSearch(item: DataArray; count:integer;
key:DataItem):integer;
var
t:integer;
begin
t:=1;
while (key<>item[t]) and (t<=count) t:=t+1;
if t>count then SeqSearch:=0
else SeqSearch:=t;
end; { конец последовательного поиска }
Эта функция выдает либо значение индекса для найденного элемента массива, либо нулевое значение, когда требуемый элемент не найден.
При прямом последовательном поиске в среднем проверяются n/2 элементов. В лучшем случае будет проверяться только один элемент, а в худшем случае будут проверятся n элементов. Если информация размещается на диске, то поиск может быть очень долгим. Однако, если данные не отсортированы, то последовательный поиск является единственным возможным в данном случае методом поиска.
Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел
1 2 3 4 5. Здесь средним элементом является 3. Это значени.
меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел
4 5. На следующем шаге нужный элемент будет найден. При дво.
ичном поиске число сравнений в худшем случае равно
log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".
function BSearch (item: DataArray; count:integer;
key:DataItem):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false; { не найден }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key<item[mid] then high:=mid-1
else if key>item[mid] then low:=mid+1
else found:=true; { найден }
end;
if found then BSearch:=mid
else BSearch:=0; { не найден }
end; { конец поиска }
В следующей главе исследуются различные подходы к представлению данных, которые в некоторых случаях значительно облегчают сортировку и поиск.
Глава 2. Очереди, стеки, связанные списки и деревья
Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, которая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем "багаже"
соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "integer", "real". На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных. а последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с "машиной данных", которая управляет способом доступа к информации в вашей программе. Имеется четыре такие "машины":
- очередь;
- стек;
- связанный список;
- двоичное дерево.
Каждый метод используется при решении определенного класса задач. Каждый метод по существу является неким "устройством", которое обеспечивает для заданной информации определенный способ хранения и при запросе выполняет определенные операции поиска данных. В каждом из этих методов используется две операции: добавить элемент и найти элемент /под элементом понимается некоторая информационная единица/. В этой главе будет показано, как эти методы можно использовать в ваших программах.
Очереди
Очередь представляет собой линейный список данных, доступ к которому осуществляется по принципу "первый вошел, первый вышел"
/иногда сокращенно его называют методом доступа FIFO/. Элемент, который был первым поставлен в очередь, будет первым получен при поиске. Элемент, поставленный в очередь вторым, при поиске будет получен также вторым и т.д. Этот способ является единственным при постановке элементов в очередь и при поиске элементов в очереди.
Применение очереди не позволяет делать прямой доступ к любому конкретному элементу.
В повседневной жизни очереди встречаются часто. Например, очередь в банке или очередь в кафетериях с быстрым обслуживанием являются очередью в указанном выше смысле /исключая те случае, когда человек пытается добиться обслуживания вне очереди!/. Для того, чтобы лучше понять работу очереди, рассмотрим две процедуры: постановка в очередь и выборка из очереди. При выполнении процедуры постановки в очередь элемент помещается в конец очереди. При выполнении процедуры выборки из очереди из нее удаляется первый элемент, который является результатом выполнения данной процедуры. Работа очереди проиллюстрирована на рис.4. Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент. Если этот элемент нигде не будет сохранен, то в последствии к нему нельзя будет осуществить доступ.
Операция Содержимое очереди
1 Qstore(A) A
1 Qstore(B) A B
1 Qstore(C) A B C
2 Qretrieve returns A B C
1 Qstore(D) B C D
2 Qretrieve returns B C D
2 Qretrieve returns C D
Рис.4. Работа очереди:
1 - постановка в очередь;
2 - выборка из очереди элемента А, В, С.
Очереди в программировании используются во многих случаях, например, при моделировании (обсуждается ниже в соответствующей главе), при планировании работ (метод ПЕРТ или графики Гатта), при буферизации ввода-вывода.
В качестве примера рассмотрим простую программу планирования предписаний, которая позволяет обращаться к нескольким предписаниям. При каждом обращении предписание удаляется из списка и на экран выводится следующее предписание. Для простоты в программе используется массив символьных строк для управления событиями.
Описание предписания ограничивается 80 символами и число предписаний не должно превышать 100. Прежде всего в этой программе планирования должны быть предусмотрены процедура постановки в очередь и процедура выборки из очереди. Эти процедуры приводятся ниже и даются необходимые описания глобальных переменных и типов данных.
const
MAX_EVENT = 100;
type
EvtType = string[80];
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos: integer;
{добавить в очередь}
procedure Qstore(q:EvtType);
begin
if spos=MAX_EVENT then
WriteLn('List full')
else
begin
event[spos]:=q;
spos:=spos+1;
end;
end; {конец процедуры постановки в очередь}
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=spos then
begin
WriteLn('No appointments scheduled.');
Qretrieve := '';
end else
begin
rpos:=rpos+1;
Qretrieve := event[rpos-1];
end;
end; { конец процедуры выборки из очереди }
В работе этих функций используются три глобальные переменные: "spos", которая содержит индекс следующего свободного элемента; "rpos", которая содержит индекс следующего выбираемого элемента и "event", которая представляет собой массив символьных строк с описанием предписаний. Переменные "spos" и "rpos" должны быть установлены в нулевое значение до первого обращения к процедурам постановки в очередь и выборки из очереди.
В этой программе процедура постановки в очередь помещает новые события в конец списка и делает проверку заполнения списка.
Функция выборки из очереди выбирает события из очереди при необходимости их обработки. Когда планируется новое событие, переменная "spos" увеличивается на единицу, а когда событие завершается, то увеличивается на единицу переменная "rpos". Фактически переменная "rpos" преследует переменную "spos" в проходах по очереди.
Этот процесс иллюстрируется на рис.5. Если значение указателя свободного места совпадает со значением указателя выбираемого элемента, то это означает, что в очереди нет событий. Следует помнить, что хотя функция выборки элемента из очереди в действительности не нарушает информацию в очереди, повторный доступ к ней невозможен и фактически она исчезает.
Ниже приводится целиком программа, осуществляющая простое планирование предписаниями. Вы можете усовершенствовать эту программу по собственному желанию.
Циклическая очередь
spos 2
1 Queue ---T--T--T--T--T--T--T--T--T--T--¬
at Start-up ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos 3
spos 2
4 Qstore('A') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos 3
spos 2
4 Qstore('B') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos 3
spos 2
5 Qreirieve ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos 3
spos 2
5 Qreirieve ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos 3
spos 2
4 Qstore('C') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦C ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+-- rpos .
Рис.5. Указатель поиска преследует указатель свободного места в очереди:
1 - очередь в исходном положении;
2 - указатель свободного места в очереди;
3 - указатель следующего выбираемого элемента;
4 - процедура постановки в очередь;
5 - функция выборки из очереди.
{ простое планирование предписаниями }
procram MiniScheduler;
uses Grt;
const
MAX_EVENT = 100;
type
EvtType = string[80];
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos, t: integer;
ch:char;
done:boolean;
{ добавить в очередь }
procedure Qstore(q:EvtType);
begin
if spos=MAX_EVENT then
WriteLn('List full')
else
begin
event[spos] := q;
spos := spos+1;
end;
end; { конец процедуры постановки в очередь }
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=spos then
begin
WriteLn('No appointments scheduled.);
Qretrieve := '';
end else
begin
rpos := rpos+1;
Qretrieve := event[rpos-1];
end;
end; { конец функции выборки элемента из очереди }
{ ввести предписание в планировщик }
procedure Enter;
var
s: string[80];
begin
repeat
Write('Enter appointment',spos+1, ':');
ReadLn(s);
WriteLn;
if Length(s)<>0 then Qstore(s);
until Length(s)=0;
end; { конец процедуры ввода }
{ вывести предписание }
procedure Review;
var
t: integer;
begin
for t:=rpos to spos-1 do WriteLn(t+1,':',event[t]);
end; { конец процедуры вывода }
{ активизировать предписание }
procedure Periorm;
var
s:string[80];
begin
s:=Qretrieve; { получить следующее предписание }
if Length(s)<>0 then WriteLn(s);
end; { конец процедуры активизации предписаний }
begin { начало планировщика }
for t:= 1 to MAX_EVENT do event[t]:=''; { инициализация
событий}
spos:=0; rpos:=0; done:=FALSE;
repeat
Write('Enter,Review, Pertorm,Quit: ');
ch:= ReadKey;
WriteLn;
Case upcase(ch) of
'E':Enter;
'R':Review;
'P':Perform;
'Q':done:=TRUE;
end;
until done=TRUE;
end.При чтении предыдущего раздела вы возможно подумали об улучшении программы планирования предписаниями. Вместо остановки программы по достижению предела массива, который используется под очередь, можно указатель постановки в очередь и указатель выборки из очереди вернуть на начало массива. В этом случае в очередь можно добавлять любое число элементов в то время как элементы будут также выбираться из очереди. Такая очередь называется циклической, поскольку теперь массив используется не как линейный список, а как циклический список.
Для создания циклической очереди в программе планирования предписаний требуется изменить подпрограммы постановки в очередь и выборки из очереди следующим образом:
procedure Qstore(q: EvtType);
begin
{ убедитесь, что имеется свободное место в очереди }
if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then
WriteLn('List full')
else
begin
event[spos] := q;
spos := spos+1;
if spos=MAX_EVENT then spos:=1; { возврат в начало }
end;
end; { конец процедуры постановки в очередь }
function Qretrieve:EvtType;
begin
if rpos=MAX_EVENT then rpos:=1; { возврат в начало }
else rpos:=rpos+1;
if rpos=spos then
begin
WriteLn('Queue empty');
Qretrieve:=';';
end else
Qretrieve:=event[rpos-1];
end; { конец функции выборки из очереди }
В действительности очередь становится заполненной только в том случае, когда указатель свободного места совпадает с указателем выборки следующего элемента. В противном случае очередь будет иметь свободное место для нового элемента. Однако, это значит, что в начале программы индекс выборки должен устанавливаться не в нулевое значение, а на значение максимального числа событий. В противном случае первое обращение к процедуре постановки в очередь приведет к появлению сообщения о заполнении списка. Следует помнить, что очередь может содержать только на один элемент меньше, чем значение максимального числа событий, поскольку указатели выборки и постановки в очередь всегда должны отличаться хотя бы на единицу (в противном случае нельзя будет понять заполнена ли очередь или она пустая).
Далее рассматривается циклический массив, который используется в новой версии программы планирования. Наиболее широко циклические очереди применяются в операционных системах при буферизации информации, которая считывается или записывается на дисковые файлы или консоль. Другое широкое применение эти очереди нашли в решении задач реального времени, когда, например, пользователь может продолжать делать ввод с клавиатуры во время выполнения другой задачи. Так работают многие текстовые процессоры, когда изменяется формат параграфа или выравнивается строка. Имеется короткий промежуток времени, когда набранная на клавиатуре информация не выводится на экран до окончания другого процесса. Для достижения такого эффекта в программе должна предусматриваться постоянная проверка ввода с клавиатуры в ходе выполнения другого процесса. При вводе некоторого символа его значение должно быстро ставиться в очередь и процесс должен продолжаться. После завершения процесса набранные символы выбираются из очереди и обрабатываются обычным образом.
Для того, чтобы понять, как это можно сделать с помощью циклической очереди, рассмотрим следующую простую программу, состоящую из двух процессов. Первый процесс выполняет подсчет до 32 000. Второй процесс устанавливает символы в циклическую очередь по мере того как они вводятся с клавиатуры. При этом вводимые символы не будут выводиться на экран до тех пор, пока не будет введена точка с запятой. Вводимые символы не будут выводиться на экран, поскольку первый процесс будет иметь более высокий приоритет до тех пор, пока вы не введете точку с запятой или пока счетчик не достигнет максимального значения. Затем из очереди будут выбраны введенные символы и выведены на экран.
{ программа, иллюстрирующая применение циклической очереди }
program KeyBuffer;
uses Crt, Dos;
const
MAX_EVENT = 10;
type
EvtType = char;
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos, t: integer;
ch: char;
{ поместить объект в очередь }
procedure Qstore(q:EvtType);
begin
2 { убедиться, что в очереди имеется свободное место}
if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then
WriteLn('List full')
else
begin
event[spos]:=q;
spos:=spos+1;
if spos=MAX_EVENT then spos:=1; { вернуться в начало
очереди }
end;
end; { конец процедуры постановки в очередь }
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=MAX_EVENT then rpos:=1; { вернуться в начало
очереди }
else rpos:=rpos+1;
if rpos=spos then
begin
WriteLn('Queue empty');
Qretrieve:=';';
end else
begin
Qretrieve:= event[rpos-1];
end;
end; { конец функции выборки объекта из очереди }
begin { буфер набранных с помощью клавиатуры символов }
spos := 0;
rpos := MAX_EVENT;
{ установить переменную "ch" на начальное значение,
отличное от точки с запятой }
ch:=' ';
t := 1;
repeat
if KeyPressed then
begin
ch := ReadKey;
Qstore(ch);
end;
t:=t+1;
write(t); write(' ');
until (t=32000) or (ch=';');
{ вывести содержимое буфера введенных с клавиатуры символов }
repeat
ch:=Qretrieve;
if ch<>';' then Write(ch);
until ch = ';';
end.Процедура "KeyPressed" делает обращение к программе операционной системы, которая возвращает значение "истина", если была нажата какая-либо клавиша, или значение "ложь", если клавиатура не использовалась.
Стеки
Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" /такой метод доступа иногда называют методом LIFO/. Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка
/которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "posh" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" / вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно выделить область памяти, используя средство динамического распределения памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет потерян, если его не сохранить гденибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.
const
MAX = 100;
var
stack:array[1..100] of integer;
tos:integer; {points to top of stask}
{ помещение объекта в стек }
procedure Push(i:integer);
begin
if tos>=MAX then WriteLn('Stask full')
else
begin
stack[tos]:=i;
tos:=tos+1;
end;
end; { конец процедуры помещения объекта в стек}
{ выборка объекта из стека }
function Pop:integer;
begin
tos:=tos-1;
if tos<1 then
begin
WriteLn('Stack underflow');
tos:=tos+1;
Pop:=0;
end
else Pop := stack[tos];
end; { конец функции выборки объекта из стека }
Переменная "tos" содержит значение индекса для следующего помещаемого в стек элемента. При реализации этих процедур никогда нельзя забывать о проверке ситуаций переполнения стека и выборки из пустого стека. В приведенных процедурах нулевое значение указателя "tos" означает, что стек пуст, а значение этого указателя, равное или превышающее адрес последней ячейки памяти, где содержится стек, означает заполнение стека. Рис.7 иллюстрирует работу стека.
Операция Содержимое стека
Push(A) A
Push(B) B A
Push(C) C B A
Pop, выбирается С В А
Push(F) F B A
Pop, выбирается F B A
Pop, выбирается В .
Рор, выбирается А пуст.
Рис.7. Работа стека.
Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые калькуляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.
Ниже показана программа для такого калькулятора.
{ калькулятор с четырьмя операциями, иллюстрирующий работу }
program four_function_calc;
const
MAX = 100;
var
stack:array [1..100] of integer;
tos:integer; { указатель вершины стека }
a, b:integer;
s:string[80];
{ поместить объект в стек }
procedure Push(i:integer);
begin
if tos >= MAX then Writeln('Stack full')
else
begin
stack[tos] :=1;
tos := tos+1;
end;
end;{Push}
{ выборка объекта из стека }
function Pop:integer;
begin
tos := tos-1;
if tos < 1 then
begin
Writeln('Stack underflow')
tos := tos+1;
Pop := 0;
end
else Pop := stack[tos];
end;{ Pop }
begin { калькулятор }
tos := 1;
Writeln('For Function Calculator');
repeat
Write(': '); { вывод приглашения }
Readln(s);
Val(s, a, b) { преобразование строки символов в
целое число }
{ считается, что при успешном преобразовании
пользователь ввел число, а в противном
случае пользователь ввел оператор}
if (b=0) and ((Length(s)>1) or (s[1]<>'-')) then
Push(a)
else
case s[1] of
'+' begin
a := Pop
b := Pop
Writeln(a+b);
Push(a+b);
end;
'-' begin
a := Pop
b := Pop
Writeln(b+a);
Push(b+a);
end;
'*' begin
a := Pop
b := Pop
Writeln(a*b);
Push(a*b);
end;
'/' begin
a := Pop
b := Pop
if a=0 then Writeln('divide by zero');
else
begin
Writeln(b div a);
Push(b div a);
end;
end;
'.' begin
a := Pop
Writeln(a);
Push(a);
end;
end;
until UpCase(s[1])='G'
end.Для того, чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифметические действия только с целыми числами, ее легко можно приспособить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя оператор "div" в оператор деления для чисел с плавающей запятой /наклонная черта/.
Связанные списки
Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохранен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/.
В отличии от стека и очереди связанный список позволяет осуществлять доступ к любым элементам, поскольку каждая единица информации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со сложными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае следует предусмотреть дополнительно операцию удаления элемента из списка.
Связанные списки используются в двух основных случаях. Во-первых, при создании массивов, которые располагаются в оперативной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей задачи, то вы можете использовать простой массив. Однако, если действительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в базах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего дискового файла. По этим причинам связанные списки широко используются в программах по управлению базами данных.
Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависимости от решаемой задачи.
Связанные списки с одиночной связью
В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8.
------¬ ------¬ ------¬
¦1info¦ ¦1info¦ ¦1info¦
+-----+ +-----+ +-----+
¦2link¦ ¦2link¦ ¦3 nil¦
L------ L------ L-----.
Рис.8. Расположение списка с одиночной связью в памяти:
1 - информация; 2 - указатель связи; 3 - нуль.
Имеется два способа построения списка с одиночной связью. В первом случае каждый новый элемент добавляется в начало или в конец списка. Во втором случае каждый элемент добавляется в свое место в списке /например, так, чтобы обеспечить упорядочность по возрастанию/.
Способ построения списка определяется процедурой постановки нового элемента в список. Ниже дается такая процедура для простого случая, когда элементы добавляются в конец списка. Необходимо определить запись, которая будет содержать информацию и указатели связи. В этом примере запись содержит адрес почтовой корреспонденции. Тип записи для каждого элемента в списке адресов определяется ниже:
AddrPointer = ^address;
address = record
name: string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
next: AddrPointer; { указатель на следующую запись }
end;
DataItem = address;
var
start.last: AddrPointer;
Ниже представлена функция добавления в список с одной связью, когда каждый новый элемент помещается в конец списка.
Указатель записи типа "address" должен передаваться в качестве аргумента функции:
{ добавление в список с одной связью }
procedure SL_Store(i: AddrPointer);
Legin
if last=nil then { первый элемент списка } 2
begin
last := i;
start := i;
i^.next := nil;
end else
begin
last^.next := i;
i^.next := nil;
last := i;
end;
end; { конец процедуры добавления элементов в список с
одной связью }Следует помнить, что до первого обращения к этой функции переменные "start" и "last" должны быть установлены на значение "nil".
Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во время вставки путем установки каждого нового элемента в соответствующее место списка. Кроме того, если список уже является отсортированным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не будет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей.
При вставке элемента в список с одной связью может воникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.9 показано, как для каждого из этих случаев изменяются связи.
Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избежать этого, в качестве первого элемента нужно использовать фиктивный элемент. Этот фиктивный элемент должен иметь такое значение, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостатком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется.
1 Новый первый элемент
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦ ¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
6 New Middle Item
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦ ¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
7 New Last Item
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦5 nil¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦ ¦
L------ L------ L------ L------ L------ L------
Рис.9. Вставка элемента в список с одной связью:
1 - новый первый элемент;
2 - новый элемент;
3 - информационные поля;
4 - справа дается преобразованный список;
5 - нулевой указатель связи;
6 - новый средний элемент;
7 - новый последний элемент.
Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле
"name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка.
{ добавление элементов в список с одной связью с сохранением
упорядоченности }
function SLS_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
var
old, top: AddrPointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start=nil then
begin { первый элемент списка }
info^.next:=nil;
last:=info;
SLS_Store:=info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.name < info^.name then
begin
old:=start;
start:=start^.next;
end else
begin { вставка в середину }
if old<>nil then
begin
old^.next:=info;
info^.next:=start;
SLS_Store:=top; { сохранить начало }
done:=TRUE;
end else
begin
info^.next:=start; { новый первый элемент }
SLS_Store:=info;
done:=TRUE;
end;
end;
end; {while}
if not done then
begin
last^.next:=info; { вставка в конец }
info^.next:=nil;
last:=info;
SLS_Store:=top;
end;
end;
end;
{ конец процедуры упорядоченной вставки в список с одной связью}Для связанного списка обычно не предусматривается отдельная функция, связанная с процессом поиска, при котором элементы выдаются в порядке их расположения в списке. Эта функция обычно программируется очень просто и оформляется вместе с другими функциями, например, поиском отдельного элемента, его удалением или выводом на экран. В качестве примера ниже приводится процедура вывода всех фамилий в списке адресов почтовых корреспонденций:
procedure Display(start: AddrPointer);
begin
while start<>nil do begin
WriteLn(start^.name);
start:=start^.next;
end;
end; { конец процедуры вывода}
Здесь переменная "start" является указателем на первую запись в списке.
Поиск элемента в списке представляет собой простую процедуру прохода по цепочке. Процедуру поиска адресов по фамилиям можно составить следующим образом:
function Search(start:AddrPointer;name:str80):AddrPointer;
var
done:boolean;
begin
done := FALSE;
while (start<>nil) and (not done) do
begin
if name=start^.name then
begin
Search:=start;
done:=TRUE;
end else
start:=start^.next;
end;
if start=nil then Search := nil; { нет в списке }
end; { конец процедуры поиска элемента }
Поскольку эта процедура поиска в результате выдает указатель на тот элемент списка, который соответствует искомой фамилии, переменная "Search" должна объявляться как указатель записи типа
"address". Если требуемый элемент отсутствует в списке, то в результате выдается нулевой указатель.
Процедура удаления элемента из списка с одной связью программируется просто. Как при вставке элемента здесь может встретиться один из трех случаев: удаляется первый элемент, удаляется средний элемент и удаляется последний элемент. На рис.10 иллюстрируется каждая ситуация.
1 Deleting the First Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
6 Deleting a Middle Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5nil ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
7 Deleting the Last Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦
L------ L------ L------ L------ L------ L------
Рис.10. Удаление элемента из списка с одной связью:
1 - удаление первого элемента;
2 - левый список преобразуется в правый;
3 - информационные поля;
4 - удаленный элемент;
5 - связь с нулевым значением;
6 - удаление среднего элемента;
7 - удаление последнего элемента.
Приводимая ниже функция выполняет удаление заданного элемента из списка записей адресов:
function SL_Delete(start, item, prior_item: AddrPointer)
:AddrPointer;
begin
if prior_item<>nil then
prior_item^.next:=item^.next
else start:= item^.next;
SL_Delete:=start;
end; { конец функции удаления элемента из списка с одной
связью }
Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка.
Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может удалиться первый элемент и необходимо знать, где будет новый первый элемент списка.
Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просматривать в обратном направлении. Для этих целей используются списки с двойной связью.
Списки с двойной связью
Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Рис.11 иллюстрирует характер связей в таком списке. Список, который вместо одной имеет две связи, отличается двумя основными преимуществами. Во-первых, список может читаться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях. Во-вторых, и прямая и обратная связь позволяют прочитать список полностью и поэтому при нарушении одной из связей список может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка.
-----------¬ -----------¬ ------------¬
¦1 info ¦ ¦1 info ¦ ¦1 info ¦
+-----T----+ +-----T----+ +-----T-----+
¦2nil ¦ ¦ ¦ ¦ ¦ ¦ ¦2 nil¦
L-----+----- L-----+----- L-----+-----
Рис.11. Список с двойной связью:
1 - информационные поля; 2 - связь с нулевым значением.
Для списка с двойной связью предусматриваются три основные операции: вставка нового первого элемента, вставка нового среднего элемента и вставка нового последнего элемента. Эти операции проиллюстрированы на рис.12.
Список с двойной связью строится подобно списку с одной связью, причем в записи должно быть предусмотрено место для двух указателей. Для примера со списком почтовых корреспонденций запись адреса можно модифицировать следующим образом:
type
str80 = string[80];
AddrPointer = ^address;
address = record
1 Inserling a New First Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+---T--+ +---T--+
¦ ¦ ¦ ¦ ¦ ¦
L---+--- L---+-- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +--T---+ +---T--+ +--T---+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
L---+--- L--+---- L--+---- L--+---- L---+--- L--+--- 6 Inserling a New Middle Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+--T---+ +---T--+
¦ ¦ ¦ ¦ ¦ ¦
L--+---- L---+-- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +---T--+ +--T---+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
L---+--- L--+---- L--+---- L---+--- L---+--- L--+--- 7 Inserling a New Last Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+--T---+ +--T---+
¦ ¦ ¦ ¦ ¦nil¦3
L--+---- L--+--- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +--T---+ +---T--+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L---+--- L--+---- L--+---- L---+--- L--+---- L---+---
Рис.12. Вставка элемента в список с двойной связью:
1 - вставка нового первого элемента;
2 - новый элемент;
3 - указатель с нулевым значением;
4 - левый список преобразуется в правый;
5 - информационные поля;
6 - вставка нового среднего элемента;
7 - вставка нового последнего элемента.
name : string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
next: AddrPointer; { указатель на следующую запись }
prior: AddrPointer; { указатель на предыдущую запись }
end;
DataItem = address;
DataArray = array [1..100] of AddrPointer;
Ниже приводится функция, которая позволяет строить список с двойной связью для записей адресов:
{добавление элементов в список с двойной связью }
procedure DL_Store(i: AddrPointer);
begin
if last=nil then { первый элемент списка }
begin
last:=i;
start:=i;
i^.next:=nil;
i^.prior:=nil;
end
else
begin
last^.next:=i;
i^.next:=nil;
i^.prior:=last;
last:=i;
end;
end; { конец функции добавления в список с двойной связью }Эта функция помещает каждый новый элемент в конец списка. Следует иметь в виду, что перед первым обращением к функции переменные "start" и "last" должны устанавливаться в нулевое значение. В ходе построения списка с двойной связью каждый новый элемент может /как и для списка с одной связью/ устанавливаться не в конец, а в соответствующее место, обеспечивая упорядочность элементов в списке. Ниже приводится функция, которая создает список с двойной связью, упорядоченый по возрастанию фамилий из записей адресов:
{упорядоченная установка элементов в список с двойной связью}
function DSL_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
{ вставка элементов в соответствующее место с сохранением
порядка }
var
old, top: AddrPointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DCL_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.name < info^.name then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DSL_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DSL_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DSL_Store := top; { сохранение начала }
end;
end;
end; { конец функции DSL_Store }Поскольку элемент может помещаться в самое начало списка, эта функция должна выдавать указатель на начало списка, чтобы в других частях программы учесть изменения начала списка. При поиске конкретного элемента списка, как и для списка с одиночной связью, делается последовательный проход по цепочке связей пока не будет найден требуемый элемент.
При удалении элемента из списка возникает одна из трех ситуаций: удаление первого элемента, удаление среднего элемента и удаление последнего элемента. Рис.13 иллюстрирует изменение связей для этих случаев.
1 Deleting the First Item
3becomes
-------¬ -------¬ -------¬ --------¬ -------¬ -------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ 4¦2 info ¦ ¦2 info¦ ¦2 info¦
+---T--+ +--T---+ +--T---+ +---T---+ +---T--+ +--T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦nil¦55¦nil¦ ¦ ¦ ¦nil¦5
L---+--- L--+---- L--+---- L---+---- L---+--- L--+---
6 Deleting a Middle Item
3becomes
-------¬ -------¬ -------¬ -------¬ --------¬ -------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦ ¦2 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +---T---+ +--T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦5 ¦nil¦nil¦5¦ ¦nil¦5
L---+--- L--+---- L--+---- L---+--- L---+---- L--+---
7 Deleting the Last Item
3becomes
-------¬ -------¬ -------¬ -------¬ -------¬ --------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦
+---T--+ +--T---+ +--T---+ +---T--+ +--T---+ +---T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦ ¦ ¦nil¦55¦nil¦nil¦5
L---+--- L--+---- L--+---- L---+--- L--+---- L---+----
Рис.13. Удаление элемента из списка с двойной связью:
1 - удаление первого элемента;
2 - информационные поля;
3 - левый список преобразуется в правый;
4 - удаленный элемент;
5 - указатель с нулевым значением;
6 - удаление среднего элемента;
7 - удаление последнего элемента.
Ниже приводится функция, которая выполняет удаление элемента типа "address" из списка с двойной связью:
{ удаление элемента из списка с двойной связью }
function DL_Delete(start: AddrPointer;
key: str80): AddrPointer;
var
temp, temp2: AddrPointer;
done: boolean;
begin
if start^.name=key then begin { первый элемент списка}
DL_Delete:=start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp<>nil) and (not done) do
begin
if temp^.name=key then
begin
temp^.next:=temp^.next;
if temp^.next<>nil then
temp^.next^.prior:=temp2;
done:=TRUE;
dispose(temp);
end else
begin
temp2:=temp;
temp:=temp^.next;
end;
end;
DL_Delete:=start; { начало не изменяется }
if not done then WriteLn('not found');
end;
end; { конец функции удаления элемента
из списка с двойной связью }Этой функции передается на один указатель меньше, чем для соответствующей функции при использовании списка с одной связью. /Удаленный элемент уже имеет указатель на предыдущий элемент и указатель на следующий элемент/. Поскольку первый элемент в списке может измениться, функция возвращает указатель на начало списка.
Список адресов почтовых корреспонденций, построенный в виде списка с двумя связями
Ниже приведена простая программа для списка почтовых корреспонденций, построенного в виде списка с двойной связью. Здесь весь список содержится в оперативной памяти. Однако, программа может быть изменена для хранения списка на диске.
{простая программа для списка адресов почтовых корреспон денций, иллюстрирующая применение списков с двойной связью}
program mailing_list;
type
str80 = string[80];
AddrPointer = -address;
address = record
name: string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
next: AddrPointer; { указатель на следующую запись }
prior: AddrPointer; { указатель на предыдущую запись }
end;
DataItem = address;
filtype = file of address;
var
t, t2: integer;
mlist: FilType;
start, last: AddrPointer;
done: boolean;
{ вызов меню }
function MenuSelect: char;
var
ch: char;
begin
Writeln('1. Enter names');
Writeln('2. Delete a name');
Writeln('3. Display the list');
Writeln('4. Search for a name');
Writeln('5. Save the list');
Writeln('6. Load the list');
Writeln('7. Quit');
repeat
Writeln;
Write('Enter your choice: ');
Readln(ch);
ch := UpCase(ch);
until (ch>='1') and (ch<='7')
MenuSelect := ch;
end;{ конец выбора по меню }
{ упорядоченная установка элементов в список с двойной связью }
function DSL_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
{ вставка элементов в соответствующее место с сохранением
порядка }
var
old, top: AddrPointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DSL_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.name < info^.name then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DSL_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DSL_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DSL_Store := top; { сохранение начала }
end;
end;
end; { конец функции DSL_Store }
{ удалить элемент из списка с двойной связью }
function DL_Delete(start: AddrPointer
key: str[80]): AddrPointer
var
temp, temp2: AddrPointer
done: boolean;
begin
if star^.name = key then begin { первый элемент
списка }
DL_Delete := start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp <> nil) and (not done) do
begin
if temp^.next <> nil then
temp^.next^.prior := temp2
done := TRUE
dispose(temp);
end else
begin
temp2 := temp;
temp := temp^.next;
end;
end;
DL_Delete := start; { начало не изменяется }
if not done then Writeln('not found');
end;
end; { конец функции DL_Delete }
{ удаление адреса из списка }
procedure remove;
var
name:str80;
begin
Writeln('Enter name to delete: ');
Readln(name);
start := DL_Delete(start,name);
end; { конец процедуры удаления адреса из списка }
procedure Enter;
var
info: AddrPointer;
done: boolean;
begin
done := FALSE;
repeat
new(info) { получить новую запись }
Write('Enter name: ');
Readln(info^.name);
if Length(info^.name)=0 then done := TRUE
else
begin
Write(Enter street: ');
Readln(info.street);
Write(Enter city: ');
Readln(info.city);
Write(Enter state: ');
Readln(info.state);
Write(Enter zip: ');
Readln(info.zip);
start := DSL_Store(info, start, last); { вставить
запись }
end;
until done;
end; { конец ввода }
{ вывести список }
procedure Display(start:AddrPointer);
begin
while start <> nil do begin
Writeln(start^.name);
Writeln(start^.street);
Writeln(start^.city);
Writeln(start^.state);
Writeln(start^.zip);
start := start^.next
Writeln;
end;
end;
{ найти элемент с адресом }
function Search(start: AddrPointer; name: str80):
AddrPointer;
var
done: boolean;
begin
done := FALSE
while (start <> nil) and (not done) do begin
if name = start^.name then begin
search := start;
done := TRUE;
end else
start := star^.next;
end;
if start = nil then search := nil; { нет в списке }
end; { конец поиска }
{ найти адрес по фамилии }
procedure Find;
var
loc: Addrpointer;
name: str80;
begin
Write('Enter name to find: ');
Readln(name);
loc := Search(start, name);
if loc <> nil then
begin
Writeln(loc^.name);
Writeln(loc^.street);
Writeln(loc^.city);
Writeln(loc^.state);
Writeln(loc^.zip);
end;
else Writeln('not in list')
Writeln;
end; { Find }
{ записать список на диск }
procedure Save(var f:FilType; start: AddrPointer):
begin
Writeln('saving file');
Rewrite(f);
while start <> nil do begin
write(f,start);
start := start^.next;
end;
end;
{ загрузить список с файла }
procedure Load(var f:FilType; start: AddrPointer):
AddrPointer;
var
temp, temp2: AddrPointer
first: boolean;
begin
Writeln('load file');
Reset(f);
while start <> nil do begin { освобождение памяти
при необходимости }
temp := start^.next
dispose(start);
start := temp;
end;
start := nil; last := nil;
if not eof(f) then begin
New(temp);
Read(i, temp^);
temp^.next := nil; temp^.prior:= nil;
load := temp; { указатель на начало списка }
end;
while not eof(f) do begin
New(temp2);
Read(i, temp2^);
temp^.next := temp2; { построить список }
temp2^.next := nil;
temp^.prior := temp2;
temp := temp2;
end;
last := temp2;
end; { конец загрузки }
begin
start := nil; { сначала список пустой }
last := nil;
done := FALSE;
Assign(mlist, 'mlistd.dat');
repeat
case MenuSelect of
'1': Enter;
'2': Remove;
'3': Display(start);
'4': Find;
'5': Save(mlist, start);
'6': start := Load(mlist, start);
'7': done := TRUE;
end;
until done=TRUE;
end. { конец программы }Двоичные деревья
В этом разделе рассматривается четвертая структура данных, которая называется двоичным деревом. Имеется много типов деревьев. Однако, двоичные деревья занимают особое положение. Если такие деревья упорядочить, то операции поиска, вставки и удаления будут выполняться очень быстро. Каждый элемент двоичного дерева имеет информационные поля, связь с левым элементом и связь с правым элементом. На рис.14 показано небольшое дерево.
При описании деревьев используется специальная терминология. Первый элемент дерева называется его корнем. Каждый элемент называют вершиной /или листом/ дерева, а часть дерева носит название поддерева. Вершина, которая не имеет поддеревьев, называется терминальной вершиной. Высота дерева равна числу уровней вершин в дереве. В дальнейшем при рассмотрении деревьев можно считать, что в памяти они располагаются так же, как на бумаге. Однако следует помнить, что деревья представляют собой лишь способ представления данных в памяти, а память в действительности имеет линейную форму.
Root Node 1
--------¬
¦2 info ¦
+---T---+
¦ ¦ ¦
3 L---+---- 4
Left Subtree Righl Subtree
--------¬ --------¬
¦ 2 info¦ ¦2 info ¦
+---T---+ +---T---+
¦ ¦ ¦ 5¦nil¦ ¦
L---+---- L---+---
--------¬ --------¬ --------¬
¦2 info ¦ ¦2 info ¦ ¦2 info ¦
+---T---+ +---T---+ +---T---+
5¦nil¦nil¦5 5¦nil¦nil¦5 5¦nil¦nil¦5
L---+---- L---+---- L---+---
6
Terminal Nodes
Рис.14. Пример двоичного дерева:
1 - корневая вершина;
2 - информационные поля;
3 - левое поддерево;
5 - указатель связи с нулевым значением;
6 - терминальные вершины.
Двоичное дерево представляет собой особую форму связанного списка. Доступ к элементам, их вставка и удаление могут выполняться в любом порядке. Кроме того, операция поиска не носит разрушительный характер. Хотя деревья легко представляются образно, для программирования они представляют достаточно непростую задачу. Поэтому они стали рассматриваться лишь в этом разделе.
Большинство функций над деревьями носят рекурсивный характер, поскольку дерево само по себе является рекурсивной структурой данных. /Т.е. каждое поддерево само является деревом/. Поэтому представленные в этом разделе программы являются, как правило, рекурсивными. Имеются нерекурсивные версии этих функций, однако разобраться в них значительно труднее.
Упорядоченность дерева зависит от порядка доступа к дереву.
Процесс доступа к каждой вершине дерева называется обходом дерева.
Имеется три способа обхода дерева: во внутреннем порядке, в прямом порядке и в обратном порядке. При прохождении дерева во внутреннем порядке сначала посещается левое поддерево, затем корень и затем посещается правое дерево. При прохождении дерева в прямом порядке сначала посещается корень, затем левое поддерево и затем правое поддерево. При прохождении дерева в обратном порядке сначала посещается левое поддерево, затем правое поддерево и затем корень.
Порядок прохождения ds, выбранного в качестве примера дерева будет следующим:
- при прохождении во внутреннем порядке: a b c d e f g;
- при прохождении в прямом порядке: d b a c f e g;
- при прохождении в обратном порядке: a c b e g f d.
Хотя дерево не обязательно должно быть упорядочено, в большинстве случаев оно должно быть таким. Упорядоченность дерева зависит от того, как вы будете проходить дерево. В приводимых ниже примерах используется внутренний порядок прохода по дереву. В отсортированном двоичном дереве левое поддерево содержит вершины, которые меньше или равны корню, а вершины правого поддерева больше или равны корню. Ниже приводится функция, которая выполняет построение отсортированного двоичного дерева:
type
TreePointer = ^tree;
tree = record
data: char;
left: TreePointer;
right:TreePointer;
end;
{ добавить элемент в двоичное дерево }
function Stree(root,r:TreePointer;data:char);TreePointer;
begin
if r=nil then
begin
new(r); { получить новую вершину }
r^.left:=nil;
r^right:=nil;
r^.data:=data;
if data<root^.data then root^.left:=r
else root^.right:=r;
STree:=r;
end else
begin
if data<r^.data then STree:=STree(r, r^.left, data)
else STree:=STree(r, r^.right, data);
end;
end; { конец функции добавления элемента в двоичное
дерево }
В этом алгоритме выполняется просто прохождение по связям дерева, двигаясь вправо или влево в зависимости от поля данных.
При применении этой функции необходимо предусмотреть глобальную переменную для корня дерева. Вначале эта глобальная переменная должна быть установлена в нулевое значение. Указатель на корень будет установлен при первом обращении к указанной функции. Поскольку при последующих обращениях к этой функции нет необходимости делать новую установку корня, то используется фиктивная переменная. Если глобальной переменной будет "rt", то обращение к указанной функции может иметь следующий вид:
{call STree}
if rt=nil rt:=STree(rt, rt, info)
else dummy := STree(rt, rt, info);При таком обращении к функции вставка и первого и последующих элементов будет выполняться корректно.
Указанная функция является рекурсивной, как и большинство других процедур с деревьями. Если этот алгоритм преобразовать, используя прямой метод перехода рекурсивных алгоритмов в циклическую форму, то программа будет в несколько раз длинее. При обращении к функции задается указатель на корень и указатель на поддерево, а также помещаемые в дерево данные. Здесь в качкестве вставляемых в дерево данных используется символьное данное. Однако, в качестве такого данного можно использовать данное любого типа.
Для обхода дерева с использованием указанной функции и выдачи на печать поля данных каждой вершины можно использовать следующую функцию:
procedure InOrder(root:TreePointer);
begin
if root<>nil then
begin
InOrder(root^.left);
Write(root^.data);
InOrder(root^.right);
end;
end.
Эта функция делает обход дерева во внутреннем порядке и завершается при обнаружении терминального листа /указателя о нулевом завершении/. Ниже показаны функции для прохождения дерева в прямом и обратном порядке:
procedure PreOrder(root:TreePointer);
begin
if root<>nil then
begin
write(root^.data);
preorder(root^.left);
preorder(root^.right);
end;
end.
procedure PostOrder(root:TreePointer);
begin
if root<>nil then
begin
postorder(root^.left);
postorder(root^.right);
Write(root^.data);
end;
end.
Вы можете составить короткую программу, которая строит упорядоченное двоичное дерево и, кроме того, печатает его на экране вашего компьютера. Для этого требуется выполнить лишь незначительные изменения в процедуре прохода дерева во внутреннем порядке. Ниже приводится программа, которая выдает вершины дерева во внутреннем порядке:
{ вывод на экран вершин дерева /слева направо/ }
programm DisplayTree;
uses Crt;
type
TreePointer = ^tree
tree = record
data: char;
left: TreePointer;
right: TreePointer;
end;
var
root, dummy: TreePointer;
ch:char;
function STree(root, r:TreePointer; data: char):
TreePointer;
begin
if r = nil then
begin
new(r); { получить новую вершину }
r^.left := nil;
r^.right := nil;
r^.data := data;
if data < root^.data then root^.left := r
else root^.right := r;
STree := r;
end else
begin
if data<r^.data then STree := STree(r, r^.left, data)
else STree := STree(r, r^.right, data)
end;
end; { конец процедуры STree }
procedure PrintTree(r: TreePointer; n: integer);
var
i:integer;
begin
if r<>nil then begin
PrintTree(r.^left, n+1);
for i := 1 to n do Write(' ');
Writeln(r^.data);
PrintTree(r^.right, n+1);
end;
end; { конец процедуры PrintTree }
begin
root := nil;
repeat
Write('enter a letter (Q to quit): ');
ch := ReadKey; Writeln(ch);
if root= nil then root := STree(root, root, ch)
else dummy := STree(root, root, ch);
ch := UpCase(ch);
until ch ='Q';
PrintTree(root, 0);
end;В этой программе фактически делается сортировка полученной информации. В данном случае используется вариант сортировки вставкой, которая описывается в предыдущей главе. Для среднего случая сортировка вставкой имеет достаточно хорошие характеристики, однако быстрая сортировка все же является лучшим методом сортировки, так как она требует меньше оперативной памяти и выполняется быстрее. Однако, если дерево строится на основе использования других деревьев или если вам приходится поддерживать упорядоченное дерево, то новые элементы всегда будут вставляться с использованием функции STree.
Если вы воспользуетесь программой вывода на экран двоичного дерева, то возможно вы заметите, что некоторые деревья сбалансированы /т.е. все поддеревья имеют одинаковую или почти одинаковую высоту/, а другие сильно несбалансированы. Если вы введете дерево
"abcd", то оно примет следующий вид:
a
\
\
b
\
\
c
\
\
.
В этом случае левых поддеревьев не будет. Это дерево называется вырожденным, поскольку оно выродилось в линейный список. В общем случае, если используемые для построения дерева данные являются в достаточной мере случайными, дерево будет приближаться к сбалансированному. Однако, если информация уже упорядочена, то в результате будет получаться вырожденное дерево. /Имеется возможность переупорядочивать дерево, сохраняя при каждой вставке его балансировку. Однако такой алгоритм достаточно сложен и если он вас заинтересовал, то следует воспользоваться книгами по усовершенствованным методам составления алгоритмов программ/.
Функции поиска для двоичных деревьев составляются легко. Ниже приводится функция, результатом которой является указатель на вершину дерева, которая совпадает с ключем. В противном случае возвращается нулевое значение.
{ поиск элемента в дереве }
function Search(root:TreePointer;
key:DataItem):TreePointer;
begin
if root <> nil
begin
while (root^.data <> key) and (root <> nil) do
begin
if key < root^.data then root := root^.left
else root := root^.right;
end;
end;
Search := root;
end; { конец процедуры поиска элемента }
К сожалению, удаление вершины дерева выполняется не так просто, как поиск вершины. Удаленной вершиной может быть корень, левая вершина или правая вершина. Вершина может также иметь от нуля до двух поддеревьев. Необходимость изменения указателей приводит, например, к следующему рекурсивному алгоритму
{ удаление элемента из дерева }
function DTree(root:TreePointer;key:char):TreePointer;
var
temp,temp2:TreePointer;
begin
if root^.data = key then
begin
if root^.left=root^.right tnen
begin
dispose(root)
DTree := nil;
end
else if root^.left=nil tnen
begin
temp := root^.right
dispose(root)
DTree := temp;
end
else if root^.right=nil tnen
begin
temp := root^.left
dispose(root)
DTree := temp;
end
else
begin { имеются два листа }
temp2 := root^.right
temp := root^.right
while temp^.left <> nil do temp := temp^.left;
temp^.left := root^.left
dispose(root);
DTree := temp2
end;
else
begin
if root^.data < key
then root^.right := DTree(root^.right, key)
else root^.left := DTree(root^.left, key)
DTree := root;
end;
end; { конец функции DTree }Следует помнить, что в основной программе необходимо обновлять указатель на корень дерева, так как удаленная вершина может оказаться корнем дерева. Использование двоичных деревьев позволяет создавать мощные, гибкие и эффективные программы по управлению баз данных. Информация в этом случае может находиться на диске и поэтому важное значение может иметь время доступа. Число сравнений при использовании сбалансированных двоичных деревьев для худшего случая равно log2(n). Поэтому в этом случае поиск выполняется значительно быстрее, чем поиск в связанном списке, который посуществу является последовательным поиском.
Глава 3. Динамическое распределение памяти
Разработка программы для компьютера в некотором смысле напоминает процесс составления проекта здания, включающий в себя рассмотрение многочисленных функциональных и эстетических вопросов, влияющих на окончательный результат. Например, некоторые программы имеют строгое функциональное назначение как дом, который имеет определенное число спальных комнат, кухню, две ванные комнаты и т.д. Другие программы носят менее завершенный характер, как центры для проведения собраний, которые имеют передвижные стены и модульные полы, позволяющие лучше приспособить здание для каждого конкретного случая. В этой главе описывается механизм управления памятью, позволяющий разрабатывать гибкие программы, которые могут адаптироваться к конкретным нуждам пользователя и возможностям ЭВМ.
Следует отметить, что в этой главе используется термин "логический массив" и термин "физический массив". Логический массив
- это такой массив, который представляется существующим в системе. Например, матрица на листе бумаги является логическим массивом. Физический массив - это массив, который в действительности имеется в вычислительной системе. Связь между двумя этими массивами обеспечивается программами по поддержке разреженных массивов. В этой главе рассматривается четыре метода создания разреженных массивов: посредством связанного списка, двоичного дерева, массива указателей и хеширования. Затем будут даны примеры динамического распределения памяти, которое позволяет повысить производительность программы.
В программе на языке Паскаль информацию в основной памяти ЭВМ можно хранить двумя способами. Первый способ заключается в использовании глобальных или локальных переменных, включая массивы и записи, которые предусмотрены в языке Паскаль. Глобальные переменные занимают постоянное место в памяти во время выполнения программы. Для локальных переменных память выделяется из стека ЭВМ. Хотя управление глобальными и локальными переменными на Паскале реализовано эффективно, программист должен знать заранее объем необходимой памяти для каждого конкретного случая. Другой и более эффективный способ управления памятью на Паскале обеспечивается применением функций по динамическому управлению памятью.
Таким являются функции "New", "Dispose", "Mark" и "Release".
В обоих методах динамического управлению памятью память выделяется из свободного участка, который не входит в постоянную область программы, и стека /который используется в Паскале для хранения локальных переменных/. Эта область называется динамической (heap).
Рис.15 иллюстрирует структуру памяти для программы на языке Турбо Паскаль. Стек увеличивается в нижнем направлении. Объем памяти, необходимой стеку, зависит от характера программы. Например, программа со многими рекурсивными функциями будет требовать много стековой памяти, поскольку при каждом рекурсивном обращении выделяется участок стековой памяти. Участок выделяемой под программу и глобальные переменные памяти имеет постоянную величину и не изменяется во время выполнения программы. Память для запросов функции "New" берется из свободного участка памяти, который начинается сразу после глобальных переменных и продолжается до стека.
В исключительных случаях может использоваться для стека область динамической памяти.
Старшие адреса памяти-------------------¬
¦ Хип ¦
¦ ¦
+------------------+
¦ ¦
¦ ¦
¦ Стек ¦
¦ ¦
+------------------+
¦Глобальные перемен¦
+------------------+
¦ ¦
¦ ¦
¦ Программа ¦
¦ ¦.
Младшие адреса памятиL------------------
Рис.15. Использование памяти в программе на языке Турбо Паскаль.
Использование динамической памяти зависит от того, какая функция применяется для освобождения памяти и возвращения ее системе: функция "Dispose" или пара процедур "Mark" и "Release". Как указано в справочном руководстве по языку Турбо Паскаль, эти два способа нельзя никогда смешивать в одной программе. Следовательно, вам заранее необходимо решить, каким из способов пользоваться. Для того, чтобы понять, чем эти способы отличаются друг от друга, ниже дается краткое описание этих функций.
Функция New
Использование этой функции позволяет получить память из динамической области. Эта встроенная процедура в качестве аргумента использует указатель на ту переменную, которая должна размещаться в динамической области. После обращения значение аргумента будет указывать на выделенный участок памяти. Например, для размещения вещественного числа в динамической области можно записать следующий код:
type
rpntr = real;
var
p:rpntr;
begin
New(p);
. . .
Если в динамической области не будет свободного участка, то будет выдан код ошибки FF /конфликт динамической области памяти или стека/. Для того, чтобы избежать этого, необходимо перед вызовом указанной функции сделать вызов функции "Max-AvatI", которая определяет размер в байтах *незанятой части динамической области памяти. /Пользователи версии 3.0 должны иметь в виду, что указанная функция определяет число свободных блоков,а не байт/ В приведенном выше примере этот шаг отсутствует, но возможно он потребуется при решении ваших задач.
Функция Dispose
Одна из причин динамического распределения памяти заключается в возможности ее повторного использования. Один из способов возврата памяти в динамическую область предусматривает использование функции "Dispose". В качестве аргумента этой функции используется указатель, который применялся при вызове функции
"New", т.е. эта функция использует указатель на участок, который действительно располагается в динамической области. После обращения к этой функции память, которая выделялась по заданному указателю, будет освобождена и может использоваться в дальнейшем. Например, ниже приводится короткая программа, которая динамически выделяет память под массив из сорока целых чисел и перед завершением возвращает занятую память системе:
{Динамическое выделение памяти с использованием функций New и
Dispose.}
program Sample;
type
pntr = ^RecType;
RecType = array[1..40] of integer;
var
p: pntr;
t: integer;
begin
New(p);
for t: = 1 to 40 do p^[t]: = t*2;
for t: = 1 to 40 do Write(p^[t], ' ');
WriteLn;
Dispose(p);
end.Функции Mark и Release
Альтернативой использованию функции Dispose является применение функций Mark и Release, которые совместно обеспечивают освобождение динамического участка памяти после его использования в программе. В действительности вызов функции Mark должен делаться до обращения к функции New, а вызов функции Release должен делаться после функции New, когда требуется перераспределить память. Функция Release освобождает все участки памяти, которые выделялись между вызовами функций Mark и Release. Таким способом системе возвращается несколько участков памяти, а при использовании функции Dispose возвращается только один участок памяти, задаваемый соответствующим указателем.
В функции Mark используется один аргумент. Он должен являться указателем переменной любого типа, поскольку единственным назначением этой функции является сохранением начала области памяти в динамической области. Функция Release должна использовать тот же указатель, который не должен модифицироваться. Например, в приведенной ниже программе выполняется динамическое выделение памяти под массив из сорока целых чисел и освобождение ее при помощи функций Mark и Release:
{Динамическое выделение памяти с использованием Mark и Release.}
program alloc;
type
pntr = ^RecType;
RecType = array[1..40] of integer;
var
p: pntr;
t: integer;
q: ^integer;
begin
Mark(q);
New(p);
for t: = 1 to 40 do p^[t]:=t*2;
for t:= 1 to 40 do Write(p^[t], ' ');
WriteLn;
Release(q);
{В этом месте вся память уже возвращена системе}
end.Метод управления динамическим распределением памяти зависит от того, как вы хотите возвращать память системе. Если память будет возвращаться частично, то следует использовать функцию Dispose. Если вы всегда предполагаете освобождать всю память, то лучше использовать функции Mark и Release. В примерах в этой книге используется функция Dispose, поскольку такой метод обладает большей гибкостью. Однако вы можете свободно пользоваться функциями Mark и Release для освобождения памяти, если это больше подходит для ваших задач.
Обработка разреженных массивов
Обработка разреженных массивов является основной областью применения динамического распределения памяти. В разреженных массивах фактически имеются не все элементы. Такой массив может потребоваться в тех случаях, когда размеры массива значительно превышают размер памяти вашей машины и когда не все элементы массива будут использоваться. Массивы большой размерности требуют большого расхода памяти, поскольку ее объем растет по экспоненте в зависимости от размера массива. Например, для символьной матрицы 10 х10 требуется только 100 байт памяти, а для матрицы 100х100 требуется 10 000 байт и для матрицы 1000х1000 требуется уже 1 000 000 байт памяти.
Электронная таблица является хорошим примером разреженной матрицы. Даже если матрица будет большой, например, 999х999, в каждый конкретный момент времени будет использована только некоторая ее часть. Каждому элементу электронной матрицы ставится в соответствие формула, значение или символьные строки. Память под каждый элемент разреженной матрицы выделяется по мере необходимости. Хотя использоваться может лишь небольшая часть элементов, вся матрица может быть очень большой - больше чем обычные размеры памяти ЭВМ.
Имеется три различных метода создания разреженных массивов: связанный список, двоичное дерево и массив указателей. Каждый из этих методов предполагает, что электронная матрица имеет форму, представленную на следующей странице.
В этом примере Х располагается в ячейке В2.
----А---- ----В---- ----С---- ...
1
2 Х
3
4
5
. . .
Использование связанного списка для организации разреженного массива
При реализации разреженного массива с помощью связанного списка формируется запись, которая содержит информационные поля для каждого элемента массива и поле позиции элемента в массиве, а также указатели на предыдущий и следующий элементы списка. Все записи в списке упорядочены по индексу массива. Доступ к элементам массива осуществляется путем прохода по связям элементов списка.
Например, может использоваться следующая запись для создания разреженного массива:
str128 = string[128];
str9 = string[9];
CellPointer = ^cell;
cell = record
CellName: str9; {содержит название ячейки}
formula: str128; {содержит формулу}
next: CellPointer; {указатель на следующую запись}
prior: CellPointer; {указатель на предыдущую запись}
end;
В этом примере поле "CellName" содержит строку с названием ячейки, например, А1, В34 или Z19. Строка "formula" содержит формулу для каждой ячейки электронной таблицы. Ниже приводятся несколько примерных программ, использующих разреженные матрицы на базе связанного списка. (Следует помнить, что имеется много способов реализации электронных таблиц. К приводимым ниже структурам данных и программам следует относиться только как к примерам использования таких методов). Для указателей начала и конца связанного списка используются следующие глобальные переменные:
start, last: CellPointer;
Когда вы вводите формулу в ячейку типичной электронной таблицы, вы фактически создаете новый элемент разреженной матрицы. Если электронная таблица строится на базе связанного списка, то вставка нового элемента будет производится с помощью функции "DLS_Store", которая рассматривается в главе 2. (Поскольку Паскаль позволяет создавать независимые функции указанная функция может использоваться фактически без всяких изменений). В приводимом примере список сортируется по названию ячейки (т.е. А12 предшествует А13 и т.д.)
{ упорядоченная вставка элементов в список и установка указателя
на начало списка }
function DLS_Store(info, start: CellPointer;
var last: CellPointer): CellPointer;
var
old, top: CellPointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DLS_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.CellName < info^.CellName then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DLS_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DLS_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DLS_Store := top; { сохранение начала }
end;
end;
end; { конец функции DLS_Store }Для удаления элемента из электронной таблицы необходимо удалить соответствующую запись из списка и возвратить занимаемую им память системе с помощью функции Dispose. Функция DL_Delete удаляет ячейку из списка по заданному названию:
{ удаление ячейки из списка }
function DL_Delete(start: CellPointer;
key str9): CellPointer;
var
temp, temp2: CellPointer;
done: boolean;
begin
if start^.CellName=key then
begin { первый элемент в списке }
DL_Delete := start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
Dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp<>nil) and (not done) do
begin
if temp^.CellName=key then
begin
temp2^.next := temp^.next;
if temp^.next<>nil then
temp^.next^.prior := temp2;
done := TRUE;
last := temp^.prior;
Dispose(temp);
end else
begin
temp2 := temp;
temp := temp^.next; end;
end;
DL_Delete := start; { начало не изменяется }
if not done then WriteLn('not found');
end;
end; { конец процедуры удаления элемента из списка }Функция Find позволяет обратиться к любой конкретной ячейке. Эта функция имеет важное значение, так как многие формулы электронной таблицы имеют ссылки на другие ячейки и нужно эти ячейки найти, чтобы обновить их значения. В этой функции используется линейный поиск и, как показано в главе 2, среднее число операций при линейном поиске равно n/2, где n является числом элементов в списке. Кроме того, значительные потери будут из-за того, что каждая ячейка может содержать ссылки на другие ячейки и тогда потребуется выполнить поиск этих ячеек. Ниже дается пример функции Find (см.след.стр.).
{ найти конкретную ячейку и установить указатель на нее }
function Find(cell: CellPointer): CellPointer;
var
c: CellPointer;
begin
c := start;
while c<>nil do
begin
if c^.CellName=cell^.CellName then find:=c
else c := c^.next;
end;
WriteLn('cell not found');
Find:=nil;
end; { конец процедуры поиска }Создание, поддержка и обработка разряженных массивов имеет один большой недостаток, когда такой массив строится на базе связанного списка. Этот недостаток заключается в необходимости использовать линейный поиск каждой ячейки списка. Без дополнительной
информации, которая требует дополнительного расхода памяти, нельзя обеспечить двоичный поиск ячейки. Даже процедура вставки использует линейный поиск для нахождения соответствующего места для вставки новой ячейки в отсортированный список. Эти проблемы можно решить, используя для построения разреженного массива двоичное дерево.
Использование двоичного дерева для организации разреженных массивов
Двоичное дерево является по существу модифицированным списком с двойной связью. Основное его преимущество над обычным списком является быстрота поиска элемента, и как следствие, быстрота вставок и просмотров. В тех случаях, когда требуется обеспечить быстрый поиск в связанном списке записей, применение двоичных деревьев дает очень хорошие результаты.
При использовании двоичного дерева для реализации электронной таблицы, запись "cell" следует изменить следующим образом:
CellPointer = ^cell;
str9 = string[9];
str128 = string[128];
cell = record
CellName: str9;
formula: str128;
left: CellPointer;
right: CellPointer;
end;
Функцию "Stree", приведенную в главе 2, можно модифицировать так, что дерево будет строиться по названию ячейки. Следует отметить, что параметр "New" является указателем на новый элемент дерева.
При вызове этой функции в качестве первых двух аргументов должен задаваться указатель корневой вершины, а в качестве третьего аргумента должен задаваться указатель на новую ячейку.
В качестве результата выдается указатель корневой вершины.
{ вставка ячейки в дерево }
function STree(root, r, New:CellPointer; data: char):
CellPointer;
begin
if r = nil then
begin
New^.left := nil;
New^.right := nil;
if New^.Cellname < root^.Cellname
then root^.left := New
else root^.right := New;
STree := New;
end else
begin
if New^.Cellname<r^.Cellname then
STree := STree(r,r^.left, New)
else STree := STree(r, r^.right, New)
end;
Stree := root
end; { конец процедуры STree }Для удаления ячейки из электронной таблицы следует модифицировать функцию Dtree, в качестве ключа используя название ячейки:
{ удаление элемента из дерева }
function DTree(root:Cellpointer;key:str9):Cellpointer;
var
temp,temp2:Cellpointer;
begin
if root^.CellName = key then
begin
if root^.left=root^.right tnen
begin
dispose(root)
DTree := nil;
end
else if root^.left=nil tnen
begin
temp := root^.right
dispose(root)
DTree := temp;
end
else if root^.right=nil tnen
begin
temp := root^.left
dispose(root)
DTree := temp;
end
else
begin { имеются два листа }
temp2 := root^.right
temp := root^.right
while temp^.left <> nil do temp := temp^.left;
temp^.left := root^.left
dispose(root);
DTree := temp2
end;
else
begin
if root^.CellName < key
then root^.right := DTree(root^.right, key)
else root^.left := DTree(root^.left, key)
DTree := root;
end;
end; { конец функции DTree }И наконец, можно модифицировать функцию поиска для быстрого нахождения ячейки по ее названию:
{ найти заданную ячейку и установить указатель на нее }
function Search(root: CellPointer; key str9): CellPointer
begin
if root:=nil then Search := nil
else begin
while (root^.CellName<>key) and (root<>nil) do
begin
if root^.CellName<>key then root:=root^.left
else root:=root^.right;
end;
Search := root;
end; { конец процедуры поиска }Самым важным преимуществом двоичных деревьев над обычным связанным списком является значительно меньшее время поиска. Следует помнить, что при последовательном поиске в среднем требуется выполнить n/2 операций сравнения, где n является числом элементов в списке, а при двоичном поиске требуется выполнить только log n операций сравнений.
Применение массива указателей для организации разреженных массивов
Предположим, что электронная матрица имеет размеры 26х100 /с А1 по Z100/ и состоит всего из 2 600 элементов. Теоретически можно использовать следующий массив записей:
str9 = string[9];
str128 = string[128];
CellPointer = CellPointer;
cell = record
CellName:str9;
formula:str128;
end;
var
pa:array[1..2600] of cell;
Однако, 2 600 ячеек, помноженные на 128 (размер одного поля для формулы), потребует 332 800 байт памяти под довольно небольшую электронную таблицу. Такой подход, очевидно, нельзя использовать на практике. В качестве альтернативы можно использовать массив указателей записей. В этом случае потребуется значительно меньше памяти, чем при создании всего массива. Кроме того, производительность будет значительно выше, чем при использовании связанного списка или дерева. Для этого метода данные описываются следующим образом:
type
str9 = string[9];
str128 = string[128];
cell = record
CellName:str9;
formula:str128;
end;
var
sheettarray[1..10000] of CellPointer;
Этот массив меньшего размера можно использовать для содержания указателей на информацию, введенную пользователем в электронную матрицу. При вводе каждого элемента указатель на информационную ячейку помещается в соответствующее место массива. Рис.16 иллюстрирует структуру памяти, когда разреженный массив строится на основе массива указателей.
a
----T----T---T----T-----------T----T---¬
¦ ¦1nil¦ ¦1nil¦ ¦1nil¦ ¦
L-+-+----+-+-+----+-----------+----+-+-
¦ ¦ ¦ ---------------¬
¦ ¦ L---¦2info for A[n]¦
¦ ¦ L-------------- ¦ ¦
¦ ¦ ----------------¬
¦ L-- ¦2 info for A[a]¦
¦ L---------------
¦ ----------------¬
L---¦2 info for A[l]¦
L---------------
Рис.16. Использование массива указателей для организации разреженного массива:
1 - нулевое значение указателя;
2 - информационные поля соответствующего элемента.
Перед первым использованием массива указателей необходимо каждый элемент установить в нулевое значение, что означает отсутствие элемента в этой позиции. Используйте следующую функцию:
procedure InitSheet;
var
t:integer;
begin
for t := 1 to 10000 do sheet[t] := nil;
end; { конец блока инициализации }
Перед написанием процедуры вставки следует запрограммировать функцию поиска индекса. Эта функция находит соответствующий индекс массива указателей по заданному названию ячейки. При поиске индекса предполагается, что все названия начинаются с большой буквы, за которой идет некоторое число, например, В34, С19 и т.д. Эта функция приводится ниже на следующей странице.
{ эта функция определяет индекс указанной ячейки }
function FindIndex(i: CellPointer): integer;
var
loc,temp,code:integer;
t:str9;
begin
loc := ord(i^.CellName[1]);
t := copy(i^.CellName,2,9);
val(t,temp,code);
loc := loc+(temp*20);
find := loc;
end; { конец функции поиска индекса }Эта функция позволяет при реализации процедуры вставки соответствующую позицию массива указателей для каждой ячейки. Как видно, поиск нужного индекса выполняется просто и быстро, так как нет необходимости выполнять последовательный просмотр. Этот метод иногда называют прямым хешированием, поскольку индекс ячейки памяти определяется непосредственно по заданному элементу. Когда пользователь вводит формулу для ячейки, то эта ячейка /которая задается своим обозначением/ задает индекс массива указателей "sheet". Индекс определяется по обозначению ячейки путем его преобразования в число с помощью функции FindIndex. Вставка осуществляется с помощью следующей процедуры:
procedure Store(New: CellPointer);
var
loc:integer;
begin
loc := FindIndex(New);
if loc>10000 then WriteLn('Location out of bounds')
else sheet[loc] := New;
end; { конец процедуры вставки }
Поскольку каждая ячейка имеет уникальное обозначение, она будет иметь также уникальный индекс. Поскольку используется стандартная кодировка символов, указатель каждого элемента будет правильно помещен в массив. Если вы сравните эту процедуру с вариантом для связанного списка, то вы обнаружите, что она значительно короче и проще.
Функция удаления также выглядит короче. При вызове этой функции задается индекс ячейки и возвращается указатель элемента. Кроме того, освобождаемая память возвращается системе:
{ удаление ячейки из массива }
procedure Delete(r_cell: CellPointer);
var
loc:integer;
begin
loc := FindIndex(r_cell);
if loc>10000 then WriteLn('Cell out of bounds')
else
begin
Dispose(r_cell);
sheet[loc]:=nil;
end;
end; { конец процедуры удаления }Если вы сравните эту процедуру с версией, использующей связанный список или дерево, то обнаружите, что она значительно проще и выполняется быстрее.
Следует помнить, что сам массив указателей требует некоторого дополнительного расхода памяти под каждую ячейку. В некоторых случаях это является серьезным ограничением.
Хеширование
Хешированием называется процесс выделения элемента индексного массива непосредственно по информации, которая содержится в массиве. Полученный индекс называется хеш-адресом. Хеширование обычно используется для уменьшения времени доступа к дисковым файлам. Однако, тот же метод можно использовать для реализации разреженных матриц. В приводимом ниже примере используется процедура, где применяется специальная форма хеширования, называемая прямым индексированием. При прямом индексировании каждому ключу соответствует одна и только одна ячейка. (Т.е. хеширование дает уникальный индекс для каждого ключа. Однако, следует заметить, что применение массива указателей не обязательно требует использования прямой индексации; просто для решения данной задачи такой подход является очевидным). На практике такая схема прямого хеширования используется не очень часто и чаще требуется более гибкий метод. В этом разделе будут рассмотрены более общие методы хеширования, более мощные и более гибкие.
Из предыдущего примера по электронной матрице ясно, что даже в особых случаях не все ячейки будут использованы. Предположим, что в большинстве случаев не более десяти процентов потенциальных ячеек будет действительно использовано. Это значит, что логический массив с размерами 26х100 (2600 ячеек) потребует в действительности иметь память только под 260 элементов. Следовательно, потребуется иметь физический массив как максимум на 260 элементов. Тогда встает следующая задача: как логический массив отобразить на физический массив и как осуществлять к нему доступ? Ответ заключается в использовании списка индексов хеширования.
Когда пользователь вводит формулу в электронную матрицу (логический массив), адрес ячейки, задаваемый ее обозначением, используется для поручения индекса небольшого физического массива. Предположим, что переменная "sheet" является физическим массивом. Индекс определяется на основе обозначения ячейки путем его преобразования в число, как было сделано в примере с массивом указателей. Затем это число делится на десять для получения начальной точки входа в массив. (Следует помнить, что для вашего примера физический массив составляет только десять процентов от логического массива). Если ячейка с этим индексом свободна, то в нее помещается логический индекс и значение. В противном случае возникает конфликт. Конфликт случается при получении во время хеширования двух одинаковых ключей. В этом случае полученный индекс будет соответствовать одному элементу физического массива. Следовательно, в массиве "sheet" делается поиск свободного элемента. Когда свободный элемент найден, в него помещается информация, а указатель на это место будет помещен в исходный элемент.
Это иллюстрируется на рис.17.
Для поиска элемента в физическом массиве при заданном индексе логического массива сначала делается преобразование логического индекса в адрес, полученный посредством хеширования, и затем делается проверка физического массива на наличие в элементе с этим индексом требуемого значения. Если сравнение выполняется удачно, то информация найдена. В противном случае следует пройти по цепочке индексов до тех пор, пока не будет найдено нужное значение или пока не будет обнаружен конец цепочки.
Для того, чтобы понять, как эту процедуру можно применить к программе электронной таблицы сначала определим в качестве физического массива следующий массив записей:
const
SIZE = 260;
type
str9 = string[9];
str128 = string[128];
cell = record
CellName: str9;
formula: str128;
next: integer;
end;
var
sheet:array[0..SIZE] of cell;
name: cell;
Таблица
Индекс Знач. След. Индекс в таблице
-------T------T------¬
A1 ¦ A1 ¦ 100 ¦ 1 ¦0
+------+------+------+
A2 ¦ A2 ¦ 200 ¦ 3 ¦1
+------+------+------+
B19 ¦ B19 ¦ 50 ¦ -1 ¦2
+------+------+------+
A3 ¦ A3 ¦ 300 ¦ -1 ¦3
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦4
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦5
+------+------+------+
D2 ¦ D2 ¦ 99 ¦ -1 ¦6
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦7
+------+------+------+
¦ ¦ ¦
¦ ¦
¦ ¦
¦ ¦
¦ ¦ ¦
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2597
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2598
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2599
L------+------+-------
Предполагается, что в ячейке A1 значение 100, в A2 значение 200, в A3 - 300, в B19 - 50, а в D2 - 99.
Рис.17. Пример хеширования.
Перед использованием этот массив должен быть инициализирован. Приводимая ниже процедура используется для установки поля обозначения ячейки на значение "empty" (пусто) для указания на отсутствие элемента. Значение -1 в поле следующего индекса означает конец цепочки индексов хеширования.
{ инициализация физического массива }
procedure InitSheet;
var
t:integer;
begin
for t := 0 to SIZE do
begin
sheet[t].CellName := 'empty';
sheet[t].next:= -1;
end;
end; { конец процедуры инициализации физического массива }В процедуре вставки делается обращение к функции HashIndex для вычисления индекса хеширования и помещения его в массив "sheet". Следует отметить, что если непосредственно полученное значение индекса хеширования указывает на занятую ячейку, то в процедуре выполняется поиск первого свободного места. Это делается путем просмотра цепочки индексов хеширования до тех пор пока не будет обнаружена первая свободная ячейка. Когда свободная ячейка найдена, то делается запоминание значения логического индекса и значения элемента массива. Значение логического индекса требуется сохранить, поскольку он требуется при новом обращении к этому элементу.
{ вычисление индекса хеширования и вставка значения элемента }
function HashIndex(i:str9):integer;
var
loc, temp, code:integer
t :str9;
begin
loc := ord(i[1]-ord('A');
t := copy(i,2,9)
val(t, temp, code)
HashIndex := (loc*26+temp) div 10;
end;
{ выполнение действительной вставки значения элемента }
procedure Store(New:Cell);
var
loc, i:integer;
begin
loc := HashIndex(New.Cellname);
if loc>SIZE then Writeln('Location out of bounds')
else
begin
if ((sheet[loc].Cellname = 'empty') or
(sheet[loc].Cellname = New.Cellname)) then
begin
sheet[loc].Cellname = New.Cellname;
sheet[loc].formula = New.formula;
end else { поиск свободной ячейки }
begin
{ сначала просмотр до конца всей цепочки существующих индексов}
while(sheet[loc].next <>-1) do
loc := sheet[loc].next;
{ теперь поиск свободной ячейки }
i := loc;
while ((i<SIZE) and (sheet[loc].Cellname='empty'))
do i := i+1;
if(i = SIZE) then
begin
Writeln('cannot plase in hash array');
end else
begin { поместить значение в свободную ячейку и
обновить цепочку }
sheet[i].Cellname = New.Cellname;
sheet[i].formula = New.formula;
sheet[loc].next := i; { обеспечение связи в
цепочке }
end;
end;
end;
end; { конец процедуры вставки }При поиске значения элемента сначала вычисляется индекс хеширования и делается проверка на равенство логического индекса, который содержится в физическом массиве, и искомого логического индекса. Если они совпадают, то в результате выдается этот индекс хеширования. В противном случае делается просмотр цепочки индексов до обнаружения требуемого значения или до обнаружения значения -1 в поле ссылки на следующий элемент. Последняя ситуация возникает при отсутствии требуемого элемента в физическом массиве. Ниже приводится функция, выполняющая эти действия:
{ поиск физического адреса ячейки }
function Find(cname:cell):integer;
var
loc:integer;
begin
loc := FindIndex(cname.CellName);
while((sheet[loc].CellName<>cname.CellName) and
(loc <> -1)) do loc:=sheet[loc].next;
if(loc = -1) then
begin
WriteLn('Not found');
Find := -1;
end else Find := loc;
write('loc is'); writeLn(loc);
end; { конец функции поиска }Следует иметь в виду, что описанная в этом разделе схема хеширования очень проста и на практике приходится применять более сложные схемы хеширования. Например, при возникновении конфликта очень часто используют вторичное и третичное хеширование прежде, чем воспользоваться просмотром цепочки индексов хеширования. Однако, основные принципы хеширования остаются неизменными.
Анализ хеширования
При хешировании в лучшем случае (который встречается достаточно редко) каждый полученный хеш-функцией физический индекс является уникальным и время доступа приближается к времени прямого индексирования. Это значит, что цепочка индексов хеширования не создается и все операции поиска по существу являются операциями прямого поиска. Однако, это случается редко, поскольку требуется, чтобы логический индекс равномерно распределялся в пространстве логических индексов. В худшем случае (который также редок) схема хеширования вырождается в схему поиска в связанном списке. Это будет в том случае, когда все полученные с помощью хеш-функции значения логических индексов будут равны. В среднем случае, который на практике встречается чаще всего, время поиска любого конкретного элемента посредством хеширования соответствует времени прямого индексирования, поделенного на некоторую константу, которая пропорциональна средней длине цепочки индексов хеширования.
Самым существенным при использовании метода хеширования для реализации разряженной матрицы является обеспечение равномерности распределения физических индексов, чтобы не возникало длинных цепочек. Кроме того, метод хеширования очень хорошо использовать в тех случаях, когда известно какое максимальное число элементов действительно потребуется.
Выбор метода реализации разряженных матриц
При выборе связанного списка, двоичного дерева или массива указателей в качестве основы реализации разряженное матрицы следует учитывать эффективность использования оперативной памяти и время доступа.
Если разряженность очень большая, то память наиболее эффективно будет использоваться при применении связанного списка и двоичного дерева, поскольку в данном случае в памяти будут располагаться только требуемые элементы. Связи требуют небольшого дополнительного расхода памяти и обычно на расход памяти влияют незначительно. При использовании массива указателей необходимо предусмотреть место для указателя вне зависимости от наличия элемента. Здесь необходимо предусмотреть не только размещение в памяти всего массива указателей, но обеспечить память для других целей, определяемых конкретной задачей. В одних случаях это вызовет серьезные трудности, хотя в других случаях этих трудностей может не быть. Обычно приходится делать расчет требуемой памяти, чтобы понять, достаточно ли ее будет для вашей программы.
Метод хеширования занимает промежуточное место между методом, построенным на базе массива указателей, и методом, построенным на базе связанного списка или двоичного дерева. Хотя в данном случае требуется размещение в памяти всего физического массива несмотря на то, что часть элементов не будет использована, его размеры все -же будут меньше размеров массива указателей, для которого требуется предусмотреть по крайней мере один указатель для каждого логического элемента.
Однако при почти полном заполнении массива память будет использоваться более эффективно, когда применяется массив указателей. В связанных списках в двоичных деревьях как правило используется два указателя, в то время как массив указателей требует только одного указателя на каждый элемент. Например, полный массив из тысячи элементов, когда каждый указатель занимает два байта, потребует для реализации связанного списка или двоичного дерева 4000 байт для хранения указателей. Для массива указателей в этом случае потребуется 2000 байт, т.е. экономия составляет 2000 байт.
Наименьшее время доступа обеспечивает подход с применением массива указателей. Как в примере с электронной таблицей этот метод часто обеспечивает простой доступ к массиву указателей и просто обеспечивается связь с разреженной матрицей. Этот метод обеспечивает доступ к элементам разреженной матрицы почти со скоростью работы обычного массива. Поиск в связанном списке осуществляется очень медленно, поскольку здесь выполняется последовательный просмотр элементов списка. Даже при добавлении данных в связанный список, обеспечивающих более быстрый поиск элементов, поиск будет выполняться медленней, чем прямой доступ к элементам массива указателей. При использовании двоичного дерева быстродействие повышается, но все-же оно меньше, чем при прямом доступе к элементам массива указателей.
При правильном выборе алгоритма хеширования этот метод часто дает лучшее время доступа, чем время доступа при использовании двоичных деревьев. Однако он никогда не достигнет быстродействия метода массива указателей.
Если возможно применение метода массива указателей, то этот метод является наилучшим из-за очень хорошего быстродействия. Однако, если решающее значение имеет эффективность использования памяти, то остается использовать лишь связанный список или двоичное дерево.
Буферизация
При использовании разряженной матрицы вместо обычных переменных можно применять динамическое выделение памяти под матрицу. Пусть, например, имеется два процесса А и В, выполняющиеся в одной программе. Предположим, что процесс А требует при работе 60% доступной памяти, а при работе процесса В требуется 55% памяти. Если в процессе А и в процессе В память будет выделяться с помощью локальных переменных, то процесс А не сможет обратиться к процессу В, а процесс В не сможет обратиться к процессу А, поскольку потребуется более 100% памяти. Если процесс А не обращается к процессу В, то никаких трудностей не будет. Трудности появятся при попытке процесса А обратиться к процессу В. Выход из этого положения заключается в динамическом выделении памяти и для процесса А и для процесса В с освобождением памяти перед обращением одного процесса к другому процессу. Другими словами, если при выполнении каждого процесса, А и В, требуется более половины имеющейся доступной памяти и процесс А обращается к процессу В, то должно использоваться динамическое распределение памяти. В этом случае процессы А и В будут получать в свое распоряжение память, когда она им действительно потребуется.
Предположим, что при выполнении некоторой программы, использующей две указанные ниже функции, остается 100 000 байт неиспользованной памяти.
procedure B; forward;
procedure A;
var
a:array[1..600000] of char;
.
.
.
begin
.
.
.
B;
.
.
.
end;
procedure B;
var
b:array[1..55000] of char;
begin
.
.
.
end;
Здесь каждый из процессов А и В имеет локальные переменные, на которые расходуется более половины имеющейся доступной памяти. В данном случае нельзя будет выполнить процесс В, поскольку памяти недостаточно для выделения 55 000 байт под локальный массив "в".
В подобных случаях трудности часто оказываются непреодолимыми, но в некоторых случаях кое-что сделать можно. Если процесс А не требует сохранения содержимого массива "а" при выполнении процесса В, то процессы А и В могут совместно использовать один участок памяти. Это можно обеспечить динамическим выделением памяти под массивы А и В. Процесс А перед обращением к процессу В должен освободить память и затем вновь ее получить после завершения процесса В. Программа должна иметь следующую структуру:
procedure B; forward;
procedure A;
var
a:^array[1..600000] of char;
begin
New(a);
.
.
.
Dispose(a); { освобождение памяти для процесса В }
B;
New(a); { новое выделение памяти }
.
.
.
Dispose;
end;
procedure B;
var
b:^array[1..55000] of char;
begin
New(b);
.
.
.
Dispose(b);
end;
При выполнении процесса В существует только указатель "а". Хотя этим методом вы будете пользоваться нечасто, его следует хорошо знать, поскольку он часто является единственным способом решения подобных проблем.
Оптимальное использование доступной памяти на примере текстового редактора
Если вы являетесь профессиональным программистом, то вам возможно приходилось сталкиваться с трудностями, возникающими когда размер доступной памяти заранее неизвестен. Эти трудности возникают при разработке программы, определенные характеристики которой зависят от размера памяти некоторых или всех ЭВМ, где она будет выполняться. Примерами таких программ являются программы управления электронными таблицами, программы обработки списков почтовых корреспонденций и программы сортировки. Например, программа внутренней сортировки, способная отсортировать 10 000 адресов в ЭВМ с памятью 256К, сможет отсортировать лишь 5 000 адресов в ЭВМ с памятью 128К. Если эту программу предполагается использовать на ЭВМ, размер памяти которой заранее неизвестен, то трудно выбрать оптимальный размер фиксированного массива для хранения сортируемой информации: либо программа не будет работоспособна для ЭВМ с малой памятью, либо программа будет рассчитана на худший случай и нельзя будет воспользоваться дополнительной памятью, когда она имеется. Выход из этого положения заключается в динамическом выделении памяти.
Подобные трудности и их решение хорошо можно проиллюстрировать на примере программы редактирования текста. Большинство текстовых редакторов не рассчитаны на использование фиксированного числа символов. Напротив, они используют всю память ЭВМ, которая идет на хранение текста, введенного пользователем. Например, при вводе каждой строки делается выделение памяти и достраивается список строк. При удалении строки память возвращается системе. Для реализации такого текстового редактора может использоваться следующая запись для каждой строки:
LinePointer = ^Line;
str80 = string[80];
Line = record
next: str80; { для хранения каждой строки }
num: integer;
next: LinePointer; {указатель на следующую строку}
prior: LinePointer; {указатель на предыдущую запись }
end;
Для простоты в этом случае для каждой строки выделяется память под 80 символов. На практике будет выделяться память под точное число символов в строке и изменение строки потребует дополнительных затрат. В элементе "num" содержится номер каждой строки текста. Это позволяет использовать стандартную функцию "DLS_Store" для создания и поддержки текстового файла в виде упорядоченного списка с двойной связью.
Ниже приводится полная программа для простого текстового редактора. Он обеспечивает вставку и удаление любых строк с указанием номера строки. Он позволяет также просматривать текст и помещать его на диск.
В целом работа текстового редактора строится на базе применения упорядоченного связанного списка строк текста. В качестве ключа сортировки используется номер строки. Указывая начальный номер строки можно не только легко делать нужные вставки в текст, но также легко можно удалить текст. Единственной необычной функцией является функция "Patchup", которая перенумеровывает строки текста, когда этого требуют операции вставки и удаления.
В этом примере размер текста, который может размещаться в редакторе, зависит от доступной пользователю памяти. Таким образом, этот редактор будет автоматически использовать дополнительную память и не потребует перепрограммирования. Возможно это является самым важным достоинством динамического распределения памяти.
Возможности приводимой программы очень ограничены, однако она обеспечивает основные функции текстового редактора. Эту программу можно усовершенствовать и получить текстовый редактор с требуемыми возможностями.
{ очень простой текстовый редактор }
program TextEd;
type
str80 = string[80];
LinePointer = ^Line;
line = record
text: str80;
num: integer;
next: LinePointer; {указатель на следующую строку}
prior: LinePointer; {указатель на предыдущую запись }
end;
DataItem = line;
filType = file of line;
var
text: filtype;
start, last: LinePointer;
done: boolean;
iname: str80;
{ возвращает выбранную пользователем функцию }
function MenuSelect: char;
var
ch: char;
begin
WriteLn('1. Enter text');
WriteLN('2. Delete a line');
WriteLn('3. Display the file');
WriteLn('4. Save the file');
WriteLn('5. Load the file');
WriteLn('6. Quit');
repeat
WriteLn;
Write('Enter your choice: ');
ReadLn(ch); ch := UpCase(ch);
until (ch>='1') and (ch<='6')
MenuSelect := ch;
end;{ конец выбора по меню }
{ поиск заданной строки и выдача указателя на нее }
function Find(num: integer): LinePointer;
var
i: LinePointer;
begin i:= start;
find := nil;
while (i<>nil) do begin
if lnum=i^.num then find :=i;
i := i^.next;
end;
end;
{ формирование номеров строк при вставке или удаления из
текста }
procedure PatchUp(lnum, incr: integer);
var
i:LinePointer;
begin
i := Find(lnum)
while (i<>nil) do begin
i^.num := i^.num +incr;
i := i^.next
end:
end;
{ упорядоченная вставка строк в текст }
function DLS_Store(info, start: LinePointer;
var last: LinePointer): LinePointer;
var
old, top: LinePointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DLS_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.num < info^.num then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DLS_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DLS_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DLS_Store := top; { сохранение начала }
end;
end;
end; { конец функции DLS_Store }
{ удаление строки текста }
function DL_Delete(start: LinePointer
key: str[80]:) LinePointer
var
temp, temp2: LinePointer
done: boolean;
begin
if star^.num = key then begin { первый элемент
списка }
DL_Delete := start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp <> nil) and (not done) do
begin
if temp^.num = key then
begin
temp2^.next := temp^.next;
if temp^.next = <> nil then
temp^.next^.prior := temp2
done := TRUE
last := temp^.prior
dispose(temp);
end else
temp2 := temp;
temp := temp^.next;
end;
end;
DL_Delete := start; { начало не изменяется }
if not done then Writeln('not found');
else PatchUp(key+1,-1);
end;
end; { конец функции DL_Delete }
{ подсказка пользователю для ввода номера удаляемой строки }
procedure Remove;
var
num:integer;
begin
Writeln('Enter line to delete: ');
Readln(num);
start := DL_Delete(start,num);
end; { конец процедуры удаления }
{ ввод строк текста }
procedure Enter;
var
info: LinePointer;
done: boolean;
begin
done := FALSE;
Write('Enter starting lnie number: ');
Readln(num);
repeat
new(info) { получить новую запись }
info^.num := num;
Write(info^.num,':')
Readln(info^.text);
if Length(info^.text = 0 then done := TRUE
else begin
if Find(num)<> nil then PatchUp(num,1);
start := DLS_Store(info, start, last);
end;
num := num +1;
until done;
end; { конец ввода }
{ вывод файла на экран }
procrdure Display(start: LinePointer);
begin
while start <> nil do begin
Write(start^.num,':');
Writeln(start^.text);
start := start^.next
end;
Writeln;
end;
{ записать файл на диск }
procedure Save(var f:FilType; start: LinePointer):
begin
Writeln('saving file');
rewrite(f);
while start <> nil do begin
write(f,start);
start := start^.next;
end;
end;
{ загрузчика файла с диска и получение указателя на начало
списка }
procedure Load(var f:FilType; start: LinePointer):
LinePointer;
var
temp: LinePointer
begin
Writeln('load file');
reset(f);
while start <> nil do begin
temp := start^.next
dispose(start);
start := temp;
end;
start := nil; last := nil;
if not eof(f) then begin
begin
New(temp);
Read(f,temp^);
start := DLS_Store(temp, start, last);
end;
begin
start := nil; { сначала список пустой }
last := nil;
done := FALSE;
Write('Enter Filename: ');
Readln(filename);
Assign(text,filename);
repeat
case MenuSelect of
'1': Enter;
'2': Remove;
'3': Display(start);
'4': Save(text,start);
'5': start := Load(text);
'6': done := TRUE;
end;
until done = TRUE;
end.Фрагментация
Когда блоки доступной памяти располагаются между участками распределенной памяти, то говорят, что происходит фрагментация памяти. Хотя свободной памяти как правило бывает достаточно, чтобы удовлетворить запрос памяти, однако трудность заключается в том, что размеры отдельных участков свободной памяти недостаточны для этого, несмотря на то, что при их объединении получится достаточный объем памяти. На рис.18 показано, как при определенной последовательности обращения к процедурам "New" и "Dispose" может возникнуть такая ситуация.
Когда блоки доступной памяти располагаются между участками распределенной памяти, то говорят, что происходит фрагментация памяти. Хотя свободной памяти как правило бывает достаточно, чтобы удовлетворить запрос памяти, однако трудность заключается в том, что размеры отдельных участков свободной памяти недостаточны для этого, несмотря на то, что при их объединении получится достаточный объем памяти. На рис.18 показано, как при определенной последовательности обращения к процедурам "New" и "Dispose" может возникнуть такая ситуация.
A,B,C,D:^integer
W,X,Y,Z:^real;
-----T------------------------------------¬
new(A) ¦ A ¦ ¦
L----+------------------------------------ -----T-------T----------------------------¬
new(W) ¦ A ¦ W ¦ ¦
L----+-------+---------------------------- -----T-------T----T-----------------------¬
new(B) ¦ A ¦ W ¦ B ¦ ¦
L----+-------+----+----------------------- -----T-------T----T----T------------------¬
new(C) ¦ A ¦ W ¦ B ¦ C ¦ ¦
L----+-------+----+----+------------------ -----T-------T----T----T-------T----------¬
new(X) ¦ A ¦ W ¦ B ¦ C ¦ X ¦ ¦
L----+-------+----+----+-------+---------- -----T-------T----T----T-------T------T---¬
new(Y) ¦ A ¦ W ¦ B ¦ C ¦ X ¦ Y ¦ ¦
L----+-------+----+----+-------+------+--- -----T-------T----T----T-------T------T---¬
dispose(B)¦ A ¦ W ¦ ¦ C ¦ X ¦ Y ¦ ¦
L----+-------+----+----+-------+------+--- new(Z) Запрос не может быть удовлетворен, поскольку
нет участка непрерывной свободной памяти доста точного размера
В некоторых случаях фрагментация уменьшается, так как функции динамического распределения памяти объединяют соседние участки памяти. Например, пусть были выделены участки памяти A,B,C,и D
/см. ниже/. Затем освобождаются участки B и C. Эти участки можно объединить, поскольку они располагаются рядом. Однако, если освобождаются участки B и D, то объединить их нельзя будет, поскольку между ними находится участок C который еще не освобожден:
________________________
¦ ¦ ¦ ¦ ¦
¦ A ¦ B ¦ C ¦ D ¦
¦_____¦_____¦_____¦_____¦
Так как B и D освобождены, а C занят, то может возникнуть вопрос: "Почему бы Турбо Паскалю не переслать содержимое C в D и затем объединить B и C?" Трудность заключается в том, что ваша программа не будет "знать", что это пересылка произошла.
Один из способов предотвращения большой фрагментации заключается в том, чтобы всегда выделять одинаковые участки памяти. В этом случае все освобожденные участки могут использоваться при любых последующих запросах на выделение памяти и таким образом будет использована вся свободная память. Если нельзя использовать всегда одинаковый размер выделяемых участков, то следует ограничиться только несколькими размерами. Иногда этого можно достигнуть путем объединения нескольких запросов на выделение небольших участков в один запрос на выделение одного большого участка памяти. Не следует для предотвращения фрагментации выделять больше памяти, чем действительно требуется, поскольку получаемая выгода не окупит потерь от неиспользованной памяти. Можно использовать другой подход к решению этой проблемы: при работе программы можно записывать информацию во временный дисковый файл, освободить всю память и затем считать информацию с диска в память. При считывании информации не будет создаваться никаких промежутков.
Динамическое распределение памяти и задачи искусственного интеллекта
Хотя Паскаль не является основным языком, который используется при решении задач искусственного интеллекта, его можно использовать и в этой области. Основной чертой многих программ из области искусственного интеллекта является наличие списка информационных элементов, который может расширяться программой автоматически по мере ее "обучения". В таком языке как Пролог, который считается основным языком искусственного интеллекта, поддержка списка обеспечивается автоматически. На языке Паскаль такие процедуры должны программироваться с применением связанных списков и механизма динамического распределения памяти. Хотя приводимый пример является очень простым, те же принципы применимы для разработки более сложных "разумных" программ.
Одну интересную область искусственного интеллекта составляют программы, работа которых напоминает поведение людей. Знаменитая программа "Элиза", например, ведет себя как психиатр. Совсем неплохо иметь программу, которая может "разговаривать" на любую тему - как было бы хорошо запустить такую программу, когда вы устанете от программирования и почувствуете себя одиноким! Ниже приводиться очень простая версия такой программы. В ней используются слова и их определения для ведения простого диалога с пользователем. Одной общей чертой всех программ искусственного интеллекта является связь информационного элемента с его смыслом. В этом примере слова связываются с их смыслом. Ниже описывается запись, предназначенная для содержания каждого слова, его определения, части речи и его дополнения:
type
str80 = string[80];
str30 = string[30];
VocabPointer = "тильда"vocab;
vocab = record
typ: char; { часть речи }
connotate: char; { дополнение }
word: str30; { само слово }
def: str80; { определение }
next: VocabPointer; { указатель на следующую
запись }
prior: VocabPointer; { указатель на предыдущую
запись }
end
В приводимой ниже программе делается ввод слова, его определения, типа слова и его дополнения типа "хорошо", "плохо" и "безразлично". Для поддержки такого словаря строится связанный список с использованием механизма динамического выделения памяти. Функция "DLS_Store" создает и поддерживает упорядоченный список слов словаря. После ввода нескольких слов в словарь можно начать диалог с ЭВМ. Например, вы можете ввести такое предложение, как "Сегодня хороший день". Программа будет просматривать предложения для поиска имени существительного, которое находится в словаре. Если оно найдено, то будет выдано замечание об этом имени существительном, зависящее от его смысла. Если программа встретит ей неизвестные" слова, то она попросит ввести его и определить его характеристики. Для завершения диалога вводится слово "quit".
Процедура "Talk" является частью программы, которая поддерживает диалог. Вспомогательная функция "Dissect" выделяет из предложения слова. В переменной "sentence" содержится введенное вами предложение. Выделенное из предложения слово помещается в переменную "word". Ниже приводятся функции "Talk" и "Dissect":
{ поочередное выделение слов из предложения }
procedure Dissect(var s:str80;var w:str30);
var
t, x:integer;
temp:str80;
begin
t :=1;
while(s[t]=' ') do t := t+1;
x := t;
while(s[t]=' ') and (t<=Length(s)) do t := t+1;
if t<=Length(s) then t := t-1;
w := copy(s, x, t-x+1);
temp := s;
s := copy(temp,t+1,Length(s))
end;
{ формирование ответов на основании введенного пользователем
предложения }
procedure Talk;
var
sentence: str80
word: str30
w: VocabPointer;
begin
Writeln('Conversation mode (quit to exit)');
repeat
Write(': ')
Readln(sentence)
repeat
Dissect(sentence,word);
w := Search(start, word);
if w <> nil then begin
if w^.type = 'n' then
begin
case w^.connotate of
'g': Write('I like ');
'b': Write('I do not like ');
end;
Writeln(w^.def);
end;
else Writeln(w^.def);
end;
else if word <>'quit' then
begin
Writeln(word,'is unknown.');
enter(TRUE);
end;
until Length(sentence) = 0;
until word = 'quit';
end;Ниже приводится вся программа:
{ программа, которая позволяет вести очень простой диалог }
program SmartAlec;
type
str80 = string[80];
str30 = string[30];
VocabPointer = ^vocab
vocab = record;
typ: char; { часть речи }
connotate: char; { дополнение }
word: str80; { само слово }
def: str30; { определение }
next: VocabPointer; { указатель на следующую
запись }
prior: VocabPointer; { указатель на предыдущую
запись }
DataItem = vocab;
DataArray = array [1..100] of VocabPointer
filtype = file of vocab;
var
test: DataArray;
smart: filtype;
start, last:VocabPointer;
done: boolean;
{ возвращает функцию, выбранную пользователем }
function MenuSelect:char;
var
ch: char;
begin
Writeln('1. Enter words');
Writeln('2. Delete a word');
Writeln('3. Display the list');
Writeln('4. Search for a word');
Writeln('5. Save the list');
Writeln('6. Load the list');
Writeln('7. Converse');
Writeln('8. Quit');
repeat
Writeln;
Write('Enter your choice: ');
Readln(ch);
ch := UpCase(ch);
until (ch>='1') and (ch<='8')
MenuSelect := ch;
end;{ конец выбора по меню }
{ добавление элементов в словарь }
function DLS_Store(info, start: VocabPointer;
var last: VocabPointer): VocabPointer;
var
old, top: VocabPointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DLS_Store := info;
end else
begin
while (start<>nil) and (not cone) do
begin
if start^.word < info^.word then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DLS_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DLS_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DLS_Store := top; { сохранение начала }
end;
end;
end; { конец функции DLS_Store }
{ удаление слова }
function DL_Delete(start: VocabPointer
key: str[80]:) VocabPointer
var
temp, temp2: VocabPointer
done: boolean;
begin
if star^.num = key then begin { первый элемент
списка }
DL_Delete := start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp <> nil) and (not done) do
begin
if temp^.word = key then
begin
temp2^.next := temp^.next;
if temp^.next = <> nil then
temp^.next^.prior := temp2
done := TRUE;
if last := temp then last := last^.prior
dispose(temp);
end else
begin
temp2 := temp;
temp := temp^.next;
end;
end;
DL_Delete := start; { начало не изменяется }
if not done then Writeln('not found');
end;
end; { конец функции DL_Delete }
{ удаление слова, заданного пользователем }
procedure remove;
var
name:str80;
begin
Writeln('Enter word to delete: ');
Readln(name);
start := DL_Delete(start,name);
end; { конец процедуры удаления слова, заданного
пользователем}
{ ввод слов в базу данных }
procedure Enter;
var
info: VocabPointer;
done: boolean;
begin
done := FALSE;
repeat
new(info) { получить новую запись }
Write('Enter word: ');
Readln(info^.word);
if Length(info^.word)=0 then done := TRUE
else
begin
Write(Enter type(n,v,a): ');
Readln(info.typ);
Write(Enter connotation (g,b,n): ');
Readln(info.connotation);
Write(Enter difinition: ');
Readln(info.dif);
start := DLS_Store(info, start, last); { вставить
запись }
end;
until done or one;
end; { конец ввода }
{ вывод слов из базы данных }
procrdure Display(start: VocabPointer);
begin
while start <> nil do begin
Writeln('word',start^.word);
Writeln('type',start^.typ);
Writeln('connotation',start^.connotation);
Writeln('difinition',start^.def);
Writeln;
start := start^.next
end;
end; {конец процедуры вывода }
{ поиск заданного слова }
function Search(start: VocabPointer; name: str80):
VocabPointer;
var
done: boolean;
begin
done := FALSE
while (start <> nil) and (not done) do begin
if word = start^.word then begin
search := start;
done := TRUE;
end else
start := star^.next;
end;
if start = nil then search := nil; { нет в списке }
end; { конец поиска }
{ поиск слова,заданного пользователем }
procedure Find;
var
loc: VocabPointer;
word: str80;
begin
Write('Enter word to find: ');
Readln(word);
loc := Search(start, word);
if loc <> nil then
begin
Writeln('word',loc^.word);
Writeln('type',loc^.typ);
Writeln('connotation',loc^.connotation);
Writeln('difinition',loc^.def);
Writeln;
end;
else Writeln('not in list')
Writeln;
end; { Find }
{ записать словарь на диск }
procedure Save(var f:FilType; start: VocabPointer):
begin
Writeln('saving file');
rewrite(f);
while start <> nil do begin
write(f,start);
start := start^.next;
end;
end;
{ загрузить словарь с диска }
procedure Load(var f:FilType; start: VocabPointer):
VocabPointer;
var
temp, temp2: VocabPointer
first: boolean;
begin
Writeln('load file');
reset(f);
while start <> nil do begin
temp := start^.next
dispose(start);
start := temp;
end;
start := nil; last := nil;
if not eof(f) then begin
New(temp);
Read(f,^temp)
start := DLS_Store(temp,start,last);
end;
Load := start;
end; { Load }
{ поочередное выделение слов из предложения }
procedure Dissect(var s:str80;var w:str30);
var
t, x:integer;
temp:str80;
begin
t :=1;
while(s[t]=' ') do t := t+1;
x := t;
while(s[t]=' ') and (t<=Length(s)) do t := t+1;
if t<=Length(s) then t := t-1;
w := copy(s, x, t-x+1);
temp := s;
s := copy(temp,t+1,Length(s))
end;
{ формирование ответов на основании введенного пользователем
предложения }
procedure Talk;
var
sentence: str80
word: str30
w: VocabPointer;
begin
Writeln('Conversation mode (quit to exit)');
repeat
Write(': ')
Readln(sentence)
repeat
Dissect(sentence,wort);
w := Search(start, word);
if w <> nil then begin
if w^.type = 'n' then
begin
case w^.connotate of
'g': Write('I like ');
'b': Write('I do not like ');
end;
Writeln(w^.def);
end;
else Writeln(w^.def);
end;
else if word <>'quit' then
begin
Writeln(word,'is unknown.');
enter(TRUE);
end;
until Length(sentence) = 0;
until word = 'quit';
end;
begin
start := nil;
last := nil;
done := FALSE;
Assign(smart,'smart.dfd')
repeat
case MenuSelect of
'1': Enter(FALSE);
'2': Remove;
'3': Display(start);
'4': Find;
'5': Save(smart,start);
'6': start := Load(smart,start);
'7': Talk;
'8': done := TRUE;
end;
until done=TRUE;
end.Эта программа составляется несложно. Вы можете ее несколько усовершенствовать. Можно, например, выделить из предложения глаголы и заменить их на альтернативные в комментарии. Вы можете также предусмотреть возможность задавать вопросы.
Глава 4. Интерфейс с программами на ассемблере и связь с операционной системой
Имея такой мощный инструмент программирования, как Турбо Паскаль, иногда вам потребуется составить программу на ассемблере или сделать вызов системной программы. Это может потребоваться для ускорения вашей программы или для обеспечения доступа к некоторому специальному оборудованию, применение которого непосредственно в Турбо Паскале не предусмотрено. Какими бы причинами не объяснялось применение ассемблера, оно предусматривается в рамках языка Турбо Паскаль.
Приводимые в этой главе примеры рассчитаны на применение версии ИБМ языка Турбо Паскаль в рамках операционной системы ДОС. Более того, эти примеры рассчитаны на применение версии 4 языка Турбо Паскаль. Следует иметь в виду, что в версии 4 языка Турбо Паскаль интерфейс с ассемблером отличается от такого интерфейса для более ранних версий. Если вы имеете предыдущую версию или версию для другой ЭВМ, то подробную информацию об интерфейсе с ассемблером можно найти в руководстве пользователя.
Интерфейс с ассемблером
Имеется несколько причин, по которым требуется составлять программу на ассемблере:
- для повышения скорости работы и эффективности использования памяти;
- для выполнения машинно-зависимых функций, которые отсутствуют в Турбо Паскале;
- для того, чтобы можно было воспользоваться пакетом программ общего назначения, написанных на ассемблере.
Хотя компилятор языка Турбо Паскаль создает эффективный компактный объектный код, никакой компилятор не сможет постоянно создавать более эффективный и компактный код, чем код, написанный компетентным программистом. Небольшое различие обычно не означает, что при написании программы на ассемблере не потребуется затратить заметно больше времени. Однако в особых случаях требуется составлять программы и процедуры на ассемблере, чтобы обеспечить быструю работу программы. Это требуется делать для часто используемых программ и процедур, существенно влияющих на общее быстродействие программы. Хорошим примером такого применения ассемблера является пакет подпрограмм, выполняющих операции над числами с плавающей запятой. Кроме того, специальное оборудование иногда требует точной синхронизации в работе, которая обеспечивается только программированием на ассемблере.
Многие ПЭВМ, включая машины, построенные на базе процессоров 8086 и 8088, обладают возможностями, которыми нельзя воспользоваться непосредственно на Турбо Паскале. Например, используя Турбо Паскаль нельзя изменить сегменты данных и возникают трудности при доступе к специальным регистрам.
На практике часто приобретаются библиотеки подпрограмм. В качестве таких библиотек подпрограмм можно назвать широко распространенные библиотеки подпрограмм для работы с числами с плавающей запятой и пакеты графических программ. Иногда имеются только объектные коды этих подпрограмм, поскольку разработчик не поставляет исходные тексты. В одних случаях эти подпрограммы могут просто вызываться в программе на Паскале. В других случаях приходится составлять интерфейсный модуль для обеспечения связи Турбо Паскаля с приобретенными подпрограммами.
Имеется два способа применения ассемблера в программе на Турбо Паскале. Во-первых, можно написать отдельную программу, ассемблировать ее и затем подсоединить ее к основной программе, используя команду "external". Во-вторых, в программе на языке TURBO-Паскаль можно непосредственно записывать код на ассемблере.
Обучение программированию на языке ассемблера выходит за рамки этой книги. В этой главе подразумевается, что вы уже знакомы с языком ассемблера, который имеется на вашей ЭВМ. Приводимые примеры только иллюстрируют применение ассемблера.
Внутренние форматы данных и соглашения о связях в языке Турбо Паскаль
Прежде чем писать подпрограмму на ассемблере для использования ее в программе на языке Турбо Паскаль необходимо понять , как данные представляются в программе и как они передаются между подпрограммами. Для версии ИБМ все глобальные переменные и константы хранятся в сегменте данных и доступ к ним осуществляется с использованием регистра DS. Все локальные переменные помещаются в стек и доступ к ним осуществляется с применением регистра ВР, который используется для индексации стека. Рис.19 показывает способ хранения для данных каждого типа. Следует иметь в виду, что байты указателей задаются в обратном порядке. Следовательно, указатель, имеющий смещение В000 и сегмент 0010, будут храниться в следующем виде:
-------¬ -------¬ -------¬ -------¬
¦ 10 ¦ ¦ 00 ¦ ¦ 00 ¦ ¦ B0 ¦
L------- L------- L------- L------.
Сегмент Смещение
Соглашения о связях представляют собой метод, который используется компьютером языка Турбо Паскаль для передачи информации подпрограмм и передачи результатов. В языке Турбо Паскаль для передачи параметров в подпрограмму используется стек /он также используется для передачи результатов функции/. При этом в регистре АХ передается результат однобайтовой или однословной функции. Точное содержимое стека при вызове подпрограммы запвисит от типа передаваемых переменных и от типа передачи параметра.
Параметры-значения
Параметры-значения передаются в одном направлении: в подпрограмму передается значение параметра, но любые изменения этого параметра не оказывают влияния на действительную переменную, которая использовалась при вызове подпрограммы. Подпрограмме передается не адрес этой переменной, а копия ее значения и поэтому сама переменная не изменяется. По существу процедуре и функции передается лишь некоторое значение.
Значения будут помещаться в стек при передаче параметров следующих типов:
- двоичного /булевского/;
- символьного;
- целого;
- целого длинного;
- целого короткого;
- байта;
- слова;
- вещественного;
- указателя;
- перечисления.
Для двойных слов сначала в стек помещается старшая часть значения и затем младшая часть.
Массивы и записи, размер которых превышает четыре байта, в действительности не передаются функции. Передается адрес /сегмент и смещение/ переменной. Сначала в стек помещается сегмент и затем смещение. /Массивы, размер которых меньше пяти байт непосредственно помещаются в стек/. Множества и строки тоже передаются с использованием указателей на действительные переменные. Поскольку для данных этих типов в функции передаются адреса, необходимо делать копии действительных данных, чтобы изменения данных, произведенные внутри функции, не повлияли на эти переменные вне функции.
Параметры-переменные
В отличии от параметров-значений параметры-переменные передаются посредством помещения в стек адресов. Это значит, что подпрограмма работает непосредственно с этими переменными. Параметрыпеременные передаются в обоих направлениях, т.е. информация передается в подпрограмму и может также передаваться обратно в вызывающую программу, поскольку значение параметров может меняться. Для передачи сегмента и смещения параметра-переменной в стек помещается два слова вне зависимости от типа переменной.
Передача результата функции
Когда написанная на языке Турбо Паскаль функция завершает свою работу, она передает значение результата обратно в вызывающую программу. Для всех скалярных типов кроме вещественного значение передается через регистр АХ. Для булевской переменной должен также устанавливаться флажок нуля: единичное значение означает булевское значение "истина", а нулевое значение означает булевское значение "ложь". При передачи указателей сегмент передается в регистр DX, а смещение передается в регистр АХ. Вещественные переменные передаются в виде DX:BX:AX, причем в регистр DX помещается старшее слово, а в регистр АХ помещается младшее слово.
При передаче в качестве результата символьных строк, массивов и записей адрес значения передается в виде DX:AX. Результат функции помещается сразу за адресом возврата. На рис.20 показан вид стека при вызове функции.
-----------------------¬
¦ Параметры ¦
¦ . . . ¦
+----------------------+
Вершина стека ---- ¦ Адрес возврата ¦
+----------------------+
¦ ¦
¦ ¦
L----------------------
Рис.20. Вид стека при вызове функции
Сохранение регистров
Во всех подпрограммах на ассемблере необходимо предусмотреть сохранение регистров BP, DS и SS. Обычно это делается при помощи инструкций "push" и "pop".
Если составляется программа на ассемблере, которая будет обращаться к подпрограмме на языке Турбо Паскаль, то нужно следовать всем соглашениям о связях, которые рассматривались ранее.
Только при соблюдении этих соглашений можно обеспечить правильный вызов программы на языке Турбо Паскаль из модуля, написанном на ассемблере.
Создание внешней программы на ассемблере
Теперь, когда рассмотрены соглашения о связях, приведем код действительной программы на ассемблере. Предположим, что требуется составить программу на ассемблере для следующей функции:
function Xmul(a, b: integer): integer; begin
a: = a*b;
Xnul: = a;
end;
Поскольку эта функция будет вызываться из программы на TURBO-Паскале, то два аргумента целого типа будет помещаться в стек, занимая два слова. Поэтому при следующем вызове функции
xmu(10,20);
первым будет помещаться в стек значение 20 и затем значение 10. Следует помнить, что для скалярных переменных значения по мещаются в стек. Для массива и записи в стек помещается адрес.
Результат этой функции будет помещен в регистр АХ. Ниже приводится код этой функции на ассемблере:
code segment 'code'
assume cs:code
public xmul
xmul proc near
;сохранить указатель стека
push bp
mov bp,sp
;получить первый параметр
mov ax,[bp]+4
;умножить на второй параметр
mul word ptr [bp]+6
;восстановить "вр" и очистить стек
;результат уже находится в регистре АХ
pop bp
ret 4
xmul endp
code ends
end
Следует отметить, что все регистры сохраняются при помощи инструкций "push" и "рор" и доступ к аргументам осуществляется через стек. Кроме того, функция "xmul" объявлена как "public". Это необходимо для обеспечения Турбо Паскалем ее правильной связи с остальной программой. Если вы незнакомы с ассемблером процессоров 8086 и 8088, то вам могут помочь следующие пояснения. Рассмотрим следующий код:
mov bp,sp
mov ax,[bp]+4.
Эти инструкции помещают адрес вершины стека в регистр ВР и затем сдвигают четвертый байт дальше в стек /т.е. параметр "а" помещается в регистр АХ/. Параметры занимают четвертый и шестой байты, поскольку адрес возврата и инструкция "push bp" занимают четыре байта. Следовательно, параметры начинаются на четыре байта ниже вершины стека.
Внешняя функция "xmul" является "близкой" процедурой. Если процедура объявляется в программе или в разделе реализации блока, она должна объявляться с параметром "near". Если внешняя функция объявляется в секции интерфейса блока, то она должна будет объявляться с параметром "far".
Перед использованием этой внешней функции она должна быть ассемблирована с применением макроассемблера фирмы "Майкроусофт". Следует помнить, что все процедуры, функции и переменные, к которым необходимо обеспечить доступ в вашей программе, должны объявляться с параметром "public".
В вашей программе на Турбо Паскале можно использовать указанную внешнюю функцию следующим образом:
{программа, которая обеспечивает связь с внешней подпрог
раммой, написанной на ассемблере}
program asmtest;
{SL XMUL}
var
a, b, c: integer;
function xmul(x, y: integer): integer; external;
begin
a: = 40;
b: = 20;
c: = xmul(a,b); {умножение "а" на "в" и получение
результата}
WriteLn(c);
end.
Директива компилятора $L используется для указания на необходимость подсоединения к программе объектного кода модуля "xmul".
Следует помнить, что все примеры даются для ассемблера процессоров 8086 и 8088. Если используется Турбо Паскаль версии СР/М, то примеры должны быть изменены в соответствии с руководством пользователя по Турбо Паскалю. Кроме того, связь с подпрограммами на языке ассемблера будет отличаться для TURBOПаскаля версий более ранних, чем версия 4.0.
Встроенный код ассемблера
В отличие от стандартного Паскаля в Турбо Паскале предусматривается возможность непосредственного включения кода на ассемблере. Таким образом, нет необходимости составлять отдельную внешнюю подпрограмму. Такой подход имеет два преимущества: во-первых, программист не должен писать код, реализующий связь между программами; во-вторых, весь код расположен в одном месте, что делает простой сопровождение программы. Единственный недостаток заключается в том, что встроенный код ассемблера имеет неудобный формат.
Оператор "inline" позволяет внутри программы на Турбо Паскале использовать код на ассемблере. Общая форма этого оператора будет следующей:
inline (значение/.../значение);
где "значение" представляет собой любую правильную инструкцию ассемблера или данные. Для ссылки на счетчик адреса может использоваться звездочка. (В ассемблере процессора 8088 для этой цели используется валютный знак. Поскольку в Турбо Паскале валютный знак используется для шестнадцатиричных чисел, то для обозначения счетчика адреса используется звездочка).
Для малых значений, которые могут разместиться в одном байте, используется только один байт. В противном случае для хранения переменной используются два байта. Если вы хотите поступить иначе, то следует воспользоваться директивами ">" и "<". Если перед значением стоит знак меньше, то будет использован только младший байт. Если перед значением стоит знак больше, то будет сформировано двубайтовое слово с нулевым старшим байтом. Например, <$1234 приведет к формированию только одного байта со значением $34, a >$12 приведет к формированию двух байт со значением $
0012.
Следующая короткая программа перемножает два целых числа, используя функцию "Mul", которая использует код на ассемблере для выполнения действительного умножения. Сравните эту программу с внешней подпрограммой "xmul", которая рассматривалась в предыдущем разделе.
{ пример встроенного кода ассемблера }
program asm_inline;
var
a, b, c: integer;
function Mul(x, y: integer): integer;
begin
inline($80/$46/$04/ {mov ax,[bp]+4}
$F6/366/$06/ {mul [bp]+6 }
$89/$EC/ {mov sp,bp}
$56/ {pop bp}
$02/$06/$00/ {ret 6}
end;
begin
a: = 10;
b: = 20;
c: = Mul(a,b);
WriteLn(c);
end.В данном случае компилятор Турбо Паскаля автоматически генерирует код для возврата из функции. Когда компилятор встречает оператор "inline", в этом месте он генерирует указанные оператором машинные инструкции.
Часто встроенный код ассемблера используется для обеспечения связи с оборудованием, которое не поддерживается непосредственно в языке Турбо Паскаль. Например, приводимая ниже подпрограмма может использоваться для включения вентилятора, когда показание датчика температуры достигнет определенной величины. В данном случае предполагается, что установка в единичное значение порта 200 приводит к включению вентилятора:
procedure fan(temp:integer);
{вентилятор включается, когда температура достигнет 100
градусов }
begin
if temp>=100 then
inline(100/00/01/ {mov AX,1}
$E7/$C8); {out 200,AX}
end;
Следует помнить, что компилятор Турбо Паскаля обеспечивает необходимый код для входа и выхода из функции. Пользователю необходимо лишь обеспечить тело функции и придерживаться соглашений о связях при доступе к аргументам.
При использовании указанного метода создается машинно-зависимый код, что затрудняет перенос программы на новую машину или в среду новой операционной системы. Однако в тех случаях, когда нельзя обойтись без кода ассемблера, применение указанного метода оправдано.
Когда следует применять ассемблер
Большинство программистов используют ассемблер только при крайней необходимости, поскольку программировать на ассемблере достаточно сложно. Общее правило заключается в том, что вообще не следует использовать ассемблер - он создает слишком много проблем. Однако можно указать два случая практического применения ассемблера. Первый возникает когда нет другого пути решения задачи. Например, когда требуется обеспечить непосредственную связь с оборудованием, управление которым не предусмотрено в языке Турбо Паскаль.
Во-вторых, такая ситуация возникает при необходимости уменьшения времени выполнения программ и все возможности оптимизации кода Турбо Паскаля исчерпаны. В данном случае необходимо делать тщательный выбор функций для их кодирования на ассемблере. Если выбор будет сделан неправильно, то эффект будет незначительный. При правильном выборе эффект может быть очень большим. Для того, чтобы определить какие подпрограммы требуют перекодировки, необходимо определить операционную блок-схему вашей программы. Обычно для реализации на ассемблере выбираются подпрограммы, которые используются внутри циклов, поскольку они выполняются много раз. Кодирование на ассемблере процедуры или функции, которые выполняются один или два раза, может не дать заметного эффекта, а кодирование на ассемблере функции, которая выполняется много раз, может дать такой эффект. Например, рассмотрим следующую процедуру:
procedure ABC;
var
t: integer;
begin
init;
for t:=0 to 1000 do begin
phase1;
phase2;
if t=10 then phase3;
end;
byebye;
end;
Перекодировка процедур "init" и "byebye" может не повлиять заметно на скорость выполнения программы, поскольку они выполняются только один раз. Процедуры "phase1" и "phase2" выполняются 1000 раз и их перекодировка несомненно даст заметный эффект. Несмотря на то, что процедура "phase3" расположена внутри цикла, она выполняется лишь один раз и поэтому ее перекодировка не даст эффекта.
При тщательном выборе процедур для их кодировки на ассемблере можно добиться улучшения быстродействия программы за счет перекодировки лишь небольшого числа подпрограмм.
Связь с операционной системой
Поскольку часто системные программы пишутся на языке Турбо Паскаль, необходимо обеспечить непосредственную связь с операционной системой для выполнения определенных операций в обход стандартного интерфейса Турбо Паскаля. Может возникнуть также потребность в специальных системных функциях, которые отсутствуют в Турбо Паскале. По этой причине применение специальных средств операционной системы является обычным при программировании на Турбо Паскале.
В настоящее время несколько операционных систем поддерживает Турбо Паскаль:
- PC-DOS или MS-DOS;
- СР/М;
- СР/М-86. Все операционные системы предусматривают возмож.
ность применения в программах таких функций, как открытие дисковых файлов, ввод символов с консоли и вывод символов на консоль, выделение памяти для выполнения программы. Способ применения этих функций зависит от операционной системы, но во всех случаях используется таблица переходов. В такой операционной системе как СР/М вызов системной функции осуществляется инструкцией CALL с передачей управления в определенный участок памяти, когда регистр содержит требуемый код функции. В операционной системе PC-DOS применяется программное прерывание. В обоих случаях для связи системной функции с вашей программой используется таблица переходов. На рис.21 показано расположение операционной системы и таблицы переходов в памяти.
----------------------¬
¦ Операционная ¦ -------¬
------- ¦ система ¦ ----¬ ¦
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦
¦ --- ¦ ¦ ¦ ¦
¦ ¦ +---------------------+ ¦ ¦
¦ ¦ ¦ . . . ¦ ¦ ¦
¦ ¦ +---------------------+ ¦ ¦
¦ ¦ ¦ Функция 4 --+-----+--
¦ ¦ +---------------------+ ¦
¦ ¦ ¦ Функция 3 --+-----
¦ ¦ +---------------------+
¦ L---+- Функция 2 ¦
¦ +---------------------+
L-------+- Функция 1 ¦
L---------------------.
Рис.21. Расположение в памяти операционной системы и таблицы переходов
В этой книге нет возможности рассмотреть все операционные системы. В этой главе будет рассматриваться только операционная система PC-DOS, получившая наибольшее распространение. Однако рассматриваемые здесь общие методы применимы и для других операционных систем.
Доступ к системным ресурсам в операционной системе PC-DOS
В операционной системе PC-DOS доступ к системным функциям осуществляется посредством программных прерываний. Каждое прерывание позволяет сделать обращение к функциям определенной категории. Тип функции определяется значением регистра АН. Дополнительная информация при необходимости передается через регистры AL,
BX, CX и DX. Операционная система PC-DOS состоит из базовой системы ввода-вывода и ДОС /дисковой операционной системой/. Базовая система ввода-вывода обеспечивает процедуры ввода-вывода самого низкого уровня, которые используются в ДОС для реализации процедур ввода-вывода более высокого уровня. Возможности этих двух систем перекрываются, однако в основном доступ к ним осуществляется одинаково. Ниже дается список таких прерываний:
Прерывание Функция
5 Утилита вывода экрана
10 Ввод-вывод на дисплей
11 Список оборудования
12 Размер памяти
13 Ввод-вывод на диск
14 Ввод-вывод на последовательный порт
15 Управление кассетой
16 Ввод-вывод с помощью клавиатуры
17 Ввод-вывод на печать
18 Вызов Бейсика, расположенного в ПЗУ
19 Выполнить начальную загрузку
21 Вызов процедуры ДОС высокого уровня
IA Время и дат.
Полный список прерываний и их подробное описание можно найти в техническом справочном руководстве фирмы ИБМ.
Каждое из этих прерываний предоставляет ряд возможностей, которые зависят от значения регистра АН. В табл.1 дается неполный список возможностей для каждого прерывания. К функциям, которые приводятся в табл.1 можно обращаться двумя способами. Во-первых, посредством предусмотренной в Турбо Паскале встроенной функции MsDos /для операционной системы PC-DOS/. Во-вторых, через интерфейс с ассемблера.
Применение процедуры MsDos
Процедура MsDos осуществляет прерывание 2In для доступа к одной из функций операционной системы высокого уровня. Обращение к этой процедуре имеет следующий общий вид:
MsDos(регистры);
где "регистры" представляет собой запись типа "registrs", которая определяется в блоке ДОС. Регистровый тип определяется следующим образом:
regisrers = record
Case integer of
0: (AX, BX, CX, DX, BP, SI, DI,
DS, ES, FLAGS: word);
1: (AL, AH,BL, BH, CL, CH, DL, DH: byte);
end;
Такое определение позволяет вам смешивать значения типа "байт" и "слово". В каждой конкретной ситуации вы должны решить какой тип подходит лучше.
Приводимые ниже в этой главе примеры отчасти дублируют стандартные процедуры, которые уже реализованы в Турбо Паскале. Такой выбор сделан по трем причинам. Во-первых, Турбо Паскаль имеет почти все, что требуется в большинстве случаях. Вовторых, требуется возможно полнее проиллюстрировать принципы построения интерфейса, чтобы можно было их применить в конкретных ситуациях. В-третьих, приводимые примеры в некоторой мере проясняют способ реализации процедур и функций в Турбо Паскале.
Ниже приводится простой пример. Эта функция определяет было ли нажатие клавиши. Она аналогична функции "keyressed", встроенной в язык Турбо Паскаль. Результат этой функции "KbHrt" будет
"истина", если нажата некоторая клавиша, или "ложь" в противном случае. Она использует прерывание 21n с шестнадцатиричным номером $B. Следует помнить, что перед шестнадцатиричным числом должен стоять валютный знак, который для компилятора является указателем шестнадцатиричного числа. Сама программа будет выводить на экран точки до тех пор, пока не будет нажата какая-нибудь клавиша:
{ демонстрация процедуры MsDos }
program kb;
uses Dos;
function KbHit:boolean; { функция специфична для DOS }
var
regs: registers;
begin
regs.AY:=SB;
MsDos(regs);
if regs.AL=0 then KbHit:=FALSE
else KbHit:=TRUE;
end;
begin
repeat
Write('.');
until KbHit;
end.Следует отметить, что в этом вызове нет необходимости задавать значения остальным регистрам, поскольку здесь требуется функция с единственным номером $B. В общем случае если какой-то регистр не используется при вызове, то его значение может не устанавливаться.
Таблица 1
Системные подпрограммы, вызываемые посредством прерываний
---------------------------------------------------------------
Регистр АН Функция
---------------------------------------------------------------
Функции ввода-вывода на дисплей - прерывание 10h
0 Установка режима экрана
Если AL=0: 40х25 черно-белый;
1: 40х25 цветной;
2: 80х25 черно-белый;
3: 80х25 цветной;
4: 320х200 цветной графический;
5: 320х200 черно-белый графический;
6: 340х200 черно-белый графический
1 Установка строк курсора
Биты 0-4 СН содержат начало строки,
биты 5-7 нулевые;
биты 0-4 CL содержат конец строки,
биты 5-7 нулевые
2 Установка позиции курсора
DH: строка,
DL: столбец,
ВН: номер страницы экрана
3 Читать позицию курсора
ВН: номер страницы экрана
Результат:
DH: строка,
DL: столбец,
СХ: режим
4 Читать позицию светового пера
Результат:
если АН=0, то световое перо не инициировано;
если АН=1, то световое перо инициировано;
DH: строка,
DL: столбец,
СН: строка растра (0-199)
ВХ: столбец элемента изображения (0-319 или
0-639)
5 Установка активной страницы экрана
AL может принимать значение от 0 до 7
Функции ввода-вывода на дисплей - прерывание 10h
6 Просмотр страницы вверх
AL: число сдвигаемых строк (от нуля до всех)
СН: строка верхнего левого угла,
CL: столбец верхнего левого угла,
DH: строка нижнего правого угла,
DL: столбец нижнего правого угла,
ВН: атрибуты пустой строки
7 Просмотр страницы вниз
см. предыдущую функцию
8 Чтение символа в позиции курсора
ВН: страница экрана,
Результат:
AL: считанный символ,
АН: атрибут
9 Записать символ и атрибут в позицию курсора
ВН: страница экрана,
BL: атрибут,
СХ: число символов записи,
AL: символ
10 Записать символ в текущей позиции курсора
ВН: страница курсора,
СХ: число символов записи,
AL: символ
11 Установить палитру цвета
ВН: номер палитры,
BL: цвет
12 Записать точку
DX: номер строки,
СХ: номер столбца,
AL: цвет
13 Читать точку
DX: номер строки,
СХ: номер столбца
Результат:
AL: считанная точка
14 Записать символ на экран и продвинуть курсор
AL: символ,
BL: цвет,
ВН: страница экрана
15 Читать состояние экрана
Результат:
AL: текущий режим,
АН: число столбцов на экране,
ВН: текущая активная страница экрана
Список оборудования - прерывание 11h
Читать список оборудования
Результат:
АХ: список установленного оборудования:
бит 0: имеется одна из дискет,
бит 1: не используется,
бит 2,3: ЗУ системной платы, 11=64К,
бит 4,5: начальный режим экрана:
10: 80 столбцов, цветной,
11: монохромный,
01: 40 столбцов, цветной,
бит 6,7: число дисковых накопителей, 0=1
бит 8: установка микросхемы прямого доступа в
память, 0 - установлена
бит 9,10,11: число портов интерфейса RS-232
бит 12: 1 - установлен игровой адаптер,
бит 13: 1 - последовательное печатающее
устройство /только типа PCir/
бит 14,15: число печатающих устройств
Размер памяти - прерывание 12h
Результат представляет собой число килобайт
оперативной памяти, имеющейся в системе
Результат:
АХ: число килобайт ОЗУ
Функции ввода-вывода на диск - прерывание 13h
0 Сброс дисковой системы
1 Чтение состояния диска
Результат:
AL: состояние/см.техническое справочное
руководство фирмы ИБМ/
2 Чтение секторов в память
DL: номер драйвера,
DH: номер головки,
СН: номер дорожки,
CL: номер сектора,
AL: число считываемых секторов,
ES:BX: адрес буфера
Результат:
AL: число считанных секторов,
АН: нуль при успешном чтении, в противном
случае выдается состояние
3 Запись секторов на диск
/как для операции чтения/
4 Проверить
/как для операции чтения/
5 Формат дорожки
DL: номер драйвера,
DH: номер головки,
СН: номер дорожки,
EL:BX: информация сектора
Функции ввода-вывода посредством клавиатуры - прерывание 16h
0 Чтение кода сканирования
Результат:
АН: код сканирования,
AL: код символа
1 Получить состояние буфера
Результат:
ZE: 1 при пустом буфере,
0 при наличии символов и следующим
символом в регистре АХ
2 Получить состояние клавиатуры
(см.техническое справочное руководство
фирмы IBM)
Функции ввода-вывода на печатающее устройство - прерывание
17h
0 Печатать символ
AL: символ,
DX: номер печатающего устройства
Результат:
АН: состояние
1 Инициализировать печатающее устройство
DX: номер печатающего устройства
Результат:
АН: состояние
2 Читать состояние
DX: номер печатающего устройства
Результат:
АН: состояние
Функции ДОС высокого уровня - прерывание 21h (неполный
список)
1 Чтение символа с клавиатуры
Результат:
AL: символ
2 Вывод символа на экран
DL: символ
3 Чтение символа с асинхронного порта
Результат:
AL: символ
4 Запись символа по асинхронному порту
DL: символ
5 Выдать символ на устройство из списка
DL: символ7 Чтение символа с клавиатуры без вывода на экран
Результат:
AL: символ
В Проверить состояние клавиатуры
Результат:
AL: OFFH при нажатии клавиши; 0 в противном
случае
D Сбросить диск
E Установить стандартный драйвер
DL: номер драйвера /0-А, 1-В,.../
11 Поиск имени файла
/4Е под 2.х/ DX: адрес блока FCB
Функции ввода-вывода на экран - прерывание 10h
Результат:
AL: 0, если найден, FFh, если не найден
12 Найти следующее имя файла
/4F под 2.х/ /как в предыдущем случае/
1А Установить адрес передачи диска
DX: адрес передачи диска
2А Получить дату системы
Результат:
СХ: год /1980-2099/,
DX: месяц /1-12/,
DL: день /1-31/
2В Установить системную дату
СХ: год /1980-2099/,
DH: месяц /1-12/,
DL: день /1-31/
2С Получить системное время
Результат:
СН: часы /0-23/,
CL: минуты /0-59/,
DH: секунды /0-59/,
DL: сотые секунды /0-99/
2D Установить системное время
СН: часы /0-23/,
CL: минуты /0-59/,
DH: секунды /0-59/,
DL: сотые секунды /0-99/
Использование функций базовой системы ввода-вывода и ДОС
В некоторых случаях желательно иметь возможность использовать внешние программы, написанные на ассемблере, для доступа к системным функциям. Рассмотрим несколько примеров. Пусть во время работы программы требуется изменить режим экрана. Ниже приводятся семь режимов экрана при использовании цветного графического адаптера в операционной среде PC-DOS:
Режим Тип Размеры Адаптеры
0 Текст, черно- 40 х 25 CGA, EG.
белый
1 Текст, 16 40 х 25 CGA, EG.
цветов
2 Текст, черно- 80 х 25 CGA, EG.
белый
3 Текст, 16 80 х 25 CGA, EG.
цветов
4 Графика, 4 320 х 200 CGA, EG.
цвета
5 Графика, 4 320 х 200 CGA, EG.
черно-белы.
тона
6 Графика 640 х 200 CGA, EG.
черно-белая
7 Текст, черно- 80 х 25 Монохроматически.
белый
8 Графика, 16 160 х 200 PCj.
цветов
9 Графика, 16 320 х 200 PCj.
цветов
10 Графика 320 х 200 PCjr, EGA
PCjr - 4 цвета
EGA - 16 цветов
13 Графика, 16 320 х 200 EG.
цветов
14 Графика, 16 640 х 200 EG.
цветов
15 Графика, 4 640 х 350 EG.
цвета
Приводимая ниже процедура "mode" выполняет обращение к функции 1 базовой системы ввода-вывода (функция установки режима) для перевода экрана в графический режим 640х200, выдачи на экран сообщения-приветствия "HI" и ожидания нажатия пользователем клавиши "RETURN". При нажатии указанной клавиши будет сделан возврат в режим цветного экрана с размерами 80х25 (приводимая программа будет работать только в операционной системе PC-DOS при наличии цветного графического адаптера):
program modetest;
{SL MODE}
procedure Mode(ModeSet:integer):external;
begin
Mode(6);
WriteLn('hi'); read;
Mode(3);
end.
Ниже приводится внешняя функция "mode", написанная на ассемблере:
; Эта процедура делает установку режима экрана, используя
; 1 целочисленный параметр.
code segment 'code'
assume cs:code
public mode
mode proc near
; сохранить стек
push bp
mov bp,sp
; получить режим
mov ax,[bp]+4
mov ah,0 ; команда для переключения режима
int 010h ; вызов базовой системы ввода-вывода
; восстановление и выход
pop bp
ret 2
mode endp
code ends
endНиже приводится функция, которая очищает экран посредством процедуры "clr":
program clr_screen;
{SL CLR}
procedure Clr; external;
begin
WriteLn('нажмите ВВОД для чистки экрана');
ReadLn;
Clr;
WriteLn('экран полностью очищен');
end.Ниже приводится внешняя процедура "clr", написанная на ассемблере.
; прерывание с номером 6
cseq segment 'code'
assume cs:cseq
public clr
clr proc near
; сохранить используемые регистры
push ax
push bx
push cx
push dx
mov cx, 0 ; начать с начала координат
mov dh, 24 ; конец в строке 24
mov dl, 79 ; столбец 79
mov ah, 0 ; установить режим просмотра
mov al, 0 ; очистить экран
mov bh, 7
int 10h
; восстановление и выход
pop ax
pop bx
pop cx
pop dx
clr endp
cseq ends
enu
Другим примером связи с базовой системой ввода-вывода посредством применения ассемблера является функция "xy", которая устанавливает курсор в координаты Х и Y. Эта функция аналогична процедурe "GotoXY", предусмотренной в языке Турбо Паскаль. В ПЭВМ фирмы IBM левый верхний угол экрана имеет координаты (0,0)
program gotoxy;
{$l XY}
var
t: integer;
procedure xy(x, y): integer); external ;
begin
for t := 0 to 24 do begin
xy(t,t);
write(t);
end;
end.
Ниже приводится внешняя процедура "xy", написанная на ассемблере:
; эта функция устанавливает курсор в координаты (Х,Y.сode cseq segment 'code'
assume cs:cseq
public xy
xy proc near
; сохранение указателя стека
puch bp
mov bp,sp
; получить первый параметр
mov dh,[up]+4 ; получить Х
mov dl,[up]+8 ; получить Y
mov ah,2 ; указатель точки перехода для
; BIOS
mov bh,0 ; номер страницы
int 10h
pop bp
ret 4
xy endp
code ends
end
Использование кодов клавиш сканирования
При работе на ПЭВМ фирмы ИБМ наиболее сложно обрабатывать программно коды функциональных клавиш и клавиш со стрелками /также клавиш INS, DEL, PGOP, PGDN, END и HOME/. При нажатии такой клавиши генерируется не восьмибитовый /однобайтовый/ код, как делается при нажатии других клавиш. При нажатии такой клавиши в действительности генерируется шестнадцатибитовый код, называемый кодом сканирования. Код сканирования состоит из младшего байта, который при нажатии обычной клавиши будет содержать код ASCII для этой клавиши, и старшего байта, который содержит позицию клавиши на клавиатуре.
Для большинства клавиш операционная система преобразует код сканирования в соответствующий восьмибитовый код ASCII. Но для функциональных клавиш и клавиш со стрелками это преобразование не делается, поскольку код символа для специальной клавиши будет иметь нулевое значение. Это означает, что для определения нажатой клавиши необходимо воспользоваться кодом позиции. Программу чтения символа с клавиатуры посредством обращения к функции ДОС с номером I нельзя использовать для чтения специальных клавиш. Это, очевидно, приводит к трудностям, когда в программе необходимо использовать специальные клавиши. В Турбо Паскале версии 4 предусматривается функция "Readkey", предназначенная для чтения и символов и кодов. Однако в приводимой ниже процедуре используется другой подход. Здесь делается прерывание $16 для получения полного шестнадцатибитового кода клавиши.
; эта процедура выдает шестнадцатибитовый код, младший байт
; которого содержит либо символ ASCII, либо нулевое значе ; ние. В последнем случае старший байт содержит код сканиро ; вания
code segment 'code'
assume cs:code
public scan
scan proc near
; сохранить указатель стека
push bp
mov bp,sp
; получить первый параметр
mov ah,0
int 16h
mov [bx+2],ax; возвращаемое значение
; восстановление и выход
pop bp
ret 2
scan endp
code endx
end
После вызова код сканирования и код символа уже будут находиться в регистре АХ, который следует использовать для передачи информации в вызывающую процедуру. После прерывания 16n с нулевым функциональным номером код позиции будет находиться в регистре АН, а код символа будет находиться в регистре AL. Процедура "scan" написана с учетом того, что при нажатии специальной клавиши код символа имеет нулевое значение.
Если код символа имеет нулевое значение, то декодируется код позиции для определения, какая клавиша была нужна. Для обработки всякого ввода с клавиатуры посредством указанной функции решения следует принимать на основе содержимого регистров АН и AL. Один из таких способов иллюстрируется ниже в короткой программе:
program special_keys;
{SL SCAN}
var
t: integer;
function Scan:integer; external;
begin
repeat
t: = Scan;
if lo(t)=0 then WriteLn('scan code is', hi(t))
else WriteLn(chr(lo(t)));
until chr(lo(t))='q';
end.
Для доступа к обеим половинам шестнадцатиразрядного значения, полученного процедурой "scan", можно воспользоваться предусмотренными в Турбо Паскале стандартными функциями "Ht" и "Lo".
Кроме того, для преобразования целого числа в символ потребуется функция "Chr".
Для декодирования кода сканирования вы можете воспользоваться техническим справочным руководством фирмы ИБМ. Другой, более интересный способ, заключается в написании короткой программы, единственным назначением которой является лишь экспериментальная выдача кодов нажатых клавиш. Для начала приведем коды сканирования для клавиш со стрелками:
Левая стрелка - 75,
Правая стрелка - 77,
Стрелка вверх - 72,
Стрелка вниз - 80.
Для полного совмещения специальных клавиш с обычными кла вишами необходимо написать специальные функции ввода данных и использовать их вместо обычных функций "read" и "readln". К сожалению этот путь является единственным. Однако, наградой будет возможность работать в вашей программе с полным набором клавиш ПЭВМ фирмы ИБМ.
Заключительные замечания относительно связи с операционной системой
В этой главе лишь кратко рассмотрены возможности применения системных ресурсов. Для полного использования возможностей операционной системы потребуется подробная информация по системным функциям.
Применение системных функций дает несколько преимуществ. Вопервых, это позволяет лучше использовать особенности конкретной ПЭВМ и сделать программу более профессионально. Во-вторых, использование системных функций вместо встроенных в TURBO -Паскаль иногда позволяет создавать более быстрые и более эффективные программы. В-третьих, это позволяет использовать функции, которые отсутствуют в Турбо Паскале.
Однако, применение системных функций обеспечивается не бесплатно. Используя системные функции вместо стандартных функций и процедур, вы создаете себе дополнительные трудности, поскольку ваша программа теперь не будет мобильной. Ваша программа может также зависеть от конкретной версии данной операционной системы и компилятора Турбо Паскаля, что создает проблемы совместимости при распространении ваших программ. Только вы сами должны решать, когда следует в программе использовать функции, зависимые от машины или операционной системы.