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

 

Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская записьСтруктуры данных

"Алгоритмы + структуры данных = программы". Это - название книги Никлауса Вирта, знаменитого швейцарского специалиста по программированию, автора языков Паскаль, Модула-2, Оберон. С именем Вирта связано развитие структурного подхода к программированию. Н.Вирт известен также как блестящий педагог и автор классических учебников.
Обе составляющие программы, выделенные Н.Виртом, в равной степени важны. Не только несовершенный алгоритм, но и неудачная организация работы с данными может привести к замедлению работы программы в десятки, а иногда и в миллионы раз. С другой стороны, владение теорией прораммирования и умение системтически применять ее на практике позволяет быстро разрабатывать эффективные и в то же время эстетически красивые программы.
Общее понятие структуры данных
Структура данных — это исполнитель, который организует работу с данными, включая их хранение, добавление и удаление, модификацию, поиск и т.д. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку. При описании структуры данных нужно перечислить набор действий, которые возможны для нее, и четко описать результат каждого действия. Будем называть такие действия предписаниями. С программной точки зрения, системе предписаний структуры данных соответствует набор функций, которые работают над общими переменными.
Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс, сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java.
Тем не менее, структуры данных столь же успешно можно реализовывать и в традиционных языках программирования, таких как Фортран или Си. При этом следует придерживаться объектно-ориентированного стиля программирования: четко выделить набор функций, которые осуществляют работу со структурой данных, и ограничить доступ к данным только этим набором функций. Сами данные реализуются как статические (не глобальные) переменные. При программировании на языке Си структуре данных соответствуют два файла с исходными текстами:

  1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;
  2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных

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

http://localhost:3232/img/empty.gifМассив как базовая структура

Оперативная память с точки зрения программиста — это массив элементов. Любой элемент массива можно прочитать или записать сразу, за одно элементарное действие. Массив можно рассматривать как простейшую структуру данных. Структуры данных, в которых возможен непосредственный доступ к произвольным их элементам, называют структурами данных с прямым, или с произвольным доступом (по-английски random access). Наряду с массивом, структурой данных с прямым доступом является множество, которое будет рассмотрено ниже. В других структурах данных непосредственный доступ возможен лишь к одному или нескольким элементам, для доступа к остальным элементам надо выполнить дополнительные действия. Такие структуры данных называются структурами последовательного доступа. Примером структуры последовательного доступа является магнитофон, на которым записаны песни. В любой момент можно прослушать лишь очередную песню. Чтобы добраться до других музыкальных фрагментов, надо перемотать ленту вперед или назад. Кстати, такие магнитофоны, или накопители на магнитной ленте, очень долго использовались на ЭВМ, хотя сейчас уступили свое место более надежным и компактным системам (съемным магнитным и оптическим дискам, флэш-памяти и т.п.). Устройство компьютерного магнитофона было аналогично устройству обычного бытового магнитофона.
С логической точки зрения, массивом является также важнейшая составляющая компьютера — магнитный диск. Элементарной единицей чтения и записи для магнитного диска служит блок. Размер блока зависит от конструкции конкретного диска, обычно он кратен 512. За одну элементарную операцию можно прочесть или записать один блок с заданным адресом.
Итак, наиболее важные запоминающие устройства компьютера — оперативная память и магнитный диск — представляют собой массивы. Массив как бы дан программисту свыше, так же как математику целые числа. Работа с элементами массива осуществляется исключительно быстро, все элементы массива доступны без всяких предварительных действий.
Тем не менее массивов недостаточно для написания эффективных программ. Например, поиск элемента в массиве, если его элементы не упорядочены, невозможно реализовать эффективно: нельзя изобрести ничего лучшего, кроме последовательного перебора элементов. В случае упорядоченного хранения элементов можно использовать эффективный бинарный поиск, но затруднения возникают при добавлении или удалении элементов в середине массива и приводят к массовым операциям, т.е. операциям, время выполнения которых зависит от числа элементов структуры. От этих недостатков удается избавиться, реализуя множество элементов на базе сбалансированных деревьев или хеш-функции.
Есть и другие причины, по которым необходимо использовать более сложные, чем массивы, структуры данных. Логика многих задач требует организации определенного порядка доступа к данным. Например, в случае очереди элементы можно добавлять только в конец, а забирать только из начала очереди; в стеке доступны лишь элементы в вершине стека, в списке — элементы до и за указателем.
Наконец, массив имеет ограниченный размер. Увеличение размера массива в случае необходимости приводит к переписыванию его содержимого в захваченную область памяти большего размера, т.е. опять же к массовой операции. От этого недостатка свободны ссылочные реализации структур данных: реализации на основе линейных списков или на основе деревьев.

Реализация одних структур на базе других

Реализация структуры данных на основе базовой структуры — это описание ее работы в терминах базовой структуры. При этом считается, что базовая структура либо дана изначально, либо уже кем-то реализована. Реализация должна включать в себя описание идеи реализации (каким образом элементы реализуемой структуры хранятся в базовой структуре, какие дополнительные переменные используются) и набор подпрограмм, каждая из которых моделирует некоторое предписание реализуемой структуры при помощи предписаний базовой структуры.
При рассмотрении любой структуры данных необходимо сначала описать ее с логической точки зрения, а затем рассмотреть различные способы ее реализации. В качестве базы реализации в большинстве случаев выступает либо массив, либо динамическая память (т.е. память, в которой можно захватывать участки требуемого размера и освобождать ранее захваченные участки, когда они уже больше не нужны; см. раздел 3.7.3).

Простейшие структуры данных. Стек. Очередь

Наиболее важными из простейших структур данных являются стек и очередь. Эти структуры встречаются в программировании буквально на каждом шагу, в самых разнообразных ситуациях. Особенно интересен стек, который имеет самые неожиданные применения. В свое время при разработке серии ЭВМ IBM 360 в начале 70-х годов XX века фирма IBM совершила драматическую ошибку, не предусмотрев аппаратную реализацию стека. Эта серия содержала много других неудачных решений, но, к сожалению, была скопирована в Советском Союзе под названием ЕС ЭВМ (Единая Серия), а все собственные разработки были приостановлены. Это отбросило советскую промышленность на много лет назад в области разработки копьютеров.

Очередь

