================================================================= ПРОГРАММА-СПРАВОЧНИК по книге Г.Шилдта Р А Б О Т А С ТУРБО ПАСКАЛЕМ (Главы 1-5) г. Москва, 1990 г. ================================================================= Оглавление Работа с Турбо Паскалем #1/2 = 1 = Предисловие.....................................................4 Введение........................................................5 ГЛАВА 1. СОРТИРОВКА И ПОИСК.....................................7 СОРТИРОВКА......................................................7 Классы алгоритмов сортировки....................................7 Оценка алгоритмов сортировки....................................8 Сортировка пузурьковым методом..................................9 Сортировка выбором.............................................13 Сортировка вставкой............................................14 Усовершенствованные алгоритмы сортировки.......................16 Сортировка Шелла...............................................17 ГЛАВА 2. ОЧЕРЕДИ, СТЕКИ, СВЯЗАННЫЕ СПИСКИ И ДЕРЕВЬЯ............32 ОЧЕРЕДИ........................................................33 Циклическая очередь............................................36 СТЕКИ..........................................................43 СВЯЗАННЫЕ СПИСКИ...............................................47 Связанные списки с одиночной связью............................47 Списки с двойной связью........................................55 Список адресов почтовых корреспонденций, построенный в виде списка с двумя связями........................................61 ДВОИЧНЫЕ ДЕРЕВЬЯ...............................................68 ГЛАВА 3. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ.....................76 ФУНКЦИЯ New...................................................78 ФУНКЦИЯ Dispose...............................................79 ФУНКЦИИ Mark и Release........................................80 ОБРАБОТКА РАЗРЕЖЕННЫХ МАССИВОВ.................................82 Использование связанного списка для организации разреженного массива.........................................83 Использование двоичного дерева для организации разреженных массивов......................................................87 Применение массива указателей для организации разреженных массивов......................................................90 ХЕШИРОВАНИЕ....................................................94 Анализ хеширования............................................100 Выбор метода реализации разряженных матриц....................100 БУФЕРИЗАЦИЯ...................................................102 ФРАГМЕНТАЦИЯ..................................................111 Динамическое распределение памяти и задачи искусственного интеллекта...................................................113 ГЛАВА 4. ИНТЕРФЕЙС С ПРОГРАММАМИ НА АССЕМБЛЕРЕ И СВЯЗЬ С ОПЕРАЦИОННОЙ СИСТЕМОЙ........................................123 ИНТЕРФЕЙС С АССЕМБЛЕРОМ.......................................123 ВНУТРЕННИЕ ФОРМАТЫ ДАННЫХ И СОГЛАШЕНИЯ О СВЯЗЯХ В ЯЗЫКЕ ТУРБО ПАСКАЛЬ................................................125 Параметры-значения............................................126 Параметры-переменные..........................................127 Передача результата функции...................................128 Сохранение регистров..........................................128 Работа с Турбо Паскалем #1/2 = 2 = Создание внешней программы на ассемблере......................128 Встроенный код ассемблера.....................................130 Когда следует применять ассемблер.............................132 СВЯЗЬ С ОПЕРАЦИОННОЙ СИСТЕМОЙ.................................134 Доступ к системным ресурсам в операционной системе PC-DOS.....135 Применение процедуры MsDos....................................136 Таблица 1 Системные подпрограммы, вызываемые посредством прерываний...................................................138 Использование кодов клавиш сканирования.......................148 Заключительные замечания относительно связи с операционной системой.....................................................151 ГЛАВА 5. СТАТИСТИЧЕСКИЙ АНАЛИЗ................................152 ВЫБОРКИ, ГЕНЕРАЛЬНЫЕ СОВОКУПНОСТИ, РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ И ПЕРЕМЕННЫЕ....................................153 Основные статистические оценки................................154 Среднее значение..............................................154 Медианы.......................................................155 Мода..........................................................156 Применение среднего значения, медианы и моды..................158 Дисперсия и стандартное отклонение............................160 Вывод на экран простых графиков...............................162 Прогнозирование и уравнение регрессии.........................168 ПОЛНАЯ ПРОГРАММА ПО СТАТИСТИЧЕСКОМУ АНАЛИЗУ...................173 Применение программы статистического анализа..................183 ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ......................................184 Работа с Турбо Паскалем #1/2 = 3 = ================================================================= Авторский коллектив "*.*" ПРОГРАММА-СПРАВОЧНИК по книге Г.Шилдта Р А Б О Т А С ТУРБО ПАСКАЛЕМ г. Москва, 1990 г. ================================================================= Работа с Турбо Паскалем #1/2 = 4 = Предисловие ----------------------------------------------------------------- Для опытного пользователя, применяющего Турбо Паскаль, эта книга станет необходимым инструментом при разработке программ в среде системы Турбо Паскаль. Турбо Паскаль насчитывает во всем мире более 700 000 пользо- вателей и стал фактически стандартным Паскалем для персональных компьютеров. В этот раз Герберт Шилдт, который сам является прог- раммистом, в своей книге, предназначенной для опытных пользовате- лей Турбо Паскаля, представляет алгоритмы и методы разработки эф- фективных, мобильных программ, свободных от ошибок. Шилдт пользуется подходом, при котором лучшее усвоение мате- риала обеспечивается примерами решения задач. Как всегда от четко выражает свои мысли и иллюстрирует их многочисленными примерами. Автор проводит читателя по всему языку Паскаль и останавливается на конкретных вопросах программирования. Главы 9 и 10 заслуживают особого внимания. В главе 9 описываются средства Турбо Паскаля, предназначенные для работы с базой данных. Эти средства представ- ляют собой библиотеку процедур Паскаля, которая позволяет разра- батывать мощные системы баз данных. В главе 10 описываются графи- ческие средства Турбо Паскаля. Эти средства представляют собой библиотеку программ, предназначенных для разработки коммерческих графических систем с высокой разрешающей способностью. Мне было приятно работать с издательством "Макгроу-Хилл" и Шилдтом при подготовке книги, которая является важным этапом в развитии системы Турбо Паскаль. Все программисты, стремящиеся к максимальной производительности при разработке программ в среде системы Турбо Паскаль, захотят прочесть и воспользоваться этой книгой. Филипп Кан, президент фирмы "Борланд интернейшил". Работа с Турбо Паскалем #1/2 = 5 = Введение ----------------------------------------------------------------- Эта книга поможет вам раскрыть на конкретных примерах боль- шие возможности системы Турбо Паскаль. В каждой главе рассматри- вается определенная тема программирования и разрабатываются прог- раммы, относящиеся к этой теме. В ходе этого процесса вы увидите какие преимущества дает Турбо Паскаль при решении некоторых обыч- ных задач программирования. В то же время вы сможете усовершенс- твовать свои программистские способности. Глава 1 посвящена сортировке массивов и дисковых файлов. В главе 2 рассматриваются стеки, очереди, связанные списки и двоич- ные деревья. Такой диапазон вопросов, рассматриваемых в одной главе, может показаться слишком широким, однако предмет обсужде- ния обладает достаточной однородностью. В главе 3 рассматриваются методы динамического управления памятью, а в главе 4 дается обзор принципов связи с операционной системой и с языком ассемблера. Темой главы 5 является статисти- ческий анализ и в нее включены законченные программы по статисти- ческому анализу. В главе 6 рассматриваются вопросы кодировки, шифрования и сжатия данных. В нее также включена краткая история криптографии. В главе 7 рассматривается несколько генераторов случайных числе и затем обсуждается их использование при решении двух задач моделирования /контрольной линии на складе и управле- ния портфелем заказов/. Глава 8, которая мне нравится больше всего, содержит полный код рекурсивного нисходящего синтаксического анализатора. /Нес- колько лет назад я готов был заплатить почти любую цену за такой код/. Глава 8 предназначена для тех, кому требуется выполнять анализ выражений. Средства, предназначенные для работы с базой данных, и графические средства, которые являются двумя очень по- лезными дополнениями Турбо Паскаля, рассматриваются соответствен- но в главе 9 и главе 10. В главе 11 рассматриваются вопросы эф- фективности, мобильности и отладки программ. В конце книги дается три приложения. В приложении А показано, как программы на языках Си и Бейсик можно преобразовать в программу на языке TURBO -Пас- каль. В приложении Б описаны отличия языка Турбо Паскаль от стан- дартного Паскаля. В приложении В рассматривается применение бло- ков в Турбо Паскале. Поскольку Турбо Паскаль всегда отличался особенно высокой скоростью компиляции и эффективностью получаемого кода трудно бы- ло ожидать, что его можно будет каким-либо способом заметно улуч- шить. Однако с выходом Турбо Паскаля версии 4 значительно расши- ряется область применения Турбо Паскаля. Теперь /и впервые/ программисты, использующие Турбо Паскаль, не ограничены 64К в от- ношении размера кода программы. Поскольку в версии 4.0 обеспечена раздельная компиляция и связь блоков размер программ ограничива- ется размером имеющейся памяти. В результате использования этих Работа с Турбо Паскалем #1/2 = 6 = дополнительных возможностей некоторые программы, которые разраба- тывались с применением первых версий системы Турбо Паскаль, не будут компилироваться в версии 4.0. Соответственно, некоторые программы, написанные для версии 4, не будут компилироваться в первых версиях системы Турбо Паскаль. Из-за важности использован- ных в Турбо Паскале версии 4 усовершенствований приводимые в этой книге примеры соответствуют версии 4. Таким образом, если вы ис- пользуете первые версии системы Турбо Паскаль, то вам придется выполнить небольшие изменения в некоторых примерах. /Однако наи- лучшим выходом из положения является переход на более совершенную версию 4 Турбо Паскаля/. Если вы хотите получить гибкий диск для микрокомпьютера фир- мы ИБМ /или совместимого с ним/ со всеми программами и алгоритма- ми, которые представлены в этой книге, то заполните форму заказа с подтверждением оплаты. Если вы торопитесь, то можете сделать заказ по телефону /217/ 586-4021. Г. Шилдт Пожалуйста, пришлите мне ___ копий /каждая по цене 24,95 долларов/ программ из книги "Усовершенствованный Турбо Паскаль версии 4". Иностранные заказчики должны добавить 5 долларов за дополнительные расходы на перевозку и обработку. Имя заказчика ________________________ Адрес заказчика ___________________________________ Город ___________Страна ______________почтовый индекс ______ Телефон ____________ Размер дискеты: 5 1/4 дюйма ________ 3 1/2 дюйма ___________ Способ оплаты: чек ______ виза ___________ МС ___________ Номер кредитной карточки ___________________ Дата отправки ___________________ Подпись _________________________ Посылать по адресу: Герберт Шилдт, RR 1, бокс 130, г.Магомет, шт.Иллиноис 61853, США. Предоставление дискет с программами является исключительно предложением Герберта Шилдта. Издательство не несет ответствен- ности за выполнение этого заказа. Работа с Турбо Паскалем #1/2 = 7 = ГЛАВА 1. СОРТИРОВКА И ПОИСК. ----------------------------------------------------------------- В информатике, по-видимому, нет более глубоко исследованных задач, чем задачи сортировки и поиска. Подпрограммы сортировки и поиска используются фактически во всех программах, работающих с базами данных, а также в компиляторах, интерпретаторах и в опера- ционных системах. В этой главе рассматриваются основные вопросы сортировки и поиска. Сортировка рассматривается первой, поскольку она обычно делает поиск данных более простым и быстрым. СОРТИРОВКА ----------------------------------------------------------------- Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убыва- ния их значений. Например, список i из n элементов будет отсорти- рован в порядке возрастания значений элементов, если i <= i <= ... <= i Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на дис- ке в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах. В этой главе рассматривается в основном сортировка первого вида, поскольку она представляет наибольший интерес для пользователей микрокомпьюте- ров. Однако в конце главы делается общий метод сортировки после- довательных файлов. Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент вре- мени доступен лишь один элемент. Из-за этих отличий методы сорти- ровки существенно отличаются для этих двух видов сортировки. В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляются полное имя и адрес. Для простоты в примерах, иллюстрирующих методы сортировки, использу- ются символьные массивы. Затем будет показано, как эти методы можно адаптировать к любым структурам данных. Классы алгоритмов сортировки ----------------------------------------------------------------- Имеется три способа сортировки массивов: Работа с Турбо Паскалем #1/2 = 8 = - сортировка обменом; - сортировка выбором; - сортировка вставкой. Представьте, что перед вами лежит колода карт. Для сортиров- ки карт обменом вы должны разложить карты на столе лицевой сторо- ной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной. Для сортировки выбором вы должны разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем вы должны из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже име- ется у вас в руке. Этот процесс вы должны продолжать до тех пор, пока все карты не окажутся у вас в руках. Поскольку каждый раз вы выбираете наименьшую по значению карту из оставшихся на столе, по завершению такого процесса карты у вас в руке будут отсортирова- ны. Для сортировки вставкой вы должны держать карты в своей ру- ке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соот- ветствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты. Оценка алгоритмов сортировки ----------------------------------------------------------------- Для каждого метода сортировки имеется много алгоритмов. Каж- дый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от ответов, которые будут получены на следую- щие вопросы: - с какой средней скоростью этот алгоритм сортирует информа- цию?; - какова скорость для лучшего случая и для худшего случсая?; - поведение алгоритма является естественным или является не- естественным?; - выполняется ли перестановка элементов для одинаковых клю- чей? Для конкретного алгоритма большое значение имеет скорость сортировки. Скорость, с которой массив может быть упорядочен, прямо зависит от числа сравнений и числа необходимых операций об- мена, причем операции обмена занимают большее время. Ниже в этой главе будет показано, что для некоторых алгоритмов время сорти- ровки зависит экспоненциально от числа элементов, а для других алгоритмов это время находится в логарифмической зависимости от числа элементов сортировки. Работа с Турбо Паскалем #1/2 = 9 = Время работы алгоритма для лучшего и худшего случаев важно учитывать, когда ожидается их частое появление. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худ- шего случая, и наоборот. Считается поведение алгоритма сортировки естественным, если время сортировки наименьшее при упорядоченном списке элементов, время сортировки увеличивается при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. Время сортировки зависит от числа операций сравнения и операций обмена. Для того, чтобы понять важность перегруппировки элементов с одинаковыми ключами сортировки, представим базу данных, которая упорядочена по основному ключу и дополнительному ключу. /Напри- мер, список почтовых отправлений с почтовым индексом в качестве основного ключа и фамилией в качестве дополнительного ключа в рамках одного почтового индекса/. Когда новый адрес добавляется в список и список вновь сортируется, вам не требуется перестановка дополнительных ключей. Для обеспечения этого сортировка не должна выполнять операции обмена для основных ключей с одинаковыми зна- чениями. В следующих разделах приводятся алгоритмы сортировки каждого класса и анализируется их эффективность. Каждая программа сорти- ровки использует два типа данных, определенных пользователем, ко- торые определяются следующим образом: type DataItem = char; DataArray = array [1..80] of DataItem; Следовательно, для изменения используемых в сортировках ти- пов данных требуется изменить только эти два определения типов. Размерность массива выбрана произвольно и вы можете при необходи- мости их изменить. Сортировка пузурьковым методом. ----------------------------------------------------------------- Наиболее известной (и наиболее "бесславной") является сорти- ровка пузырьковым методом. Ее популярность объясняется запоминаю- щимся названием и простотой алгоритма. Однако, эта сортировка яв- ляется одной из самых худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название про- исходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ни- же показана самая простая форма программы сортировки методом пу- зырька: { сортировка пузырьковым методом} Работа с Турбо Паскалем #1/2 = 10 = 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); Работа с Турбо Паскалем #1/2 = 11 = 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 = 12 = неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это оз- начает, что при сортировке пузырьковым методом всегда выполняется 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"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направ- лении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым ме- тодом, получившая название "челночной сортировки" из-за соот- ветствующего характера движений по массиву. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выпол- нения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на нез- начительную величину. Работа с Турбо Паскалем #1/2 = 13 = { челночная сортировка является улучшенной версией сортиров- ки пузырьковым методом } 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", то будут получены следующие проходы: Работа с Турбо Паскалем #1/2 = 14 = - исходное состояние: 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]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/2 = 16 = дет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т. е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направле- нии. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки встав- кой он по-прежнему будет упорядочен по двум ключам. Несмотря на то, что число сравнений может быть довольно не- большим для определенных наборов данных, постоянные сдвиги масси- ва требуют выполнения большого числа операций пересылок. Однако, сортировка вставкой имеет естественное поведение, требуя наимень- шее число операций обмена для почти упорядоченного списка и наи- большее число операций обмена, когда массив упорядочен в обратном направлении. Усовершенствованные алгоритмы сортировки ----------------------------------------------------------------- Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения про- порционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины они будут слишком медленными, чтобы их можно было использовать на практике. Каждый программист слышал или рассказывал "страшные" истории о "сортировке, которая выполнялась три дня". К сожалению эти истории часто не являлись выдумкой. Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Однако, первая реакция на такое поведение сортировки выражается словами: "Давай напишем программу на ассемблере". Хотя использование ассемблера почти всегда позво- ляет повысить быстродействие программы в некоторое число раз с постоянным коэффициентом, но если выбранный алгоритм не является достаточно хорошим, то сортировка вне зависимости от оптимальнос- ти кода по-прежнему будет выполняться долго. Следует помнить, что при квадратичной зависимости времени выполнения программы от чис- ла элементов массива повышение оптимальности кода или повышение быстродействия ЭВМ приведет лишь к незначительному улучшению, поскольку время выполнения программы будет увеличиваться по экс- поненте. /Кривая, показанная на рис.1 лишь слегка сместится впра- во, однако ее вид не изменится/. Следует помнить, что если какая- либо программа, написанная на языке Турбо Паскаль, выполняется недостаточно быстро, то она не станет выполняться достаточно быстро, если ее написать на ассемблере. Решение лежит в использо- вании лучшего алгоритма сортировки. В этой главе будут рассмотрены две очень хорошие сортировки. Первая носит название сортировки Шелла, а вторая называется быст- Работа с Турбо Паскалем #1/2 = 17 = рой сортировкой, алгоритм которой признан наилучшим. Эти сорти- ровки выполняются очень быстро. Сортировка Шелла ----------------------------------------------------------------- Сортировка Шелла получила свое название по имени ее создате- ля Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морс- ких ракушек друг на друга. ("Ракушка" - одно из значений слова 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 f Рис.2. Сортировка Шелла: { сортировка Шелла } 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 Работа с Турбо Паскалем #1/2 = 18 = begin s := -k; s := s+1; item[s] := x; end; while (x0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сор- тировки Шелла используют специальные управляющие элементы, кото- рые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значе- ния. Однако, применение таких управляющих элементов требует спе- циальных знаний о той информации, которая сортируется, и это сни- жает универсальность процедуры сортировки. Анализ сортировки Шелла требует решения некоторых сложных математических задач, которые выходят за рамки этой книги. Время выполнения сортировки Шелла пропорционально n**1.2. Эта зависи- мость значительно лучше квадратичной зависимости, которой подчи- Работа с Турбо Паскалем #1/2 = 19 = няются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в ви- ду, что быстрая сортировка дает даже еще лучшие результаты. Быстрая сортировка ----------------------------------------------------------------- Метод быстрой сортировки был разработан Ч.Ф.Р.Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представ- ляет собой простейшую версию обменной сортировки. В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все эле- менты, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива "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 Работа с Турбо Паскалем #1/2 = 20 = i, j: integer; x, y: DataItem; begin i:=l; j:=r; x:=it[(l+r) div 2]; repeat while it[i]j; if lj; if lj; if ly; if l=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; Работа с Турбо Паскалем #1/2 = 29 = 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нец сортировки методом слияния } ПОИСК ----------------------------------------------------------------- В настоящее время имеются базы данных, где информация хра- ниться таким образом, что пользователь время от времени может по- лучить требуемые данные из соответствующих записей, когда ему из- вестны их ключи. Для неупорядоченных файлов или массивов используются одни методы поиска, а для упорядоченных файлов или массивов используются другие методы поиска. МЕТОДЫ ПОИСКА ----------------------------------------------------------------- Поиск информации в неотсортированном массиве требует прове- дения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива. Этот метод должен использоваться для неотсортированных данных, но он также может использоваться для отсортированных данных. Если данные отсортированы, то может ис- пользоваться двоичный поиск, который выполняется значительно быстрее. Последовательный поиск ----------------------------------------------------------------- Алгоритм последовательного поиска имеет очень простой вид. Работа с Турбо Паскалем #1/2 = 30 = Ниже представлена функция, которая выполняет поиск в символьном массиве заданной длины элемента с заданным значением ключа: 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. Для среднего случая это значение будет несколько лучше, а Работа с Турбо Паскалем #1/2 = 31 = в лучшем случае оно равно единице. Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой про- извольной структуры данных, изменив блок сравнения и определение типа данного "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 keyitem[mid] then low:=mid+1 else found:=true; { найден } end; if found then BSearch:=mid else BSearch:=0; { не найден } end; { конец поиска } В следующей главе исследуются различные подходы к представлению данных, которые в некоторых случаях значительно об- легчают сортировку и поиск. Работа с Турбо Паскалем #1/2 = 32 = ГЛАВА 2. ОЧЕРЕДИ, СТЕКИ, СВЯЗАННЫЕ СПИСКИ И ДЕРЕВЬЯ ----------------------------------------------------------------- Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, ко- торая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем "багаже" соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации. В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "integer", "real". На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных. а последнем уровне, когда уже не рассматриваются физичес- кие аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По су- ществу физические данные связаны с "машиной данных", которая уп- равляет способом доступа к информации в вашей программе. Имеется четыре такие "машины": - очередь; - стек; - связанный список; - двоичное дерево. Каждый метод используется при решении определенного класса задач. Каждый метод по существу является неким "устройством", ко- торое обеспечивает для заданной информации определенный способ хранения и при запросе выполняет определенные операции поиска данных. В каждом из этих методов используется две операции: доба- вить элемент и найти элемент /под элементом понимается некоторая информационная единица/. В этой главе будет показано, как эти ме- тоды можно использовать в ваших программах. Работа с Турбо Паскалем #1/2 = 33 = ОЧЕРЕДИ ----------------------------------------------------------------- Очередь представляет собой линейный список данных, доступ к которому осуществляется по принципу "первый вошел, первый вышел" /иногда сокращенно его называют методом доступа 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 - выборка из очереди элемента А, В, С. Очереди в программировании используются во многих случаях, например, при моделировании (обсуждается ниже в соответствующей главе), при планировании работ (метод ПЕРТ или графики Гатта), при буферизации ввода-вывода. В качестве примера рассмотрим простую программу планирования предписаний, которая позволяет обращаться к нескольким предписа- ниям. При каждом обращении предписание удаляется из списка и на экран выводится следующее предписание. Для простоты в программе используется массив символьных строк для управления событиями. Работа с Турбо Паскалем #1/2 = 34 = Описание предписания ограничивается 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" должны быть установлены в нулевое значение до первого обращения к проце- дурам постановки в очередь и выборки из очереди. Работа с Турбо Паскалем #1/2 = 35 = В этой программе процедура постановки в очередь помещает но- вые события в конец списка и делает проверку заполнения списка. Функция выборки из очереди выбирает события из очереди при необ- ходимости их обработки. Когда планируется новое событие, перемен- ная "spos" увеличивается на единицу, а когда событие завершается, то увеличивается на единицу переменная "rpos". Фактически пере- менная "rpos" преследует переменную "spos" в проходах по очереди. Этот процесс иллюстрируется на рис.5. Если значение указателя свободного места совпадает со значением указателя выбираемого элемента, то это означает, что в очереди нет событий. Следует помнить, что хотя функция выборки элемента из очереди в действи- тельности не нарушает информацию в очереди, повторный доступ к ней невозможен и фактически она исчезает. Ниже приводится целиком программа, осуществляющая простое планирование предписаниями. Вы можете усовершенствовать эту прог- рамму по собственному желанию. Работа с Турбо Паскалем #1/2 = 36 = Циклическая очередь ----------------------------------------------------------------- spos 2 1 Queue ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ at Start-up │ │ │ │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 spos 2 4 Qstore('A') ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │A │ │ │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 spos 2 4 Qstore('B') ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │A │B │ │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 spos 2 5 Qreirieve ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │A │B │ │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 spos 2 5 Qreirieve ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │A │B │ │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 spos 2 4 Qstore('C') ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │A │B │C │ │ │ │ │ │ │ │ │ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ rpos 3 Рис.5. Указатель поиска преследует указатель свободного мес- та в очереди: 1 - очередь в исходном положении; 2 - указатель свободного места в очереди; 3 - указатель следующего выбираемого элемента; 4 - процедура постановки в очередь; 5 - функция выборки из очереди. { простое планирование предписаниями } procram MiniScheduler; uses Grt; const MAX_EVENT = 100; Работа с Турбо Паскалем #1/2 = 37 = 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); Работа с Турбо Паскалем #1/2 = 38 = 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. При чтении предыдущего раздела вы возможно подумали об улуч- шении программы планирования предписаниями. Вместо остановки программы по достижению предела массива, который используется под очередь, можно указатель постановки в очередь и указатель выборки из очереди вернуть на начало массива. В этом случае в очередь можно добавлять любое число элементов в то время как элементы бу- дут также выбираться из очереди. Такая очередь называется цикли- ческой, поскольку теперь массив используется не как линейный спи- сок, а как циклический список. Для создания циклической очереди в программе планирования Работа с Турбо Паскалем #1/2 = 39 = предписаний требуется изменить подпрограммы постановки в очередь и выборки из очереди следующим образом: 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; { конец функции выборки из очереди } В действительности очередь становится заполненной только в том случае, когда указатель свободного места совпадает с указате- лем выборки следующего элемента. В противном случае очередь будет иметь свободное место для нового элемента. Однако, это значит, что в начале программы индекс выборки должен устанавливаться не в нулевое значение, а на значение максимального числа событий. В противном случае первое обращение к процедуре постановки в оче- редь приведет к появлению сообщения о заполнении списка. Следует помнить, что очередь может содержать только на один элемент мень- ше, чем значение максимального числа событий, поскольку указатели выборки и постановки в очередь всегда должны отличаться хотя бы на единицу (в противном случае нельзя будет понять заполнена ли очередь или она пустая). Далее рассматривается циклический массив, который использу- ется в новой версии программы планирования. Наиболее широко цик- лические очереди применяются в операционных системах при буфери- зации информации, которая считывается или записывается на диско- вые файлы или консоль. Другое широкое применение эти очереди наш- Работа с Турбо Паскалем #1/2 = 40 = ли в решении задач реального времени, когда, например, пользова- тель может продолжать делать ввод с клавиатуры во время выполне- ния другой задачи. Так работают многие текстовые процессоры, ког- да изменяется формат параграфа или выравнивается строка. Имеется короткий промежуток времени, когда набранная на клавиатуре инфор- мация не выводится на экран до окончания другого процесса. Для достижения такого эффекта в программе должна предусматриваться постоянная проверка ввода с клавиатуры в ходе выполнения другого процесса. При вводе некоторого символа его значение должно быстро ставиться в очередь и процесс должен продолжаться. После заверше- ния процесса набранные символы выбираются из очереди и обрабаты- ваются обычным образом. Для того, чтобы понять, как это можно сделать с помощью цик- лической очереди, рассмотрим следующую простую программу, состоя- щую из двух процессов. Первый процесс выполняет подсчет до 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 Работа с Турбо Паскалем #1/2 = 41 = 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. Работа с Турбо Паскалем #1/2 = 42 = Процедура "KeyPressed" делает обращение к программе операци- онной системы, которая возвращает значение "истина", если была нажата какая-либо клавиша, или значение "ложь", если клавиатура не использовалась. Работа с Турбо Паскалем #1/2 = 43 = СТЕКИ ----------------------------------------------------------------- Организация стека в определенном смысле противоположна орга- низации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" /такой метод доступа иногда назы- вают методом 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 Работа с Турбо Паскалем #1/2 = 44 = 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; Работа с Турбо Паскалем #1/2 = 45 = 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 Работа с Турбо Паскалем #1/2 = 46 = 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" в оператор деления для чисел с плаваю- щей запятой /наклонная черта/. Работа с Турбо Паскалем #1/2 = 47 = СВЯЗАННЫЕ СПИСКИ ----------------------------------------------------------------- Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохра- нен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/. В отличии от стека и очереди связанный список позволяет осу- ществлять доступ к любым элементам, поскольку каждая единица ин- формации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со слож- ными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае сле- дует предусмотреть дополнительно операцию удаления элемента из списка. Связанные списки используются в двух основных случаях. Во -первых, при создании массивов, которые располагаются в оператив- ной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей зада- чи, то вы можете использовать простой массив. Однако, если дейс- твительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в ба- зах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего диско- вого файла. По этим причинам связанные списки широко используются в программах по управлению базами данных. Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависи- мости от решаемой задачи. Связанные списки с одиночной связью ----------------------------------------------------------------- В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8. Работа с Турбо Паскалем #1/2 = 48 = ┌─────┐ ┌─────┐ ┌─────┐ │1info│ │1info│ │1info│ ├─────┤ ├─────┤ ├─────┤ │2link│ │2link│ │3 nil│ └─────┘ └─────┘ └─────┘ Рис.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; Работа с Турбо Паскалем #1/2 = 49 = end; end; { конец процедуры добавления элементов в список с одной связью } Следует помнить, что до первого обращения к этой функции пе- ременные "start" и "last" должны быть установлены на значение "nil". Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во вре- мя вставки путем установки каждого нового элемента в соответству- ющее место списка. Кроме того, если список уже является отсорти- рованным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не бу- дет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей. При вставке элемента в список с одной связью может воникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.9 показано, как для каждого из этих случаев изме- няются связи. Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избе- жать этого, в качестве первого элемента нужно использовать фик- тивный элемент. Этот фиктивный элемент должен иметь такое значе- ние, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостат- ком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется. Работа с Турбо Паскалем #1/2 = 50 = 1 Новый первый элемент ┌─────┐ ┌─────┐ │2 new│ │2 new│ ├─────┤ ├─────┤ │ │ │ │ └─────┘ └─────┘ 4becomes ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │3info│ │3info│ │3info│ │3info│ │3info│ │3info│ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ │ │ │ │ │5 nil│ │ │ │ │ │5 nil│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ 6 New Middle Item ┌─────┐ ┌─────┐ │2 new│ │2 new│ ├─────┤ ├─────┤ │ │ │ │ └─────┘ └─────┘ 4becomes ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │3info│ │3info│ │3info│ │3info│ │3info│ │3info│ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ │ │ │ │ │5 nil│ │ │ │ │ │5 nil│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ 7 New Last Item ┌─────┐ ┌─────┐ │2 new│ │2 new│ ├─────┤ ├─────┤ │ │ │5 nil│ └─────┘ └─────┘ 4becomes ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │3info│ │3info│ │3info│ │3info│ │3info│ │3info│ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ │ │ │ │ │5 nil│ │ │ │ │ │ │ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ Рис.9. Вставка элемента в список с одной связью: 1 - новый первый элемент; 2 - новый элемент; 3 - информационные поля; 4 - справа дается преобразованный список; 5 - нулевой указатель связи; 6 - новый средний элемент; Работа с Турбо Паскалем #1/2 = 51 = 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; Работа с Турбо Паскалем #1/2 = 52 = 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; Работа с Турбо Паскалем #1/2 = 53 = 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│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ 6 Deleting a Middle Item 2becomes ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │3info│ │3info│ │3info│ │3info│ │ │ │3info│ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ │ │ │ │ │5nil │ │ │ │5 nil│ │5 nil│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ 7 Deleting the Last Item 2becomes ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │3info│ │3info│ │3info│ │3info│ │3info│ │ │ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ ├─────┤ │ │ │ │ │5 nil│ │ │ │5 nil│ │5 nil│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ Рис.10. Удаление элемента из списка с одной связью: 1 - удаление первого элемента; 2 - левый список преобразуется в правый; 3 - информационные поля; 4 - удаленный элемент; 5 - связь с нулевым значением; 6 - удаление среднего элемента; 7 - удаление последнего элемента. Приводимая ниже функция выполняет удаление заданного элемен- та из списка записей адресов: Работа с Турбо Паскалем #1/2 = 54 = 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; { конец функции удаления элемента из списка с одной связью } Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка. Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может уда- литься первый элемент и необходимо знать, где будет новый первый элемент списка. Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просмат- ривать в обратном направлении. Для этих целей используются списки с двойной связью. Работа с Турбо Паскалем #1/2 = 55 = Списки с двойной связью ----------------------------------------------------------------- Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент спис- ка. Рис.11 иллюстрирует характер связей в таком списке. Список, который вместо одной имеет две связи, отличается двумя основными преимуществами. Во-первых, список может читаться в обоих направ- лениях. Это не только упрощает сортировку списка, но также позво- ляет пользователям базы данных просматривать данные в обоих нап- равлениях. Во-вторых, и прямая и обратная связь позволяют прочитать список полностью и поэтому при нарушении одной из свя- зей список может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка. ┌──────────┐ ┌──────────┐ ┌───────────┐ │1 info │ │1 info │ │1 info │ ├─────┬────┤ ├─────┬────┤ ├─────┬─────┤ │2nil │ │ │ │ │ │ │2 nil│ └─────┴────┘ └─────┴────┘ └─────┴─────┘ Рис.11. Список с двойной связью: 1 - информационные поля; 2 - связь с нулевым значением. Для списка с двойной связью предусматриваются три основные операции: вставка нового первого элемента, вставка нового средне- го элемента и вставка нового последнего элемента. Эти операции проиллюстрированы на рис.12. Список с двойной связью строится подобно списку с одной связью, причем в записи должно быть предусмотрено место для двух указателей. Для примера со списком почтовых корреспонденций за- пись адреса можно модифицировать следующим образом: type str80 = string[80]; AddrPointer = ^address; address = record 1 Inserling a New First Element ┌──────┐ ┌──────┐ │2 new │ │2 new │ ├───┬──┤ ├───┬──┤ │ │ │ │ │ │ └───┴──┘ └───┴──┘ 4becomes Работа с Турбо Паскалем #1/2 = 56 = ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├──┬───┤ ├───┬──┤ ├──┬───┤ 3│nil│ │ │ │ │ │ │nil│3 │ │ │ │ │ │ │ │nil│3 └───┴──┘ └──┴───┘ └──┴───┘ └──┴───┘ └───┴──┘ └──┴───┘ 6 Inserling a New Middle Element ┌──────┐ ┌──────┐ │2 new │ │2 new │ ├──┬───┤ ├───┬──┤ │ │ │ │ │ │ └──┴───┘ └───┴──┘ 4becomes ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├───┬──┤ ├───┬──┤ ├──┬───┤ 3│nil│ │ │ │ │ │ │nil│3 3│nil│ │ │ │ │ │ │nil│3 └───┴──┘ └──┴───┘ └──┴───┘ └───┴──┘ └───┴──┘ └──┴───┘ 7 Inserling a New Last Element ┌──────┐ ┌──────┐ │2 new │ │2 new │ ├──┬───┤ ├──┬───┤ │ │ │ │ │nil│3 └──┴───┘ └──┴───┘ 4becomes ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ │5 info│ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├───┬──┤ ├──┬───┤ ├───┬──┤ 3│nil│ │ │ │ │ │ │nil│3 3│nil│ │ │ │ │ │ │ │ └───┴──┘ └──┴───┘ └──┴───┘ └───┴──┘ └──┴───┘ └───┴──┘ Рис.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; Работа с Турбо Паскалем #1/2 = 57 = 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; Работа с Турбо Паскалем #1/2 = 58 = 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 } Поскольку элемент может помещаться в самое начало списка, эта функция должна выдавать указатель на начало списка, чтобы в других частях программы учесть изменения начала списка. При поис- ке конкретного элемента списка, как и для списка с одиночной Работа с Турбо Паскалем #1/2 = 59 = связью, делается последовательный проход по цепочке связей пока не будет найден требуемый элемент. При удалении элемента из списка возникает одна из трех ситу- аций: удаление первого элемента, удаление среднего элемента и удаление последнего элемента. Рис.13 иллюстрирует изменение свя- зей для этих случаев. 1 Deleting the First Item 3becomes ┌──────┐ ┌──────┐ ┌──────┐ ┌───────┐ ┌──────┐ ┌──────┐ │2 info│ │2 info│ │2 info│ 4│2 info │ │2 info│ │2 info│ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├───┬───┤ ├───┬──┤ ├──┬───┤ 5│nil│ │ │ │ │ │ │nil│5 5│nil│nil│55│nil│ │ │ │nil│5 └───┴──┘ └──┴───┘ └──┴───┘ └───┴───┘ └───┴──┘ └──┴───┘ 6 Deleting a Middle Item 3becomes ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌───────┐ ┌──────┐ │2 info│ │2 info│ │2 info│ │2 info│ │2 info │ │2 info│ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├───┬──┤ ├───┬───┤ ├──┬───┤ 5│nil│ │ │ │ │ │ │nil│5 5│nil│ │5 │nil│nil│5│ │nil│5 └───┴──┘ └──┴───┘ └──┴───┘ └───┴──┘ └───┴───┘ └──┴───┘ 7 Deleting the Last Item 3becomes ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌───────┐ │2 info│ │2 info│ │2 info│ │2 info│ │2 info│ │2 info │ ├───┬──┤ ├──┬───┤ ├──┬───┤ ├───┬──┤ ├──┬───┤ ├───┬───┤ 5│nil│ │ │ │ │ │ │nil│5 5│nil│ │ │ │nil│55│nil│nil│5 └───┴──┘ └──┴───┘ └──┴───┘ └───┴──┘ └──┴───┘ └───┴───┘ Рис.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 Работа с Турбо Паскалем #1/2 = 60 = 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; { конец функции удаления элемента из списка с двойной связью } Этой функции передается на один указатель меньше, чем для соответствующей функции при использовании списка с одной связью. /Удаленный элемент уже имеет указатель на предыдущий элемент и указатель на следующий элемент/. Поскольку первый элемент в спис- ке может измениться, функция возвращает указатель на начало спис- ка. Работа с Турбо Паскалем #1/2 = 61 = Список адресов почтовых корреспонденций, построенный в виде списка с двумя связями ----------------------------------------------------------------- Ниже приведена простая программа для списка почтовых коррес- понденций, построенного в виде списка с двойной связью. Здесь весь список содержится в оперативной памяти. Однако, программа может быть изменена для хранения списка на диске. {простая программа для списка адресов почтовых корреспон- денций, иллюстрирующая применение списков с двойной связью} 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; Работа с Турбо Паскалем #1/2 = 62 = 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; Работа с Турбо Паскалем #1/2 = 63 = 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; { начало не изменяется } Работа с Турбо Паскалем #1/2 = 64 = 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); Работа с Турбо Паскалем #1/2 = 65 = 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 Работа с Турбо Паскалем #1/2 = 66 = 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'); Работа с Турбо Паскалем #1/2 = 67 = 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. { конец программы } Работа с Турбо Паскалем #1/2 = 68 = ДВОИЧНЫЕ ДЕРЕВЬЯ ----------------------------------------------------------------- В этом разделе рассматривается четвертая структура данных, которая называется двоичным деревом. Имеется много типов деревь- ев. Однако, двоичные деревья занимают особое положение. Если та- кие деревья упорядочить, то операции поиска, вставки и удаления будут выполняться очень быстро. Каждый элемент двоичного дерева имеет информационные поля, связь с левым элементом и связь с пра- вым элементом. На рис.14 показано небольшое дерево. При описании деревьев используется специальная терминология. Первый элемент дерева называется его корнем. Каждый элемент назы- вают вершиной /или листом/ дерева, а часть дерева носит название поддерева. Вершина, которая не имеет поддеревьев, называется тер- минальной вершиной. Высота дерева равна числу уровней вершин в дереве. В дальнейшем при рассмотрении деревьев можно считать, что в памяти они располагаются так же, как на бумаге. Однако следует помнить, что деревья представляют собой лишь способ представления данных в памяти, а память в действительности имеет линейную фор- му. Root Node 1 ┌───────┐ │2 info │ ├───┬───┤ │ │ │ 3 └───┴───┘ 4 Left Subtree Righl Subtree ┌───────┐ ┌───────┐ │ 2 info│ │2 info │ ├───┬───┤ ├───┬───┤ │ │ │ 5│nil│ │ └───┴───┘ └───┴───┘ ┌───────┐ ┌───────┐ ┌───────┐ │2 info │ │2 info │ │2 info │ ├───┬───┤ ├───┬───┤ ├───┬───┤ 5│nil│nil│5 5│nil│nil│5 5│nil│nil│5 └───┴───┘ └───┴───┘ └───┴───┘ 6 Terminal Nodes Рис.14. Пример двоичного дерева: 1 - корневая вершина; 2 - информационные поля; 3 - левое поддерево; 5 - указатель связи с нулевым значением; 6 - терми- Работа с Турбо Паскалем #1/2 = 69 = нальные вершины. Двоичное дерево представляет собой особую форму связанного списка. Доступ к элементам, их вставка и удаление могут выпол- няться в любом порядке. Кроме того, операция поиска не носит раз- рушительный характер. Хотя деревья легко представляются образно, для программирования они представляют достаточно непростую зада- чу. Поэтому они стали рассматриваться лишь в этом разделе. Большинство функций над деревьями носят рекурсивный харак- тер, поскольку дерево само по себе является рекурсивной структу- рой данных. /Т.е. каждое поддерево само является деревом/. Поэто- му представленные в этом разделе программы являются, как правило, рекурсивными. Имеются нерекурсивные версии этих функций, однако разобраться в них значительно труднее. Упорядоченность дерева зависит от порядка доступа к дереву. Процесс доступа к каждой вершине дерева называется обходом дере- ва. Имеется три способа обхода дерева: во внутреннем порядке, в прямом порядке и в обратном порядке. При прохождении дерева во внутреннем порядке сначала посещается левое поддерево, затем ко- рень и затем посещается правое дерево. При прохождении дерева в прямом порядке сначала посещается корень, затем левое поддерево и затем правое поддерево. При прохождении дерева в обратном порядке сначала посещается левое поддерево, затем правое поддерево и за- тем корень. Порядок прохождения 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; Работа с Турбо Паскалем #1/2 = 70 = begin if r=nil then begin new(r); { получить новую вершину } r^.left:=nil; r^right:=nil; r^.data:=data; if datanil 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; Работа с Турбо Паскалем #1/2 = 72 = 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 datanil 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'; Работа с Турбо Паскалем #1/2 = 73 = PrintTree(root, 0); end; В этой программе фактически делается сортировка полученной информации. В данном случае используется вариант сортировки вставкой, которая описывается в предыдущей главе. Для среднего случая сортировка вставкой имеет достаточно хорошие характеристи- ки, однако быстрая сортировка все же является лучшим методом сор- тировки, так как она требует меньше оперативной памяти и выполня- ется быстрее. Однако, если дерево строится на основе использования других деревьев или если вам приходится поддержи- вать упорядоченное дерево, то новые элементы всегда будут встав- ляться с использованием функции STree. Если вы воспользуетесь программой вывода на экран двоичного дерева, то возможно вы заметите, что некоторые деревья сбаланси- рованы /т.е. все поддеревья имеют одинаковую или почти одинаковую высоту/, а другие сильно несбалансированы. Если вы введете дерево "abcd", то оно примет следующий вид: a \ \ b \ \ c \ \ d В этом случае левых поддеревьев не будет. Это дерево называ- ется вырожденным, поскольку оно выродилось в линейный список. В общем случае, если используемые для построения дерева данные яв- ляются в достаточной мере случайными, дерево будет приближаться к сбалансированному. Однако, если информация уже упорядочена, то в результате будет получаться вырожденное дерево. /Имеется возмож- ность переупорядочивать дерево, сохраняя при каждой вставке его балансировку. Однако такой алгоритм достаточно сложен и если он вас заинтересовал, то следует воспользоваться книгами по усовер- шенствованным методам составления алгоритмов программ/. Функции поиска для двоичных деревьев составляются легко. Ни- же приводится функция, результатом которой является указатель на вершину дерева, которая совпадает с ключем. В противном случае возвращается нулевое значение. { поиск элемента в дереве } function Search(root:TreePointer; key:DataItem):TreePointer; begin Работа с Турбо Паскалем #1/2 = 74 = 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; Работа с Турбо Паскалем #1/2 = 75 = 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). Поэтому в этом случае поиск выполняется значительно быстрее, чем поиск в связанном списке, который посуществу являет- ся последовательным поиском. Работа с Турбо Паскалем #1/2 = 76 = ГЛАВА 3. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ----------------------------------------------------------------- Разработка программы для компьютера в некотором смысле напо- минает процесс составления проекта здания, включающий в себя рассмотрение многочисленных функциональных и эстетических вопро- сов, влияющих на окончательный результат. Например, некоторые программы имеют строгое функциональное назначение как дом, кото- рый имеет определенное число спальных комнат, кухню, две ванные комнаты и т.д. Другие программы носят менее завершенный характер, как центры для проведения собраний, которые имеют передвижные стены и модульные полы, позволяющие лучше приспособить здание для каждого конкретного случая. В этой главе описывается механизм уп- равления памятью, позволяющий разрабатывать гибкие программы, ко- торые могут адаптироваться к конкретным нуждам пользователя и возможностям ЭВМ. Следует отметить, что в этой главе используется термин "ло- гический массив" и термин "физический массив". Логический массив - это такой массив, который представляется существующим в систе- ме. Например, матрица на листе бумаги является логическим масси- вом. Физический массив - это массив, который в действительности имеется в вычислительной системе. Связь между двумя этими масси- вами обеспечивается программами по поддержке разреженных масси- вов. В этой главе рассматривается четыре метода создания разре- женных массивов: посредством связанного списка, двоичного дерева, массива указателей и хеширования. Затем будут даны примеры дина- мического распределения памяти, которое позволяет повысить произ- водительность программы. В программе на языке Паскаль информацию в основной памяти ЭВМ можно хранить двумя способами. Первый способ заключается в использовании глобальных или локальных переменных, включая масси- вы и записи, которые предусмотрены в языке Паскаль. Глобальные переменные занимают постоянное место в памяти во время выполнения программы. Для локальных переменных память выделяется из стека ЭВМ. Хотя управление глобальными и локальными переменными на Пас- кале реализовано эффективно, программист должен знать заранее объем необходимой памяти для каждого конкретного случая. Другой и более эффективный способ управления памятью на Паскале обеспечи- вается применением функций по динамическому управлению памятью. Таким являются функции "New", "Dispose", "Mark" и "Release". В обоих методах динамического управлению памятью память вы- деляется из свободного участка, который не входит в постоянную область программы, и стека /который используется в Паскале для хранения локальных переменных/. Эта область называется динамичес- кой (heap). Рис.15 иллюстрирует структуру памяти для программы на языке Турбо Паскаль. Стек увеличивается в нижнем направлении. Объем па- мяти, необходимой стеку, зависит от характера программы. Напри- Работа с Турбо Паскалем #1/2 = 77 = мер, программа со многими рекурсивными функциями будет требовать много стековой памяти, поскольку при каждом рекурсивном обращении выделяется участок стековой памяти. Участок выделяемой под прог- рамму и глобальные переменные памяти имеет постоянную величину и не изменяется во время выполнения программы. Память для запросов функции "New" берется из свободного участка памяти, который начи- нается сразу после глобальных переменных и продолжается до стека. В исключительных случаях может использоваться для стека область динамической памяти. Старшие адреса памяти┌──────────────────┐ │ Хип │ │ │ ├──────────────────┤ │ │ │ │ │ Стек │ │ │ ├──────────────────┤ │Глобальные перемен│ ├──────────────────┤ │ │ │ │ │ Программа │ │ │ Младшие адреса памяти└──────────────────┘ Рис.15. Использование памяти в программе на языке Турбо Пас- каль. Использование динамической памяти зависит от того, какая функция применяется для освобождения памяти и возвращения ее сис- теме: функция "Dispose" или пара процедур "Mark" и "Release". Как указано в справочном руководстве по языку Турбо Паскаль, эти два способа нельзя никогда смешивать в одной программе. Следователь- но, вам заранее необходимо решить, каким из способов пользовать- ся. Для того, чтобы понять, чем эти способы отличаются друг от друга, ниже дается краткое описание этих функций. Работа с Турбо Паскалем #1/2 = 78 = ФУНКЦИЯ New ----------------------------------------------------------------- Использование этой функции позволяет получить память из ди- намической области. Эта встроенная процедура в качестве аргумента использует указатель на ту переменную, которая должна размещаться в динамической области. После обращения значение аргумента будет указывать на выделенный участок памяти. Например, для размещения вещественного числа в динамической области можно записать следую- щий код: type rpntr = real; var p:rpntr; begin New(p); . . . Если в динамической области не будет свободного участка, то будет выдан код ошибки FF /конфликт динамической области памяти или стека/. Для того, чтобы избежать этого, необходимо перед вы- зовом указанной функции сделать вызов функции "Max-AvatI", кото- рая определяет размер в байтах *незанятой части динамической об- ласти памяти. /Пользователи версии 3.0 должны иметь в виду, что указанная функция определяет число свободных блоков,а не байт/ В приведенном выше примере этот шаг отсутствует, но возможно он потребуется при решении ваших задач. Работа с Турбо Паскалем #1/2 = 79 = ФУНКЦИЯ 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. Работа с Турбо Паскалем #1/2 = 80 = ФУНКЦИИ 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. Метод управления динамическим распределением памяти зависит от того, как вы хотите возвращать память системе. Если память бу- дет возвращаться частично, то следует использовать функцию Работа с Турбо Паскалем #1/2 = 81 = Dispose. Если вы всегда предполагаете освобождать всю память, то лучше использовать функции Mark и Release. В примерах в этой кни- ге используется функция Dispose, поскольку такой метод обладает большей гибкостью. Однако вы можете свободно пользоваться функци- ями Mark и Release для освобождения памяти, если это больше под- ходит для ваших задач. Работа с Турбо Паскалем #1/2 = 82 = ОБРАБОТКА РАЗРЕЖЕННЫХ МАССИВОВ ----------------------------------------------------------------- Обработка разреженных массивов является основной областью применения динамического распределения памяти. В разреженных мас- сивах фактически имеются не все элементы. Такой массив может пот- ребоваться в тех случаях, когда размеры массива значительно пре- вышают размер памяти вашей машины и когда не все элементы массива будут использоваться. Массивы большой размерности требуют большо- го расхода памяти, поскольку ее объем растет по экспоненте в за- висимости от размера массива. Например, для символьной матрицы 10 х10 требуется только 100 байт памяти, а для матрицы 100х100 тре- буется 10 000 байт и для матрицы 1000х1000 требуется уже 1 000 000 байт памяти. Электронная таблица является хорошим примером разреженной матрицы. Даже если матрица будет большой, например, 999х999, в каждый конкретный момент времени будет использована только неко- торая ее часть. Каждому элементу электронной матрицы ставится в соответствие формула, значение или символьные строки. Память под каждый элемент разреженной матрицы выделяется по мере необходи- мости. Хотя использоваться может лишь небольшая часть элементов, вся матрица может быть очень большой - больше чем обычные размеры памяти ЭВМ. Имеется три различных метода создания разреженных массивов: связанный список, двоичное дерево и массив указателей. Каждый из этих методов предполагает, что электронная матрица имеет форму, представленную на следующей странице. В этом примере Х располагается в ячейке В2. ----А---- ----В---- ----С---- ... 1 2 Х 3 4 5 . . . Работа с Турбо Паскалем #1/2 = 83 = Использование связанного списка для организации разреженного массива ----------------------------------------------------------------- При реализации разреженного массива с помощью связанного списка формируется запись, которая содержит информационные поля для каждого элемента массива и поле позиции элемента в массиве, а также указатели на предыдущий и следующий элементы списка. Все записи в списке упорядочены по индексу массива. Доступ к элемен- там массива осуществляется путем прохода по связям элементов списка. Например, может использоваться следующая запись для создания разреженного массива: 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 и т.д.) Работа с Турбо Паскалем #1/2 = 84 = { упорядоченная вставка элементов в список и установка указателя на начало списка } 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; Работа с Турбо Паскалем #1/2 = 85 = 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; Работа с Турбо Паскалем #1/2 = 86 = 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; { конец процедуры поиска } дополнительной информации, которая требует дополнительного расхо- да памяти, нельзя обеспечить двоичный поиск ячейки. Даже процеду- ра вставки использует линейный поиск для нахождения соответствую- щего места для вставки новой ячейки в отсортированный список. Эти проблемы можно решить, используя для построения разреженного мас- сива двоичное дерево. Работа с Турбо Паскалем #1/2 = 87 = Использование двоичного дерева для организации разреженных массивов ----------------------------------------------------------------- Двоичное дерево является по существу модифицированным спис- ком с двойной связью. Основное его преимущество над обычным спис- ком является быстрота поиска элемента, и как следствие, быстрота вставок и просмотров. В тех случаях, когда требуется обеспечить быстрый поиск в связанном списке записей, применение двоичных де- ревьев дает очень хорошие результаты. При использовании двоичного дерева для реализации электрон- ной таблицы, запись "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 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) Работа с Турбо Паскалем #1/2 = 89 = 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 операций сравнений. Работа с Турбо Паскалем #1/2 = 90 = Применение массива указателей для организации разреженных массивов ----------------------------------------------------------------- Предположим, что электронная матрица имеет размеры 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 иллюстрирует структуру памяти, когда разреженный массив строится на основе массива указателей. Работа с Турбо Паскалем #1/2 = 91 = a ┌───┬────┬───┬────┬───────────┬────┬───┐ │ │1nil│ │1nil│ │1nil│ │ └─┼─┴────┴─┼─┴────┴───────────┴────┴─┼─┘ │ │ │ ┌──────────────┐ │ │ └───│2info for A[n]│ │ │ └──────────────┘ │ │ │ │ ┌───────────────┐ │ └── │2 info for A[a]│ │ └───────────────┘ │ ┌───────────────┐ └───│2 info for A[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); Работа с Турбо Паскалем #1/2 = 92 = 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; Работа с Турбо Паскалем #1/2 = 93 = end; { конец процедуры удаления } Если вы сравните эту процедуру с версией, использующей свя- занный список или дерево, то обнаружите, что она значительно про- ще и выполняется быстрее. Следует помнить, что сам массив указателей требует некоторо- го дополнительного расхода памяти под каждую ячейку. В некоторых случаях это является серьезным ограничением. Работа с Турбо Паскалем #1/2 = 94 = ХЕШИРОВАНИЕ ----------------------------------------------------------------- Хешированием называется процесс выделения элемента индексно- го массива непосредственно по информации, которая содержится в массиве. Полученный индекс называется хеш-адресом. Хеширование обычно используется для уменьшения времени доступа к дисковым файлам. Однако, тот же метод можно использовать для реализации разреженных матриц. В приводимом ниже примере используется проце- дура, где применяется специальная форма хеширования, называемая прямым индексированием. При прямом индексировании каждому ключу соответствует одна и только одна ячейка. (Т.е. хеширование дает уникальный индекс для каждого ключа. Однако, следует заметить, что применение массива указателей не обязательно требует исполь- зования прямой индексации; просто для решения данной задачи такой подход является очевидным). На практике такая схема прямого хеши- рования используется не очень часто и чаще требуется более гибкий метод. В этом разделе будут рассмотрены более общие методы хеши- рования, более мощные и более гибкие. Из предыдущего примера по электронной матрице ясно, что даже в особых случаях не все ячейки будут использованы. Предположим, что в большинстве случаев не более десяти процентов потенциальных ячеек будет действительно использовано. Это значит, что логичес- кий массив с размерами 26х100 (2600 ячеек) потребует в действи- тельности иметь память только под 260 элементов. Следовательно, потребуется иметь физический массив как максимум на 260 элемен- тов. Тогда встает следующая задача: как логический массив отобра- зить на физический массив и как осуществлять к нему доступ? Ответ заключается в использовании списка индексов хеширования. Когда пользователь вводит формулу в электронную матрицу (ло- гический массив), адрес ячейки, задаваемый ее обозначением, ис- пользуется для поручения индекса небольшого физического массива. Предположим, что переменная "sheet" является физическим массивом. Индекс определяется на основе обозначения ячейки путем его преоб- разования в число, как было сделано в примере с массивом указате- лей. Затем это число делится на десять для получения начальной точки входа в массив. (Следует помнить, что для вашего примера физический массив составляет только десять процентов от логичес- кого массива). Если ячейка с этим индексом свободна, то в нее по- мещается логический индекс и значение. В противном случае возни- кает конфликт. Конфликт случается при получении во время хеширования двух одинаковых ключей. В этом случае полученный ин- декс будет соответствовать одному элементу физического массива. Следовательно, в массиве "sheet" делается поиск свободного эле- мента. Когда свободный элемент найден, в него помещается информа- ция, а указатель на это место будет помещен в исходный элемент. Это иллюстрируется на рис.17. Для поиска элемента в физическом массиве при заданном индек- Работа с Турбо Паскалем #1/2 = 95 = се логического массива сначала делается преобразование логическо- го индекса в адрес, полученный посредством хеширования, и затем делается проверка физического массива на наличие в элементе с этим индексом требуемого значения. Если сравнение выполняется удачно, то информация найдена. В противном случае следует пройти по цепочке индексов до тех пор, пока не будет найдено нужное зна- чение или пока не будет обнаружен конец цепочки. Для того, чтобы понять, как эту процедуру можно применить к программе электронной таблицы сначала определим в качестве физи- ческого массива следующий массив записей: 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; Работа с Турбо Паскалем #1/2 = 96 = Таблица Индекс Знач. След. Индекс в таблице ┌──────┬──────┬──────┐ 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 └──────┴──────┴──────┘ Предполагается, что в ячейке A1 значение 100, в A2 значение 200, в A3 - 300, в B19 - 50, а в D2 - 99. Рис.17. Пример хеширования. Перед использованием этот массив должен быть инициализиро- ван. Приводимая ниже процедура используется для установки поля обозначения ячейки на значение "empty" (пусто) для указания на отсутствие элемента. Значение -1 в поле следующего индекса озна- чает конец цепочки индексов хеширования. { инициализация физического массива } procedure InitSheet; var t:integer; Работа с Турбо Паскалем #1/2 = 97 = 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 Работа с Турбо Паскалем #1/2 = 98 = 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 ((icname.CellName) and (loc <> -1)) do loc:=sheet[loc].next; Работа с Турбо Паскалем #1/2 = 99 = if(loc = -1) then begin WriteLn('Not found'); Find := -1; end else Find := loc; write('loc is'); writeLn(loc); end; { конец функции поиска } Следует иметь в виду, что описанная в этом разделе схема хе- ширования очень проста и на практике приходится применять более сложные схемы хеширования. Например, при возникновении конфликта очень часто используют вторичное и третичное хеширование прежде, чем воспользоваться просмотром цепочки индексов хеширования. Од- нако, основные принципы хеширования остаются неизменными. Работа с Турбо Паскалем #1/2 = 100 = Анализ хеширования ----------------------------------------------------------------- При хешировании в лучшем случае (который встречается доста- точно редко) каждый полученный хеш-функцией физический индекс яв- ляется уникальным и время доступа приближается к времени прямого индексирования. Это значит, что цепочка индексов хеширования не создается и все операции поиска по существу являются операциями прямого поиска. Однако, это случается редко, поскольку требуется, чтобы логический индекс равномерно распределялся в пространстве логических индексов. В худшем случае (который также редок) схема хеширования вырождается в схему поиска в связанном списке. Это будет в том случае, когда все полученные с помощью хеш-функции значения логических индексов будут равны. В среднем случае, кото- рый на практике встречается чаще всего, время поиска любого конк- ретного элемента посредством хеширования соответствует времени прямого индексирования, поделенного на некоторую константу, кото- рая пропорциональна средней длине цепочки индексов хеширования. Самым существенным при использовании метода хеширования для реа- лизации разряженной матрицы является обеспечение равномерности распределения физических индексов, чтобы не возникало длинных це- почек. Кроме того, метод хеширования очень хорошо использовать в тех случаях, когда известно какое максимальное число элементов действительно потребуется. Выбор метода реализации разряженных матриц ----------------------------------------------------------------- При выборе связанного списка, двоичного дерева или массива указателей в качестве основы реализации разряженное матрицы сле- дует учитывать эффективность использования оперативной памяти и время доступа. Если разряженность очень большая, то память наиболее эффек- тивно будет использоваться при применении связанного списка и двоичного дерева, поскольку в данном случае в памяти будут распо- лагаться только требуемые элементы. Связи требуют небольшого до- полнительного расхода памяти и обычно на расход памяти влияют незначительно. При использовании массива указателей необходимо предусмотреть место для указателя вне зависимости от наличия эле- мента. Здесь необходимо предусмотреть не только размещение в па- мяти всего массива указателей, но обеспечить память для других целей, определяемых конкретной задачей. В одних случаях это вызо- вет серьезные трудности, хотя в других случаях этих трудностей может не быть. Обычно приходится делать расчет требуемой памяти, чтобы понять, достаточно ли ее будет для вашей программы. Метод хеширования занимает промежуточное место между мето- Работа с Турбо Паскалем #1/2 = 101 = дом, построенным на базе массива указателей, и методом, построен- ным на базе связанного списка или двоичного дерева. Хотя в данном случае требуется размещение в памяти всего физического массива несмотря на то, что часть элементов не будет использована, его размеры все -же будут меньше размеров массива указателей, для ко- торого требуется предусмотреть по крайней мере один указатель для каждого логического элемента. Однако при почти полном заполнении массива память будет ис- пользоваться более эффективно, когда применяется массив указате- лей. В связанных списках в двоичных деревьях как правило исполь- зуется два указателя, в то время как массив указателей требует только одного указателя на каждый элемент. Например, полный мас- сив из тысячи элементов, когда каждый указатель занимает два бай- та, потребует для реализации связанного списка или двоичного де- рева 4000 байт для хранения указателей. Для массива указателей в этом случае потребуется 2000 байт, т.е. экономия составляет 2000 байт. Наименьшее время доступа обеспечивает подход с применением массива указателей. Как в примере с электронной таблицей этот ме- тод часто обеспечивает простой доступ к массиву указателей и просто обеспечивается связь с разреженной матрицей. Этот метод обеспечивает доступ к элементам разреженной матрицы почти со ско- ростью работы обычного массива. Поиск в связанном списке осущест- вляется очень медленно, поскольку здесь выполняется последова- тельный просмотр элементов списка. Даже при добавлении данных в связанный список, обеспечивающих более быстрый поиск элементов, поиск будет выполняться медленней, чем прямой доступ к элементам массива указателей. При использовании двоичного дерева быстро- действие повышается, но все-же оно меньше, чем при прямом доступе к элементам массива указателей. При правильном выборе алгоритма хеширования этот метод часто дает лучшее время доступа, чем время доступа при использовании двоичных деревьев. Однако он никогда не достигнет быстродействия метода массива указателей. Если возможно применение метода массива указателей, то этот метод является наилучшим из-за очень хорошего быстродействия. Од- нако, если решающее значение имеет эффективность использования памяти, то остается использовать лишь связанный список или двоич- ное дерево. Работа с Турбо Паскалем #1/2 = 102 = БУФЕРИЗАЦИЯ ----------------------------------------------------------------- При использовании разряженной матрицы вместо обычных пере- менных можно применять динамическое выделение памяти под матрицу. Пусть, например, имеется два процесса А и В, выполняющиеся в од- ной программе. Предположим, что процесс А требует при работе 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 . Работа с Турбо Паскалем #1/2 = 103 = . . 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; Работа с Турбо Паскалем #1/2 = 104 = При выполнении процесса В существует только указатель "а". Хотя этим методом вы будете пользоваться нечасто, его следует хо- рошо знать, поскольку он часто является единственным способом ре- шения подобных проблем. Оптимальное использование доступной памяти ----------------------------------------------------------------- Если вы являетесь профессиональным программистом, то вам возможно приходилось сталкиваться с трудностями, возникающими когда размер доступной памяти заранее неизвестен. Эти трудности возникают при разработке программы, определенные характеристики которой зависят от размера памяти некоторых или всех ЭВМ, где она будет выполняться. Примерами таких программ являются программы управления электронными таблицами, программы обработки списков почтовых корреспонденций и программы сортировки. Например, прог- рамма внутренней сортировки, способная отсортировать 10 000 адре- сов в ЭВМ с памятью 256К, сможет отсортировать лишь 5 000 адресов в ЭВМ с памятью 128К. Если эту программу предполагается использо- вать на ЭВМ, размер памяти которой заранее неизвестен, то трудно выбрать оптимальный размер фиксированного массива для хранения сортируемой информации: либо программа не будет работоспособна для ЭВМ с малой памятью, либо программа будет рассчитана на худ- ший случай и нельзя будет воспользоваться дополнительной памятью, когда она имеется. Выход из этого положения заключается в динами- ческом выделении памяти. Подобные трудности и их решение хорошо можно проиллюстриро- вать на примере программы редактирования текста. Большинство текстовых редакторов не рассчитаны на использование фиксированно- го числа символов. Напротив, они используют всю память ЭВМ, кото- рая идет на хранение текста, введенного пользователем. Например, при вводе каждой строки делается выделение памяти и достраивается список строк. При удалении строки память возвращается системе. Для реализации такого текстового редактора может использоваться следующая запись для каждой строки: LinePointer = ^Line; str80 = string[80]; Line = record next: str80; { для хранения каждой строки } num: integer; next: LinePointer; {указатель на следующую строку} prior: LinePointer; {указатель на предыдущую запись } end; Для простоты в этом случае для каждой строки выделяется па- мять под 80 символов. На практике будет выделяться память под точное число символов в строке и изменение строки потребует до- Работа с Турбо Паскалем #1/2 = 105 = полнительных затрат. В элементе "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; Работа с Турбо Паскалем #1/2 = 106 = 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; Работа с Турбо Паскалем #1/2 = 107 = 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 } Работа с Турбо Паскалем #1/2 = 108 = { удаление строки текста } 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: '); Работа с Турбо Паскалем #1/2 = 109 = 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; Работа с Турбо Паскалем #1/2 = 110 = { загрузчика файла с диска и получение указателя на начало списка } 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. Работа с Турбо Паскалем #1/2 = 111 = ФРАГМЕНТАЦИЯ ----------------------------------------------------------------- Когда блоки доступной памяти располагаются между участками распределенной памяти, то говорят, что происходит фрагментация памяти. Хотя свободной памяти как правило бывает достаточно, что- бы удовлетворить запрос памяти, однако трудность заключается в том, что размеры отдельных участков свободной памяти недостаточны для этого, несмотря на то, что при их объединении получится дос- таточный объем памяти. На рис.18 показано, как при определенной последовательности обращения к процедурам "New" и "Dispose" может возникнуть такая ситуация. Когда блоки доступной памяти располагаются между участками распределенной памяти, то говорят, что происходит фрагментация памяти. Хотя свободной памяти как правило бывает достаточно, что- бы удовлетворить запрос памяти, однако трудность заключается в том, что размеры отдельных участков свободной памяти недостаточны для этого, несмотря на то, что при их объединении получится дос- таточный объем памяти. На рис.18 показано, как при определенной последовательности обращения к процедурам "New" и "Dispose" может возникнуть такая ситуация. A,B,C,D:^integer W,X,Y,Z:^real; ┌────┬────────────────────────────────────┐ new(A) │ A │ │ └────┴────────────────────────────────────┘ ┌────┬───────┬────────────────────────────┐ new(W) │ A │ W │ │ └────┴───────┴────────────────────────────┘ ┌────┬───────┬────┬───────────────────────┐ new(B) │ A │ W │ B │ │ └────┴───────┴────┴───────────────────────┘ ┌────┬───────┬────┬────┬──────────────────┐ new(C) │ A │ W │ B │ C │ │ └────┴───────┴────┴────┴──────────────────┘ ┌────┬───────┬────┬────┬───────┬──────────┐ new(X) │ A │ W │ B │ C │ X │ │ └────┴───────┴────┴────┴───────┴──────────┘ ┌────┬───────┬────┬────┬───────┬──────┬───┐ new(Y) │ A │ W │ B │ C │ X │ Y │ │ └────┴───────┴────┴────┴───────┴──────┴───┘ ┌────┬───────┬────┬────┬───────┬──────┬───┐ dispose(B)│ A │ W │ │ C │ X │ Y │ │ └────┴───────┴────┴────┴───────┴──────┴───┘ new(Z) Запрос не может быть удовлетворен, поскольку Работа с Турбо Паскалем #1/2 = 112 = нет участка непрерывной свободной памяти доста- точного размера В некоторых случаях фрагментация уменьшается, так как функ- ции динамического распределения памяти объединяют соседние участ- ки памяти. Например, пусть были выделены участки памяти A,B,C,и D /см. ниже/. Затем освобождаются участки B и C. Эти участки можно объединить, поскольку они располагаются рядом. Однако, если осво- бождаются участки B и D, то объединить их нельзя будет, поскольку между ними находится участок C который еще не освобожден: ________________________ │ │ │ │ │ │ A │ B │ C │ D │ │_____│_____│_____│_____│ Так как B и D освобождены, а C занят, то может возникнуть вопрос: "Почему бы Турбо Паскалю не переслать содержимое C в D и затем объединить B и C?" Трудность заключается в том, что ваша программа не будет "знать", что это пересылка произошла. Один из способов предотвращения большой фрагментации заклю- чается в том, чтобы всегда выделять одинаковые участки памяти. В этом случае все освобожденные участки могут использоваться при любых последующих запросах на выделение памяти и таким образом будет использована вся свободная память. Если нельзя использовать всегда одинаковый размер выделяемых участков, то следует ограни- читься только несколькими размерами. Иногда этого можно достиг- нуть путем объединения нескольких запросов на выделение небольших участков в один запрос на выделение одного большого участка памя- ти. Не следует для предотвращения фрагментации выделять больше памяти, чем действительно требуется, поскольку получаемая выгода не окупит потерь от неиспользованной памяти. Можно использовать другой подход к решению этой проблемы: при работе программы можно записывать информацию во временный дисковый файл, освободить всю память и затем считать информацию с диска в память. При считыва- нии информации не будет создаваться никаких промежутков. Работа с Турбо Паскалем #1/2 = 113 = Динамическое распределение памяти и задачи искусственного интеллекта ----------------------------------------------------------------- Хотя Паскаль не является основным языком, который использу- ется при решении задач искусственного интеллекта, его можно ис- пользовать и в этой области. Основной чертой многих программ из области искусственного интеллекта является наличие списка инфор- мационных элементов, который может расширяться программой автома- тически по мере ее "обучения". В таком языке как Пролог, который считается основным языком искусственного интеллекта, поддержка списка обеспечивается автоматически. На языке Паскаль такие про- цедуры должны программироваться с применением связанных списков и механизма динамического распределения памяти. Хотя приводимый пример является очень простым, те же принципы применимы для раз- работки более сложных "разумных" программ. Одну интересную область искусственного интеллекта составляют программы, работа которых напоминает поведение людей. Знаменитая программа "Элиза", например, ведет себя как психиатр. Совсем неп- лохо иметь программу, которая может "разговаривать" на любую тему - как было бы хорошо запустить такую программу, когда вы устанете от программирования и почувствуете себя одиноким! Ниже приводить- ся очень простая версия такой программы. В ней используются слова и их определения для ведения простого диалога с пользователем. Одной общей чертой всех программ искусственного интеллекта явля- ется связь информационного элемента с его смыслом. В этом примере слова связываются с их смыслом. Ниже описывается запись, предназ- наченная для содержания каждого слова, его определения, части ре- чи и его дополнения: type str80 = string[80]; str30 = string[30]; VocabPointer = "тильда"vocab; vocab = record typ: char; { часть речи } connotate: char; { дополнение } word: str30; { само слово } def: str80; { определение } next: VocabPointer; { указатель на следующую запись } prior: VocabPointer; { указатель на предыдущую запись } end В приводимой ниже программе делается ввод слова, его опреде- ления, типа слова и его дополнения типа "хорошо", "плохо" и Работа с Турбо Паскалем #1/2 = 114 = "безразлично". Для поддержки такого словаря строится связанный список с использованием механизма динамического выделения памяти. Функция "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); Работа с Турбо Паскалем #1/2 = 115 = 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; Работа с Турбо Паскалем #1/2 = 116 = { возвращает функцию, выбранную пользователем } 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; Работа с Турбо Паскалем #1/2 = 117 = 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; Работа с Турбо Паскалем #1/2 = 118 = 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 Работа с Турбо Паскалем #1/2 = 119 = 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 Работа с Турбо Паскалем #1/2 = 120 = 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); Работа с Турбо Паскалем #1/2 = 121 = 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); Работа с Турбо Паскалем #1/2 = 122 = 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. Эта программа составляется несложно. Вы можете ее несколько усовершенствовать. Можно, например, выделить из предложения гла- голы и заменить их на альтернативные в комментарии. Вы можете также предусмотреть возможность задавать вопросы. Работа с Турбо Паскалем #1/2 = 123 = ГЛАВА 4. ИНТЕРФЕЙС С ПРОГРАММАМИ НА АССЕМБЛЕРЕ И СВЯЗЬ С ОПЕРАЦИОННОЙ СИСТЕМОЙ ----------------------------------------------------------------- Имея такой мощный инструмент программирования, как Турбо Паскаль, иногда вам потребуется составить программу на ас- семблере или сделать вызов системной программы. Это может потре- боваться для ускорения вашей программы или для обеспечения досту- па к некоторому специальному оборудованию, применение которого непосредственно в Турбо Паскале не предусмотрено. Какими бы при- чинами не объяснялось применение ассемблера, оно предусматривает- ся в рамках языка Турбо Паскаль. Приводимые в этой главе примеры рассчитаны на применение версии ИБМ языка Турбо Паскаль в рамках операционной системы ДОС. Более того, эти примеры рассчитаны на применение версии 4 языка Турбо Паскаль. Следует иметь в виду, что в версии 4 языка Турбо Паскаль интерфейс с ассемблером отличается от такого интер- фейса для более ранних версий. Если вы имеете предыдущую версию или версию для другой ЭВМ, то подробную информацию об интерфейсе с ассемблером можно найти в руководстве пользователя. ИНТЕРФЕЙС С АССЕМБЛЕРОМ ----------------------------------------------------------------- Имеется несколько причин, по которым требуется составлять программу на ассемблере: - для повышения скорости работы и эффективности использова- ния памяти; - для выполнения машинно-зависимых функций, которые отсутс- твуют в Турбо Паскале; - для того, чтобы можно было воспользоваться пакетом прог- рамм общего назначения, написанных на ассемблере. Хотя компилятор языка Турбо Паскаль создает эффективный ком- пактный объектный код, никакой компилятор не сможет постоянно создавать более эффективный и компактный код, чем код, написанный компетентным программистом. Небольшое различие обычно не означа- ет, что при написании программы на ассемблере не потребуется зат- ратить заметно больше времени. Однако в особых случаях требуется составлять программы и процедуры на ассемблере, чтобы обеспечить быструю работу программы. Это требуется делать для часто исполь- зуемых программ и процедур, существенно влияющих на общее быстро- действие программы. Хорошим примером такого применения ассемблера является пакет подпрограмм, выполняющих операции над числами с плавающей запятой. Кроме того, специальное оборудование иногда требует точной синхронизации в работе, которая обеспечивается только программированием на ассемблере. Многие ПЭВМ, включая машины, построенные на базе процессоров 8086 и 8088, обладают возможностями, которыми нельзя воспользо- Работа с Турбо Паскалем #1/2 = 124 = ваться непосредственно на Турбо Паскале. Например, используя Турбо Паскаль нельзя изменить сегменты данных и возникают труд- ности при доступе к специальным регистрам. На практике часто приобретаются библиотеки подпрограмм. В качестве таких библиотек подпрограмм можно назвать широко расп- ространенные библиотеки подпрограмм для работы с числами с плава- ющей запятой и пакеты графических программ. Иногда имеются только объектные коды этих подпрограмм, поскольку разработчик не постав- ляет исходные тексты. В одних случаях эти подпрограммы могут просто вызываться в программе на Паскале. В других случаях прихо- дится составлять интерфейсный модуль для обеспечения связи Турбо Паскаля с приобретенными подпрограммами. Имеется два способа применения ассемблера в программе на Турбо Паскале. Во-первых, можно написать отдельную программу, ас- семблировать ее и затем подсоединить ее к основной программе, ис- пользуя команду "external". Во-вторых, в программе на языке TURBO -Паскаль можно непосредственно записывать код на ассемблере. Обучение программированию на языке ассемблера выходит за рамки этой книги. В этой главе подразумевается, что вы уже знако- мы с языком ассемблера, который имеется на вашей ЭВМ. Приводимые примеры только иллюстрируют применение ассемблера. Работа с Турбо Паскалем #1/2 = 125 = ВНУТРЕННИЕ ФОРМАТЫ ДАННЫХ И СОГЛАШЕНИЯ О СВЯЗЯХ В ЯЗЫКЕ ТУРБО ПАСКАЛЬ ----------------------------------------------------------------- Прежде чем писать подпрограмму на ассемблере для использова- ния ее в программе на языке Турбо Паскаль необходимо понять , как данные представляются в программе и как они передаются между подпрограммами. Для версии ИБМ все глобальные переменные и конс- танты хранятся в сегменте данных и доступ к ним осуществляется с использованием регистра DS. Все локальные переменные помещаются в стек и доступ к ним осуществляется с применением регистра ВР, ко- торый используется для индексации стека. Рис.19 показывает способ хранения для данных каждого типа. Следует иметь в виду, что байты указателей задаются в обратном порядке. Следовательно, указатель, имеющий смещение В000 и сегмент 0010, будут храниться в следующем виде: ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 10 │ │ 00 │ │ 00 │ │ B0 │ └──────┘ └──────┘ └──────┘ └──────┘ Сегмент Смещение Соглашения о связях представляют собой метод, который ис- пользуется компьютером языка Турбо Паскаль для передачи информа- ции подпрограмм и передачи результатов. В языке Турбо Паскаль для передачи параметров в подпрограмму используется стек /он также используется для передачи результатов функции/. При этом в ре- гистре АХ передается результат однобайтовой или однословной функ- ции. Точное содержимое стека при вызове подпрограммы запвисит от типа передаваемых переменных и от типа передачи параметра. Работа с Турбо Паскалем #1/2 = 126 = ──────────────────────────────────────────────────────────────── Тип Длина Комментарии данного данного ──────────────────────────────────────────────────────────────── двоичный 1 байт однобай- 1 байт товый символьный 1 байт целый 2 байта целый ко- 1 байт роткий целый 4 байта длинный слово 2 байта вещест- 6 байт Первый байт содержит мантиссу, следующий венный байт является младшим и последний байт является старшим одиночный 4 байта Стандартный формат числа с плавающей запятой двойной 8 байт Стандартный формат числа с плавающей запятой и с двойной точностью расширен- 10 байт Стандартный формат числа с плавающей ный запятой и повышенной точностью для вы- 3 байт Дополнительный код числа с плавающей числений запятой строка перемен- Первый байт содержит текущую длину строки; ная следующий байт является первым символом строки множество перемен- Поскольку каждый элемент использует один ная бит и максимальное число элементов равно 256, то максимальная длина множества равна 32 байта Указатель 4 байта Два младших байта содержат смещение, а старшие байты содержат сегмент. Байты хранятся в обратном порядке. Нулевое значение занимает 4 байта Массивы перемен- Значения с меньшим индексом имеют меньший ная адрес памяти Записи перемен- Первое поле имеет наименьший адрес, ная последнее поле имеет самый старший адрес ─────────────────────────────────────────────────────────────── Рис.19. Представление данных в памяти Параметры-значения ----------------------------------------------------------------- Работа с Турбо Паскалем #1/2 = 127 = Параметры-значения передаются в одном направлении: в подп- рограмму передается значение параметра, но любые изменения этого параметра не оказывают влияния на действительную переменную, ко- торая использовалась при вызове подпрограммы. Подпрограмме пере- дается не адрес этой переменной, а копия ее значения и поэтому сама переменная не изменяется. По существу процедуре и функции передается лишь некоторое значение. Значения будут помещаться в стек при передаче параметров следующих типов: - двоичного /булевского/; - символьного; - целого; - целого длинного; - целого короткого; - байта; - слова; - вещественного; - указателя; - перечисления. Для двойных слов сначала в стек помещается старшая часть значения и затем младшая часть. Массивы и записи, размер которых превышает четыре байта, в действительности не передаются функции. Передается адрес /сегмент и смещение/ переменной. Сначала в стек помещается сегмент и затем смещение. /Массивы, размер которых меньше пяти байт непосредс- твенно помещаются в стек/. Множества и строки тоже передаются с использованием указателей на действительные переменные. Поскольку для данных этих типов в функции передаются адреса, необходимо де- лать копии действительных данных, чтобы изменения данных, произ- веденные внутри функции, не повлияли на эти переменные вне функ- ции. Параметры-переменные ----------------------------------------------------------------- В отличии от параметров-значений параметры-переменные пере- даются посредством помещения в стек адресов. Это значит, что подпрограмма работает непосредственно с этими переменными. Пара- метрыпеременные передаются в обоих направлениях, т.е. информация передается в подпрограмму и может также передаваться обратно в вызывающую программу, поскольку значение параметров может менять- ся. Для передачи сегмента и смещения параметра-переменной в стек помещается два слова вне зависимости от типа переменной. Работа с Турбо Паскалем #1/2 = 128 = Передача результата функции ----------------------------------------------------------------- Когда написанная на языке Турбо Паскаль функция завершает свою работу, она передает значение результата обратно в вызываю- щую программу. Для всех скалярных типов кроме вещественного зна- чение передается через регистр АХ. Для булевской переменной дол- жен также устанавливаться флажок нуля: единичное значение означает булевское значение "истина", а нулевое значение означает булевское значение "ложь". При передачи указателей сегмент пере- дается в регистр DX, а смещение передается в регистр АХ. Вещест- венные переменные передаются в виде DX:BX:AX, причем в регистр DX помещается старшее слово, а в регистр АХ помещается младшее сло- во. При передаче в качестве результата символьных строк, масси- вов и записей адрес значения передается в виде DX:AX. Результат функции помещается сразу за адресом возврата. На рис.20 показан вид стека при вызове функции. ┌──────────────────────┐ │ Параметры │ │ . . . │ ├──────────────────────┤ Вершина стека ──── │ Адрес возврата │ ├──────────────────────┤ │ │ │ │ └──────────────────────┘ Рис.20. Вид стека при вызове функции Сохранение регистров ----------------------------------------------------------------- Во всех подпрограммах на ассемблере необходимо предусмотреть сохранение регистров BP, DS и SS. Обычно это делается при помощи инструкций "push" и "pop". Если составляется программа на ассемблере, которая будет об- ращаться к подпрограмме на языке Турбо Паскаль, то нужно следо- вать всем соглашениям о связях, которые рассматривались ранее. Только при соблюдении этих соглашений можно обеспечить правильный вызов программы на языке Турбо Паскаль из модуля, написанном на ассемблере. Создание внешней программы на ассемблере ----------------------------------------------------------------- Работа с Турбо Паскалем #1/2 = 129 = Теперь, когда рассмотрены соглашения о связях, приведем код действительной программы на ассемблере. Предположим, что требует- ся составить программу на ассемблере для следующей функции: 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. Эти инструкции помещают адрес вершины стека в регистр ВР и затем сдвигают четвертый байт дальше в стек /т.е. параметр "а" Работа с Турбо Паскалем #1/2 = 130 = помещается в регистр АХ/. Параметры занимают четвертый и шестой байты, поскольку адрес возврата и инструкция "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. Встроенный код ассемблера Работа с Турбо Паскалем #1/2 = 131 = ----------------------------------------------------------------- В отличие от стандартного Паскаля в Турбо Паскале предусмат- ривается возможность непосредственного включения кода на ассемб- лере. Таким образом, нет необходимости составлять отдельную внеш- нюю подпрограмму. Такой подход имеет два преимущества: во-первых, программист не должен писать код, реализующий связь между прог- раммами; во-вторых, весь код расположен в одном месте, что делает простой сопровождение программы. Единственный недостаток заключа- ется в том, что встроенный код ассемблера имеет неудобный формат. Оператор "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} Работа с Турбо Паскалем #1/2 = 132 = $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; Следует помнить, что компилятор Турбо Паскаля обеспечивает необходимый код для входа и выхода из функции. Пользователю необ- ходимо лишь обеспечить тело функции и придерживаться соглашений о связях при доступе к аргументам. При использовании указанного метода создается машинно-зави- симый код, что затрудняет перенос программы на новую машину или в среду новой операционной системы. Однако в тех случаях, когда нельзя обойтись без кода ассемблера, применение указанного метода оправдано. Когда следует применять ассемблер ----------------------------------------------------------------- Большинство программистов используют ассемблер только при крайней необходимости, поскольку программировать на ассемблере Работа с Турбо Паскалем #1/2 = 133 = достаточно сложно. Общее правило заключается в том, что вообще не следует использовать ассемблер - он создает слишком много проб- лем. Однако можно указать два случая практического применения ас- семблера. Первый возникает когда нет другого пути решения задачи. Например, когда требуется обеспечить непосредственную связь с оборудованием, управление которым не предусмотрено в языке Турбо Паскаль. Во-вторых, такая ситуация возникает при необходимости умень- шения времени выполнения программ и все возможности оптимизации кода Турбо Паскаля исчерпаны. В данном случае необходимо делать тщательный выбор функций для их кодирования на ассемблере. Если выбор будет сделан неправильно, то эффект будет незначительный. При правильном выборе эффект может быть очень большим. Для того, чтобы определить какие подпрограммы требуют перекодировки, необ- ходимо определить операционную блок-схему вашей программы. Обычно для реализации на ассемблере выбираются подпрограммы, которые ис- пользуются внутри циклов, поскольку они выполняются много раз. Кодирование на ассемблере процедуры или функции, которые выполня- ются один или два раза, может не дать заметного эффекта, а коди- рование на ассемблере функции, которая выполняется много раз, мо- жет дать такой эффект. Например, рассмотрим следующую процедуру: 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" расположена внутри цикла, она выполняется лишь один раз и поэтому ее перекодировка не даст эф- фекта. При тщательном выборе процедур для их кодировки на ассембле- ре можно добиться улучшения быстродействия программы за счет пе- рекодировки лишь небольшого числа подпрограмм. Работа с Турбо Паскалем #1/2 = 134 = СВЯЗЬ С ОПЕРАЦИОННОЙ СИСТЕМОЙ ----------------------------------------------------------------- Поскольку часто системные программы пишутся на языке Турбо Паскаль, необходимо обеспечить непосредственную связь с операционной системой для выполнения определенных операций в об- ход стандартного интерфейса Турбо Паскаля. Может возникнуть также потребность в специальных системных функциях, которые отсутствуют в Турбо Паскале. По этой причине применение специальных средств операционной системы является обычным при программировании на Турбо Паскале. В настоящее время несколько операционных систем поддерживает Турбо Паскаль: - PC-DOS или MS-DOS; - СР/М; - СР/М-86. Все операционные системы предусматривают возмож- ность применения в программах таких функций, как открытие дисковых фай- лов, ввод символов с консоли и вывод символов на консоль, выделе- ние памяти для выполнения программы. Способ применения этих функ- ций зависит от операционной системы, но во всех случаях используется таблица переходов. В такой операционной системе как СР/М вызов системной функции осуществляется инструкцией CALL с передачей управления в определенный участок памяти, когда регистр содержит требуемый код функции. В операционной системе PC-DOS применяется программное прерывание. В обоих случаях для связи системной функции с вашей программой используется таблица перехо- дов. На рис.21 показано расположение операционной системы и таб- лицы переходов в памяти. ┌─────────────────────┐ │ Операционная │ ───────┐ ┌────── │ система │ ────┐ │ │ │ │ │ │ │ │ │ │ │ │ ┌── │ │ │ │ │ │ ├─────────────────────┤ │ │ │ │ │ . . . │ │ │ │ │ ├─────────────────────┤ │ │ │ │ │ Функция 4 ──┼─────┼──┘ │ │ ├─────────────────────┤ │ │ │ │ Функция 3 ──┼─────┘ │ │ ├─────────────────────┤ │ └───┼─ Функция 2 │ │ ├─────────────────────┤ └───────┼─ Функция 1 │ └─────────────────────┘ Рис.21. Расположение в памяти операционной системы и таблицы переходов Работа с Турбо Паскалем #1/2 = 135 = В этой книге нет возможности рассмотреть все операционные системы. В этой главе будет рассматриваться только операционная система 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/. Во-вторых, через интер- фейс с ассемблера. Работа с Турбо Паскалем #1/2 = 136 = Применение процедуры 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; Работа с Турбо Паскалем #1/2 = 137 = end; begin repeat Write('.'); until KbHit; end. Следует отметить, что в этом вызове нет необходимости зада- вать значения остальным регистрам, поскольку здесь требуется функция с единственным номером $B. В общем случае если какой-то регистр не используется при вызове, то его значение может не ус- танавливаться. Работа с Турбо Паскалем #1/2 = 138 = Таблица 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: столбец верхнего левого угла, Работа с Турбо Паскалем #1/2 = 139 = 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: не используется, Работа с Турбо Паскалем #1/2 = 140 = бит 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: информация сектора Работа с Турбо Паскалем #1/2 = 141 = Функции ввода-вывода посредством клавиатуры - прерывание 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: символ Работа с Турбо Паскалем #1/2 = 142 = 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/ ─────────────────────────────────────────────────────────────── Использование функций базовой системы ввода-вывода и ДОС ----------------------------------------------------------------- В некоторых случаях желательно иметь возможность использо- вать внешние программы, написанные на ассемблере, для доступа к Работа с Турбо Паскалем #1/2 = 143 = системным функциям. Рассмотрим несколько примеров. Пусть во время работы программы требуется изменить режим экрана. Ниже приводятся семь режимов экрана при использовании цветного графического адап- тера в операционной среде PC-DOS: Режим Тип Размеры Адаптеры 0 Текст, черно- 40 х 25 CGA, EGA белый 1 Текст, 16 40 х 25 CGA, EGA цветов 2 Текст, черно- 80 х 25 CGA, EGA белый 3 Текст, 16 80 х 25 CGA, EGA цветов 4 Графика, 4 320 х 200 CGA, EGA цвета 5 Графика, 4 320 х 200 CGA, EGA черно-белых тона 6 Графика 640 х 200 CGA, EGA черно-белая 7 Текст, черно- 80 х 25 Монохроматический белый 8 Графика, 16 160 х 200 PCjr цветов 9 Графика, 16 320 х 200 PCjr цветов 10 Графика 320 х 200 PCjr, EGA PCjr - 4 цвета EGA - 16 цветов 13 Графика, 16 320 х 200 EGA цветов 14 Графика, 16 640 х 200 EGA цветов Работа с Турбо Паскалем #1/2 = 144 = 15 Графика, 4 640 х 350 EGA цвета Приводимая ниже процедура "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 Ниже приводится функция, которая очищает экран посредством Работа с Турбо Паскалем #1/2 = 145 = процедуры "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 Другим примером связи с базовой системой ввода-вывода Работа с Турбо Паскалем #1/2 = 146 = посредством применения ассемблера является функция "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 Работа с Турбо Паскалем #1/2 = 147 = code ends end Работа с Турбо Паскалем #1/2 = 148 = Использование кодов клавиш сканирования ----------------------------------------------------------------- При работе на ПЭВМ фирмы ИБМ наиболее сложно обрабатывать программно коды функциональных клавиш и клавиш со стрелками /так- же клавиш 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; возвращаемое значение ; восстановление и выход Работа с Турбо Паскалем #1/2 = 149 = 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". Для декодирования кода сканирования вы можете воспользовать- ся техническим справочным руководством фирмы ИБМ. Другой, более интересный способ, заключается в написании короткой программы, единственным назначением которой является лишь экспериментальная выдача кодов нажатых клавиш. Для начала приведем коды сканирова- ния для клавиш со стрелками: Работа с Турбо Паскалем #1/2 = 150 = Левая стрелка - 75, Правая стрелка - 77, Стрелка вверх - 72, Стрелка вниз - 80. Для полного совмещения специальных клавиш с обычными кла ви- шами необходимо написать специальные функции ввода данных и использовать их вместо обычных функций "read" и "readln". К сожа- лению этот путь является единственным. Однако, наградой будет возможность работать в вашей программе с полным набором клавиш ПЭВМ фирмы ИБМ. Работа с Турбо Паскалем #1/2 = 151 = Заключительные замечания относительно связи с операционной системой ----------------------------------------------------------------- В этой главе лишь кратко рассмотрены возможности применения системных ресурсов. Для полного использования возможностей опера- ционной системы потребуется подробная информация по системным функциям. Применение системных функций дает несколько преимуществ. Во- первых, это позволяет лучше использовать особенности конкретной ПЭВМ и сделать программу более профессионально. Во-вторых, ис- пользование системных функций вместо встроенных в TURBO -Паскаль иногда позволяет создавать более быстрые и более эффективные программы. В-третьих, это позволяет использовать функции, которые отсутствуют в Турбо Паскале. Однако, применение системных функций обеспечивается не бесп- латно. Используя системные функции вместо стандартных функций и процедур, вы создаете себе дополнительные трудности, поскольку ваша программа теперь не будет мобильной. Ваша программа может также зависеть от конкретной версии данной операционной системы и компилятора Турбо Паскаля, что создает проблемы совместимости при распространении ваших программ. Только вы сами должны решать, когда следует в программе использовать функции, зависимые от ма- шины или операционной системы. Работа с Турбо Паскалем #1/2 = 152 = ГЛАВА 5. СТАТИСТИЧЕСКИЙ АНАЛИЗ ----------------------------------------------------------------- Большинство людей, пользующихся ЭВМ, в какой-то мере исполь- зуют их для статистического анализа. Такой анализ может принимать форму предсказания изменений курса акций, выполнения клинических тестов для определения границ применения нового лекарства или да- же определения средних результатов команд из Младшей Лиги. Ветвь математики, которая занимается обобщением, обработкой и экстрапо- ляцией данных, называется статистическим анализом. Как отдельная дисциплина статистический анализ стал рассмат- риваться не так давно. Он появился в 1700-е годы в результате изучения игр со случайными событиями. Статистический анализ и те- ория вероятности в действительности сильно связаны друг с другом. Современные подходы к статистическому анализу сложились на рубеже нынешнего столетия, когда стали доступны для обработки большие наборы данных. Применение ЭВМ позволяет быстро находить связь и обрабатывать очень большие наборы данных, а также представлять их в удобной для человека форме. Теперь, когда все больше информации создается и используется правительством и средствами массовой ин- формации, почти каждый аспект жизни подвергается статистической обработке. Практически нельзя слушая радио, смотря телевизор или читая газеты не получить некоторую статистическую информацию. Хотя Турбо Паскаль не разрабатывался специально для програм- мирования задач по статистическому анализу, он достаточно хорошо подходит для этой цели. В некоторых случаях он обладает даже большей гибкостью, чем некоторые языки экономической ориентации, например, Кобол и Бейсик. Одним из преимуществ Турбо Паскаля над Коболом является простота использования графического интерфейса для выдачи графиков данных. Кроме того, математические подпрог- раммы Турбо Паскаля работают значительно быстрее, чем большинство таких подпрограмм в других языках. В этой главе рассматривается расчет следующих величин, ис- пользуемых в статистическом анализе: - среднего значения; - медианы; - моды; - стандартного отклонения; - коэффициента регрессии; - коэффициента корреляции. Кроме того, дается несколько простых методов графического вывода. Работа с Турбо Паскалем #1/2 = 153 = ВЫБОРКИ, ГЕНЕРАЛЬНЫЕ СОВОКУПНОСТИ, РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ И ПЕРЕМЕННЫЕ ----------------------------------------------------------------- Прежде чем перейти к статистическому анализу, следует позна- комиться с некоторыми ключевыми понятиями. Для получения статис- тических данных сначала берется выборка определенных значений данных, на основании которой затем делаются обобщающие выводы. Каждая выборка берется из генеральной совокупности, представляю- щей собой все возможные значения, которые могут быть в исследуе- мой ситуации. Например, если оценивать результаты работы фабрики, выпускающей ящики, по данным выпуска только за каждую среду и де- лая по ним вывод о выпуске за весь год, то здесь выборка предс- тавляет собой данные о выпуске по всем средам года и является частью генеральной совокупности данных о ежедневном выпуске за год. Выборка может совпадать с генеральной совокупностью и в этом случае она будет исчерпывающей. Для приведенного примера выборка будет совпадать с генеральной совокупностью в том случае, когда будут использоваться данные о выпуске по всем пяти дням в неделю в течение года. Если выборка меньше генеральной совокупности, то всегда результат может иметь ошибку. Однако, в большинстве случа- ев можно определить вероятность этой ошибки. В этой главе предпо- лагается, что выборка совпадает с генеральной совокупностью, и следовательно, такие ошибки не рассматриваются. При оценке результатов выборов и проведении опросов общест- венного мнения результаты относительно небольшой выборки расп- ространяются на все население. Например, статистическую информа- цию о курсе акций Дау Джонса можно использовать для оценки курса акций на всем рынке. Конечно, достоверность таких выводов может меняться в широком диапазоне. В других случаях выборка, совпадаю- щая или почти совпадающая с генеральной совокупностью, использу- ется для суммирования большого набора чисел и упрощения обработ- ки. Например, в отчетах органов образования обычно приводятся средние оценки для класса вместо индивидуальных оценок учащихся. Статистика зависит от распределения случайных событий в ге- неральной совокупности. Из нескольких широко распространенных в природе наиболее важным (и единственным рассматриваемым в этой главе) является нормальное распределение. Наиболее вероятными значениями являются средние значения. И действительно, график этого распределения полностью симметричен относительно своей вер- шины, которая представляет также среднее значение. Чем дальше расстояние от среднего значения, тем меньше вероятность события. Многие ситуации в реальной жизни описываются нормальным распреде- лением. В любом статистическом процессе имеется независимая перемен- ная, которая является предметом изучения, и зависимая переменная, которая является фактором, влияющим на независимую переменную. В Работа с Турбо Паскалем #1/2 = 154 = этой главе в качестве зависимой переменной используется время (как промежуток между соседними событиями). Например, исследуя курсы акций, вы можете захотеть рассмотреть их изменения в тече- ние дня. Вам поэтому потребуется изучить изменения курса акций в течение заданного периода без относительно к действительной ка- лендарной дате. В этой главе будут разработаны отдельные статистические функции и затем они будут объединены в одну программу, которая работает с помощью меню. Эта программа может использоваться для разнообразного статистического анализа. Она также может использо- ваться для вывода графиков на экран. Элементы выборки в дальнейшем будут обозначаться буквой D с индексом от I до N, где N является номером последнего элемента. Основные статистические оценки ----------------------------------------------------------------- Статистический анализ во многих случаях основывается на по- лучении трех важных величин, которые имеют также самостоятельное значение. Этими величинами являются среднее значение, медиана и мода. Среднее значение ----------------------------------------------------------------- Среднее значение или арифметическое среднее наиболее широко используется в статистике. Это одно значение может использоваться для представления некоторого набора данных. В этом случае среднее значение можно назвать "центром тяжести" этого набора. Среднее значение вычисляется следующим образом: складываются все значения выборки и результат делится на общее число значений. Например, сумма набора значений 1 2 3 4 5 6 7 8 9 10 равна 55. Если это значение разделить на число элементов выборки, равное десяти, то получим среднее значение 5,5. При разработке статистических функций на Турбо Паскале будем считать, что все данные хранятся в массиве чисел с плавающей за- пятой с названием "DataArray", тип которого определяется пользо- вателем. Будем считать, что число элементов выборки известно. Все функции и процедуры будут использовать массив "data" для хранения выборки и переменную "num" для хранения числа элементов. Приводи- мая ниже функция вычисляет среднее значение для массива из "num" чисел с плавающей запятой. Результат получается в виде данного типа числа с плавающей запятой: Работа с Турбо Паскалем #1/2 = 155 = { вычисление среднего значения } function mean(data: DataArray; num: integer): real; var t: integer; avg: real; begin avg:=0; for t:= 1 to num do avg:=avg+data[t]; mean:= avg/num; end; { конец вычисления среднего значения } Например, если вы вызовете функции "Mean" с десятиэлементным массивом, содержащим числа от 1 до 10, то в результате получите 5,5. Медианы ----------------------------------------------------------------- Медианой выборки является среднее значение из всего упорядо- ченного набора значений. Например, для выборки 1 2 3 4 5 6 7 8 9 медианой будет 5, поскольку это число находится в середине. В на- боре значений 1 2 3 4 5 6 7 8 9 10 в качестве медианы может использоваться 5 или 6. В хорошо упоря- доченной выборке, какой является выборка с нормальным распределе- нием, среднее значение и медиана имеют очень близкие значения. Однако по мере увеличения отклонения закона распределения выборки от нормального увеличивается разница между медианой и средним значением. Медиана вычисляется путем сортировки выборки в порядке возрастания значений и выбора среднего значения с индексом N/ 2. Результатом приводимой ниже функции "Median" является значе- ние среднего элемента выборки. Для сортировки массива данных ис- пользуется модифицированная версия процедуры быстрой сортировки, разработанной в главе 1: { версия процедуры быстрой сортировки для упорядочения целых чисел } procedure QuickSort(var item: DataArray; count: integer); procedure qs(l, r: integer; var it: DataArray); var Работа с Турбо Паскалем #1/2 = 156 = 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 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 loldcount then begin oldmd := md; oldcount := count; end; end; FindMode := oldmd; end; { конец процедуры поиска моды } Работа с Турбо Паскалем #1/2 = 158 = Применение среднего значения, медианы и моды ----------------------------------------------------------------- Среднее значение, медиана и мода служат одной цели, а имен- но, обеспечению одного значения, обобщающего все значения выбор- ки. Однако, каждое из них представляет выборку по разному. Обычно чаще всего используется среднее значение выборки. Поскольку при вычислении среднего значения делается суммирование всех значений выборки, оно является действительно отражением всех элементов вы- борки. Основным недостатком среднего значения является чувстви- тельность к одному экстремальному значению. Например, пусть в не- кой фирме "Уидгeт" заработок владельца составляет 100000 долларов в год, а заработок каждого из девяти рабочих составляет 10 000 долларов в год. Средний заработок в этой фирме будет равен 19 000 долларов в год, однако эта цифра недостаточно правильно описывает ситуацию в фирме. В случаях, аналогичных описанному, иногда вместо среднего значения используется мода. Мода заработков в фирме "Уидгeт" рав- на 10 000 долларов в год и эта цифра более правильно отражает ре- альную ситуацию в фирме. Однако, мода также может вводить в заб- луждение. Пусть некоторая автомобильная фирма производит автомобили пяти различных цветов. За некоторую неделю было полу- чено - 100 зеленых автомобилей; - 100 оранжевых автомобилей; - 150 синих автомобилей; - 200 черных автомобилей; - 190 белых автомобилей. Здесь модой выборки являются черные автомобили, поскольку было произведено 200 черных автомобилей, что превышает число ав- томобилей любого другого цвета. Однако, неправильно делать вывод о том, что автомобильная фирма производит в основном автомобили черного цвета. Медиана представляет интерес для тех случаев, когда оправда- но предположение о нормальном распределении. Например, если вы- борка представляет собой следующий набор: 1 2 3 4 5 6 7 8 9 10 то медианой будет 5 или 6, а среднее значение 5,5. В этом случае медиана близка к среднему значению. Однако, в следующей выборке 1 1 1 1 5 100 100 100 100 медиана по-прежнему равна 5, а среднее значение приблизительно равно 46. В определенных случаях ни среднее значение, ни медиана, ни Работа с Турбо Паскалем #1/2 = 159 = мода не могут дать достоверную картину. Это приводит к использо- ванию двух наиболее важных статистических величин - дисперсии и стандартного отклонения. Работа с Турбо Паскалем #1/2 = 160 = Дисперсия и стандартное отклонение ----------------------------------------------------------------- Хотя для оценки всей выборки очень удобно использовать лишь одно значение /такое как среднее значение, мода или медиана/, этот подход легко может привести к неправильным выводам. Нетрудно понять, что причина такого положения лежит не в самой величине, а в том, что одна величина никак не отражает разброс значений дан- ных. Например, в выборке 1 1 1 1 9 9 9 9 среднее значение равно 5. Однако, в самой выборке нет ни одного элемента со значением 5. Возможно вам потребуется знать степень близости каждого элемента выборки к ее среднему значению. Или, другими словами, вам потребуется знать дисперсию значений. Зная степень изменения данных вы можете лучше интерпретировать среднее значение, медиану и моду. Степень изменения значений выборки оп- ределяется путем вычисления их дисперсии и стандартного отклоне- ния. Дисперсия и квадратный корень из дисперсии, называемый стан- дартным отклонением, характеризуют среднее отклонение от среднего значения выборки. Среди этих двух величин наиболее важное значе- ние имеет стандартное отклонение. Это значение можно представить как среднее расстояние, на котором находятся элементы от среднего элемента выборки. Дисперсию трудно интерпретировать содержательно. Однако, квадратный корень из этого значения является стандартным отклоне- нием и хорошо поддается интерпретации. Стандартное отклонение вы- числяется путем определения сначала дисперсии и затем вычисления квадратного корня из дисперсии. Например, для выборки 11 20 40 30 99 30 50 будут получены следующие значения: D D-M (D-M) 11 -29 841 20 -20 400 40 0 0 30 -10 100 99 59 3491 30 -10 100 50 10 100 Сумма 280 0 5022 Среднее значение 40 0 717,42 Работа с Турбо Паскалем #1/2 = 161 = Здесь среднее значение квадратов разностей равно 717,42. Для получения стандартного отклонения осталось лишь взять квадратный корень из этого числа. Результат составит приблизительно 26,78. Следует помнить, что стандартное отклонение интерпретируется как среднее расстояние, на котором находятся элементы от среднего значения выборки. Стандартное отклонение показывает, насколько хорошо среднее значение описывает всю выборку. Если вы являетесь владельцем кон- фетной фабрики и в полученном отчете говорится, что дневной вы- пуск за последний месяц составил 2500 упаковок, но при стандарт- ном отклонении в 2000, то вы будете знать, что производственная линия требует лучшего управления. Если ваша выборка подчиняется стандартному нормальному зако- ну распределения, то около 68% значений выборки будут находиться в рамках одного стандартного отклонения от среднего значения и около 95% будут находиться в рамках двух стандартных отклонений. Ниже приводится функция, которая вычисляет стандартное отк- лонение для заданной выборки: { вычислить стандартное отклонение } function StdDev(data: DataArray; num: integer):real; var t: integer; std, avg: real; begin avg:= mean(data, num); std := 0; for t := 1 to num do std := std+(data[t]-avg)*(data[t]-avg)); std := std/num; StdDev := sqrt(std); end; { конец функции вычисления стандартного отклонения } Работа с Турбо Паскалем #1/2 = 162 = Вывод на экран простых графиков ----------------------------------------------------------------- Применение графиков в статистике позволяет просто и точно передать смысл данных. График позволяет сразу же понять, как распределены данные и как изменяются их значения. Здесь рассмат- риваются только двумерные графики, использующие двумерную систему координат X-Y. /Получение трехмерных графиков является отдельной дисциплиной и выходит за рамки данной книги/. Имеется две распространенные формы двумерных графиков: стол- биковые диаграммы и точечные графики. В столбиковой диаграмме каждое значение представляется заштри{ованным столбиком. На то- чечном графике каждый элемент изображается точкой с координатами X и Y. Примеры графиков показаны на рис.23. │ │ │ ┌┐ │ │ ┌┐ ││ │ │ ┌┐ ││ ││ │ │ ││ ││ ┌┐ ││ │ │ ││ ││ ││ ││ │ └─┴┴─┴┴─┴┴─┴┴──── └───────────────── a б Рис.23. Примеры столбиковой диаграммы (а) и точечного графика (б) Столбиковая диаграмма обычно используется при относительно небольшом количестве данных, например, при представлении валового национального продукта за последние десять лет или ежемесячного выпуска на предприятии в процентном отношении. Точечные графики обычно используются при выводе большого числа данных, например, для вывода ежедневного курса акций некоторой фирмы в течение го- да. Применение получила также модификация точечного графика, ког- да соседние точки соединяют линией. Разработанные в этой главе графические функции требуют при- менения ПЭВМ фирмы IBM (или совместимых с ними ПЭВМ) с графичес- ким адаптером CGA или EGA. Эти подпрограммы рассчитаны на приме- нении четвертого режима вывода графиков. Графические подпрограммы используют графические функции Турбо Паскаля версии 4, которые отличаются от графических функций предыдущих версий. Если вы ис- пользуете предыдущую версию Турбо Паскаля, то вам потребуется сделать соответствующие изменения. Используются следующие графические функции: Название Назначение ---------------- ---------------------------------------------- InitGraph Инициирует графическое оборудование SetColor Устанавливает цвет рисунка для большинства Работа с Турбо Паскалем #1/2 = 163 = графических программ SetLine Определяет тип линий, выводимых посредством процедуры "Line" Line Выводит линии на экран с текущим цветом PupPixel Выводит элемент изображения в заданном цвете RestoreCrtMode Восстанавливает режим работы видеотерминала в состояние до вызова "InitGraph" OutTextXY Записывает строку в заданную позицию, нахoдясь в графическом режиме работы Эти подпрограммы используют блок "Graph". Подробное описание этих и других графических функций дается в справочном руководстве по языку Турбо Паскаль версии 4. Ниже приводится простая графическая функция, формирующая столбиковую диаграмму на ПЭВМ фирмы IBM: uses crt, graph; const MAX = 100; type DataItem = real; DataArray = array [1..MAX] of DataItem; var data: DataArray; procedure Simpleplot(data: DataArray; num: integer); var t, incr:integer; a: real; ch: char; GraphDriver, Craphmode : ineger; x, y : integer; begin { установка режима 4 для адаптеров EGA и CGA } GraphDriver := CGA ; Craphmode := CGAC1 ; InitGraph(GraphDriver, Craphmode, ''); SetColor(1); SetLineStyle(Solid, 0, NormWidth); { вычерчивание сетки } OutTextXY(0, 191, '0'); { минимум } OutTextXY(0, 0, '190'); { максимум } Работа с Турбо Паскалем #1/2 = 164 = OutTextXY(290, 191, '300'); { число } for t := 1 to 19 do PutPixel(0, t*10, 1); SetColor(3); Line(x, 190, x, 190-y); SetColor(2); for t := 1 to num do begin a := data[t]; y := trunc(a); incr := 10; x := ((t-1)*incr)+20 Line(x, 190, x, 190-y); end; ch:= ReadKey; RestoreCrtMode; end; { конец процедуры вывывода простого графика } Для ПЭВМ фирмы IBM режим с максимальной разрешающей способ- ностью в 320х200 точек устанавливается с помощью процедуры "InitGraph". Процедура "OutTextXy" устанавливает курсор в позицию с требуемыми координатами Х и Y и делает вывод заданной строки. Процедура "Line" имеет следующую общую форму: Line (начало_Х, начало_Y, конец_Х, конец_Y), где все значе- ния задаются целыми числами. При выводе строки используется теку- щий цвет, определенный при вызове процедуры "SetColor". Дополни- тельные сведения вы можете найти в справочном руководстве по языку Турбо Паскаль. В этом примере процедура вывода графика обладает серьезным недостатком. Предполагается, что все данные находятся в диапазоне от нуля до 190, поскольку только эти значения можно задавать при вызове графической функции "Line". Это предположение хорошо сра- ботает в маловероятном случае, когда ваши данные точно будут ле- жать в этом диапазоне. Для вывода данных в любом диапазоне значе- ний эти данные должны быть нормализованы перед выводом так, чтобы не выходить за допустимый диапазон значений. Нормализация заклю- чается в поиске коэффициента отношения действительного диапазона значений данных и физического диапазона разрешающей способности экрана. Значение каждого данного затем должно быть умножено на этот коэффициент и получено число, попадающее в диапазон экрана. Нормализация по оси Y должна делаться по следующей формуле: 250 Y = Y* ───────── (max-min) где Y является тем значением, которое передается процедуре вывода графика. Та же формула должна использоваться для расширения шка- лы, когда диапазон значений данных очень маленький. В таком слу- чае экран дисплея будет использоваться наиболее рационально. Функция "BarPlot" масштабирует оси Х и Y и выводит столбико- Работа с Турбо Паскалем #1/2 = 165 = вый график для 300 элементов. Предполагается, что по оси Х зада- ется время с единичным шагом. Процедура нормализации находит ми- нимальное и максимальное значение в выборке и затем вы - числяет их разницу. Это число, которое представляет разброс между мини- мальным и максимальным значениями, затем делится на разрешающую способность экрана,. Для графического режима 4 это число равно 190 для оси Y и 300 для оси Х /поскольку требуется место для гра- ничных полей и основной строки/. Полученный коэффициент затем ис- пользуется для масштабирования данных выборки. { вывод столбиковой диаграммы } procedure BarPlot(data: DataArray; num: integer); var x, y, max, min, incr, t:integer; a, norm, spread: real; ch: char; value: string[80]; begin { установка режима 4 для адаптеров EGA и CGA } GraphDriver := CGA ; Craphmode := CGAC1 ; InitGraph(GraphDriver, Craphmode, ''); SetColor(1); SetLineStyle(Solid, 0, NormWidth); { сначала для нормализации находится минимальное и максимальное значение } max := getmax(data, num) min := getmin(data, num) if min>0 then min := 0; spread := max - min; norm := 190/spread; { вычерчивание сетки } str(min, value); OutTextXY(0, 191, value); { минимум } str(max, value); OutTextXY(0, 0, value); { максимум } str(num, value); OutTextXY(300, 191, value); { число } for t := 1 to 19 do PupPixel(0, t*10, 1); SetColor(3); Line(0, 190, 320, 190); SetColor(2); { вывод данных } Работа с Турбо Паскалем #1/2 = 166 = for t := 1 to num do begin a := data[t]-min; a := a*norm; y := trunc(a); incr := 300 div num; x := ((t-1)*incr)+20 Line(x, 190, x, 190-y); end; ch := Readkey; RestoreCrtMode; end; { BarPlot } Эта версия программы кроме того делает вывод точек по оси Y. Расстояние между точками равно 1/20 разнице между максимальным и минимальным значением. На рис.24 приводится пример столбиковой диаграммы для двадцати элементов, полученной с помощью процедуры "BarPlot". Конечно, эта процедура не обладает всеми желательными свойствами, но она дает хороший вывод одной выборки. Эту процеду- ру можно легко усовершенствовать и сделать ее более удобной для конкретного случая. .95 | . | | . | | | . | | | | | . | | | | | | | . | | | | | | | . | | | | | | | | | . | | | | | | | | | . | | | | | | | | | | . | | | | | | | | | | | . | | | | | | | | | | | | | | . | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | __|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| 20 Рис 24. Пример столбиковой диаграммы, полученной с помощью процедуры "BarPlot" Для получения процедуры по выводу точечных графиков требует- ся сделать только небольшие изменения в процедуре "BarPlot" Ос- новное изменение связано с заменой функции "Line" на функцию вы- Работа с Турбо Паскалем #1/2 = 167 = вода одной точки. Для этого используется функция "PutPixel" В общем виде она записывается в следующей форме: PutPixel(x,y,цвет) где все аргументы являются целыми числами. Цвет каждой выводимой точки задается параметром "цвет". Для режима 4 он должен прини- мать значения от 0 до 3. Ниже приводится функция "ScatterPlot": { вывод точечного графика } procedure ScatterPlot(data: DataArray; num, ymin, ymax, xmax, xmin: integer); var x, y, incr, t:integer; a, norm, spread: real; ch: char; value: string[80]; begin { сначала для нормализации находится минимальное и максимальное значение } if ymin>0 then ymin := 0; spread := ymax - ymin; norm := 190/spread; { вычерчивание сетки } str(ymin, value); OutTextXY(0, 191, value); { минимум } str(ymax, value); OutTextXY(0, 0, value); { максимум } str(xmax, value); OutTextXY(300, 191, value); { число } SetColor(3); for t := 1 to 19 do PutPixel(0, t*10, 1); Line(0, 190, 320, 190); SetColor(2); { вывод данных } for t := 1 to num do begin a := data[t]-ymin; a := a*norm; y := trunc(s); incr := 300 div xmax; x := ((t-1)*incr)+20; PutPixel(x, 190-y, 2); Работа с Турбо Паскалем #1/2 = 168 = end; end; { конец процедуры вывода точечного графика} В процедуре "BarPlot" минимальное и максимальное значение вычисляется внутри процедуры. В отличие от этой процедуры в про- цедуре "ScatterPlon" не делается этих вычислений, а минимальное и максимальное значения передаются самой процедуре. Это позволяет выводить сразу несколько графиков на один экран без изменения масштаба, накладывая таким образом один график на другой. Прогнозирование и уравнение регрессии ----------------------------------------------------------------- Статистическая информация часто используется для вывода "обоснованных предположений" о будущем. Хотя каждому известно, что на основе прошлого опыта не обязательно можно предсказать бу- дущее и что каждое правило имеет исключение, все же данные о прошлом используются для этого. Очень часто тенденции, имевшие место в прошлом и настоящем, сохраняются и в будущем. В этих слу- чаях вы можете определить конкретные значения для некоторого вре- мени в будущем. Этот процесс называется прогнозированием или ана- лизом тенденций. Например, рассмотрим некое исследование продолжительности жизни за десятилетний период. Пусть получены следующие данные: Год Продолжительность жизни 1980 69 1981 70 1982 72 1983 68 1984 73 1985 71 1986 75 1987 74 1988 78 1989 77 Сначала следует понять, если здесь какая-нибудь тенденция? Если она действительно имеется, то можно узнать какой она имеет характер. И, наконец, если наблюдается действительно заметная тенденция, то можно предсказать, например, среднюю продолжитель- ность в 1995 году. Сначала рассмотрим столбиковую диаграмму и точечный график для этих данных, представленные на рис.26. Исследуя их, можно сделать вывод, что средняя продолжительность жизни в целом увели- чивается. Если приложить линейку так, чтобы наилучшим образом ли- ния соответствовала графику, и продолжить линию до 1995 года, то Работа с Турбо Паскалем #1/2 = 169 = окажется, что продолжительность жизни будет в районе 82. Однако, насколько можно быть уверенным в достоверности такого вывода? Несмотря на интуитивное ощущение правильности такого вывода вы можете захотеть использовать более формальные и точные методы по прогнозированию тенденции средней продолжительности жизни. Имея набор изменяющихся во времени данных лучше всего полу- чать прогноз путем поиска линии наилучшего соответствия по отно- шению к имеющимся данным. Именно это делалось с применением ли- нейки. Линия наилучшего соответствия располагается наиболее близко ко всем точкам и лучше всего отражает их тенденцию. Хотя некоторые или даже все данные не будут находиться на линии, сама линия хорошо представляет их. Достоверность линии зависит от бли- зости точек выборки. Линия в двумерном пространстве задается следующим основным уравнением: Y = a + bX, где Y является независимой переменной, Х является зависимой пере- менной, "а" является точкой пересечения оси Y, а "в" задает нак- лон линии. Таким образом, для определения линии наилучшего соот- ветствия выборки требуется определить "а" и "в". 78 │ . │ │ │ . │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ . │ │ │ │ │ │ │ │ │ │ a ────┴───┴───┴───┴───┴───┴───┴───┴───┴───┴──── 0 10 Рис.26. Столбиковая диаграмма /а/ для прогноза средней про- должительности жизни Для определения значений этих параметров можно использовать несколько методов, но наиболее распространенным (и как правило наилучшим) является метод наименьших квадратов. Этот метод пост- роен на минимизации расстояния от действительных значений данных до линии. Этот метод состоит из двух шагов: сначала вычисляется Работа с Турбо Паскалем #1/2 = 170 = "в" (наклон линии) и затем вычисляется "а" (пересечение оси Y). Вывод этой формулы выходит за рамки этой книги. Получив "в" вы можете, используя этот параметр, вычислить "а": Определив значения параметров "а" и "в" вы можете, задав лю- бое значение Х, найти соответствующее значение Y. Например, ис- пользуя приведенные выше данные по средней продолжительности жиз- ни, можно получить следующее уравнение регрессии: Y = 67,46 + 0,95 * X. Следовательно, для нахождения ожидаемой продолжительности жизни в 1995 году (15 лет от 1980 года) делаются следующие вычис- ления: 67,46 + 0,95*15 = 82. Однако, даже имея для данных линию наилучшего соответствия вам может потребоваться знание действительной корреляции данных с этой линии. Если линия и данные слабо коррелированы, то будет ма- ло пользы от линии регрессии. Однако, если линия хорошо соответс- твует данным, то по ней можно делать очень достоверный прогноз. Наиболее распространенным способом определения и представления корреляции данных и линии регрессии является вычисление коэффици- ентов корреляции, которые могут принимать значения от нуля до единицы. Коэффициенты корреляции по существу определяет степень близости каждой точки к линии. Если коэффициент корреляции имеет единичное значение, то данные хорошо соответствуют линии /т.е. каждый элемент выборки также находится на линии регрессии/. Если коэффициент корреляции имеет нулевое значение, то никакое значе- ние из выборки не располагается на линии. В действтительности ко- эффициент корреляции может принимать любое значение из диапазона от нуля до единицы. Коэффициент корреляции вычисляется по форму- ле, приведенной на следующей странице. Здесь М является средним значением координаты Х и М является средним значением координаты Y. Обычно в качестве сильной корре- ляции рассматривается значение 0,81. В этом случае 66% данных со- ответствует линии регрессии. Для получения процентного соотноше- ния необходимо просто возвести в квадрат значение коэффициента корреляции. Ниже приводится функция "Regress". В ней используется опи- санный выше метод поиска коэффициентов регрессии и коэффициентов корреляции: { вычисление коэффициентов регрессии и вывод линии регрессии } procedure Regress(data: DataArray; num: integer); var Работа с Турбо Паскалем #1/2 = 171 = a, b, x_avg, y_avg, temp, temp2, cor: real; data2: DataArray t, min, max: integer; ch: char; begin { поиск среднего значения Х и У } y_avg := 0; x_avg := 0; for t := 1 to num do begin y_avg := y_avg + data[t]; x_avg := x_avg + t; { поскольку Х представляет собой время } end; x_avg := x_avg/num; y_avg := y_avg/num; { поиск коэффициента 'в' уравнения регрессии } temp := 0; temp2 := 0; for t := 1 to num do begin temp := temp +(data[t] - y_avg)*(t-x_avg); temp2 := temp2 +(t - x_avg)*(t-x_avg); end; b := temp/temp2; { поиск коэффициента 'a' уравнения регрессии } a := y_avg-(b*x_avg); { вычисление коэффициента корреляции } for t := 1 to num do data2[t] := t; cor := temp/num; cor := cor/(StdDev(data, num)*StdDev(data2,num); Writeln('Уравнение регресии : Y = ', a: 15: 5, '+',b: 15: 5, '* X'); Writeln('Коэффициент корреляции : ', cor: 15:5); Writeln('Вывести данные и линию регрессии ? (y/n)'); Readln(ch); ch := upcase(ch); if ch <> 'N' then begin { установка режима 4 для адаптеров EGA и CGA } GraphDriver := CGA ; Craphmode := CGAC1 ; InitGraph(GraphDriver, Craphmode, ''); SetColor(1); SetLineStyle(Solid, 0, NormWidth); Работа с Турбо Паскалем #1/2 = 172 = { вывод графиков } for t := 1 to num*2 do data2[t] := a+(b*t); { массив регресси } min:= getmin(data, num)*2; max:= getmax(data, num)*2; ScatterPlot(data, num, min, max. num*2); ScatterPlot(data2, num*2, min, max, num*2); ch := ReadKey; RestoreCrtMode; end; end; { конец процедуры вычисления коэффициентов регрессии и корреляции } При проведении прогнозирования подобно описанному выше сле- дует помнить, что по данным о прошлом не всегда можно предсказать будущее. Однако в тех случаях, когда это можно сделать, могут по- лучить очень интересные результаты. Работа с Турбо Паскалем #1/2 = 173 = ПОЛНАЯ ПРОГРАММА ПО СТАТИСТИЧЕСКОМУ АНАЛИЗУ ----------------------------------------------------------------- К этому моменту в этой главе были разработаны несколько функций по выполнению статистических вычислений для генеральных совокупностей с одной переменной. В этом разделе эти функции бу- дут собраны в одну программу по анализу данных, выводу стол - би- ковых диаграмм , точечных графиков и прогнозирования. Перед про- ектированием такой программы необходимо определить запись для хранения переменных данных и несколько необходимых вспомогатель- ных подпрограмм. Прежде всего нам потребуется массив для хранения значений выборки. Можно использовать одномерный массив чисел с плавающей точкой 'data' с размером МАХ. Максимальное значение должно выби- раться таким, чтобы вместить максимальную выборку. В нашем случае это число равно 100. Ниже дается определение констант и типов, а также глобальных переменных: Uses Crt, Graph; const MAX = 100; type str80 = string[80]; DataItem = real; DataArray = array [1..80] of DataItem; var data: DataArray; a, m, md, std: real; num: integer; ch: char; datafile: file of DataItem; GraphDriver, Craphmode : ineger; Кроме уже разработанных статистических функций вам потребу- ется ефкже подпрограммы по сохранению и загрузке данных. Подпрог- рамма "Save" должна также сохранить число элементов данных, а подпрограмма "Load" должна считывать это число. { сохранить данные } procedure Save(data: DataArrary; num: integer): var t: integer; fname: string[80]; Работа с Турбо Паскалем #1/2 = 174 = temp: real; begin Write('Enter Filename: '); Readln(fname); Assign(datafile,fname); rewrite(datafile); temp := num; write(datafile,temp); for t := 1 to num do write(datafile,data[t]); close(datafile); end; { загрузить данные } procedure Load; var t: integer; fname: string[80]; temp: real; begin Write('Enter Filename: '); Readln(fname); Assign(datafile,fname); reset(datafile); Read(datafile,temp); num := trunc(temp); for t := 1 to num do Read(datafile,data[t]); close(datafile); end; Ниже приводится полная программа по статистическому анализу: program stats; Uses Crt, Graph; const MAX = 100; type str80 = string[80]; DataItem = real; DataArray = array [1..80] of DataItem; var data: DataArray; a, m, md, std: real; Работа с Турбо Паскалем #1/2 = 175 = num: integer; ch: char; datafile: file of DataItem; GraphDriver, Craphmode : integer; { версия быстрой сортировки для челых чисел } 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 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 oldcount then begin oldmd := md; oldcount := count; end; end; FindMode := oldmd; end; { FindMode } { поиск медианы } function median(data: DataArray; num: integer): real; var dtemp: DataArray; t: integer; begin Работа с Турбо Паскалем #1/2 = 178 = for t := 1 to num do dtemp[t] := data[t]; QuickSort(dtemp,num); median := dtemp[num div 2]; end; { median } { поиск максимального значения данных } function getmax(data: DataArray; num: integer):integer; var t: integer; max: real; begin max := data[1]; for t := 2 to num do if data[t]>max then max := data[t]; getmax := trunc(max); end; { getmax } { поиск минимального значения данных } function getmin(data: DataArray; num: integer):integer; var t: integer; min: real; begin min := data[1]; for t := 2 to num do if data[t]0 then min := 0; spread := max - min; norm := 190/spread; { вычерчивание сетки } str(min, value); OutTextXY(0, 191, value); { минимум } str(max, value); OutTextXY(0, 0, value); { максимум } str(num, value); OutTextXY(300, 191, value); { число } for t := 1 to 19 do PutPixel(0, t*10, 1); SetColor(3); Line(0, 190, 320, 190); SetColor(2); { вывод данных } for t := 1 to num do begin a := data[t]-min; a := a*norm; y := trunc(a); incr := 300 div num; x := ((t-1)*incr)+20; Line(x, 190, x, 190-y); end; ch := Readkey; RestoreCrtMode; end; { BarPlot } { вывод точечного графика } procedure ScatterPlot(data: DataArray; num, ymin, ymax, xmax: integer); var x, y, incr, t:integer; a, norm, spread: real; ch: char; value: string[80]; begin { сначала для нормализации находится минимальное и максимальное значение } if ymin>0 then ymin := 0; spread := ymax - ymin; norm := 190/spread; Работа с Турбо Паскалем #1/2 = 180 = { вычерчивание сетки } str(ymin, value); OutTextXY(0, 191, value); { минимум } str(ymax, value); OutTextXY(0, 0, value); { максимум } str(xmax, value); OutTextXY(300, 191, value); { число } SetColor(3); for t := 1 to 19 do PutPixel(0, t*10, 1); Line(0, 190, 320, 190); SetColor(2); { вывод данных } for t := 1 to num do begin a := data[t]-ymin; a := a*norm; y := trunc(a); incr := 300 div xmax; x := ((t-1)*incr)+20; Putpixel(x, 190-y, 2); end; end; { ScatterPlot } procedure Regress(data: DataArray; num: integer); var a, b, x_avg, y_avg, temp, temp2, cor: real; data2: DataArray; t, min, max: integer; ch: char; begin { поиск среднего значения Х и У } y_avg := 0; x_avg := 0; for t := 1 to num do begin y_avg := y_avg + data[t]; x_avg := x_avg + t; { поскольку Х представляет собой время } end; x_avg := x_avg/num; y_avg := y_avg/num; { поиск коэффициента 'в' уравнения регрессии } temp := 0; temp2 := 0; for t := 1 to num do begin temp := temp +(data[t] - y_avg)*(t-x_avg); Работа с Турбо Паскалем #1/2 = 181 = temp2 := temp2 +(t - x_avg)*(t-x_avg); end; b := temp/temp2; { поиск коэффициента 'a' уравнения регрессии } a := y_avg-(b*x_avg); { вычисление коэффициента корреляции } for t := 1 to num do data2[t] := t; cor := temp/num; cor := cor/(StdDev(data, num)*StdDev(data2,num)); Writeln('Уравнение регресии : Y = ', a: 15: 5, '+',b: 15: 5, '* X'); Writeln('Коэффициент корреляции : ', cor: 15:5); Writeln('Вывести данные и линию регрессии ? (y/n)'); Readln(ch); ch := upcase(ch); if ch <> 'N' then begin { установка режима 4 для адаптеров EGA и CGA } GraphDriver := CGA ; Craphmode := CGAC1 ; InitGraph(GraphDriver, Craphmode, ''); SetColor(1); SetLineStyle(Solidln, 0, NormWidth); { получение графиков } for t := 1 to num*2 do data2[t] := a+(b*t); min := getmin(data, num)*2; max := getmax(data, num)*2; ScatterPlot(data, num, min,max, num*2); ScatterPlot(data2, num*2, min,max, num*2); ch := Readkey; RestoreCrtMode; end; end; { regress } { сохранить данные } procedure Save(data: DataArray; num: integer); var t: integer; fname: string[80]; temp: real; begin Write('Enter Filename: '); Readln(fname); Assign(datafile,fname); Работа с Турбо Паскалем #1/2 = 182 = rewrite(datafile); temp := num; write(datafile,temp); for t := 1 to num do write(datafile,data[t]); close(datafile); end; { загрузить данные } procedure Load; var t: integer; fname: string[80]; temp: real; begin Write('Enter Filename: '); Readln(fname); Assign(datafile,fname); reset(datafile); Read(datafile,temp); num := trunc(temp); for t := 1 to num do Read(datafile,data[t]); close(datafile); end; { Load } begin repeat ch := upcase(menu); case ch of 'E': Enter(data); 'B': begin a := mean(data, num); m := median(data, num); std := StdDev(data,num); md := FindMode(data,num); Writeln('mean: ',a: 15: 5); Writeln('median: ',m: 15: 5); Writeln('standart deviation: ',std: 15: 5); Writeln('mode: ',md: 15: 5); Writeln; end; 'D': Display(data,num); 'P': BarPlot(data,num); 'R': Regress(data,num); 'S': Save(data,num); 'L': Load; end; until ch='Q' end. Работа с Турбо Паскалем #1/2 = 183 = Применение программы статистического анализа ----------------------------------------------------------------- Для того, чтобы показать, как можно пользоваться разработан- ной в этой главе программой по статистическому анализу, прове- демпростой анализ акций фирмы "Уидгет". Как вкладчик вы пытаетесь определить целесообразность вклада в данный момент капитала в де- ло фирмы "Уидгет" посредством покупки ее акций или продажи акций без надежд на быстрое снижение курса с возможностью их покупки по более низкой цене или вклад в другое предприятие. Ниже приводится курс акций фирмы "Уидгет" за последние 24 месяца: Месяц Курс акций /в долларах/ 1 10 2 10 3 11 4 9 5 8 6 8 7 9 8 10 9 10 10 13 11 11 12 11 13 11 14 11 15 12 16 13 17 14 18 16 19 17 20 15 21 15 22 16 23 14 24 18 Сначала следует определить задают ли эти данные какую-нибудь тенденцию. Основные статистические оценки будут следующими: - среднее значение: 12.08; - медиана: 11; - стандартное отклонение: 2.68; - мода: 11. Работа с Турбо Паскалем #1/2 = 184 = Затем получим столбиковую диаграмму для курса акций (рис. 28). График говорит о наличии тенденции, однако следует провести регрессионный анализ. Уравнение регрессии будет следующим: Y = 7.90 + 0.33*X .17 . | . | | | | . | | | | | | . | | | | | | | | | . | | | | | | | | | | . | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | . | | | | | | | | | | | | | | | | | | | | | | | __|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|__ 24 Рис. 28. График курса акций фирмы "Уидгет" за последние 24 ме- сяца. Коэффициент корреляции будет равен 0,85, что соответствует 74%. Это значение является достаточно хорошим, свидетельствующим о наличии заметной тенденции. Очевиден рост курса акций. Такой результат заставит вкладчика отбросить подозрения и приобрести как можно скорее 1000 акций. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ ----------------------------------------------------------------- Правильное применение результатов статистического анализа требует общего понимания метода получения результатов и их смыс- ла. Как в примере с фирмой "Уидгет" легко можно позабыть, что прошлые события не могут учесть обстоятельств, способных сущест- венно повлиять на окончательный результат. Слепое применение ста- тистических оценок в некоторых случаях может дать очень неприят- ные результаты. Следует помнить, что статистика является Работа с Турбо Паскалем #1/2 = 185 = отражением реальности, но нельзя считать, что реальность является отражением статистики.