Очередь как структура данных понятна даже людям, не знакомым с программированием. Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.
Очередь можно представить в виде трубки. В один конец трубки можно добавлять шарики — элементы очереди, из другого конца они извлекаются. Элементы в середине очереди, т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются шарики, соответствует концу очереди, конец, из которого они извлекаются — началу очереди. Таким образом, концы трубки не симметричны, шарики внутри трубки движутся только в одном направлении.
В принципе, можно было бы разрешить добавлять элементы в оба конца очереди и забирать их также из обоих концов. Такая структура данных в программировании тоже существует, ее название — "дек", от англ. Double Ended Queue, т.е. очередь с двумя концами. Дек применяется значительно реже, чем очередь.
Использование очереди в программировании почти соответствует ее роли в обычной жизни. Очередь практически всегда связана с обслуживанием запросов, в тех случаях, когда они не могут быть выполнены мгновенно. Очередь поддерживает также порядок обслуживания запросов. Рассмотрим, к примеру, что происходит, когда человек нажимает клавишу на клавиатуре компьютера. Тем самым человек просит компьютер выполнить некоторое действие. Например, если он просто печатает текст, то действие должно состоять в добавлении к тесту одного символа и может сопровождаться перерисовкой области экрана, прокруткой окна, переформатированием абзаца и т.п.
Любая, даже самая простая, операционная система всегда в той или иной степени многозадачна. Это значит, что в момент нажатия клавиши операционная система может быть занята какой-либо другой работой. Тем не менее, операционная система ни в какой ситуации не имеет права проигноровать нажатие на клавишу. Поэтому происходит прерывание работы компьютера, он запоминает свое состояние и переключается на обработку нажатия на клавишу. Такая обработка должна быть очень короткой, чтобы не нарушить выполнение других задач. Команда, отдаваемая нажатием на клавишу, просто добавляется в конец очереди запросов, ждущих своего выполнения. После этого прерывание заканчивается, компьютер восстанавливает свое состояние и продолжает работу, которая была прервана нажатием на клавишу. Запрос, поставленный в очередь, будет выполнен не сразу, а только когда наступит его черед.
В системе Windows работа оконных приложений основана на сообщениях, которые посылаются этим приложениям. Например, бывают сообщения о нажатии на клавишу мыши, о закрытии окна, о необходимости перерисовки области окна, о выборе пункта меню и т.п. Каждая программа имеет очередь запросов. Когда программа получает свой квант времени на выполнение, она выбирает очередной запрос из начала очереди и выполняет его. Таким образом, работа оконного приложения состоит, упрощенно говоря, в последовательном выполнении запросов из ее очереди. Очередь поддерживается операционной системой.
Подход к программированию, состоящий не в прямом вызове процедур, а в посылке сообщений, которые ставятся в очередь запросов, имеет много преимуществ и является одной из черт объектно-ориентированного программирования. Так, например, если оконной программе необходимо завершить работу по какой-либо причине, лучше не вызывать сразу команду завершения, которая опасна, потому что нарушает логику работы и может привести к потере данных. Вместо этого программа посылает самой себе сообщение о необходимости завершения работы, которое будет поставлено в очередь запросов и выполнено после запросов, поступивших ранее.

Реализация очереди на базе массива

Как уже было сказано, программисту массив дан свыше, все остальные структуры данных нужно реализовывать на его основе. Конечно, такая реализация может быть многоэтапной, и не всегда массив выступает в качестве непосредственной базы реализации. В случае очереди наиболее популярны две реализации: непрерывная на базе массива, которую называют также реализацией на базе кольцевого буфера, и ссылочная реализация, или реализация на базе списка. Ссылочные реализации будут рассмотрены ниже.
При непрерывной реализации очереди в качестве базы выступает массив фиксированной длины N, таким образом, очередь ограничена и не может содержать более N элементов. Индексы элементов массива изменяются в пределах от 0 до N - 1. Кроме массива, реализация очереди хранит три простые переменные: индекс начала очереди, индекс конца очереди, число элементов очереди. Элементы очереди содержатся в отрезке массива от индекса начала до индекса конца.
При добавлении нового элемента в конец очереди индекс конца сперва увеличивается на единицу, затем новый элемент записывается в ячейку массива с этим индексом. Аналогично, при извлечении элемента из начала очереди содержимое ячейки массива с индексом начала очереди запоминается в качестве результата операции, затем индекс начала очереди увеличивается на единицу. Как индекс начала очереди, так и индекс конца при работе двигаются слева направо. Что поисходит, когда индекс конца очереди достигает конца массива, т.е. N - 1?
Ключевая идея реализации очереди состоит в том, что массов мысленно как бы зацикливается в кольцо. Считается, что за последним элементом массива следует его первый элемент (напомним, что последний элемент имеет индекс N - 1, а первый — индекс 0). При сдвиге индекса конца очереди вправо в случае, когда он указывает на последний элемент массива, он переходит на первый элемент. Таким образом, непрерывный отрезок массива, занимаемый элементами очереди, может переходить через конец массива на его начало.

Стек

Стек — самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается FIFO, что означает первым пришел — первым уйдешь (First In First Out). Дисциплина работы стека обозначается LIFO, последним пришел — первым уйдешь (Last In First Out).
Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop ("выстреливают").
Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя тарелка, т.е. тарелка на вершине стека. Хорошим примером будет также служить железнодорожный тупик, в который можно составлять вагоны.

Использование стека в программировании

Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и копьютер продолжает прерванную работу.
Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C, и нужно будет сохранить состояние задачи B, прежде чем перейти к C. Позже, по окончании C будет сперва восстановлено состояние задачи B, затем, по окончании B, — состояние задачи A. Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.
Стек позволяет организовать рекурсию, т.е. обращение подпрограммы к самой себе либо непосредственно, либо через цепочку других вызовов. Пусть, например, подпрограмма A выполняет алгоритм, зависящий от входного параметра X и, возможно, от состояния глобальных данных. Для самых простых значений X алгоритм реализуется непосредственно. В случае более сложных значений X алгоритм реализуется как сведение к применению того же алгоритма для более простых значений X. При этом подпрограмма A обращается сама к себе, передавая в качестве параметра более простое значение X. При таком обращении предыдущее значение параметра X, а также все локальные переменные подпрограммы A сохраняются в стеке. Далее создается новый набор локальных переменных и переменная, содержащая новое (более простое) значение параметра X. Вызванная подпрограмма A работает с новым набором переменных, не разрушая предыдущего набора. По окончании вызова старый набор локальных переменных и старое состояние входного параметра X восстанавливаются из стека, и подпрограмма продолжает работу с того места, где она была прервана.
На самом деле даже не приходится специальным образом сохранять значения локальных переменных подпрограммы в стеке. Дело в том, что локальные переменные подпрограммы (т.е. ее внутренние, рабочие переменные, которые создаются в начале ее выполнения и уничтожаются в конце) размещаются в стеке, реализованном аппаратно на базе обычной оперативной памяти. В самом начале работы подпрограмма захватывает место в стеке под свои локальные переменные, этот участок памяти в аппаратном стеке называют обычно блок локальных переменных или по-английски frame ( "кадр "). В момент окончания работы подпрограмма освобождает память, удаляя из стека блок своих локальных переменных.
Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при вызовах подпрограмм. Пусть в некоторой точке программы A вызывается подпрограмма B. Перед вызовом подпрограммы B адрес инструкции, следующей за инструкцией вызова B, сохраняется в стеке. Это так называемый адрес возврата в программу A. По окончании работы подпрограмма B извлекает из стека адрес возврата в программу A и возвращает управление по этому адресу. Таким образом, компьютер продолжает выполнение программы A, начиная с инструкции, следующей за инструкцией вызова. В большинстве процессоров имеются специальные команды, поддерживающие вызов подпрограммы с предварительным помещением адреса возврата в стек и возврат из подпрограммы по адресу, извлекаемому из стека. Обычно команда вызова назывется call, команда возврата — return.
В стек помещаются также параметры подпрограммы или функции перед ее вызовом. Порядок их помещения в стек зависит от соглашений, принятых в языках высокого уровня. Так, в языке Си или C++ на вершине стека лежит первый аргумент функции, под ним второй и так далее. В Паскале все наоборот, на вершине стека лежит последний аргумент функции. (Поэтому, кстати, в Си возможны функции с переменным числом аргументов, такие, как printf, а в Паскале нет.)
В Фортране-4, одном из самых старых и самых удачных языков программирования, аргументы передаются через специальную область памяти, которая может располагаться не в стеке, поскольку до конца 70-х годов XX века еще существовали компьютеры вроде IBM 360 или ЕС ЭВМ без аппаратной реализации стека. Адреса возврата также сохранялись не в стеке, а в фиксированных для каждой подпрограммы ячейках памяти. Программисты называют такую память статической в том смысле, что статические переменные занимают всегда одно и то же место в памяти в любой момент работы программы. При использовании только статической памяти рекурсия невозможна, поскольку при новом вызове предыдущие значения локальных переменных разрушаются. В эталонном Фортране-4 использовались только статические переменные, а рекурсия была запрещена. До сих пор язык Фортран широко используется в научных и инженерных расчетах, однако, современный стандарт Фортрана-90 уже вводит стековую память, устраняя недостатки ранних версий языка.

Реализация стека на базе массива

Реализация стека на базе массива является классикой программирования. Иногда даже само понятие стека не вполне корректно отождествляется с этой реализацией.
Базой реализации является массив размера N, таким образом, реализуется стек ограниченного размера, максимальная глубина которого не может превышать N. Индексы ячеек массива изменяются от 0 до N - 1. Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индекс элемента на вершине стека хранится в специальной переменной, которую обычно называют указателем стека (по-английски Stack Pointer или просто SP).
Когда стек пуст, указатель стека содержит значение минус единица. При добавлении элемента указатель стека сначала увеличивается на единицу, затем в ячейку массива с индексом, содержащимся в указателе стека, записывается добавляемый элемент. При извлечении элемента из стека сперва содержимое ячейки массива с индексом, содержащимся в указателе стека, запоминается во временной переменной в качестве результата операции, затем указатель стека уменьшается на единицу.
В приведенной реализации стек растет в сторону увеличения индексов ячеек массива. Часто используется другой вариант реализации стека на базе вектора, когда дно стека помещается в последнюю ячейку массива, т.е. в ячейку с индексом N - 1. Элементы стека занимают непрерывный отрезок массива, начиная с ячейки, индекс которой хранится в указателе стека, и заканчивая последней ячейкой массива. В этом варианте стек растет в сторону уменьшения индексов. Если стек пуст, то указатель стека содержит значение N (которое на единицу больше, чем индекс последней ячейки массива).

Реализация стека на языке Си

Реализуем стек вещественных чисел. Ниже мы используем эту реализацию как составную часть проекта Стековый калькулятор (см. раздел 4.4.2).
Реализация включает два файла: "streal.h", в котором описывается интерфейс исполнителя "Стек", и "streal.cpp", реализующий функции работы со стеком. Слово real обозначает вещественное число.
Используется первый вариант реализации стека на базе массива, описанный в предыдущем разделе: стек растет в сторону увеличения индексов массива. Пространство под массив элементов стека захватывается в динамической памяти в момент инициализации стека. Функции инициализации st_init передается размер массива, т.е. максимально возможное число элементов в стеке. Для завершения работы стека нужно вызвать функцию st_terminate, которая освобождает захваченную в st_init память. Ниже приведено содержимое файла "streal.h", описывающего интерфейс стека.

// Файл "streal.h"
// Стек вещественных чисел, интерфейс
//
#ifndef ST_REAL_H
#define ST_REAL_H
 
// Прототипы функций, реализующих предписания стека:
 
void st_init(int maxSize); // Начать работу (вх: цел 
                           //     макс. размер стека)
void st_terminate();    // Закончить работу
void st_push(double x); // Добавить эл-т (вх: вещ x)
double st_pop();        // Взять элемент: вещ 
double st_top();        // Вершина стека: вещ 
int st_size();          // Текущий размер стека: цел
bool st_empty();        // Стек пуст? : лог 
int st_maxSize();       // Макс. размер стека: цел
bool st_freeSpace();    // Есть свободное место? : лог
void st_clear();        // Удалить все элементы
double st_elementAt(int i); // Элемент стека на 
                            //   глубине (вх: i): вещ 
#endif
// Конец файла "streal.h"

Отметим, что директивы условной трансляции

#ifndef ST_REAL_H
#define ST_REAL_H
. . .
#endif

используются для предотвращения повторного включения h-файла: при первом включении файла определяется переменная препроцессора ST_REAL_H, а директива "#ifndef ST_REAL_H" подключает текст, только если эта переменная не определена. Такой трюк используется практически во всех h-файлах. Нужен он потому, что одни h-файлы могут подключать другие, и без этого механизма избежать повторного включения одного и того же файла трудно.
Файл "streal.cpp" описывает общие статические переменные, над которыми работают функции, соответствующие предписаниям стека, и реализует эти функции.

// Файл "streal.cpp"
// Стек вещественных чисел, реализация
//
#include <stdlib.h>
#include <assert.h>
#include "streal.h" // Подключить описания функций стека
 
// Общие переменные для функций, реализующих
// предписания стека:
static double *elements = 0; // Указатель на массив эл-тов
                             //     стека в дин. памяти
static int max_size = 0;     // Размер массива
static int sp = (-1);        // Индекс вершины стека
 
// Предписания стека:
 
void st_init(int maxSize) { // Начать работу (вх:
                            //     макс. размер стека)
    assert(elements == 0);
    max_size = maxSize;
    elements = (double *) malloc(
        max_size * sizeof(double)
    );
    sp = (-1);
}
 
void st_terminate() { // Закончить работу 
    if (elements != 0) {
        free(elements);
    }
}
 
void st_push(double x) { // Добавить эл-т (вх: вещ x)
    assert(              // утв:
        elements != 0 && //   стек начал работу и
        sp < max_size-1  //   есть своб. место
    );
    ++sp;
    elements[sp] = x;
}
 
double st_pop() { // Взять элемент: вещ 
    assert(sp >= 0); // утв: стек не пуст
    --sp;            // элемент удаляется из стека
    return elements[sp + 1];
}
 
double st_top() { // Вершина стека: вещ 
    assert(sp >= 0); // утв: стек не пуст
    return elements[sp];
}
 
int st_size() { // Текущий размер стека: цел 
    return (sp + 1);
}
 
bool st_empty() { // Стек пуст? : лог 
    return (sp < 0);
}
 
int st_maxSize() { // Макс. размер стека: цел 
    return max_size;
}
 
bool st_freeSpace() { // Есть своб. место? : лог 
    return (sp < max_size - 1);
}
 
void st_clear() { // Удалить все элементы 
    sp = (-1);
}
 
double st_elementAt(int i) { // Элемент стека на 
                             //   глубине (вх: i): вещ
    assert(                     // утв:
        elements != 0 &&        // стек начал работу и 
        0 <= i && i < st_size() // 0 <= i < размер стека 
    );
    return elements[sp - i];
}
// Конец файла "streal.cpp"
 
http://localhost:3232/img/empty.gifИспользование функции assert для проверки утверждений и ситуация отказ

В реализации стека на Си неоднократно использовалась функция assert, в переводе с английского "утверждение". Фактическим аргументом функции является логическое выражение. Если оно истинно, то ничего не происходит; если ложно, то программа завершается аварийно, выдавая диагностику ошибки.
Функция assert является реализацией конструкции "утверждение", использование которой преследует две цели:

  1. программист в процессе написания программы может явно сформулировать утверждение, которое, по его мнению, должно выполняться в данной точке программы. В этом случае конструкция "утверждение" выполняет роль комментария, облегчая создание и понимание программы;
  2. компьютер при выполнении программы проверяет все явно сформулированные утверждения. Истинность утверждения соответствует предположениям программиста, сделанным в процессе написания программы, поэтому выполнение программы продолжается. Ложность утверждения свидетельствует об ошибке программиста. При этом выдается сообщение об ошибке и выполнение программы немедленно прекращается. Таким образом, конструкция "утверждение " позволяет компьютеру проверять корректность программы непосредственно в процессе ее выполнения.

Ситуация, когда программа аварийно завершается из-за того, что утверждение не выполняется, называется отказом.
Многие предписания структуры данных выполнимы не во всех ситуациях. Например, элемент можно взять из стека только в случае, когда стек не пуст. Поэтому перед началом выполнения предписания "Взять элемент" проверяется условие "стек не пуст":

double st_pop() { // Взять элемент: вещ 
    assert(sp >= 0); // утв: стек не пуст
    . . .

Если это утверждение ложно, то возникает ситуация "отказ ": компьютер завершает работу, выдавая диагностику ошибки. Невыполнение утверждения всегда свидетельствует об ошибке программиста: программа должна быть написана таким образом, чтобы некорректные исходные данные не приводили к отказу.
Использование конструкции "утверждение " — мощное средство отладки программы. Важность ситуации "отказ " была осознана в процессе эволюции программирования далеко не сразу. На заре развития программирования на первом плане были требования эффективности программы — ее компактности и быстродействия. И лишь по мере проникновения компьютеров во все области жизни на первый план выступила надежность программы. В современном мире от надежности программы во многих случаях зависит человеческая жизнь, поэтому любые способы повышения надежности очень важны.
Почему в случае невыполнения утверждения возникает ситуация "отказ"? Альтернативой могло бы быть игнорирование некорректной ситуации и то или иное продолжение программы: например, при попытке извлечения элемента из пустого стека выдавался бы ноль. На самом деле это худшее решение из всех, которые только можно придумать! Любую ошибку надо диагностировать и исправлять как можно раньше, а имитация полезной деятельности в некорректной ситуации крайне опасна. Это может привести, например, к тому, что программа, управляющая посадкой самолетов, будет успешно сажать в среднем 999 самолетов из 1000, а каждый тысячный будет разбиваться.
Практическая рекомендация: используйте конструкцию "утверждение" как можно чаще. Если при разработке программы вы считаете, что в данной точке должно выполняться некоторое утверждение, сформулируйте его явно, чтобы компьютер при выполнении программы мог бы его проверить. Таким способом находится и исправляется львиная доля ошибок.
При частом использовании конструкции "утверждение" возникает проблема с уменьшением скорости выполнения программы. Она решена в языках Си и C++ следующим образом: на самом деле конструкция assert в Си — это не функция, а макроопределение, которое обрабатывается препроцессором. Текст Си-программы может транслироваться в двух режимах: отладочном и нормальном. В нормальном режиме в соответствии со стандартом ANSI определена переменная NDEBUG препроцессора. Для определения макрокоманды assert используется условная трансляция: если переменная NDEBUG определена, то assert определяется как пустое выражение; если нет, то assert определяется как проверка условия и вызов функции _assert (к имени добавлен символ подчеркивания) в случае, когда условие ложно. Функция _assert печатает диагностику ошибки и завершает выполнение программы, т.е. реализует ситуацию "отказ".
Таким образом, условие реально проверяется лишь при трансляции программы в отладочном режиме. Благодаря этому быстродействие программы не снижается, однако, в нормальном режиме условие не проверяется. Примерно как при обучении плаванию: в бассейне человек надевает спасательный круг, но снимает его, когда начинает плавать в океане.

Стековый калькулятор и обратная польская запись формулы

В 1920 г. польский математик Ян Лукашевич предложил способ записи арифметических формул, не использующий скобок. В привычной нам записи знак операции записывается между аргументами, например, сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польской записью.
В польской записи скобки не нужны. Например, выражение

(2+3)*(15-7)

записывается в прямой польской записи как

* + 2 3 - 15 7,

в обратной польской записи — как

2 3 + 15 7 - *.

Если прямая польская запись не получила большого распространения, то обратная оказалась чрезвычайно полезной. Неформально преимущество обратной записи перед прямой польской записью или обычной записью можно объяснить тем, что гораздо удобнее выполнять некоторое действие, когда объекты, над которыми оно должно быть совершено, уже даны.
Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек как запоминающее устройство для хранения промежуточных результатов. Такой стековый калькулятор был впервые выпущен фирмой Hewlett Packard. Обычные модели калькуляторов не позволяют вычислять сложные формулы без использования бумаги и ручки для записи промежуточных результатов. В некоторых моделях есть скобки с одним или двумя уровнями вложенности, но более сложные выражения вычислять невозможно. Также в обычных калькуляторах трудно понять, как результат и аргументы перемещаются в процессе ввода и вычисления между регистрами калькулятора. Калькулятор обычно имеет регистры X, Y и регистр памяти, промежуточные результаты каким-то образом перемещаются по регистрам, каким именно — запомнить невозможно.
В отличие от других калькуляторов, устройство стекового калькулятора вполне понятно и легко запоминается. Калькулятор имеет память в виде стека. При вводе числа оно просто добавляется в стек. При нажатии на клавишу операции, например, на клавишу +, аргументы операции сначала извлекаются из стека, затем с ними выполняется операция, наконец, результат операции помещается обратно в стек. Таким образом, при выполнении операции с двумя аргументами, например, сложения, в стеке должно быть не менее двух чисел. Аргументы удаляются из стека и на их место кладется результат, то есть при выполнении сложения глубина стека уменьшается на единицу. Вершина стека всегда содержит результат последней операции и высвечивается на дисплее калькулятора.
Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при некотором навыке это легко сделать в уме). В приведенном выше примере выражение (2+3)*(15-7) преобразуется к

2 3 + 15 7 - *

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

2 3 + 15 7 - *

Стек вначале пуст. Последовательно добавляем числа 2 и 3 в стек.

|   | вводим число 2 http://localhost:3232/img/symbols/srarr.gif | 2 | вводим число 3 http://localhost:3232/img/symbols/srarr.gif | 3 |
                                                | 2 | 

Далее читаем символ + и нажимаем на клавишу + калькулятора. Числа 2 и 3 извлекаются из стека, складываются, и результат помещается обратно в стек.

| 3 | выполняем сложение http://localhost:3232/img/symbols/srarr.gif | 5 |
| 2 | 

Далее, в стек добавляются числа 15 и 7.

| 5 | вводим число 15 http://localhost:3232/img/symbols/srarr.gif | 15 | вводим число 7 | 7  |
                         | 5  |                | 15 |
                                               | 5  |

Читаем символ - и нажимаем на клавишу - калькулятора. Со стека при этом снимаются два верхних числа 7 и 15 и выполняется операция вычитания. Причем уменьшаемым является то число, которое было введено раньше, а вычитаемым — число, введенное позже. Иначе говоря, при выполнении некоммутативных операций, таких как вычитание или деление, правым аргументом является число на вершине стека, левым — число, находящееся под вершиной стека.

| 7  | выполняем вычитание http://localhost:3232/img/symbols/srarr.gif | 8 |
| 15 |                        | 5 |
| 5  |

Наконец, читаем символ * и нажимаем на клавишу * калькулятора. Калькулятор выполняет умножение, со стека снимаются два числа, перемножаются, результат помещается обратно в стек.

| 8 | выполняем умножение http://localhost:3232/img/symbols/srarr.gif | 40 |
| 5 |

Число 40 является результатом вычисления выражения. Оно находится на вершине стека и высвечивается на дисплее стекового калькулятора.

http://localhost:3232/img/empty.gifРеализация стекового калькулятора на Си

Рассмотрим небольшой проект, реализующий стековый калькулятор на Си. Такая программа весьма полезна, поскольку позволяет проводить вычисления, не прибегая к записи промежуточных результатов на бумаге.
Программа состоит из трех файлов: "streal.h", "streal.cpp" и "stcalc.cpp". Первые два файла реализуют стек вещественных чисел, эта реализация уже рассматривалась ранее. Файл "stcalc.cpp" реализует стековый калькулятор на базе стека. Для сборки программы следует объединить все три файла в один проект. Команды построения программы зависят от операционной системы и компилятора, например, в системе Unix с компилятором "gcc" программу можно собрать с помощью команды

g++ -o stcalc -lm stcalc.cpp streal.cpp

в результате которой создается файл "stcalc" с программой, готовой к выполнению.
Ниже приведено содержимое файла "stcalc.cpp". Функция main, описанная в этом файле, организует диалог с пользователем в режиме команда-ответ. Пользователь может ввести число с клавиатуры, это число просто добавляется в стек. При вводе одного из четырех знаков арифметических операций +, -, *, / программа извлекает из стека два числа, выполняет указанное арифметическое действие над ними и помещает результат обратно в стек. Значение результата отображается также на дисплее. Кроме арифметических операций, пользователь может ввести название одной из стандартных функций: sin, cos, exp, log (натуральный логарифм). При этом программа извлекает из стека аргумент функции, вычисляет значение функции и помещает его обратно в стек. При желании список стандартных функций и возможных операций можно расширить. Наконец, можно выполнять еще несколько команд:


pop

удалить вершину стека;

clear

очистить стек;

=

напечатать вершину стека;

show

напечатать содержимое стека;

help

напечатать подсказку;

quit

завершить работу программы.

Каждая команда стекового калькулятора реализуется с помощью отдельной функции. Например, вычитание реализуется с помощью функции onSub():

static void onSub() {
    double y, x;
    if (st_size() < 2) {
        printf("Stack depth < 2.\n");
        return;
    }
    y = st_pop();
    x = st_pop();
    st_push(x - y);
    display();
}

В начале функции проверяется, что глубина стека не меньше двух. В противном случае, выдается сообщение об ошибке, и функция завершается. Далее из стека извлекаются операнды y и x операции вычитания. Элементы извлекаются из стека в порядке, обратном их помещению в стек, поэтому y извлекается раньше, чем x. Затем вычисляется разность y - x, ее значение помещается обратно в стек и печатается на дисплее, для печати вершины стека вызывается функция display.
Приведем полный текст программы.

// Файл "stcalc.cpp"
// Реализация стекового калькулятора на базе стека
//
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include "streal.h" // Интерфейс исполнителя "стек"
 
// Прототипы функций, реализующих команды калькулятора:
// Арифметические операции
static void onAdd();
static void onSub();
static void onMul();
static void onDiv();
 
// Добавить число в стек(вх: текстовая запись числа)
static void onPush(const char* line);
 
// Вычисление математических функций
static void onSin();     // sin
static void onCos();     // cos
static void onExp();     // Экспонента 
static void onLog();     // Натуральный логарифм 
static void onSqrt();    // Квадратный корень 
 
// Другие команды
static void onPop();     // Удалить вершину стека
static void onClear();   // Очистить стек
static void display();   // Напечатать вершину стека
static void onShow();    // Напечатать содержимое стека
static void printHelp(); // Напечатать подсказку 
 
int main() {
    char line[256]; // Буфер для ввода строки
    int linelen;    // Длина строки
 
    st_init(1024);  // Стек.начать работу(1024)
                    //   1024 — макс. глубина стека
    printHelp();    // Напечатать подсказку
 
    while (true) {          // Цикл до бесконечности
        scanf("%s", line);      // ввести строку
        linelen = strlen(line); // длина строки 
        if (linelen == 0)
            continue;
 
        // Разобрать команду и вызвать реализующую
        // ее функцию 
        if (strcmp(line, "+") == 0) {
            onAdd();
        } else if (strcmp(line, "-") == 0) {
            onSub();
        } else if (strcmp(line, "*") == 0) {
            onMul();
        } else if (strcmp(line, "/") == 0) {
            onDiv();
        } else if (strcmp(line, "sin") == 0) {
            onSin();
        } else if (strcmp(line, "cos") == 0) {
            onCos();
        } else if (strcmp(line, "exp") == 0) {
            onExp();
        } else if (strcmp(line, "log") == 0) {
            onLog();
        } else if (strcmp(line, "sqrt") == 0) {
            onSqrt();
        } else if (strcmp(line, "=") == 0) {
            display();
        } else if (         // Если это число 
            isdigit(line[0]) || (
                linelen > 1 &&
                (line[0] == '-' || line[0] == '+') &&
                isdigit(line[1])
            )
        ) {
            onPush(line);   // Добавить число в стек
        } else if (strcmp(line, "pop") == 0) {
            onPop();
        } else if (strcmp(line, "clear") == 0) {
            onClear();
        } else if (strcmp(line, "show") == 0) {
            onShow();
        } else if (strcmp(line, "quit") == 0) {
            break;       // Завершить работу
        } else {         // Неправильная команда =>
            printHelp(); //     напечатать подсказку
        }
    }
    return 0;
}
 
static void onAdd() {
    double y, x;
    if (st_size() < 2) {
        printf("Stack depth < 2.\n");
        return;
    }
    y = st_pop();
    x = st_pop();
    st_push(x + y);
    display();
}
 
static void onSub() {
    double y, x;
    if (st_size() < 2) {
        printf("Stack depth < 2.\n");
        return;
    }
    y = st_pop();
    x = st_pop();
    st_push(x - y);
    display();
}
 
static void onMul() {
    double y, x;
    if (st_size() < 2) {
        printf("Stack depth < 2.\n");
        return;
    }
    y = st_pop();
    x = st_pop();
    st_push(x * y);
    display();
}
 
static void onDiv() {
    double y, x;
    if (st_size() < 2) {
        printf("Stack depth < 2.\n");
        return;
    }
    y = st_pop();
    x = st_pop();
    st_push(x / y);
    display();
}
 
static void onPush(const char* line) {
    double x = atof(line);
    st_push(x);
}
 
static void onSin() {
    double x;
    if (st_empty()) {
        printf("Stack empty.\n");
        return;
    }
    x = st_pop();
    st_push(sin(x));
    display();
}
 
static void onCos() {
    double x;
    if (st_empty()) {
        printf("Stack empty.\n");
        return;
    }
    x = st_pop();
    st_push(cos(x));
    display();
}
 
static void onExp() {
    double x;
    if (st_empty()) {
        printf("Stack empty.\n");
        return;
    }
    x = st_pop();
    st_push(exp(x));
    display();
}
 
static void onLog() {
    double x;
    if (st_empty()) {
        printf("Stack empty.\n");
        return;
    }
    x = st_pop();
    st_push(log(x));
    display();
}
 
static void onSqrt() {
    double x;
    if (st_empty()) {
        printf("Stack empty.\n");
        return;
    }
    if (st_top() < 0.0) {
        printf("Arg. of square root is negative.\n");
        return;
    }
    x = st_pop();
    st_push(sqrt(x));
    display();
}
 
static void onPop() {
    st_pop();
}
 
static void onClear() {
    st_clear();
}
 
static void display() {
    if (!st_empty()) {
        printf("=%lf\n", st_top());
    } else {
        printf("stack empty\n");
    }
}
 
static void onShow() {
    int d = st_size();
    printf("Depth of stack = %d.", d);
    if (d > 0)
        printf(" Stack elements:\n");
    else
        printf("\n");
 
    for (int i = 0; i < d; i++) {
        printf("  %lf\n", st_elementAt(i));
    }
}
 
static void printHelp() {
    printf(
        "Stack Calculator commands:\n"
        "    <number>    Push а number in stack\n"
        "    +, -, *, /  Ariphmetic operations\n"
        "    sin, cos,   Calculate a function\n"
        "    exp, log,   \n"
        "    sqrt        \n"
        "    =           Display the stack top\n"
        "    pop         Remove the stack top\n"
        "    show        Show the stack\n"
        "    clear       Clear the stack\n"
        "    quit        Terminate the program\n"
    );
}
// Конец файла "stcalc.cpp"

Пример работы программы "stcalc". Пусть нужно вычислить выражение (3*3 + 4*4)1/2
Запишем выражение, используя обратную польскую запись:

3, 3, *, 4, 4, *, sqrt

(через sqrt обозначается операция извлечения квадратного корня). Последовательно отдаем соответствующие команды стековому калькулятору. При работе программы stcalc получается следующий диалог:

Stack Calculator commands:
    <number>    Push а number in stack
    +, -, *, /  Ariphmetic operations
    sin, cos,   Calculate a function
    exp, log,
    sqrt
    =           Display the stack top
    pop         Remove the stack top
    show        Show the stack
    clear       Clear the stack
    quit        Terminate the program
3 3 *
=9.000000
4 4 *
=16.000000
+
=25.000000
sqrt
=5.000000

Обратная польская запись формул оказалась исключительно удобной при работе с компьютерами. Для вычислений используется стек, что позволяет работать с выражениями любой степени сложности. Реализация стекового вычислителя не представляет никакого труда. Имеется также простой алгоритм преобразования выражения из обычной записи, в которой знак операции указывается между аргументами, в ее обратную польскую запись. Все это привело к тому, что многие компиляторы языков высокого уровня используют обратную польскую запись в качестве внутренней формы представления программы. Рассмотрим, к примеру, язык программирования Java. Как всякий объектно-ориентированный язык, он является интерпретируемым, а не компилируемым языком. Это означает, что компилятор Java преобразует исходную Java-программу не в машинные коды, а в промежуточный язык, предназначенный для выполнения (интерпретации) на специальной Java-машине. В случае Java этот промежуточный язык называют байткодом. Компилятор Java помещает байткод в файл с расширением ".class". Байткод представляет собой, упрощенно говоря, обратную польскую запись Java-прогаммы, а Java-машина — стековый вычислитель.

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gifЯзык PostScript

Другой яркий пример использования обратной польской записи — это графический язык PostScript. Он предназначен для печати текстов высокого качества на лазерных принтерах; он является стандартом представления текстов типографского качества, не зависящим от конкретной модели принтера.
То, что PostScript — язык программирования, для многих людей, знакомых с типографским делом, но далеких от программирования, звучит непривычно. Общепринятое мнение, что компьютер работает с числами и в основном что-то вычисляет, не вполне верно. Не менее часто компьютерная программа работает с текстами и с изображениями. Текст, содержащийся в обычном текстовом файле, можно рассматривать с двух точек зрения. Можно трактовать его просто как текст статьи или книги. Рассмотрим, однако, процесс печати текста на обычном (не графическом) принтере. Принтер соединен с компьютером кабелем, и компьютер просто посылает через этот кабель один за другим символы, составляющие текст. В этом случае букву A, входящую в текст, следует рассматривать как команду, предписывающую принтеру напечатать символ A в текущей точке страницы, используя текущий шрифт. После этого координату x текущей точки надо увеличить на ширину буквы A. С этой точки зрения весь текст можно трактовать как программу его собственной печати. В случае обычного текстового файла эта программа весьма примитивна, в ней, к примеру, нет команд смены шрифтов, изменения текущей позиции, рисования линий и т.д. Понятно, что текст типографского качества не может быть представлен обычным текстовым файлом.
В случае использования языка PostScript файл, пересылаемый на PostScript-принтер, представляет собой программу печати текста. Язык PostScript имеет огромное количество возможностей, и вряд ли найдется много людей, владеющих им. Чаще всего PostScript-программа создается другой программой обработки текста. Например, PostScript-файл создается TEX-ом для печати на принтере. (TEX — это язык записи текстов, содержащих математические формулы, созданный замечательным математиком и теоретиком программирования Дональдом Кнутом. Фактически TEX представляет собой язык программирования. Данная книга подготовлена в TEX'е с использованием макропакета LaTEX 2ε.) Текстовые процессоры, такие, как Adobe Acrobat или MS Word, также в случае печати на профессиональном PostScript-принтере преобразуют текст в PostScript-программу. (Более точно, такое преобразование осуществляется драйверами операционной системы.) PostScript-файлы очень удобны для распространения: поскольку это файлы в обычном текстовом формате, они будут напечатаны одинаково в любой стране независимо от национальных кодировок, операционных систем, наличия шрифтов и т.п.
PostScript-программа представляет собой обратную польскую запись в том смысле, что всякая команда записывается после своих аргументов. При выполнении PostScript-программы используется стек. Рассмотрим для примера несложную программу, рисующую график функции y = sin(x). Вот какая картинка рисуется в результате выполнения этой программы:
(Подчеркнем особо, что все рисунки, содержащиеся в данном пособии, реализованы в виде PostScript-программ, написанных вручную без использования каких-либо графических редакторов.)
Ниже приведен полный текст PostScript-программы, рисующей график функции. Отметим сразу, что символ процента % используется в языке PostScript в качестве комментария:

% Файл "func.ps"
% Рисование графика функции y = f(x)
 
% Перейти от пунктов (1/72 дюйма) к миллиметрам
2.83 2.83 scale
 
0.2 setlinewidth  % Установить толщину линии
 
% Нарисовать координатную ось X:
1 15 moveto   % переместиться в точку (1, 15)
60 15 lineto  % провести линию к точке (60, 15)
              % Рисуем стрелку:
57 16 moveto  % переместиться в точку (57, 16)
60 15 lineto  % провести линию к точке (60, 15)
57 14 lineto  % провести линию к точке (57, 14)
stroke        % нарисовать построенные линии
 
% Нарисовать координатную ось Y:
30 1 moveto   % переместиться в точку (30, 1)
30 30 lineto  % провести линию к точке (30, 30)
              % Рисуем стрелку:
29 27 moveto  % переместиться в точку (29, 27)
30 30 lineto  % провести линию к точке (30, 30)
31 27 lineto  % провести линию к точке (31, 27)
stroke        % нарисовать построенные линии
 
% Определение функции
%   f(x) = 5 * sin((x - 30) * 0.2 * 180/Pi) + 15
% Дано: число x на вершине стека.
% Надо: заменить вершину стека на f(x).
/Func {
    30 sub 0.2 mul 57.296 mul sin 5 mul 15 add
} def
 
% Рисуем график функции
 
0.3 setlinewidth  % установить толщину линии
2 2 Func moveto   % переместиться в точку (2, f(2))
2.5 0.5 58 { % цикл для x от 2.5 до 58 шаг 0.5
    dup      %   удвоить вершину стека
    Func     %   заменить x в вершине стека на f(x)
    lineto   %   провести линию к точке (x, f(x))
} for        % конец цикла
stroke       % нарисовать построенные линии
 
/Times-Roman findfont % загрузить шрифт Times-Roman
4 scalefont       % установить размер шрифта 4 мм
setfont           % установить текущий шрифт
 
40 23 moveto      % переместиться в точку (40, 23)
(y = sin x) show  % напечатать текст "y = sin x"
 
% Надписи на осях координат
59 11 moveto      % переместиться в точку (59, 11)
(x) show          % напечатать текст "x"
 
26 28 moveto      % переместиться в точку (26, 28)
(y) show          % напечатать текст "y"
 
showpage          % напечатать страницу

Разберем подробно некоторые элементы этой программы. В первой выполняемой строке устанавливается миллиметровая шкала:

2.83 2.83 scale

По умолчанию в языке PostScript единицей измерения является один пункт, или 1/72 дюйма. Всякий программист помнит, что один дюйм равен 25.4 миллиметра. Вычислим отношение одного миллиметра к одному пункту:

1 mm / 1 pt = 1 mm / (1/72)" =
        = 1 mm / (25.4/72) mm = 2.834645

Таким образом, увеличивая масштаб в 2.83 раза, мы переходим от пунктов к миллиметрам. Для изменения масштаба мы помещаем в стек два числа 2.83, соответствующих изменению масштабов по x и y. Затем выполняется команда scale (изменить масштаб). Со стека при этом снимаются два числа, и масштабы по x и по y изменяются.
Разные команды могут иметь различное число аргументов. Например, вторая строка устанавливает толщину линии.

0.2 setlinewidth

Команда setlinewidth имеет один аргумент, который помещается на стек перед ее вызовом. При выполнении команды он снимается со стека, и толщина линии устанавливается равной числу, снятому со стека.
Третья строка перемещает текущую позицию в точку с координатами x = 1, y = 15.

1 15 moveto   % переместиться в точку (1, 15)

(В качестве единиц используются миллиметры, начало координат находится в левом нижнем углу страницы.) В стек сначала добавляются два числа, соответствующие координатам x и y, и затем выполняется команда moveto, которая снимает два числа со стека и перемещает курсор в точку, координаты которой были получены из стека.
Большинство строк программы понятны благодаря комментариям, которые в языке PostScript можно записывать в конце любой строки после символа %. Отметим две конструкции, которые использованы в программе. Фрагмент

/Func {
    30 sub 0.2 mul 57.296 mul sin 5 mul 15 add
} def

определяет функцию с именем Func. Функцию затем можно вызвать, просто записав ее имя, как это делается, например, в строке

Func     % заменить x в вершине стека на f(x)

Вызов функции в PostScript'е эквивалентен записи тела функции в точке вызова. Параметры и результат функции передаются через стек.
Тело функции при ее определении записывается внутри фигурных скобок. В данном случае это строка

30 sub 0.2 mul 57.296 mul sin 5 mul 15 add

Функция вызывается при условии, что ее аргумент x находится на вершине стека. В результате выполнения тела функции вершина стека заменяется на выражение

5 * sin((x - 30) * 0:2 * 57:296) + 15

Здесь используются масштабирующие множители, чтобы график выглядел красиво на печати. Так, масштаб по обеим осям равен 5 мм, поэтому мы умножаем значение sin на 5, а аргумент sin на 0.2, т.е. на 1/5. Центр графика смещается в точку с координатами (30,15), поэтому мы прибавляем к значению sin число 15, а от аргумента вычитаем 30. Наконец, аргумент функции sin в языке PostScript задается в градусах. Чтобы перейти от радианов к градусам, мы умножаем агрумент в радианах на множитель 57.296 = 180/http://localhost:3232/img/symbols/pi.gif. Сравните выражения:

5 * sin((x - 30) * 0:2 * 57:296) + 15
    x 30 sub 0.2 mul 57.296 mul sin 5 mul 15 add

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

2.5 0.5 58 { % цикл для x от 2.5 до 58 шаг 0.5
        dup      %   удвоить вершину стека
        Func     %   заменить x в вершине стека на f(x)
        lineto   %   провести линию к точке (x, f(x))
    } for        % конец цикла

представляет собой арифметический цикл. На вершину стека последовательно помещается число x в диапазоне от 2.5 до 58 с шагом 0.5. Для каждого значения выполняется тело цикла, заключенное в фигурные скобки. В теле цикла вершина стека сначала удваивается командой dup, после ее выполнения в вершине стека будут лежать два одинаковых значения x, x. Затем вызывается функция Func, которая заменяет значение x в вершине стека на y, где y равно значению функции. Затем проводится линия от предыдущей точки к точке (x,y). При этом команда lineto удаляет оба значения x, y из стека.
Язык PostScript является достаточно мощным языком программирования, в нем есть переменные, функции, циклы, условный оператор и т.п. Используемая в нем обратная польская запись очень удобна для выполнения на компьютере. Поэтому интерпретатор языка PostScript легко встраивается в конструкцию принтера (который, конечно же, всегда содержит более или менее сложный компьютер внутри себя) и не сильно увеличивает стоимость принтера.
Язык Java, байткод которого также представляет собой обратную польскую запись, был тоже первоначально разработан для программирования недорогих бытовых приборов. Стековый вычислитель устроен просто и может быть применен там, где быстродействие не играет особой роли, зато важна скорость и дешевизна разработки программы и аппаратуры.
http://localhost:3232/img/empty.gif

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика