ЭВМ
- это устройство для автоматической обработки информации (данных). Эвм может выполнять только специальные, присущие ей команды. Чтобы машина сделала что-либо полезное, необходимо задать последовательность команд на том языке, который она понимает. Такая последовательность называется программой.
Известно, что ЦП каждого типа ЭВМ имеет свою систему команд и каждая команда внутри ЭВМ (в памяти) представляется в виде последовательности нулей и единиц - машинного кода. На этапе становления программирования программы для ЭВМ составлялись именно в машинных кодах, что стало довольно затруднительно при решении более сложных задач. Поэтому были разработаны языки программирования.
Язык низкого уровня представляет собой систему двоичных или шестнадцатеричных команд, написанных в машинных кодах. Программист общается с машиной на "ее языке". Он понимается ею без преобразований. К таким языкам можно отнести АССЕМБЛЕР. Этот язык используется, в основном, программистами профессионалами и обладает существенным недостатком - машинная зависимость, т.е. невозможность переноса программы на другой тип машин.
Работа с языками высокого уровня в машине происходит более сложно. Она вначале преобразует команды языка в шестнадцатеричные коды, затем расшифровывает их (ставит в соответствие каждому коду одну или несколько своих команд) и только после этого выполняет программу. Примерами языков высокого уровня являются Паскаль, Бейсик, Си и другие языки. В отличие от языков низкого уровня, на языках высокого уровня легче программировать, т.е. общаться с машиной. Однако часто с простотой общения теряются некоторые возможности машины, поэтому практически в каждом языке высокого уровня есть возможность писать команды непосредственно на машинном языке (программировать в "кодах").
Процесс перевода программы с языка программирования высокого уровня на машинный язык называется трансляцией. Трансляция осуществляется с помощью специальной программы, называемой транслятором. Различают два вида трансляции: интерпретация и компиляция, а соответствующие им программы - интерпретаторы и компиляторы. Трансляторы с языков являются составной частью самой системы программирования, поэтому запуск программы предполагает сначала ее трансляцию, а потом собственно выполнение.
Рассмотрим процесс выполнения программы, написанной на языках интерпретаторах, а затем компиляторах.
I. ИНТЕРПРЕТАТОР
1. Машина считывает очередной оператор программы.
2. Переводит оператор в свои, ей понятные команды.
3. При обнаружении ошибки интерпретация прерывается и машина указывает на это.
4. Выполняет переведенные команды.
5. "Забывает" считанный оператор.
6. Продолжает данный процесс, пока не выполнятся все операторы, т.е. пока не дойдет до указателя конца программы.
7. "Забывает" выполненную программу.
Процесс интерпретации можно также проиллюстрировать в виде следующей схемы
:
II. КОМПИЛЯТОР
1. Машина считывает очередной оператор, написанный на языке.
2. Переводит оператор в свои, ей понятные команды.
3. При попадании на ошибку процесс перевода прерывается, и машина указывает на это.
4. Продолжает данный процесс, пока не иссякнут все строки программы, т.е. пока не дойдет до указателя конца программы.
5. Выполняет переведенную программу целиком.
Из указанного выше процесса выполнения программы следует, что языки интерпретаторы работают медленнее, при запуске не "вылавливают" всех ошибок (лишь при попадании на них машина указывает на ошибку).
Одним из первых языков программирования, созданных специально для учебных целей, был БЕЙСИК, разработанный в 1964 году в Дартмутском колледже (США). Его создание преследовало цель предоставить возможность студентам пользоваться средствами ЭВМ без длительной предварительной подготовки. Предполагалось также, что БЕЙСИК будет использоваться в качестве универсального языка людьми, не имеющими опыта работы на ЭВМ - рядовыми пользователями. Одним из достоинств языка является его удобство для работы в интерактивном режиме, что послужило использованием БЕЙСИКа при разработке диалоговых обучающих программ.
К концу 60-х годов сложилась ситуация, когда для профессиональных целей использовались языки типа ФОРТРАН, КОБОЛ и пр., а весь учебный мир предпочитал БЕЙСИК. Естественно, что многие считали такую ситуацию неудовлетворительной. По этой причине две группы исследователей приступили к созданию универсального языка программирования, отвечающего современным требованиям. Этот язык должен был включать в себя все достоинства существующих языков, иметь логически обоснованную структуру и быть легким для восприятия. Такие языки были созданы. Одним из них являлся АЛГОЛ-68, другой же был разработан в Институте информатики г. Цюриха (Швейцария) Николасом Виртом в 1971 г. Этот язык получил название ПАСКАЛЬ в честь великого французского ученого XYII века, сумевшего первым в мире изобрести автоматическое устройство для проведения вычислений. Транслятор с языка был разработан в 1973 г.
Так же как и Бейсик, Паскаль довольно просто изучать. Главное, чем обладает Паскаль - он удовлетворяет требованиям обыкновенных пользователей и специалистов по ВТ. Известно, что первым нужен язык, который легко изучать, а вторым - логически правильно построенный язык. Паскаль имеет практически все конструкции языков ПЛ/1 и АЛГОЛ-68, однако он более лаконичен. Грамматические правила языка можно уместить на 4-х страницах.
Хотя Паскаль почти так же прост, как и Бейсик, он имеет перед ним ряд преимуществ. Так, Паскаль способствует внедрению современной технологии программирования, основанной на поэтапном построении программы (принцип "cверху-вниз"), состоящих из небольших, четко определенных процедур (структурный подход). Таким образом, преодолевается главный недостаток, свойственный Бейсику, - неэффективная организация подпрограмм. Разработанный Н. Виртом вариант языка является стандартом. Помимо стандарта языка, в связи с разработкой различных компиляторов, появились версии Паскаля, среди которых наиболее популярной является система Turbo-Pascal, используемая на IBM - совместимых компьютерах.
Понятие "структурное программирование" появилось в 1968 году, когда была опубликована статья одного из видных программистов того времени Дейкстры. Он в своей статье констатировал вредность применения оператора безусловного перехода (оператора, позволяющего сделать переход от одного оператора к другому, находящемуся в любом месте программы) и нашел хорошее объяснение причине, по которой он вреден.
Программист Нор четко обосновал, что использование основных базовых конструкций способствует обеспечению ясности и читаемости при написании и дальнейшей доработке программ.
Таким образом, структурным языком назовем тот, у которого блок-схема любой программы состоит только из базовых структур.
Имеется четыре типа управляющих структур: следование, выбор, повторение (цикл) и группирование.
Для реализации следования есть правило: все команды выполняются в порядке их следования.
Для выбора и повторения есть свои специальные инструкции (операторы, команды). Выбор предусматривает проверку условия с последующим выполнением одной или нескольких команд в зависимости от истинности или ложности условия. Выбор (или развилка) бывает полный или неполный, в зависимости от выполняемых команд:
Таким образом, конструкция работает следующим образом: при истинности условия P выполняется серия команд S1, в противном случае либо S2, либо управление передается следующей за развилкой конструкции.
Повторение, или цикл, представляет собой конструкцию, которая состоит, как и выбор, из проверки условия и серии команд. Однако, в отличие от выбора, данная серия команд может выполняться неоднократно, в зависимости от проверки условия. Повторения подразделяются на циклы с предусловием (циклы-пока) и циклы с постусловием (циклы-до).
Серия команд S выполняется циклически до тех пор, пока условие истинно в первом случае и ложно - во втором.
Группирование означает объединение одной или нескольких инструкций внутри специальной инструкции. Во всех языках имеются средства для формирования единого блока из группы инструкций (подпрограммы в Бейсике, составные инструкции и процедуры в Паскале). Примером группирования может являться также выполнение в конструкциях циклов следования или выбора и т.д.
1.5 Синтаксические диаграммы
Программирование на любом языке предполагает знание определенных форм записи, которые необходимо соблюдать при написании каждой программы. Правила записи часто бывают, сложны в написании, и поэтому прибегают к различным способам их отображения. Рассмотрим один из них - синтаксическую диаграмму.
Синтаксическая диаграмма - это графическое представление отдельных объектов языка и строения самой программы. Возьмем, например, правило записи команды проверки условия в школьном алгоритмическом языке: команда начинается со служебного слова "если", за ней следует логическое выражение, далее обязательно слово "то", серия команд 1 и, наконец, не обязательно "иначе" и серия команд 2. Синтаксическая диаграмма выражает данное правило в виде схемы игрушечной железной дороги.
Локомотив трогается из пункта, расположенного слева, и прибывает к пункту назначения, расположенному справа, петляя по рельсовым путям. Всякий раз, когда поезд проходит через овальный отсек, к нему прицепляют один вагон. Когда поезд прибывает к пункту назначения, то прицепные вагоны образуют в нашем примере команду "если". Кроме овальных отсеков в синтаксических диаграммах есть еще и прямоугольные. Прямоугольные отсеки сложнее, т.к. они представляют собой ссылки на другие синтаксические диаграммы. Лучше это можно представить так: поезд на входе в прямоугольный отсек снимается с рельс и переставляется на вход другой синтаксической
диаграммы; если там он прибывает к месту назначения, то ему нужно проехать в первой синтаксической диаграмме к выходу прямоугольного отсека. При движении локомотива следите за направленностью его движения по стрелкам.
Как и любой другой язык, Паскаль имеет свой алфавит. Программа, написанная на Паскале, состоит из лексем и разделителей. В лексемы Паскаля входят специальные символы, символы-слова, имена, числа, строки символов и директивы. Ниже приведены стандартные или зарезервированные лексемы языка Паскаль.
Буквы
: латинские от A до Z, от a до z и русские от А до Я, от а до я
Символами-разделителями считаются пробелы, концы строк (разделители строк) и комментарии. Внутри лексем ни разделители, ни их части встречаться не могут. Между двумя следующими друг за другом лексемами должен обязательно следовать один или несколько разделителей.
Комментарии в Паскаль-программе начинаются с символа { или (*и заканчиваются } или *). Сам комментарий может содержать любые символы, кроме } и *). Любой комментарий можно заменить в программе на пробел.
Символы-разделители применяются часто для улучшения читаемости программы.
Язык Паскаль, как учебный алгоритмический язык, лег в основу разработки школьного алгоритмического языка, поэтому оба они имеют много общего и прежде всего это касается структуры программ (алгоритмов).
РАЯ
ПАСКАЛЬ
АЛГ<имя>
PROGRAM<имя>
ДАНО
Раздел
НАДО
объявлений
НАЧ
BEGIN
-
-
-
Блок программы
- Серия команд
(серия операторов)
-
-
-
-
КОН
END
Сравнительный анализ представленной схемы показывает, что по своему внешнему оформлению запись алгоритма на школьном алгоритмическом языке и программы на языке Паскаль во многом схожи. Действительно, оба этих описания начинаются с заголовка, в котором обязательно указывается имя алгоритма (программы). Наличие имени связано с тем обстоятельством, что описанный алгоритм в РАЯ и программа в Паскале могут служит вспомогательным алгоритмом (процедурой) для других, более сложных алгоритмов (программ).
В обоих языках принято описывать (объявлять) все переменные, фигурирующие в алгоритме (программе) с указанием их типов. Правда, в РАЯ эти переменные подразделяются еще на аргументы, результаты и промежуточные переменные, а в Паскале они просто перечисляются в разделе объявлений.
Идентификатор - это последовательность букв или цифр, начинающаяся с буквы. Отметим, что в системе TURBO в идентификаторах могут встречаться не любые буквы, а только латинские. Под оператором понимается указание ЭВМ по выполнению каких-либо действий.
Как видно из диаграммы, любая Паскаль-программа имеет имя, за которым может следовать список идентификаторов, заключенных в скобки. Заголовок программы заканчивается точкой с запятой. Затем идут объявления, служащие для описания типов данных, процедур и функций. Далее BEGIN, один или несколько операторов, разделенных точками с запятой, и в конце ставится END с точкой. При написании программ используются лексемы и разделители, определенные алфавитом языка.
По написанию инструкций (операторов) Паскаль, как и язык РАЯ, довольно свободен. Инструкция может занимать не одну, а несколько строк. На одной строке можно разместить несколько инструкций. Здесь можно вставлять пробелы и пустые строки (но пробелы в служебных словах недопустимы). Для лучшей читабельности программы строки можно располагать лесенкой.
Данные - это общее понятие всего того, с чем оперирует ЭВМ. Любой тип данных определяет множество значений, которые может принимать та или иная переменная, и те операции, которые можно к ним применять. Каждая встречающейся в программе переменная может иметь один и только один тип.
В Паскале имеется три типа данных: простые, составные и ссылочные. Рассмотрим вначале простой тип данных, представленный на следующей схеме:
Начнем рассмотрение с ординальных типов. Под данными ординального типа понимают те, для каждого из которых можно найти их порядковый номер в данном типе. Ординальные типы, таким образом, представляют собой упорядоченные множества.
К любому ординальному значению X применимы три следующие встроенные функции:
ORD(X) - дает порядковый номер, соответствующий X. Результат относится к типу INTEGER;
SUCC(X)- дает следующее за X значение, если X не максимальный элемент соответствующего типа. В последнем случае SUCC(X) суть ошибка;
PRED(X)- дает предыдущее X значение, если только X не минимальный элемент соответствующего типа. В последнем случае PRED(X) суть ошибка.
Наиболее простыми из ординальных типов являются предописанные или встроенные типы: INTEGER, BOOLEAN и CHAR, которые определяют соответственно числовые, логические (булевские) и литерные (символьные) величины. К встроенному (но не ординальному) типу данных относится также тип REAL.
Кроме предописанных, в Паскале существует возможность задавать свои типы данных. К ним относятся перечислимый и диапазонный типы. Каждый из них состоит из элементов предописанных типов, однако, в совокупности они дают совершенно новый тип.
Перечислимый тип задается перечислением всех своих элементов, что видно на следующей синтаксической диаграмме:
DEN_NED = (MO, TU, WE, TH, FR, SA, SU);
MONETA = (1, 2, 3, 5, 10, 20, 50).
Диапазонный тип представляет собой подмножество одного из ординальных типов. Его часто называют еще интервальным.
ÍÀÏÐÈÌÅÐ:
DEN_MES = 1..31;
RAB_DEN = MO..SA;
LATBUKW = 'A'..'Z'.
ЗАМЕЧАНИЕ
. Все типы, рассмотренные ранее, включая перечислимый и символьный, называются скалярными. Величины, принадлежащие скалярному типу, - упорядочены (не путать с ординальностью):
С помощью объявлений программист сообщает компилятору, какие данные, процедуры и функции пользователя будут задействованы в программе. Описательная часть программы (объявления) состоит из 5 разделов, которые должны располагаться в следующем порядке:
- раздел модулей;
- раздел меток;
- раздел констант;
- раздел типов;
- раздел переменных;
- раздел процедур и функций.
Любой из перечисленных разделов может в объявлении отсутствовать.
Раздел описания модулей начинается со служебного слова USES, за которым идет перечень используемых в программе модулей типа CRT, DOS, GRAPH и др. Все эти модули находятся в библиотеке модулей и каждый из них поддерживает соответствующий набор встроенных процедур и функций.
Раздел описания меток начинается со служебного слова LABEL, за которым следует список меток, разделяемых запятыми. Меткой может служить любое целое число, содержащее не более четырех цифр. В конце раздела ставится точка с запятой, например:
LABEL 342,11,1445;
Раздел определения констант начинается со служебного слова CONST. Определение каждой константы содержит идентификатор (имя) константы, знак равенства и значение. Определения отделяются друг от друга точкой с запятой, как показано на диаграмме:
НАПРИМЕР:
const PI = 3.1415927; E = 2.7182818; Z = 'информатика'.
Таким образом, определенные константы принято называть именованными, в отличие от обычных констант программы.
Раздел определения типов начинается со служебного слова TYPE.
Каждому определенному типу соответствует имя. Данный раздел применяется для описания нестандартных типов (перечислимых, диапазонных и др.).
НАПРИМЕР:
type COLOR = (black, white, blue, green, red);
DEN = 1..31;
За разделом типов следует раздел описания переменных. Этот раздел начинается со служебного слова VAR. При объявлении переменных компилятору указывается, сколько переменных используется в программе, какие имена у них и данные, какого типа будут храниться в этих переменных.
НАПРИМЕР:
var X,Y,Z Ж integer; AD1,AD2: real;
TEXT: char; Q: DEN; D: 17..76.
Как видно из примера, интервальный тип не обязательно описывать в разделе TYPE, а достаточно это сделать в настоящем разделе. Это замечание касается и других типов данных, о которых речь пойдет позднее.
Как уже было сказано выше, под оператором понимается указание по выполнению алгоритмических действий. Всякий оператор имеет определенную структуру и записывается с использованием служебных слов и символов языка. Говорят, что оператор характеризуется своим синтаксисом и семантикой.
Синтаксис оператора есть правило его описания, которое может быть задано либо в виде общей формы записи оператора, либо в виде синтаксической диаграммы. Синтаксическая диаграмма задает и семантику оператора, т.е. определяет те действия, которые заложены в этом операторе, и порядок выполнения этих действий. Для некоторых сложных операторов помимо синтаксической диаграммы необходимо давать дополнительные пояснения по их семантике.
Различают простые и структурные операторы. Простым оператором является такой оператор, который не содержит в себе других операторов. В простом операторе определяется, как правило, одно элементарное действие. В Паскале имеются 3 простых оператора: присваивания, процедуры и перехода. Структурные операторы подразделяются, в свою очередь, на составные, условные, цикла и операторы над записями. Структурный оператор включает в себя другие операторы (как простые, так и составные). Существует несколько способов формирования структурных операторов, о которых речь пойдет в разделе "Структурные операторы".
Оператор присваивания относится к простым операторам и его синтаксис, и семантика определяются следующей синтаксической диаграммой:
По этому оператору переменной присваивается значение выражения. Несмотря на кажущуюся простоту оператора присваивания, при его выполнении осуществляется целый набор элементарных действий:
а) переменные выражения получают свои значения;
б) вычисляется значение выражения;
в) переменной присваивается полученное значение.
В простейшем случае, когда выражение задано константой или другой переменной, вычислений не производится и переменная сразу получает свое значение.
НАПРИМЕР:
RAZN:= A - 3.5;
N:= 25; C:= D; Y:= 'программа';
L:= true; P:= X > 10.
В языке Паскаль существует несколько типов выражений: арифметические, литерные, логические (булевские). В этом пункте мы рассмотрим только арифметические выражения.
Арифметические выражения складываются из констант, переменных, стандартных функций с использованием скобок и знаков операций.
В Tурбо-Паскале определены следующие операции над числами:
*, /, +, -, DIV, MOD, где DIV - деление нацело, MOD - вычисление остатка от деления.
Приоритет: *, /, DIV, MOD - высший;
+, - - низший.
НАПРИМЕР:
A:=13 DIV 5;(результат: A=2),
B:=13 MOD 5;(результат: B=3).
Выражения арифметического типа включают в себя числовые константы, переменные и математические функции. Каждое арифметическое выражение может иметь типы: INTEGER и REAL. Тип константы определяется самим видом константы; тип переменной задается в ее объявлении.
Тип арифметического выражения определяется по следующему правилу:
а) для операций "*, +, -", результат имеет тип REAL, если один из операндов имеет тип REAL; если оба операнда типа INTEGER, то результат имеет тип INTEGER;
б) для "/" результат всегда имеет тип REAL;
в) для "DIV, MOD" операнды и результат имеют тип INTEGER.
Значение переменной интервального типа, образованной на основе INTEGER, всегда имеет тип INTEGER. При использовании оператора присваивания нужно соблюдать типизацию объектов слева и справа от знака ":=". Смешение типов недопустимо, за исключением, когда слева от знака ":=" может стоять тип REAL, а справа - тип INTEGER.
В Паскале при написании выражений используются стандартные функции, которые разделяются на следующие виды.
1. Арифметические (математические) функции:
а) ABS(X), X - REAL и INTEGER, на выходе тот же тип;
Оператор процедуры определяет активизацию процедуры, обозначенную с помощью идентификатора (имени) процедуры. Другими словами, с помощью операторов этого типа осуществляется вызов процедур с указанием в них входных и выходных параметров (подробнее об этом будет сказано в разделе "Процедуры"). Мы начнем знакомство с операторами-процедурами на базе организации ввода/вывода данных в языке Паскаль.
Для организации ввода и вывода данных используются следующие встроенные (машинные) процедуры: READ, WRITE, READLN, WRITELN.
Процедура READ вызывается с помощью соответствующего оператора процедуры, который описывается в виде следующей синтаксической диаграммы:
ОБЩАЯ ФОРМА ЗАПИСИ:
READ(X,Y,..., Z),
где X,Y,..., Z - переменные, называемые списком ввода.
При выполнении процедуры READ работа программы приостанавливается, ЭВМ ждет ввода информации. Пользователь должен с клавиатуры ввести значения переменных, указанных в списке, отделяя их одним пробелом. Ввод завершается нажатием клавиши ENTER. Можно нажимать клавишу ввода и после набора каждого элемента ввода. В этом случае каждое нажатие клавиши ENTER осуществляет присваивание очередной переменной списка ввода ее значения, набранного с клавиатуры. По завершению ввода программа возобновляет свою работу.
Для лучшего понимания работы данной процедуры и ее умелого использования при задании значений нескольких переменных необходимо знать, что при вводе значений с клавиатуры они сначала идут в буфер клавиатуры, а потом считываются в переменные. При считывании буфер очищается по принципу очереди (первым зашел - первым вышел). Это означает, что при вводе сразу нескольких констант и последующем нажатии клавиши ENTER из буфера клавиатуры будет считано столько констант, сколько переменных в операторе READ, а остальные останутся в буфере. При следующем операторе READ остановки работы ЭВМ не будет, и его переменные получат свои значения из буфера (если только в нем достаточно констант для всех переменных).
Например, пусть имеется фрагмент программы, включающий в себя два оператора READ:
READ (A,B,C);
READ (D,E);
и пусть по первому оператору на клавиатуре набраны 5 констант. Тогда при работе второго READ останова работы программы не будет, и переменные C и D получат значения последних двух ранее введенных констант. Если же ввести 4 константы, то второй оператор READ затребует еще одну константу с клавиатуры.
Вызов процедуры READLN имеет тот же синтаксис, что и оператор READ, однако ее работа отличается от работы первой процедуры. При однократном вводе констант отличий нет, а при одноразовом вводе нескольких констант происходит очистка буфера клавиатуры. Так, если в нашем примере заменить первый READ на READLN, и тоже ввести сразу 5 констант, то второй оператор READ произведет остановку работы программы и затребует повторного ввода последних двух значений для переменных D и E. Заметим также, что оператор READN используется преимущественно при вводе текстовых констант.
Эти процедуры служат для вывода на экран констант (как числовых, так и текстовых), значений переменных и выражений. Они вызываются с помощью одноименных операторов процедур.
НАПРИМЕР: WRITE ('программа', X, Y-Z*3).
По этому оператору на экране будет напечатано в одной строке слово "программа" и далее без пробелов значения переменной X и выражения Y-Z*3. Чтобы отделить элементы вывода друг от друга, используется прием форматирования вывода. Так, WRITE(А:20) показывает, что значение переменной А занимает 20 позиций на экране. Если в А входит менее 20 символов, то они сдвигаются вправо, а слева строка заполняется пробелами.
Двойное форматирование используется только для вывода вещественных констант. Например, WRITE(C:17:7) означает, что для вывода C отведено всего 17 позиций, из них 7 позиций предназначены на представление дробной части. Если формат не указан, то вещественные константы выводятся на экран в экспоненциальной форме.
Работа оператора WRITE отличается от работы оператора WRITELN тем, что по завершению вывода у WRITE курсор остается в конце списка вывода, а у WRITELN он переходит на следующую строку. Часто используют оператор WRITELN без списка вывода для печати пустой строки.
Проиллюстрируем работу всех операторов на следующем примере:
GOTO
- это оператор безусловного перехода на оператор или процедуру с указанной меткой. Все метки должны быть описаны в объявлении в разделе LABEL.
При использовании оператора перехода необходимо соблюдать следующие правила:
1. Недопустимо метить одной меткой несколько операторов или процедур.
2. Метка, которая указывается в операторе перехода, должна находиться в том же блоке, что и сам оператор перехода. Другими словами, недопустим выход из блока или вход внутрь него.
3. Íåäîïóñòèì âõîä âíóòðü ñòðóêòóðíîãî îïåðàòîðà.
label 12;
12: write('Введитезначение N > 0 '); readln(N);
iF N <= 0 then goto 12;
Не рекомендуется часто применять оператор GOTO, т.к. это ведет к нарушению структурности программы. Наиболее распространенным случаем использования оператора GOTO является обработка ошибки неправильного ввода данных с клавиатуры, как это показано в рассмотренном примере.
Структурные операторы строятся из других операторов по определенным правилам. Операторы, входящие в структурный оператор, выполняются последовательно в составных операторах и операторах над записями, альтернативно в условных операторах, многократно в операторах цикла.
При формировании структурных операторов существуют некоторые ограничения на число входящих в него операторов. В частности, в операторе выбора IF (в школьном алгоритмическом языке команда "если"), после служебного слова THEN (аналог - "то") может стоять только один оператор. Поэтому в Паскале возникла необходимость группирования операторов в единое целое - в один составной оператор.
Любая группа операторов, размещенных между словами BEGIN и END (иначе, операторные скобки), рассматривается как один - составной оператор. При выполнении составного оператора все его компоненты (операторы) выполняются в порядке их написания (линейно).
Составные операторы обрабатываются как единое целое, как один оператор, что имеет значение там, где синтаксис языка допускает использование одного оператора. Это имеет место практически во всех структурных операторах. Примеры использования составных операторов будут рассмотрены в соответствующих разделах данного пособия.
Наряду с понятием "составной оператор" в языке существует специфическое понятие - "пустой оператор". Пустой оператор - это оператор, который не предусматривает выполнения никаких действий.
Однако практика показывает, что иногда полезно иметь такое средство, например, при выполнении искусственной задержки выполнения программы:
FOR I:=1 TO 10000 DO;
При выполнении данного цикла машина переменной I последовательно присвоит значения от 1 до 10000. В теле цикла нет операторов, значит, кроме счета ничего не будет выполнено, однако время на это затрачивается, и, следовательно, некоторое время программа "висит" на данном операторе.
Существуют и другие примеры использования пустого оператора, когда по синтаксису оператор формально необходим, но никаких действий внутри него не производится.
Оператор IF можно представить в виде следующей синтаксической диаграммы:
Конструкция "Условие" есть логическое выражение, которое принимает два значения типа BOOLEAN: TRUE, FALSE (истинно или ложно).
Само выражение (логическое) складывается из операций сравнения >, >=, <, <=, =, <>. Результат сравнения может быть TRUE или FALSE.
Логические выражения могут формироваться также и с помощью трех логических операций: NOT, AND, OR. Приоритеты операций:
Высший: ()
NOT *, /, DIV, MOD
AND
OR +, -
Низший: >, =, <, >=, <>, <=
В качестве условия может быть использована и логическая переменная.
Например:
I and J or K ---> (I and J) or K;
not X and Y ---> (not X) and Y,
где I, J, K, X, Y переменные типа BOOLEAN;
(A<B) or (B=0), где A,B - переменные простого типа.
В операторе IF всегда за словами THEN и ELSE должен следовать один оператор. Если хотя бы один из них является оператором IF, то полученную конструкцию называют вложением.
ПРИМЕР:
IF <условие1> THEN
<ветвь 1>
ELSE
IF <условие2> THEN
<ветвь 2>
ELSE
<ветвь 3>
Такое вложение используется для уменьшения числа необходимых проверок. Этот метод часто обеспечивает большую эффективность, чем составное условие, однако одновременно он уменьшает надежность программы. Не рекомендуется использовать более двух-трех уровней вложения IF. Вложения могут идти и после слова THEN. Ниже следуют два способа вложения конструкции IF в конструкцию IF:
1 способ
2 способ
IF c1 THEN
IF c1 THEN
s1
IF c2 THEN
ELSE IF c2 THEN
IF c3 THEN
s2
ELSE s2
ELSE IF c3 THEN
ELSE s3
ELSE s4
ELSE s4
Первый способ предпочтительнее, чем второй, т.к. конструкция THEN-IF менее удобна, чем ELSE-IF. С помощью конструкции ELSE-IF чаще всего осуществляется выбор одного из нескольких альтернативных путей. Заметим, однако, что иногда такое вложение лучше заменить на последовательность короткой формы оператора IF-THEN. Этовиднонаследующемпримере:
program QUARD;
var A,B,C: real; DETER: real;
begin
read(A,B,C); DETER:= sqr(B)-4*A-C;
1 вариант
2 вариант
if DETER<0 then
if DETER<0 then
write('Не имеет корней');
write('Нет корней');
if DETER=0 then
else
write('Один корень');
if DETER=0 then
if DETER>0 then
write('Один корень');
write('Два корня');
else
write('Два корня');
end
однако в Паскале существует оператор, позволяющий сделать выбор из нескольких альтернатив - множественное ветвление.
Оператор варианта состоит из выражения и списка операторов, каждому из которых предшествует одна или более констант, называемых константами выбора, что видно из синтаксической диаграммы:
ОБЩАЯ ФОРМА ЗАПИСИ:
CASE <выражение> OF
константы: оператор;
константы: оператор
ELSE < оператор >
END.
Выражение, стоящее между CASE и OF, называется селектором.
Константы (значения выражения), предшествующие двоеточию, называются метками случаев. Порядок работы оператора - сначала вычисляется значение селектора, затем выполняется оператор, метка которого совпадает со значением селектора. Все остальные операторы не выполняются, управление передается на следующий после END оператор. Если же в операторе есть строка ELSE, то при несовпадении значения селектора ни с одной константой выполняется оператор, следующий за ELSE.
Выражение "селектор" может относиться к любому скалярному типу, кроме REAL. Метки случаев должны принадлежать тому же типу, что и селектор. Недопустимо, чтобы одна и та же метка появлялась более одного раза в операторе CASE.
Оператор CASE особенно удобно использовать, во-первых, когда характер действий определяется значениями, которые не попадают в последовательно расположенные интервалы, во-вторых, когда нескольким дискретным значениям селектора соответствует одно и то же действие.
ПРИМЕР 1. Печать названия десятичных цифр
program DICITS;
var DIGIT: integer;
label 1;
begin
1: writeln ('Введитецифру');
readln(DIGIT);
if (DIGIT < 0) or (DIGIT > 9) then
begin
writeln ('Это не цифра');
GOTO 1
end
else
case DIGIT of
0: writeln('нуль');
1: writeln('один');
9: writeln('девять');
end;
end.
ПРИМЕР 2. Печать номера квартала года
program NUMKVART;
var MESIATZ: 1..12;
begin
write('Введите номер месяца года - '"; read(MESIATZ);
case MESIATZ of
1,2,3: writeln('Первыйквартал');
4,5,6: writeln('Второй квартал');
7,8,9: writeln('Третий квартал');
10,11,12: writeln('Четвертый квартал');
end;
end.
ПРИМЕР 3. Вывод на печать, является ли введенный с клавиатуры символ гласной буквой или знаком препинания
Оператор цикла задает повторное выполнение определенных операторов. Для реализации циклов в Паскале предусмотрены три различных структурных оператора: WHILE, REPEAT, FOR. Первые два используются, если число повторений (итераций) заранее не определено, но известно условие завершения цикла. Оператор FOR применяется тогда, когда число повторений тела цикла известно.
Этот оператор является наиболее мощным из всех трех, реализующих циклы. Два других оператора можно выразить с его помощью.
Логическое выражение, стоящее после WHILE, называется условием возобновления цикла и должно иметь булевский тип. Оператор, следующий за DO, является телом цикла. Он повторяется до тех пор, пока истинно условие возобновления цикла. Как только условие возобновления цикла становится ложным, управление переходит к оператору, стоящему за WHILE. Если условие возобновления не удовлетворяется до начала выполнения цикла, то тело цикла пропускается.
Из указанного описания видно, что оператор WHILE реализует базовую структуру "цикл - пока", т.к. здесь проверка условия идет до тела цикла. Поэтому оператор WHILE называют оператором цикла с предусловием.
Рассмотрим пример программы вычисления
для данного аÎ0 по известной итерационной формуле:
×
Здесь надо организовать циклический процесс и остановиться тогда, когда
,
где Е - заданная точность приближения.
program SQUR;
var A,X,EPS: real;
begin
write('Введите число ');
readln(A);
write('Введитеточность ');
readln(EPS);
X:=(A+1)/2;
while abs(sqr(X)-A) >= EPS do
X:=0.5*(X+A/X);
write('Кореньиз ',A,' = ',X);
end.
ЗАМЕЧАНИЕ. Грамотное использование оператора WHILE предполагает умение правильно написать условие возобновления цикла. Здесь надо иметь в виду следующие рекомендации:
а) в условии, как в логическом выражении, должны обязательно фигурировать переменные, изменяющие свои значения в теле цикла;
б) во избежание зацикливания лучше сначала написать условие прекращения цикла и взять потом в оператор его отрицание;
в) переменные логического выражения должны получить свои исходные значения до входа в оператор WHILE.
Оператор REPEAT называют оператором цикла с постусловием, т.к. здесь выражение, управляющее повторным выполнением последовательности операторов, помещается после тела цикла.
В этом операторе тело цикла выполняется до тех пор, пока ложно условие, стоящее после UNTIL. Условием выхода из цикла является истинность выражения. Мы видим, что это есть форма "цикла-до".
ПРИМЕР. Даны числа A, B (A>1). Получить все степени числа A, меньшие числа B
program STEPENI;
var A,B,C: real;
begin
readln(A,B); C:=A;
repeat
writeln(C);
C:= C*A;
until C >= B;
end.
ПРИМЕЧАНИЕ. Между операторами WHILE и REPEAT существуют три основных различия:
1. В операторе REPEAT проверка условия выхода из цикла выполняется в конце, а не в начале цикла, как в операторе WHILE. Поэтому в операторе REPEAT тело цикла выполняется хотя бы один раз.
2. В REPEAT выход из цикла осуществляется по истинности условия, а в WHILE - по ложности.
3. В операторе WHILE тело цикла чаще всего имеет форму составного оператора, в операторе REPEAT для организации тела цикла операторные скобки не нужны.
Он предназначен для организации циклов, когда заранее известно, сколько раз должно повториться тело цикла. Здесь управление числом повторений осуществляется с помощью специальной переменной - параметра цикла (управляющей переменной), которой присваивается возрастающая (убывающая) последовательность значений.
Здесь "переменная" есть параметр цикла, "выражение 1" - начальное значение параметра, "выражение 2" - его конечное значение. В качестве управляющей переменной должен использоваться идентификатор переменной, объявленный локальной в блоке, который содержит данный оператор FOR. Управляющая переменная должна иметь ординальный тип. Начальное и конечное значения имеют тип, совместимый с типом параметра цикла.
Когда начинает выполняться оператор FOR, начальное и конечное значения определяются один раз, и эти значения сохраняются на протяжении всего выполнения оператора.
Оператор, который содержится в теле оператора FOR, выполняется один раз для каждого значения управляющей переменной в диапазоне между начальным и конечным значениями. Управляющая переменная всегда инициализируется начальным значением. Она принимает все свои значения из диапазона с шагом 1, если TO, и с шагом -1, если DOWNTO. В случае TO, если начальное значение превышает конечное, то тело цикла не выполняется.
Для случая DOWNTO это имеет место, когда начальное значение меньше, чем конечное. Отсюда заключаем, что оператор цикла FOR реализует, как и WHILE, схему цикла "пока".
ПРИМЕЧАНИЕ:
1. Если тело цикла в этом операторе состоит из более одного оператора, то они все заключаются в операторные скобки (реализуют конструкцию составного оператора).
2. В отличие от школьного алгоритмического языка, цикл FOR нельзя прервать путем присваивания управляющей переменной ее конечного значения. Изменения переменной цикла не влияют на число повторений тела цикла. Для досрочного выхода из цикла используют оператор GOTO.
3. После выполнения оператора значение управляющей переменной становится неопределенным, если только выполнение оператора FOR не было прервано с помощью оператора перехода.
Рассмотрим примеры использования оператора FOR для организации циклических процессов:
ПРИМЕР 1. Печать отсчета цифр при старте
program START;
var SEC: integer;
begin
writeln ('До старта осталось...');
for SEC:=10 downto 1 do
writeln (SEC:4);
writeln ('ноль'); writeln ('Старт !!')
END.
В данном примере управляющая переменная SEC принимает значения типа INTEGER, однако в Паскале она определена как переменная ординального типа, следовательно, может принимать значения типа CHAR или принадлежать перечислимому типу, как показано в следующем примере:
Мы уже видели, что Паскаль-программа состоит из последовательности операторов (простых и структурных). Есть в языке также понятие функции. Система Turbo-Pascal имеет целый набор встроенных машинных функций. Однако Паскаль предоставляет возможность создавать новые операторы и функции на основе стандартных. Такие процедуры и функции принято называть пользовательскими.
В Паскале два типа подпрограмм - процедуры и функции. Создание процедур и функций является дальнейшим развитием идеи группирования, когда несколько операторов объединяются в программный блок, который имеет свое имя и к которому можно обратиться по этому имени с помощью соответствующих средств вызова. Процедура вызывается с помощью оператора процедуры с одноименным именем. Функция пользователя также имеет свое имя и ее активизация происходит при вычислении выражения, содержащего имя функции, и возвращаемое функцией значение подставляется в это выражение.
Итак, процедура - это часть программы (подпрограмма), имеющая имя и предназначенная для решения некоторой частной задачи (подзадачи). Они делятся по способам описания и обращения к ним следующим образом:
Процедура встроенная (машинная) - процедура в программировании, описание которой считается известным транслятору, в связи с чем ее можно использовать без описания.
Процедура пользователя - процедура, которую создает (описывает) программист на основе имеющихся операторов и встроенных процедур и функций данного языка по определенным правилам данного компилятора.
Процедура без параметров - процедура, при обращении, к которой не требуется задания начальных установок, значений и после выполнения которой в основную программу не передаются результаты работы данной процедуры.
Процедура с параметрами-значениями - процедура, при обращении к которой требуются начальные значения. На выходе данные не передаются в основную программу.
Процедура с параметрами-переменными - процедура, не требующая начальных значений, однако передающая в основную программу результаты своей работы (передает значения некоторых переменных).
Комбинированная процедура - процедура, имеющая параметры-переменные и параметры-значения, т.е. входные и выходные данные.
Эти процедуры являются составной частью системы программирования. Среди этих процедур есть стандартные процедуры, которыми можно пользоваться в любом месте программы без какого-либо предварительного объявления. Сюда относятся уже ранее упомянутые процедуры ввода/вывода, управления работой программы, динамического распределения памяти, строковые процедуры и пр. Полный перечень встроенных процедур можно найти в справочнике для языка.
Помимо стандартных процедур в Паскале есть также стандартные модули, представленные в виде TPU - файлов, каждый из которых содержит в себе целый набор процедур и функций. Для того, чтобы использовать процедуры из модулей, необходимо вызвать нужный модуль в разделе USES. Система Turbo-Pascal имеет модули PRINTER, DOS, CRT, GRAPH и др.
CRT - позволяет использовать все возможности дисплея и клавиатуры, включая управление режимом экрана, расширенные коды клавиатуры, цвет, окна и звуковые сигналы.
DOS - поддерживает различные функции ДОС, включая установку и получение текущего значения даты и времени, поиск по каталогам файлов и выполнение программ.
PRINTER - позволяет легко организовать доступ к устройству печати.
GRAPH - мощный графический пакет с набором процедур и функций обработки графических объектов (точек, отрезков, прямоугольников, окружностей и пр.).
Рассмотрим несколько примеров встроенных процедур:
1) CLRSCR
- процедура очистки экрана. Результатом работы является стирание всей информации с экрана. Данная процедура является примером процедур без параметров;
2) GOTOXY(A,B)
- процедура позиционирования курсора на экране дисплея в точку с координатами (A,B). A и B являются входными данными, следовательно, это пример процедуры с параметрами-значениями;
3) WRITE([A],[B],.....,[Q])
процедура вывода информации на экран дисплея. Данная процедура - процедура с параметрами-значениями.
4) READ([A],[B],....,[Q])
процедуры ввода информации в ЭВМ.
При работе с процедурами пользователя необходимо уметь производить два вида деятельности: описание процедуры и обращение к ней в основной программе. Вызов процедуры пользователя осуществляется так же, как и вызов встроенной процедуры - с помощью оператора процедуры, имя которого совпадает с именем процедуры, с указанием списка параметров, если таковые имеются. Описание же процедуры включает в себя разработку подпрограммы и правильное оформление ее заголовка. Остановимся на нем подробнее.
В основной программе все процедуры (а также и функции) пользователя должны быть объявлены. Объявление процедур и функций осуществляется после объявления переменных и перед первым словом BEGIN программы.
Заголовок программы;
Описание модулей USES;
Описание меток LABEL;
Описание констант CONST;
Описание типа TYPE;
Описание переменных VAR;
Описание процедур и функций PROCEDURE/FUNCTION;
BEGIN
Тело программы (блок);
END.
Процедура, как видно из ее определения, оформляется так же, как и основная программа. Вообще процедуру нужно воспринимать как программу в миниатюре. В свою очередь основная программа может быть легко переделана в процедуру с заменой слова PROGRAM на PROCEDURE. Если процедура объявлена, ее можно использовать в последующих частях программы, просто задавая ее имя, за которым, если необходимо, следует список параметров. Вызов процедуры для основной программы становится новым оператором. Обращение к процедуре активизирует эту процедуру, то есть приводит к выполнению группу операторов, содержащихся в ее теле. После этого управление переходит к оператору, следующему за вызовом процедуры.
Описание процедур будем рассматривать по той же схеме, что и машинные процедуры, а именно: вначале без параметров, далее с параметрами - значениями, с параметрами - переменными и, наконец, комбинированные процедуры.
Заголовок процедуры без параметров можно описать в виде:
Вызываются же такие процедуры путем написания в основной программе имени этой процедуры. В виде процедуры без параметров оформляются такие подзадачи, у которых нет входных и выходных данных, или же эти данные удобнее передавать с помощью операторов присваивания, READ и WRITE.
Рассмотрим несколько примеров, в которых представлены эти варианты.
ПРИМЕР 1. Нарисовать три вертикальных квадрата 3х3 с помощью символа "*".
Очевидно, что в этой программе надо выделить рисование квадрата в виде процедуры без параметров, а затем трижды вызвать ее в основной программе:
program RISUNOK;
procedure KVADRAT;
begin
¦ writeln('***');
¦ writeln('* *');
¦ writeln('***');
end;
begin
¦ clrscr; KVADRAT;
¦ writeln; KVADRAT; writeln; KVADRAT;
end.
ПРИМЕР 2. Вычислить площадь четырехугольника ABCD
Зная длины сторон четырехугольника и длину одной из его диагоналей, например BD, можно найти по формуле Герона площади двух вспомогательных треугольников и сложить их. Отсюда следует, что в программе надо выделить процедуру вычисления площади треугольника:
program PLOCHAD_1;
var AB,BC,CD,AD,BD,S1,S,a,b,c,p:real;
procedure GERON_1;
begin p:=(a+b+c)/2;
S:=sqrt(p*(p-a)*(p-b)*(p-c));
end;
begin {*ОСНОВНАЯПРОГРАММА*}
read (AB,BC,CD,AD,AC);
a:=AB;b:=AD;c:=BD; GERON_1; S1:= S;
a:=BC;b:=CD;c:=BD; GERON_1; S1:= S1+S;
write(S1);
end.
Прежде чем переходить к рассмотрению процедур с параметрами, необходимо определить сами эти понятия. Сделаем это на примере программы вычисления площади четырехугольника (пример 2).
Рассмотренная программа имеет недостаток в том, что в основной ее части идет ряд присваиваний, которые предшествуют вызову процедуры. Чтобы избавиться от этих присваиваний, вводят процедуры с параметрами. С помощью параметров осуществляется передача информации в процедуру, а также и прием информации из процедуры в основную программу.
Различают формальные и фактические параметры. Формальные параметры - это имена переменных, фигурирующих в самой процедуре. Их описание производится в заголовке процедуры - после имени процедуры в скобках. Среди них имеются параметры-аргументы и параметры-результаты. Эти параметры называют формальными, потому что они служат только для фиксации числа параметров процедуры, их имена могут быть произвольными, смена имен не отражается на ее работе.
Фактические параметры задаются в вызове процедуры, т.е. они принадлежат основной части программы. В отличие от формальных параметров, которые всегда есть переменные, фактические параметры имеют вид:
параметры-аргументы - это константы, переменные, выражения;
параметры-результаты - это всегда переменные.
Рассмотрим заново программу вычисления площади четырехугольника. В ней все переменные объявлены в основной программе. Однако среди них есть переменные, которые задействованы только в процедуре. Это переменные A, B, C, P, S. Такие переменные принято называть локальными по отношению к процедуре. Остальные переменные называются глобальными. Среди локальных переменных можно выделить параметры-аргументы A, B, C и параметр-результат S. Принято формальные параметры описывать в заголовке процедуры с указанием их типа. Локальная же переменная P является вспомогательной и описывается в процедуре так же, как в основной программе.
Порядок следования формальных параметров в заголовке процедуры и фактических параметров в вызове процедуры важен, поскольку определяет, какому параметру будет присвоено то или иное значение.
Все переменные должны быть отнесены к какому-то типу, поэтому необходимо задать тип каждого параметра. Передаваемое значение и соответствующий ему параметр (фактический) должны быть одного и того же типа.
Новые варианты программы вычисления площади четырехугольника будут даны в следующих разделах, а пока рассмотрим подробнее понятия локальных и глобальных переменных в Паскаль-программах.
В предыдущем разделе уже было дано определение локальных и глобальных переменных. Уточним еще раз, что локальные переменные объявляются внутри блока процедуры и они бывают двух видов: формальные параметры заголовка процедуры и вспомогательные переменные в разделе VAR процедуры. Эти переменные неизвестны основной программе и их использование в основном блоке вызовет сообщение об ошибке.
Глобальные переменные объявляются в разделе VAR основной программы. Глобальные переменные называют глобальными, потому что они могут фигурировать не только в основной программе, но и в теле процедуры. Заметим, что иногда одна и та же переменная может быть и локальной, и глобальной. Например, если переменная J является одновременно локальной и глобальной, то локальная переменная J отличается от переменной J из главной программы. Изменения, происходящие с J в процедуре, не влияют на значение переменной J из главной программы, и наоборот. Это происходит потому, что, несмотря на сходство имен переменных, компилятор отводит локальной переменной J одну ячейку памяти, а глобальной переменной J - другую. Обычно стараются избегать совпадения имен переменных во избежание нежелательных посторонних эффектов, которые могут возникнуть из-за использования одних и тех же имен для разных переменных.
Для ясности рассмотрим пример, связанный с использованием локальных и глобальных переменных:
program NEST;
var A,B:integer;
procedure NESTEGG;
var A,X: char;
begin
A:= "!";
X:= "?";
B:= B+1;
end;
begin { ОСНОВНАЯ ПРОГРАММА }
A:= 0; B:= 100;
NESTEGG;{ ВЫЗОВ ПРОЦЕДУРЫ }
writeln(A,' ',B);
end.
В этой программе X - локальная переменная для процедуры NESTEGG, поэтому основная программа не может ни изменить ее значение, ни обратиться к ней. С другой стороны, переменная B (глобальная) известна и в программе, и в процедуре. Если переменная B является глобальной, т.е. объявлена в главной программе, то все входящие в состав этой главной программы процедуры могут ссылаться к ней, но только в том случае, если в них нет другого объявления для B. Любое объявление имени в процедуре делает недоступным объект, имеющий то же самое имя и объявленный в основной программе. Так, у нас A для основной программы есть INTEGER, но в процедуре есть A типа CHAR. Процедуре NESTEGG недоступна переменная A из главной программы. Все изменения, происходящие с A в процедуре, становятся несущественными при выходе из этой процедуры. Но, поскольку B известна в главной программе, то все изменения с B в процедуре важны и сохраняются после выхода из нее. Итак, будет напечатано: 0 101.
Как было сказано ранее, процедуры с параметрами-значениями требуют входных данных (смотри п. 5.1). Где они записываются и как задаются? На этот вопрос может ответить синтаксическая диаграмма заголовка процедуры:
Здесь под параметром понимают имя переменной, которая является "входной" для процедуры (формальный параметр-аргумент). Этот параметр с синтаксической точки зрения является параметром-значением, при его описании в заголовке процедуры не требуется писать слов VAR. Параметры-значения принимают из основной программы при вызове процедуры свои конкретные значения.
При обращении к процедуре с параметрами-значениями в основной программе фактическими параметрами могут служить как имена переменных (которые описаны и определены выше), так и конкретные значения (константы) и выражения. При обращении необходимо следить за соответствием списка параметров при обращении и описании. Кроме этого, следует строго соблюдать "типизацию" параметров.
Рассмотрим работу процедур такого типа на примерах.
ПРИМЕР 1. Нарисовать квадрат с произвольной длиной стороны в левом верхнем углу (длина стороны задается с клавиатуры).
В этой программе также надо оформить рисование квадрата в виде процедуры, но уже с входным параметром-аргументом - длиной стороны квадрата:
program RISUNOK_2;
var I: integer;
procedure KVADRAT(N: integer);
var J,K: integer;
begin
for J:=1 to N do write('*'); writeln;
for J:=1 to N-2 do
begin
write('*'); for K:=1 to N-2 do write(' ');
writeln('*');
end;
for J:=1 to N do write('*');
end;
begin { Основная программа }
write('Введите длину стороны - ');
readln(I); clrscr; KVADRAT(I);
end.
ПРИМЕР 2. Вычисление площади четырехугольника с применением процедуры с параметрами-значениями:
program PLOCHAD_2;
var AB,BC,CD,AD,AC,S1,S: real;
procedure GERON_2(a,b,c: real);
var P: real;
begin
P:= (a+b+c)/2; S:= sqrt(P*(P-a)*(P-b)*(P-c));
end;
begin {*ОСНОВНАЯПРОГРАММА*}
read (AB,BC,CD,AD,AC); GERON_2(AB,BC,AC); S1:= S;
GERON_2(AD,AC,CD); write ('S = ', S1+S)
end.
В данной программе определена процедура GERON_2 с тремя параметрами-значениями и локальной переменной P. Значение же площади треугольника помещается в глобальную переменную S. При вызове этой процедуры формальные параметры a, b, c замещаются на фактические параметры AB, BC, AC при первом обращении, и на AD, AC, CD - при втором.
Заметим также, что здесь фактические параметры представлены переменными, которые получают свое значение с помощью процедуры READ. Однако, если известны длины сторон треугольника, например, 6, 7, 4, то можно вычислить площадь этого треугольника, вызвав процедуру GERON_2(6,7,4), и получить ответ в переменной S.
В отличие от процедур с параметрами-значениями, данный тип не имеет входных параметров, т.е. из основной программы не передаются значения переменных в процедуру, за исключением глобальных переменных. Отличие в описании и обращении к процедурам с параметрами-переменными заключается в специфическом написании заголовка процедуры. В остальном все процедуры схожи. Итак, синтаксическая диаграмма заголовка процедуры с параметрами-переменными:
При детальном ознакомлении с синтаксической диаграммой видно, что параметрам-переменным должно предшествовать служебное слово VAR, причем оно пишется столько раз, сколько различных типов представлено в выходных данных.
Например:
PROCEDURE PRIMER(VAR a,b,c:INTEGER; VAR m:CHAR; VAR i,j:REAL);
При обращении к процедурам с параметрами-переменными фактическими параметрами должны являться имена переменных, которые описаны в основной программе.
ПРИМЕР 1. Обмен значениями переменных A и B
program ZERKALO;
var A,B: integer;
procedure OBMEN(var X,Y: integer);
begin X:= B; Y:= A end;
begin
A:= 1; B:= 2; writeln(A,B);
OBMEN(A,B); write(A,B);
end.
ПРИМЕР 2. Вычисление площади четырехугольника
program PLOCHAD_3;
var AB,BC,CD,AD,AC,S1,S2,a,b,c: real;
procedure GERON_3(var S: real);
var P: real;
begin
P:= (a+b+c)/2; S:= sqrt(P*(P-a)*(P-b)*(P-c));
end;
begin { Основнаяпрограмма }
read (AB,BC,CD,AD,AC);
a:=AB; b:= BC; c:= AC; GERON_3(S1);
a:=AD; b:= AC; c:= CD; GERON_3(S2);
write ('S = ', S1+S2)
end.
Комбинированные процедуры включает в себя входные и выходные данные. В заголовке процедуры выходные параметры предваряются, словом VAR. Порядок следования параметров может быть произвольным.
НАПРИМЕР:
PROCEDURE PRIMER(VAR a,b,c:INTEGER; m:CHAR; VAR i,j:REAL);
Здесь a,b,c,i,j - параметры-результаты (переменные);
m - пераметр-аргумент (значение).
В качестве иллюстрации комбинированных процедур рассмотрим последний вариант вычисления площади четырехугольника:
program PLOCHAD_4;
var AB,BC,CD,AD,AC,S1,S2: real;
procedure GERON_4(a,b,c:real; var S: real);
var P: real;
begin
P:= (a+b+c)/2;
S:= sqrt(P*(P-a)*(P-b)*(P-c));
end;
begin {*ОСНОВНАЯПРОГРАММА*}
read (AB,BC,CD,AD,AC);
GERON_4(AB,BC,AC,S1);
GERON_4(AD,AC,CD,S2);
write ('S = ', S1+S2)
end.
ПРИМЕЧАНИЕ. Для более полного усвоения введенных ранее терминов перечислим на базе последнего примера все виды параметров и переменных:
a) параметры-значения (аргументы) AB, BC, CD, AD, AC;
б) параметры-переменные (результаты) S1,S2.
Попытка же описать выходной параметр в виде параметра-значения (без слова VAR в заголовке процедуры) приведет к тому, что результат работы процедуры не будет возвращен в основную программу. Это происходит потому, что характер "поведения" параметров-значений и параметров-переменных в процессе работы процедуры различен. Разница эта состоит в том, что преобразования, которые претерпевают формальные параметры-значения в процедуре, не вызывают изменения соответствующих им фактических параметров, в то время как изменения параметров-переменных может изменять значения соответствующих фактических параметров.
Причиной этого феномена является неодинаковое распределение памяти под хранение параметров процедуры. Формальному параметру-значению отводится некоторая область (ячейка) памяти, куда заносится значение соответствующего фактического параметра, вычисленного на момент обращения к процедуре. На этом связь между ними обрывается. Действительно, если фактическим параметром является константа или выражение, как изменения в формальном параметре-значении (а это есть всегда переменная) могут повлиять, например, на выражение.
Фактическим же параметром, соответствующим формальному параметру-переменной, является всегда переменная. На время выполнения процедуры эти параметры отождествляются, им соответствует одна и та же область памяти. Вполне понятно, что в этой ситуации изменения формального параметра влекут адекватные изменения фактического параметра, и после завершения процедуры его значение может отличаться от его первоначального значения.
Именно поэтому, объявив в процедуре параметр-результат как параметр-значение, этот результат так и останется в формальном параметре-переменной без его передачи в соответствующий фактический параметр.
Функция как объект языка Паскаль является другой версией реализации технологии построения программ с использованием структуры группирования. Можно также сказать, что функция есть частный вид определенного типа процедур, а именно, процедур с одним параметром - переменной.
Функция отличается от процедуры только тем, что всегда возвращает в точку вызова одно скалярное значение. При этом функция, как процедура, может содержать параметры-значения или быть без оных. Общая форма записи заголовка функции:
FUNCTION имя (список параметров: тип): тип;
или
FUNCTION имя: тип;
Тип результата есть тип значения функции. Список параметров такой же, что и для процедуры, только здесь все параметры-аргументы. Имя переменной, которая хранит значение функции, совпадает с именем функции.
Итак, заголовок функции отличается от заголовка процедуры не только сменой слова PROCEDURE на FUNCTION, но и удалением из списка параметров параметра-результата с присвоением его типа имени функции:
PROCEDURE <имя процедуры>(аргументы; VAR параметр-результат: тип);
| |
¾¾¾¾¾¬¾¾¾¾¬¾¾¾¾
FUNCTION <имя функции> (аргументы): тип;
Другой особенностью описания функции является наличие в нем хотя бы одного оператора присваивания, в левой части которого стоит имя определяемой функции, а в правой - выражение для вычисления результата функции. Очевидно, что тип этого выражения должен совпадать с указанным в заголовке типом функции.
Вызов функции также отличается от вызова процедуры. Если вызов процедуры осуществляется с помощью специального оператора вызова (оператора процедуры), функция вызывается только с помощью некоторого выражения. Для того чтобы осуществить обращение к функции, необходимо использовать ее имя со списком фактических параметров в каком-либо выражении, тип которого совпадает с типом значения функции. Само же выражение, внутри которого вызывается функция, может быть правой частью оператора присваивания, частью логического выражения и пр.
Известно, что Паскаль имеет набор стандартных функций. Однако этот набор ограничен. Пользователь может по желанию расширить список функций, создав свои функции - функции пользователя. Так, например, в Паскале есть SQR(X) = X2
, а вот функции F(X)= Xn
, где n принадлежит множеству целых чисел Z, нет. Используя определенное ранее понятие функции, можно создать для этого универсальную функцию, которая давала бы степени произвольного вещественного числа с любым целым показателем.
Определим вещественную функцию POWER, которая должна иметь два параметра-аргумента - для показателя и для основания степени:
function POWER (FACTOR:real;EXPONENT:integer):real;
var COUNT: integer; TFACTOR: real;
begin
¦ if EXPONENT = 0 then POWER:= 1
¦ else begin
¦ ¦ TFACTOR:= FACTOR;
¦ ¦ for COUNT:= 2 to ABS(EXPONENT) do
¦ ¦ TFACTOR:= TFACTOR*FACTOR;
¦ ¦ if EXPONENT<0 then POWER:= 1/TFACTOR
¦ ¦ else POWER:= TFACTOR
¦ end
end;
Теперь можно эту функцию вызывать следующим образом:
а) РI:=POWER(3.14,1);
б) WRITELN("PI=",POWER(3.14,1):5:2);
в) IF X > 2*POWER(6.2,3) THEN WRITE('ДА');
г) A:= POWER(X,2) + POWER(X,3) + POWER(X,4).
К функциям можно обращаться тремя способами: из тела основной программы, из тела другой функции, из тела самой функции, т.е. функция, может вызывать саму себя. Функции называются рекурсивными, если в описании функции происходит вызов самой себя, а процесс обращения - рекурсией. Продемонстрируем использование рекурсии на примере вычисления значения факториала произвольного натурального числа N.
В математике известно рекурсивное определение факториала:
n! = 1, при n = 0;
n! = (n-1)!×n, при n > 0.
Это рекурсивное определение можно реализовать с помощью соответствующей рекурсивной функции:
function FACTORIAL(VALUE:integer):integer;
begin
iF VALUE=0 then FACTORIAL:=1
else FACTORIAL:= VALUE*FACTORIAL(VALUE-1)
end;
Теперь можно обращаться к этой функции в теле основной программы, как показано в следующем примере:
program FINDFACTORIAL;
var N:integer;
begin
writeln('Введитечисло');
readln(N);
if N<0 then writeln('Нетфакториала')
else writeln('Фактрориал',N,'равен',FACTORIAL(N))
end.
Мы видим, что характерной особенностью построенной функции является наличие в ее теле оператора присваивания.
FACTORIAL:= VALUE*FACTORIAL(VALUE-1), где происходит вызов определяемой функции. Здесь идентификатор FACTORIAL в левой части оператора обозначает имя переменной для хранения значения функции, а в правой - имя вызываемой функции.
Важным моментом при составлении любой рекурсивной функции является организация выхода из рекурсии. В некоторых простых случаях должно существовать не рекурсивное решение. Рекурсивный процесс должен шаг за шагом так упрощать задачу, чтобы в конце концов для нее появилось не рекурсивное решение. В этих функциях должны проверяться значения аргумента для принятия решения о завершении. В нашем случае условием завершения рекурсии является VALUE=0.
При описании рекурсивных функций необходимо хорошо представлять процесс вычислений. Всякая рекурсия состоит из двух этапов: углубление (погружение) внутрь рекурсии и выход из нее. На первом этапе никаких вычислений не производится, а идет только настройка рабочей формулы на конкретные операнды. На втором этапе происходит процесс вычислений по настроенным формулам.
Рассмотрим рекурсивный процесс на примере вычисления факториала для N = 3. Получим следующие шаги:
1) N = 3, где N<>0, следовательно, FACTORIAL:=3*FACTORIAL(2);
2) N = 2, где N<>0, следовательно, FACTORIAL:=2*FACTORIAL(1);
3) N = 1, где N<>0, следовательно, FACTORIAL:=1*FACTORIAL(0);
4) N =0, следовательно, FACTORIAL:=1,
т.е. получили не рекурсивное значение. Углубление в рекурсию закончено, далее пойдет процесс выхода из нее с выполнением необходимых вычислений.
В выражение 1*FACTORIAL(0) вместо FACTORIAL(0) подставляется его значение 1, вычисляется произведение 1*1 и оно становится значением FACTORIAL(1). В выражение 2*FACTORIAL(1) вместо FACTORIAL(1) подставляется значение 1, вычисляется 2*1 и становится значением FACTORIAL(2). В выражение 3*FACTORIAL(2) вместо FACTORIAL(2) подставляется значение 2, вычисляется 3*2 и становится значением переменной FACTORIAL, которая возвращает в основную программу значение 3!.
Весь этот двухэтапный рекурсивный процесс реализуется в памяти ЭВМ с помощью организации в ней стека рекурсии. Дело в том, что для хранения значений переменной N (а значит, и переменной VALUE) отводится не одна ячейка, а стек с именем N. В этот стек последовательно заносятся значения 3, 2, 1, 0, причем значение 0 есть признак конца заполнения стека. Затем начинает работать цикл с телом FACTORIAL:= FACTORIAL * N, где значения N выбираются последовательно из стека в порядке 1,2,3. Исходным же значением переменной FACTORIAL является 1, как значение 0!.
Работа стека представлена на следующей схеме:
Заполнение стека
Стек №
Вычисление
(углубление)
(разуглубление)
FACTORIAL:=1
0
FACTORIAL:=1
FACTORIAL:=1*FACTORIAL(0)
1
FACTORIAL:=1*FACTORIAL
FACTORIAL:=2*FACTORIAL(1)
2
FACTORIAL:=2*FACTORIAL
FACTORIAL:=3*FACTORIAL(2)
3
FACTORIAL:=3*FACTORIAL
В заключение покажем, что часто рекурсивные функции строятся гораздо проще, чем "обычные", хотя вполне понятно, что не всякая функция может быть переделана на рекурсивную. Сделаем это на примере уже построенной ранее функции POWER.
Данная функция явно носит рекурсивный характер, исходя из ее определения: Xn
= 1, если n = 0;
Xn
= (Xn
-1)*X, если n > 1.
function POWER(FACTOR:real; EXPONENT:integer): REAL;
begin
if EXPONENT < 0
then POWER:=1/POWER(FACTOR,abs(EXPONENT))
else if EXPONENT > 0
then POWER:= FACTOR*POWER(FACTOR,EXPONENT-1)
ELSE POWER:=1
end;
ЗАМЕЧАНИЕ. Помимо рекурсивных функций в языке Паскаль можно определять по тому же принципу и рекурсивные процедуры. Подробно о них будет сказано в следующих разделах, а пока покажем, как рекурсивная функция может быть переделана в рекурсивную процедуру на примере вычисления факториала:
procedure FACTORIAL(VALUE:integer; var F: integer);
begin
iF VALUE=0 then F:=1
else begin FACTORIAL(VALUE-1,F);
F:=F*VALUE
end;
end;
Здесь уже, в отличие от функции FACTORIAL, для вычисления N! необходимо вызвать эту процедуру с помощью оператора процедуры FACTORIAL(N,FN), где FN - переменная для возвращения из процедуры значения N!.
Скалярный тип
- простой тип данных. Скалярное данное неделимо. Массивы
- это структурированные типы данных. Массив состоит из нескольких элементов. Ко всему массиву можно обращаться по его имени. Можно обращаться к его элементу, но для этого надо задать индекс (индексы). Массивы бывают одномерные и многомерные. Для объявления массива необходимо задать типы его индексов и компонент.
Тип компонент массива - это просто тип данных, ассоциированный с каждой компонентой массива. Тип компонент может быть любым REAL, INTEGER, CHAR, BOOLEAN, перечислимым, интервальным. В качестве компоненты массива может быть взят и тип массив.
Тип индекса должен быть одним из упорядоченных типов, т.е. любым скалярным типом, кроме REAL: INTEGER, CHAR, интервальный, перечислимый. Тип индекса определяет границы изменения индекса. Если сделана попытка использовать несуществующую компоненту, то возникает ошибка (ошибка неверного индекса).
а) с помощью служебного слова TYPE описывается тип массива, а затем с помощью VAR вводится переменная этого типа;
б) с помощью слова VAR сразу описывается переменная типа массив;
Например, объявление массива из 100 элементов типа REAL можно осуществить следующими двумя способами:
а) type R100 = array[1..100] of real;
var A: R100;
б) var A: array[1..100] of real.
Здесь задан массив с именем "А" и его элементы имеют имена: А[1],..., A[100]. Чаще всего для типа индекса используют интервальный тип на основе типов INTEGER и CHAR. Однако можно в качестве индексов брать перечислимый тип.
ПРИМЕР 1. Подсчет числа вхождений букв в текст определенной длины
ПОЯСНЕНИЕ. В этом примере тип индекса есть интервальный тип на базе типа CHAR, а тип компонент есть целое число. Таким образом, элементы массива - числа, а их индексы - буквы, т.е. число элементов массива равно 26 (число букв латинского алфавита). Рассмотрим теперь случай, когда тип индекса задан перечислимым типом, а компоненты массива представлены компонентами интервального типа на базе типа INTEGER.
ПРИМЕР 2. Присваивание переменной с именем месяца числа дней этого месяца
DAY:
Значение элементов
31
28
31
30
31
30
31
31
30
31
30
31
Значение Индексов
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OKT
NOV
DEC
program NUMBRDAY;
type MONAT = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,
SEP, OKT, NOV, DEC);
var DAY: array [MONAT] of 28..31; T: MONAT;
begin
for T:= JAN to DEC do
case T of
JAN, MAR, MAY, JUL, AUG, OKT, DEC: DAY[T]:= 31;
APR, JUN, SEP, NOV: DAY[T]:= 30;
FEB: DAY[T]:= 28;
end;
end.
6.2 Многомерные массивы
Для определения позиции элемента в двумерном массиве необходимы два индекса. Любой двумерный массив есть матрица, а матрица есть таблица. Поэтому удобно описывать двумерные массивы путем указания границ изменения индексов (номеров) строк и столбцов.
Например, таблица символов M x N, где M - число строк и N - число столбцов, может быть описана:
var TAB: array[1..M, 1..N] of char.
ОБЩАЯ ФОРМА ЗАПИСИ
VAR <имя>:ARRAY [тип индекса строки, тип индекса столбца]
OF <тип компонент>;
Однако, двумерный массив можно интерпретировать как вектор-столбец, каждый элемент которого в свою очередь является одномерным массивом (вектор - строка). Этот подход к определению двумерного массива влечет его описание с помощью двух строк, где первая содержит описание строки, а вторая - описание столбца:
type LINE = array[1..N] of char;
STOLB = array[1..M] of LINE;
var TAB: STOLB.
Здесь TAB[I] - переменнаятипа LINE, а TAB[I][J] - переменная
типа CHAR.
ОБЩАЯ ФОРМА ЗАПИСИ
TYPE <тип строки>=ARRAY [тип индекса] OF <тип компонент>;
<тип столбца> = ARRAY[тип индекса] OF <тип строки>;
VAR <переменная массива>: <тип столбца(массива)>;
Эти два вида определения массивов задают и два способа обращения к элементам массива: TAB[I,J] - в первом случае и TAB[I][J] - во втором.
Вполне очевидно, что сказанное выше для двумерного массива распространяется и на массивы большей размерности. Например, описание VAR CUBE: ARRAY[1..M, 1..N, 1..K] OF INTEGER определяет задание трехмерного массива целых чисел.
Обработка массивов включает в себя, как правило, следующие компоненты: ввод массива (с клавиатуры или с помощью датчика случайных чисел), вывод полученного массива на экран и собственно его обработка. Все эти компоненты рекомендуется оформлять в виде отдельных процедур. При этом надо учитывать следующий фактор: если процедуре (или функции) будет передаваться массив, то надо объявить в ней этот массив как параметр с атрибутом VAR даже в том случае, если значение массива внутри процедуры не изменяется. Это нужно для того, чтобы не тратить времени и памяти на размещение внутри процедуры копии массива. Заметим, что параметр обязательно должен относиться к типу, имеющему имя.
ПРИМЕР 3. Сумма элементов таблицы над верхней диагональю
program SUMMA;
const M =...; {числостроктаблицы}
N =...; {числостолбцовтаблицы}
type LINE = array[1..n] of integer;
TAB = array[1..m] of LINE;
var s,i,j:integer; MAS:TAB;
procedure VVODMASSIV(var MAS:TAB);
begin
¦ for i:=1 to M do
¦ for j:=1 to N do
¦ readln(MAS[i][j]);
end;
procedure VIVODMASSIV(var MAS:TAB);
begin
¦ for i:=1 to M do
¦ begin
¦ ¦ for j:=1 to N do
¦ ¦ write(MAS[i][j]:5,' '); writeln;
¦ end;
end;
procedure OBRABOTKA(MAS:TAB; var SUM:integer);
begin
¦ SUM:= 0;
¦ for i:=1 to M do
¦ for j:=1 to N do
¦ if j > i then SUM:= SUM+MAS[i][j];
end;
begin
¦ VVODMASSIV(MAS); writeln('исходныймассив');
¦ VIVODMASSIV(MAS); OBRABOTKA(MAS,s);writeln;
¦ writeln('сумма элементов = ',s);
end.
7
. ОБРАБОТКА ЛИТЕРНЫХ ВЕЛИЧИН. ДАННЫЕ ТИПА CHAR И STRING
В Паскале, как и в других языках программирования, предусмотрена обработка текстов или строк. Для этой цели в языке существуют два типа данных: SHAR и STRING.
Типу данных CHAR соответствуют символьные константы и переменные. Символьная константа есть какой-то символ алфавита, взятый в кавычки. Символьные переменные получают значения символьных констант через оператор присваивания:
ALPFA:='p'; A:='t'; B:='3'; C:=' '; D:=''.
Все символы алфавита образуют множество литер. Каждый символ имеет свой код в ASCII. Это позволяет использовать булевские сравнения: =, <>, <, <=, >, >=.
Данные этого типа описываются с помощью служебного слова CHAR.
Например, переменную ALPFA можно описать VAR ALPFA: CHAR.
ОБЩАЯ ФОРМА ЗАПИСИ: VAR <переменная>: CHAR;
При работе с данными типа CHAR, если у нас есть последовательность символов, существуют два способа ввода этих символов с клавиатуры.
При первом способе организуется цикл с помощью одного из операторов цикла, внутри которого помещается оператор READLN. При этом способе элементы последовательности вводятся поочередно и после набора на клавиатуре символа необходимо нажать клавишу ввода ENTER. Таким образом, здесь число нажатий клавиши ENTER совпадает с числом вводимых элементов последовательности.
ПРИМЕР 1. С клавиатуры последовательно вводятся символы. Признаком конца ввода является точка. Составить программу выбрасывания групп символов, расположенных между скобками (,). Сами скобки тоже выбрасываются
program SKOBKI;
var c: char; i: integer;
begin
¦ i:=0; read(c);
¦ while c <> '.' do
¦ begin
¦ ¦ if c='(' then i:=1
¦ ¦ else if c = ')' then i:=0
¦ ¦ else if i=0 then write(c);
¦ ¦ read(c);
¦ end;
end.
ПОЯСНЕНИЕ. I = 1 означает, что ранее была прочитана левая скобка, которой пока еще не нашлось парной правой. В этой ситуации прочитанные символы не выводятся на экран. В результате работы этой программы на экране будет представлена строка символов. Здесь вся последовательность символов вводится сразу по первому оператору READ, а затем в цикле из буфера клавиатуры выбираются, анализируются и печатаются символы вне круглых скобок. Например, если вводится последовательность "asg(zx)ytr.", то экран будет выглядеть так:
asg(zx)ytr. - результат работы оператора READ;
asgytr - результат работы оператора WRITE.
В этой программе можно было бы использовать оператор READLN, но тогда после набора каждого символа необходимо нажимать клавишу ввода. Кроме того, на экран будет выводиться не строка символов, а столбец, состоящий из вводимых и отпечатанных элементов. Например, при вводе последовательности "asg(zx)ytr." экран уже будет выглядеть так:
a g x t
a | g |) | t
s | (| y | r
s z y r.
Упорядоченность символов языка используется при написании циклов с параметром, где параметр цикла может пробегать буквенные значения.
ПРИМЕР 2. Программа вывода последовательности букв:
a,ab,abc,...,abc...xyz
program SUITE; РАБОТАПРОГРАММЫ
var c,d: char; a
begin ab
for c:='a' to 'z' do abc
begin abcd
for d:='a' to c do write(d); abcde
writeln(' ');...
end; abcde...xyz
7.2 Массивы литер
В рассмотренных программах все символы вводились последовательно в процессе работы цикла или хранились временно в буфере клавиатуры. Это не всегда удобно. Поэтому в языках делают строки как последовательность литер. Строку можно задать, как массив литер, при этом в качестве длины строки может выступать верхняя граница массива. Например, VAR HAMLET: ARRAY[1..17] OF CHAR.
Здесь HAMLET - массив литер, компоненты которого имеют тип CHAR; индекс имеет нижнюю границу, равную 1, верхнюю - 17. Для ввода строки в массив HAMLET необходимо организовать цикл из 17 повторений. При каждом повторе этого цикла с клавиатуры вводится очередной символ строки и нажимается клавиша ввода:
Поскольку массивы литер являются обычными массивами, но их компоненты имеют тип CHAR, то они обладают всеми свойствами регулярных массивов. Для извлечения из массива-строки отдельного символа необходимо использовать индекс этого элемента. Например, можно вывести на экран строку HAMLET в обратном порядке с помощью следующего цикла:
for n:=17 downto 1 do write (HAMLET [n]).
ПРИМЕР 3. Дана последовательность символов CHAR: S1,S2,...,S10. Определить, совпадает ли начальная часть с ее конечной частью
program SOWPADENIE;
label 1;
type t = array[1..5] of char;
var s:t; y:char; i:integer;
begin
¦ for i:=1 to 5 do read(s[i]); readln;
¦ for i:=1 to 5 do
¦ begin
¦ ¦ read(y);
¦ ¦ if s[i] <> y then
¦ ¦ begin
¦ ¦ ¦ write('несовпадает');
¦ ¦ ¦ goto 1;
¦ ¦ end;
¦ end;
¦ write('совпадает'); 1:;
end.
ПОЯСНЕНИЕ. В данной программе сначала вводятся по циклу первые пять членов последовательности в массив S[I], причем все пять символов набираются сразу и набор завершается клавишей ввода. Затем с помощью оператора READLN очищается буфер клавиатуры, куда оператор READ(Y) заносит следующие пять символов. Во втором цикле из этого буфера поочередно выбираются символы и сравниваются с ранее введенными. Если все символы совпадают, то печатается текст 'совпадает'. В случае несовпадения печатается текст 'не совпадает' и дальнейшее считывание символов из буфера клавиатуры прекращается.
Чтобы не вводить всю вторую половину символов, а ограничиться только вводом до первого несовпадающего символа, необходимо в программе заменить оператор READ(Y) на оператор READLN(Y).
7.3 Тип данных STRING
Наряду с тем положительным, что дают нам массивы литер, они обладают существенным недостатком: их длину нельзя менять во время выполнения программы. Так в рассмотренном примере пункта 2.2 переменная HAMLET есть массив из 17 элементов и, следовательно, туда можно поместить только текст, содержащий ровно 17 символов.
Это не всегда удобно. Хотелось бы иметь такую переменную, в которую можно было бы поместить текст произвольной (но ограниченной) длины. Такую возможность предоставляет тип STRING. Здесь, объявив переменную:
var HAMLET: string[17],
можно ей путем оператора присваивания (а не через цикл) задать значение текста произвольной длины (от 0 до 17).
НАПРИМЕР:
HAMLET:= 'Быть или не быть';
HAMLET:= 'Бедный Йорик';
HAMLET:= ' '; HAMLET:= ''.
Отметим также, что при компиляции программы в случае объявления строки-массива в памяти ЭВМ резервируется место под массив, который должен быть полностью заполнен потом в процессе работы программы. Для типа STRING также резервируется место в памяти того же объема, но здесь необязательно его заполнять целиком. Незаполненные места представлены пробелами.
ОБЩАЯ ФОРМА ЗАПИСИ:
TYPE <имятипа> = STRING [N];
VAR <имя переменной>: <имя типа>;
или
VAR <имя переменной>: STRING [N];
Здесь N - целая константа, задающая максимальную длину текста.
Доступ к элементам строки производится с помощью индексов, т.к. в этом типе также все элементы имеют свой (числовой) индекс от 1 до N. В результате получается величина типа CHAR.
НАПРИМЕР: HAMLET:= 'ПРОГРАММА';
HAMLET [1] = 'П'; HAMLET [9] = 'А'.
Строковое выражение состоит из строковых (символьных) констант, переменных, указателей строковых функций и операции конкатенации (склеивания) строк, обозначаемой знаком "+". Строки можно сравнивать. В результате сравнения двух строк, получается истина только в том случае, если сравниваемые строки совпадают посимвольно и имеют одинаковую длину (принадлежат одному и тому же типу).
Текущая длина строковой переменной может быть определена с помощью встроенной функции LENGTH. Например, можно распечатать в цикле значение строки HAMLET:
for c:=1 to length(HAMLET) do write(HAMLET [c]).
Конечно, подобные циклы не надо использовать в реальных программах. Переменные типа STRING могут быть напечатаны с помощью единственного оператора WRITE или WRITELN. Для того, чтобы ввести значение типа STRING, необходимо использовать READLN или READ.
При этом, в отличие от ввода строки-массива, в типе STRING вся строка вводится целиком - клавиша ENTER нажимается один раз после последнего введенного символа.
ПРИМЕР 4. С клавиатуры вводится последовательность слов длиной в 4 символа. Напечатать эти слова, пока не встретится слово STOP.
Программа решения этой задачи зависит от способа введения слов с клавиатуры. Если слова вводятся отдельно друг от друга и после ввода слова сразу идет его печать, то это может быть реализовано с помощью следующего цикла:
repeat
readln(LINE_OF_TEXT); writeln(LINE_OF_TEXT);
until LINE_OF_TEXT = 'STOP',
где LINE_OF_TEXT есть переменная типа STRING[4].
Последовательность слов может быть введена сразу целиком, и для этого совсем необязательно вводить специальную переменную для хранения этого "длинного" слова. Здесь можно воспользоваться буфером клавиатуры для временного хранения всей последовательности слов. Оператор же READ в цикле будет "откусывать" от буфера по 4
символа, а оператор WRITELN - печатать это слово:
repeat
read(LINE_OF_TEXT);
writeln(LINE_OF_TEXT);
until LINE_OF_TEXT = 'STOP'.
Заметим, кстати, что если в программах с подобным циклом еще будут операторы READ, то рекомендуется перед ними сделать очистку буфера с помощью READLN.
Следует отметить также, что в первом случае слова можно вводить и меньшей длины, но работа завершится по набору слова STOP. Во втором случае (при наборе сплошной последовательности слов) выход из цикла будет реализован только при наличии в этой последовательности числа символов, кратных 4, из них последние 4 символа есть слово STOP.
ПРИМЕР: NUMBER:= concat('12','34','50'); NUMBER = '123450'.
2. ФункцияLENGTH
(длина).
Синтаксис: length(S: string): integer.
Возвращает длину строки S.
ПРИМЕР: N:= length('345'); N = 3.
3. Функция POS
(позиция).
Функция POS в качестве аргументов использует две строки и определяет, содержится ли первая строка во второй. Возвращает номер символа, начиная с которого S входит в T. Если вхождения нет, то возвращает 0.
Возвращает подстроку, полученную из N символов строки S, начиная с позиции N1. Значение переменной S при этом не меняется.
ПРИМЕР: FRAGMENT:= copy('PROGRAMM',2,3);
FRAGMENT = 'ROG'.
5. Процедура DELETE
(стирание фрагмента).
Убирает из строки S LEN символов, начиная с POS, при этом длина строки уменьшается на LEN позиций.
ПРИМЕР: delete(FRAGMENT,2,3);
FRAGMENT:= 'PROGRAMM'; -FRAGMENT = 'PRAMM'.
6. ПроцедураINSERT
(вставка).
Синтаксис: insert(S: string; var D: string; POS: integer).
Вставляет строку S в строку D перед символом с номером POS, при этом длина строки D увеличивается на LENGTH(S) позиций.
ПРИМЕР: insert ('ROG', FRAGMENT, 2);
FRAGMENT:= 'PRAMM'; -FRAGMENT = 'PROGRAMM'.
7. Процедура STR
(преобразование в строку).
Синтаксис: str(I: integer; var S: string);
str(R: real; var S: string).
Преобразует I или R из числа в строку и записывает эту строку в S, причем R и I могут записываться форматно, как в процедуре WRITE.
ПРИМЕР: a) R:= 123.654; str(R:5:2, S); S = '123.65';
б) I:= 5683; str(I, S); s = '5683'.
8. Процедура VAL
(преобразование в число).
Синтаксис: val(S: string; var I, J: integer).
val(S: string; var I: real; var J: integer).
Преобразует строковую переменную S в число типа I. Переменная J получает значение 0, если перевод прошел без ошибок. Если же сделана попытка конвертировать в число строку, где есть нецифровые символы, то переменная J принимает значение позиции первого нецифрового символа, при этом работа процедуры будет прервана.
ПРИМЕР: S:= '4326'; S:= '43p8';
val (S,I,J); val (S,I,J);
I = 4326, J = 0 I - не определено, J = 3.
Рассмотрим теперь пример на применение указанных функций и процедур обработки строк.
ПРИМЕР 4. Изменение порядка слов в строке
program REVERSE;
var OLD_LINE, NEW_LINE: string[50];
PROBEL: integer; WORD: string[50];
begin
¦ NEW_LINE:= ''; readln(OLD_LINE);
¦ OLD_LINE:= concat(OLD_LINE,' ');
¦ while OLD_LINE <> '' do
¦ begin
¦ ¦ PROBEL:= pos(' ', OLD_LINE);
¦ ¦ word:= copy(OLD_LINE, 1, PROBEL);
¦ ¦ NEW_LINE:= concat(WORD, NEW_LINE);
¦ ¦ delete(OLD_LINE, 1, PROBEL);
¦ end;
¦ writeln(NEW_LINE)
end.
ПОЯСНЕНИЕ. С клавиатуры вводится строка OLD_LINE и к ней справа подклеивается пробел. Это делается для того, чтобы строка имела одну и ту же структуру: слово плюс пробел. Затем в цикле, признаком конца которого является пустая константа, выделяется очередное по порядку слово и подклеивается слева в переменную NEW_ LINE. После выборки очередного слова из OLD_LINE оно оттуда выбрасывается, что приводит к постепенному уменьшению строки. Здесь переменная PROBEL служит для хранения позиции первого пробела в строке, а WORD - для выбранного из OLD_LINE слова.
Например, строка ' Наша Таня громко плачет' преобразуется в строку ' плачет громко Таня Наша'.
Тип в программировании - это множество, для которого определен некоторый набор операций над его элементами. Сами элементы множества называются объектами (или значениями) данного типа. В языке Паскаль рассматриваются различные типы данных, которые по своей организации подразделяются на отдельные виды. Прежде всего следует отметить, что все типы данных делятся на стандартные и нестандартные.
Стандартные: REAL, INTEGER, CHAR, BOOLEAN. Для каждого из этих типов рассматриваются соответствующие операции над его элементами. В Паскале имеются средства, позволяющие определять, исходя из имеющихся типов, новые нестандартные типы. Примерами таких нестандартных типов являются данные типа STRING и ARRAY, т.е. литерный тип и массивы. Массив - это упорядоченный набор данных одного типа, у каждого из которых есть индекс (номер). Способ индексации, тип элементов, длина массива содержатся в определении того типа, которому принадлежит массив:
TYPE T = ARRAY[1..20] OF REAL.
Это определение типа, имя которого T. Объектами типа T будут упорядоченные наборы по 20 элементов, имеющих тип REAL; диапазон изменения значения индекса от 1 до 20. Определив с помощью TYPE тип T, можно теперь описать некоторую переменную этого типа:
VAR А: T.
Значениями переменной "А" будут массивы длины 20, элементы которых имеют тип REAL. Для того, чтобы рассматривать эти элементы по отдельности, применяются обозначения A[1], A[2],..., A[20].
Переменная А - переменная типа T, переменные A[1],...,A[20] - переменные типа REAL. С ними можно обращаться как с обычными переменными типа REAL: X, Y, Z и т.д. В квадратных скобках необязательно должно быть целое число, им может быть произвольное выражение типа INTEGER, например: A[I], A[2*I], A[2*I-1]. Значение индекса обязано лежать в указанном диапазоне от 1 до 20. Операции над объектами типа T - это доступ к отдельным элементам массивов через индексы и изменение отдельных элементов массивов с помощью операций, связанных с типом REAL.
Итак, если в Паскаль-программе определен тип с помощью конструкции ARRAY..OF, то он называется регулярным типом. Общий вид регулярного типа есть:
type U = array [N1..N2] of R.
Тип R называется базовым по отношению к типу U. Объекты регулярного типа называются массивами. Пусть R в свою очередь определен как регулярный тип:
type R = array [M1..M2] of S;
и пусть переменная А - переменная типа U. Тогда A[I] – переменная типа R, а А[I][J] - переменная типа S. Таким образом, получается переменная, представляющая собой двумерный массив как массив массивов.
Переменные типа массив относятся к так называемым структурированным типам данных. В языке Паскаль имеются и другие структурированные типы данных, к которым принадлежит и тип данных множество. Математическое понятие множества подразумевает совокупность элементов. В отличие от массива (одномерного) множество состоит из элементов, где порядок их следования не играет роли:
{1,3,5}, {5,3,1}, {1,5,3} - одно и то же множество.
В математике для обозначения множеств используются скобки {,}. В Паскале вместо фигурных скобок для представления множеств используются квадратные: [1,3,5].
Подобно массивам, переменная типа множество имеет тип компонент. Каждый элемент, входящий в множество, имеет значение, которое должно принадлежать к типу компонент.
ОБЩАЯ ФОРМА ЗАПИСИ:
TYPE <имятипа>: SET OF <типкомпонент>;
VAR <имя переменной>: <имя типа>;
или
VAR <имя переменной>: SET OF <тип компонент>;
ПРИМЕРЫ: var LETTERS: set of 'A'..'Z';
DAYS: set of 1..31; MNOGCHAR: set of char.
Итак, мы увидели, что в описании типа множество есть общее с описанием типа массив, но есть и существенные отличия:
а) нет типа индекса (элементы множества не индексируются);
б) есть, как в массиве, тип компонент.
НАПРИМЕР:
type DAYSOFWEEK = (SUN, MON, TUE, WED, THU, FRI, SAT);
var WEEKDAYS, WEEKEND: set of DAYSOFWEEK.
Теперь этим описанным переменным можно присваивать различные значения, которые суть множества, состоящие из элементов перечислимого типа - названий дней недели:
a) WEEKDAYS:= [MON, TUE, WED, THU, FRI];
б) WEEKEND:= [SAT, SUN],
причем в случае а) можно поступить иначе: WEEKDAYS:= [MON..FRI].
Заметим также, что указанные множества из элементов перечислимого типа нельзя сформировать с помощью оператора READ (в силу специфики этого типа).
Аналогом нуля в типе множество есть пустое множество: [].
Над множествами можно производить следующие операции:
1. Определение принадлежности элемента множеству.
2. Сравнение множеств.
3. Действия над множествами.
Рассмотрим подробнее эти операции.
1. Принадлежность множеству
В языке Паскаль обеспечен механизм для определения принадлежности некоторого значения множеству его элементов. Этот механизм реализуется в рамках создания булевского выражения с использованием оператора IN. Структура применения этого оператора имеет вид:
В результате работы этого оператора получается булевское выражение. Например, выражения WED in WEEKDAYS, SAT in WEEKEND являются истинными булевскими выражениями, а выражения SAT in WEEKDAYS, MON in WEEKEND являются ложными.
Булевские выражения этого типа могут входить составной частью в различные операторы, в частности, в оператор IF.
ПРИМЕР 1. Пусть переменная DAY принимает значения всех дней недели. Тогда можно написать программу печати, где этот день недели является рабочим или днем отдыха:
for DAY:= SUN to SAT do
if DAY in WEEKDAY
then WRITELN('Сегоднярабочийдень')
else WRITELN('Сегодня день отдыха').
Заметим, что здесь перед циклом нужно определить переменную DAY как переменную перечислимого типа:
var DAY: DAYSOFWEEK.
Итак, мы видим, что на базе перечислимого типа DAYSOFWEEK можно сформировать переменную DAY и множества WEEKDAYS и WEEKEND.
Булевское выражение на базе IN можно сочетать с другими типами булевских выражений.
НАПРИМЕР:
if (DAY in WEEKEND) and (DAY <> SAT) then
writeln('Сегодня - воскресенье').
Множества имеют различные применения в организации программ.
Одним из них является упрощение написания оператора IF.
Рассмотримдвапримера:
1) if (T=0) or (T=32) or (T=212) or (T=276) then...
2) if T in [0, 32, 212, 276] then...
Эти операторы эквивалентны, но второй значительно проще.
Использование множеств позволяет улучшить наглядность и понимание алгоритма работы программы. Например, можно определить, является ли литерная переменная, именуемая ONE_CHAR, цифрой, записав: if ONE_CHAR in ['0'..'9'] then...
Действия над множествами
В Паскале, как и в математике, над множествами можно выполнять следующие логические операции:
а) объединение;
б) пересечение;
в) разность.
Рассмотрим эти операции подробно, но предварительно произведем описание:
type COUNTRIES = (ENG, FR, USA, SP, IT);
var MAP1, MAP2: COUNTRIES.
а) ОБЪЕДИНЕНИЕ (+):
[ENG, FR] + [IT]-> [ENG, FR, IT];
б) ПЕРЕСЕЧЕНИЕ (*):
[ENG, FR, USA] * [ENG, USA, IT] -> [ENG, USA];
в) РАЗНОСТЬ (-):
[ENG..IT] - [ENG..SP] -> [IT].
Эти три операции используются для построения выражений над множествами.
ПРИМЕР 2. РЕШЕТО ЭРАТОСФЕНА. Найти простые числа, не превосходящие заданного.
Алгоритм базируется на вычеркивании чисел, кратных выбранному:
program ERATOS;
const MAXPRIM = 15;
var PRIMES: set of 2..MAXPRIM;
COUNT, MULTIPLE: integer;
begin
¦ writeln('простыечисла, меньше ', MAXPRIM);
¦ PRIMES:= [2..MAXPRIM];
¦ for COUNT:= 2 to MAXPRIM do
¦ if COUNT in PRIMES then
¦ begin
¦ ¦ writeln(COUNT);
¦ ¦ for MULTIPLE:=1 to (MAXPRIM div COUNT) do
¦ ¦ PRIMES:= PRIMES-[COUNT*MULTIPLE]
¦ end;
end.
ПОЯСНЕНИЕ. Начинаем с набора множества, состоящего из всех целых чисел в интервале 2..15. Программа при помощи цикла FOR проверяет каждое целое число, входящее в множество. Если целое число является элементом множества, то оно печатается, и из множества удаляются все целые числа, кратные данному числу.
Сравнение множеств
Операция IN весьма полезна, и она позволяет, например, выяснить, являются ли два множества равными. Например, если мы хотим узнать, равны ли множества MAP1 и MAP2, то можно написать:
EGALE:= true;
for MEMBER:= ENG to IT DO
if (MEMBER in MAP1) <> (MEMBER in MAP2) then EGALE:= false.
Это громоздко, поэтому в Паскале есть булевские выражения с применением операций сравнения: =, <>, >=, <=.
НАПРИМЕР: MAP1 = MAP2;
MAP1 <> MAP2;
MAP1 - MAP2 <> [FR];
MAP1 + MAP2 <> [ENG..IT];
MAP1 >= MAP2 (eсли выражение истинно, то MAP2 есть подмножество MAP1).
При работе с множествами немаловажным является вопрос распечатки элементов множества. Отметим, что в большинстве версий языка в операторах WRITE нельзя называть переменные типа "множество". Например, нельзя распечатать множество таким образом:
VAR A: SET OF 1..9;
WRITE(A).
Здесь нет ничего удивительного, т.к. даже если А есть массив, то его тоже нельзя распечатать сразу с помощью одного оператора WRITE(А). Для вывода элементов массива организуются циклы.
Для печати элементов множества также нужно организовать цикл (однократный), внутрь которого вводится некоторая переменная, пробегающая все возможные значения этого множества, а перед оператором WRITE в рамках конструкции IF проверяется, входит ли этот элемент в конкретное множество:
if K in SET1 then write(K).
Как правило, для целей распечатки элементов множеств организуются свои процедуры. Пусть мы имеем дело с множествами, состоящими из целых чисел в границах NIZ и VERH. Зададим множественный тип TS для этих границ:
type INT = NIZ..VERH; TS = set оf INT.
Тогда можно написать процедуру, содержащую в качестве параметра множество:
procedure PRINTSET (OS: TS);
var M: INT;
begin
¦ for M:= NIZ to VERH do
¦ if M in OS then writeln(M);
end.
Теперь можно обращаться к этой процедуре для печати множеств, если только они состоят из элементов, не выходящих из интервала NIZ..VERH. Пусть в разделе констант было описано:
const NIZ = 0; VERH = 10;
тогда можно распечатать множества, обратившись к процедуре:
Обращение к процедуре можно организовать также в виде:
var SET1, SET2: TS;
SET1:= [..... ]; SET2:= [......]
PRINTSET (SET1); PRINTSET (SET1+SET2); ит.д.
ПРИМЕР 3. В заключение рассмотрим пример целиком, где продемонстрируем все те действия, которые определены над множествами:
program IGRA;
type KOST = 1..6; BROSOK = set of KOST;
var A,B,C: BROSOK;
procedure SRAWNENIE (D: BROSOK);
var K: KOST;
begin
¦ for K:= 1 to 6 do
¦ if K in D then write(K:4); writeln;
end;
begin
¦ A:= [1,3,4]; B:= [2,4,6]; C:= A + B;
¦ write('[1,3,4] + [2,4,6] ='); SRAWNENIE (C);
¦ C:= A - B;
¦ write('[1,3,4] - [2,4,6] ='); SRAWNENIE (C);
¦ C:= A * B;
¦ write('[1,3,4] * [2,4,6] ='); SRAWNENIE (C);
end.
ПОЯСНЕНИЕ. В программе определяются множества A, B, C типа BROSOK, элементами которых являются целые числа из диапазона [1..6], и процедура вывода на печать элементов таких множеств.
ЗАМЕЧАНИЕ 1. Если множество задано перечислимым типом, то его элементы напечатать нельзя. На печать можно вывести элементы только ординального типа: INTEGER, CHAR, BOOLEAN, интервальный.
ЗАМЕЧАНИЕ 2. Один и тот же набор данных можно организовать в виде линейного массива ARRAY, в виде множества SET и в виде строки типа STRING. Какой из этих видов предпочтительнее? Если над элементами (числами) производятся действия, то лучше ARRAY. Если же стоит задача о взаимосвязи элементов нескольких множеств или вопрос о вхождении каких-то объектов в множество, то лучше SET.
Ранее было рассмотрено, как удобно работать с множествами и массивами. Однако все элементы множества всегда должны иметь один и тот же тип. Хотя в ряде случаев это вызывает определенные ограничения.
Рассмотрим в качестве примера задачу заполнения анкеты с некоторыми данными, например: имя, адрес, телефон, возраст, пол, семейное положение. Каждое из этих данных имеет свой тип. Однако все эти данные взаимосвязаны, они принадлежат всегда одному человеку, и хотелось бы, чтобы все они имели общее имя. Для таких случаев Паскаль предоставляет новый, комбинированный тип переменной, а именно RECORD - запись.
Так же, как и массив, запись объединяет переменные. Однако у записи переменные могут быть различных типов! Каждая компонента записи называется полем. Каждое поле записи имеет свой тип.
Мы уже знаем, что элементы массива всегда могут использоваться как отдельные переменные. Например, определив:
type RY = array [1..10] of integer;
var A: RY,
можно писать А[1],...,A[10]. Аналогичная ситуация имеет место и для записи. Здесь также можно использовать поля записи как отдельные переменные.
ПРИМЕР: type PATIENT = record
NAME: string [20];
MALADI: string [40];
AGE: integer;
MARIE: boolean;
end;
var NEKTO:PATIENT.
Это есть описание типа RECORD. Структура записи такого типа определяется здесь с помощью всех полей между RECORD и END.
В рассмотренном выше примере всей структуре этого типа присвоено имя PATIENT (пациент). Запись типа PATIENT состоит из четырех отдельных переменных, т.е. полей, которые имеют имена: NAME, MALADI, AGE, MARIE. Каждое из этих полей имеет свой тип. В разделе TYPE описывается тип PATIENT, который затем присваивается переменной NEKTO. Именно NEKTO есть переменная типа PATIENT, т.е. переменная типа RECORD.
Чтобы обратиться к некоторым полям записи, следует написать имя переменной и имя поля. Эти два идентификатора должна разделять точка.
ПРИМЕР:
NEKTO.NAME: = 'MANUELA'; NEKTO.AGE:= 20;
NEKTO.MALADI: = 'GRIP'; NEKTO.MARIE: = true.
Отметим, что поле записи, например поле NEKTO.AGE, может рассматриваться как обычная простая переменная целого типа:
NEKTO.AGE:= NEKTO.AGE + 1. Вместе с тем, запись может рассматриваться как единое целое. Пустьимеетсяследующееописание:
type DATE = record
DAY: 1...31;
MONTH: (JAN, FEB, MAR, APR, MAY, JUN, JUL,
AUG, SEP, OCT, NOV, DEC);
YEAR: integer;
end;
var HB, MB: DATE.
Мы видим, что HB и MB имеют тип DATE. Помимо действий над отдельными полями записей HB и МB можно выполнять операции над всей записью: HB:= MB.
Это присваивание эквивалентно следующей последовательности операторов: HB.DAY:= MB.DAY;
HB.MONTH: = MB.MONTH;
HB.YEAR:= MB.YEAR.
Для переменных этого типа вводятся сравнения: " = " и " <> ".
Так в нашем случае логическое выражение МB=HB является истинным.
Так как на тип компонент массива не накладывается ограничений, то можно образовывать массивы, компонентами которых являются записи. Например, вместоVAR NEKTO: PATIENT можнозаписать VAR NEKTO: ARRAY [1..N] OF PATIENT. Тогда фамилию первого пациента можно указать как NEKTO [1].NAME. Аналогично можно задать множество дат рождений N персон VAR BD: ARRAY[1..N] OF DATE.
Отсюда мы видим, что компоненты (элементы) массива BD есть записи. Чтобы обратиться к некоторому полю определенной записи массива, следует определить имя массива, индекс интересующей записи и имя необходимого поля. Например, для печати года рождения3-й персоны необходим оператор:
WRITELN (BD[3].YEAR).
Как и в случае с массивом, на типы компонент записи не накладывается каких-либо ограничений. Поля могут быть массивами, множествами или даже записями.
При работе с записями, при обращении к различным полям каждый раз приходится писать сначала имя самой записи, что не всегда удобно, если полей много. ПоэтомувПаскалеприменяетсяоператор WITH:
with NEKTO do
begin
NAME:= 'MANUELA'; AGE:= 20;
MALADI:= 'GRIP';
MARIE:= true;
end.
Другими словами, в рамках оператора, помещенного внутри оператора WITH, к полям определенной переменной можно обращаться просто по имени (префикация имен опускается).
Особенно эффективно использовать WITH, когда речь идет о вложенных записях, т.е. таких, где поля есть тоже записи. Например, запись типа PATIENT можно расширить добавлением поля DATE, которое снова есть запись с 3-мя полями:
type PATIENT = record
NAME: string [10];
MALADI: string [30];
DATE: record
DEN: integer;
MESJATS: string [10];
GOD: integer;
end;
MARIE: boolean;
end;
var NEKTO: PATIENT.
При таком вложении доступ, например, к полю GOD уже должен сопровождаться указанием двух префиксных имен, например:
read (NEKTO.DATE.GOD).
Здесь уже WITH может значительно упростить работу с полями:
with NEKTO, DATE do
begin
NAME:= 'MANUELA'; AGE:= 20;
MALADI:= 'GRIP';
DEN:= 18;
MESJATS:= 'MART';
GOD:= 1944;
MARIE:= TRUE;
end.
Оператор WITH принято называть оператором присоединения. В общем случае он выглядит так: WITH R1, R2,..., Rn do S, что эквивалентно WITH R1 do WITH R2, R3,..., Rn do S.
Имя поля в операторе присоединения обозначает компоненту комбинированной переменной из ближайшего объединяющего оператора присоединения, в котором указана переменная с таким полем. Следовательно, если две переменные из списка комбинированных переменных оператора присоединения имеют поля, обозначенные одним и тем же именем, то внутри оператора WITH это имя обозначает поле той переменной, которая указана в списке позже.
С другой стороны, при определении некоторого комбинированного типа имена отдельных полей могут совпадать с именами обычных, простых переменных, не входящих в комбинированную переменную. Как здесь происходит отличие?
Пусть, например, имеется простая переменная AGE и поле AGE некоторой комбинированной переменной NEKTO. В этом случае их можно отличить, т.к. простая переменная имеет имя AGE, а переменная-поле имеет полное имя NEKTO.AGE. А что будет в операторе WITH, где префикс NEKTO опускается?
В этом случае в операторе предпочтение отдается именам полей записи, т.е. считается, что внутри оператора WITH соответствующее имя обозначает имя поля, а не имя переменной.
Проиллюстрируем этот тезис на примере. Пусть даны типы:
const N_STUD =...;
N_SOTR =...;
n =...;
type SEX = (M,F);
STUD = RECORD
FAM,IM,OTH: array [1..N_STUD] of string[n];
POL: SEX;
GR: 111..154;
STIP: boolean;
end;
SOTR = record
FAM,IM,OTH: array [1..N_SOTR] of string[n];
POL: SEX;
DOLGN: (LAB, ASS, STPR, DOZ, PROF);
ZARPL: integer;
end;
var X: STUD; Y: SOTR;
STIP: integer;
Тогда можно дать такой фрагмент программы:
with X, Y do
begin
IM[5]:= 'ALEXANDR ';
POL:= M;
STIP:= true;
GR:= 122;
end;
STIP:= 160.
Здесь поля IM, POL относятся к переменной Y типа SOTR, т.к. эта переменная в списке переменных-записей заголовка WITH фигурирует после переменной X типа STUD. Кроме того, в этом фрагменте имя STIP в теле оператора WITH есть имя поля переменной Х.
Записи, описанные ранее - это записи с фиксированными частями. Они имеют в различных ситуациях строго определенную структуру. Однако бывают ситуации, когда нужно отказаться от этой строгой определенности. Поэтому появляются записи с вариантами.
Рассмотрим пример создания программ для введения списка библиографических ссылок. Например, научные работы могут быть оформлены в виде монографий, т.е. книг, а могут быть и журнальные публикации. Если известно, что все публикации есть книги, то это можно задать в виде следующего описания:
const MAXNOMBRE =...
type ENTRY = record
AUTOR, TITLE, PUBLISHER, SITY: STRING [100];
YEAR: 1...9999;
end;
var REFLIST: array [1...MAXNOMBRE] of ENTRY;
Здесь ENTRY - вход, т.е. данные о какой-либо научной работе. Если же некоторые работы входят в журналы, то нужно создавать новый массив данных только для журналов и работать с этими двумя массивами, что не очень удобно. В Паскале есть возможность образовать структуру с вариантами, каждый вход которой соответствует содержанию записи. Это достигается путем введения в описание записи специального оператора CASE- переключателя, который в чем-то похож на ранее введенный, но имеет свои синтаксические и семантические отличия.
В нашем примере, помимо описанного уже типа ENTRY, вводим еще один переменный тип:
Это описание делится на две части: фиксированную и вариантную. Поля: AUTOR, TITLE и YEAR - фиксированная часть. Остальная часть - вариантная, структура которой может меняться в пределах двух вариантов. Вариантная часть записи начинается со строки CASE, где в качестве селектора выступает не выражение, а идентификатор некоторого перечислимого типа. Элементы (компоненты) этого перечислимого типа (в нашем случае ENTRYTYPE) используются в качестве альтернативного определения записи: BOOK и MAGAZINE. В каждой альтернативе имеется свой набор полей:
BOOK: MAGAZINE:
AUTOR AUTOR
TITLE TITLE
YEAR YEAR
PUBLISHER MAGNAME
CITY VOLUME
ISSUE
Для того, чтобы различать, какую из ветвей нужно выбрать для работы, в такую запись вводится так называемое поле ТЕГА (tag fild) или узловое поле. Это дополнительное поле с именем TAG имеет тип ENTRYTYPE и помещается в качестве селектора в оператор CASE - OF:
Здесь поле с именем TAG имеет тип ENTRYTYPE и принимает два значения. Если это поле имеет значение BOOK, то это ссылка на книгу, в противном случае - на журнал. Для определения составления записи с вариантами достаточно проверить значение поля TAG.
ПРИМЕР: Процедура печати значений записей типа ENTRY
procedure PRINTREF (CITATION: ENTRY);
begin
with CITATION do begin
writeln (AUTOR); writeln (TITLE); writeln (YEAR);
if TAG = BOOK then
writeln (PUB,',',CITY)
else
begin writeln (MAGNAME);
writeln (VOL,',',ISSUE)
end;
end;
end;
ЗАМЕЧАНИЯ:
1. Вариантная часть может содержать произвольное число аргументов, которые задействуются или перечислимыми типами, или произвольными порядковыми типами (интервалами).
2. Любая запись имеет только одну вариантную часть, которая должна всегда располагаться в конце описания, поэтому END оператора CASE совпадает с END всего описания.
3. Имя поля не может встречаться в двух вариантах одной записи.
4. В вариантной части могут встречаться другие новые вариантные части.
До сих пор все рассмотренные типы переменных отличались тем, что в них заранее известно число компонент и тип этих компонент. Например, массив ARRAY[1..N] OF REAL состоит из N вещественных чисел, а запись:
record
POL1: string[M];
POLN: real;
end;
состоит из N полей, каждое из которых имеет свой тип. Кроме того, характерной особенностью всех рассмотренных ранее типов данных является то обстоятельство, что все эти данные неразрывно связаны с самим текстом программы и "живут" вместе с ней. Это означает, что все данные, присущие некоторой программе, не могут быть отделены от нее и использоваться в другой программе.
Но существует класс задач, когда количество компонент (пусть одного и того же типа) заранее определить невозможно. Оно выясняется только в процессе решения задачи, т.е. во время работы программы. Поэтому возникает необходимость в таком типе значений, которые представляют собой произвольные последовательности элементов одного и того же типа, но длина этих последовательностей заранее не ограничена. Такие типы называют файловыми.
Итак, файл (FILE) представляет собой совокупность данных одинакового типа. В этом файл напоминает массив. Однако у массива с помощью индекса можно указать любой его элемент, например, A[7] - седьмой элемент. У файла же вызывать данные таким образом нельзя.
Условно файлы можно изобразить как некоторую ленту, у которой есть начало, а конец не фиксируется. Элементы файла записываются на эту ленту последовательно, друг за другом:
Файл напоминает магнитную ленту для записи мелодий, начало которой заполнено, а конец пока свободен. Новые записи помещаются в конец ленты. Прокрутить какую-то мелодию на ленте означает сделать протяжку ленты. Существует несколько разновидностей файлов, отличающихся методом доступа к ним. По способу доступа к элементам файла они бывают ПОСЛЕДОВАТЕЛЬНОГО и ПРЯМОГО доступа.
Файлы
- это единственный тип данных, посредством которого данные получаются извне (входной файл) и передаются из ЭВМ во внешний мир (выходной файл). Файлы - средство связи с внешним миром.
Файл представляет собой последовательность однотипных компонент произвольной длины. Каждый файл имеет свое имя, являющееся именем соответствующей файловой переменной, которая должна быть заявлена либо с помощью слова TYPE, либо - VAR. Для обозначения этого типа данных используется служебное слово FILE:
ПРИМЕР: a) type AZMORZE = (TOCHKA, TIRE);
MESSAGE = file of AZMORZE;
var TELEGRAM: MESSAGE;
б) var PISMO: file of char;
F: file of integer.
Здесь тип компонент может быть любым, кроме файлового типа.
Итак, в последнем примере определена F - переменная файлового типа. Это означает, что на ленте могут быть записаны только целые числа. Обратите внимание, что здесь никак не упоминается точное число элементов, которые можно записать в файл. Это можно делать постоянно, хотя в реальности лента, т.е. объем памяти, отведенной под запись файла, когда-то кончится (есть предел!!!).
По своей связи с работающей программой файлы бывают внутренними и внешними.
ВНЕШНИЕ - это файлы, имена которых включены в список заголовка программы, и которые существуют вне программы, т.е. находятся на внешних носителях (дисках). Такие файлы заполнены заранее, записаны на дискету и могут быть использованы различными программами. Как уже сказано выше, их имена должны быть объявлены в заголовке программы: program OBRABOTKA (...,MESSAGE,PISMO,...).
ВНУТРЕННИЕ - это файлы, имена которых не внесены в заголовок программы. Они существуют только во время исполнения программы. Работа с ними идет одинаково, только внутренний файл пропадает после окончания работы программы.
Мы знаем, что каждый тип Паскаля имеет свой набор операций, определенный типом компонент этого объекта. Для внутренних файлов, рассматриваемых как единое целое, никаких операций нет – ни сравнения файлов, ни операции присваивания. Можно работать только с отдельными компонентами, и эта работа зависит от типа компонент файла. Для доступа к отдельным компонентам файла в Паскале введены стандартные процедуры RESET, GET, REWRITE, PUT и функции EOLN и EOF.
Обращение к ним идет с помощью процедур-операторов. Все эти процедуры тем или иным образом связаны с установкой режима работы с заданными файлами (чтение или запись). При этом происходит следующее:
ЧТЕНИЕ - присваивание переменной значения компоненты файла;
ЗАПИСЬ - запись значения переменной в конец файла.
Для удобства описания этих действий введено понятие "окно файла" или просто "окно". Окно определяет позицию доступа, т.е. компоненту файла, которая доступна для чтения (в режиме чтения), для записи (в режиме записи). Последняя позиция файла помечается специальным образом, что определяет конец файла.
Для работы с файлами в режиме чтения и записи используются операторы REWRITE, WRITE, RESET, READ и EOF. Рассмотрим их синтаксис и назначение.
1. REWRITE(F)- установка в начальное положение режима записи.
F
^
окно
1. WRITE(F,X) - записывает в файл F (где сейчас стоит окно) очередную компоненту, равную значению выражения X, после чего окно сдвигается вправо на следующую позицию файла:
F
F1
F2
F3
®
F1
F2
F3
X
…
^
^
окно
окно
1. RESET(F) - перевод в режим чтения и установка окна на первую позицию файла.
F
^
окно
1. READ(F,V) - переменной V присваивается значение текущей позиции файла F, и окно перемещается на следующую позицию.
F
F1
F2
F3
F4
…
®
F
F1
F2
F3
F4
…
^
^
окно
окно
ПРИМЕЧАНИЕ. Файл открывается либо только для записи, либо для чтения - одновременно это делать нельзя!!!
1. При работе с файлами необходимо знать конец файла. Это делает логическая функция EOF:
EOF(F) = FАLSE, если конец файла не достигнут;
EOF(F) = TRUE - признак конца файла.
Функция EOF неразрывно связана с окном файла, которое всегда "смотрит" на одну из компонент файла. Эта функция всегда имеет определенное значение в зависимости от местонахождения окна файла. При заполнении файла последняя ее компонента всегда снабжается признаком конца. Пустой файл имеет единственную компоненту, содержащую признак конца файла.
ПРИМЕР 1. Расшифровка текста
Пусть все буквы от A до Z имеют коды от 65 до 90. Имеется файл SHIFRTEXT, состоящий из чисел от 65 до 90. Напечатать расшифрованный текст:
program RASSHIFROVKA (SHFRTXT);¦ program KODIROVKA;
type KOD = 65..90; ¦ type KOD = 65..90;
LITERA = 'A'..'Z'; ¦ SHIFR = file of KOD;
SHIFR = file of KOD; ¦ var x: KOD;
var x: KOD; ¦ SH: SHIFR;
y: LITERA; ¦ begin
SH: SHIFR; ¦ ¦ assign(SH,'shfrtxt');
begin ¦ ¦ rewrite (SH);
¦ assign(sh,'shfrtxt'); ¦ ¦ read(x);
¦ reset(SH); ¦ ¦ while x<> 00 do begin
¦ while not eof(SH) do¦ ¦ ¦ write (SH,x);
¦begin ¦ ¦ ¦
¦ ¦ read(SH,x); ¦ ¦ ¦ read(x);
¦ ¦ y:=chr(x); ¦ ¦ end;
¦ ¦ write(y); ¦ ¦ close(SH);
¦ end; close(sh); ¦ end.
end.
ПОЯСНЕНИЕ. В рассмотренном примере программа RASSHIFROVKA производит расшифровку строки числовых кодов файла SHFRTXT, сформированного с помощью программы KODIROVKA. В программе KODIROVKA предусмотрен непрерывный ввод кодов - двухзначных чисел от 65 до 90, разделяемых пробелом. Признаком конца ввода является код 00.
В обеих программах фигурируют операторы ASSIGN и CLOSE, о назначении которых речь пойдет в следующем пункте.
Мы знаем, что для чтения компоненты файла используется процедура READ(F,V). По этой процедуре выполняются два действия:
1. Копирование компоненты файла F, на которую смотрит окно, и присваивание этого значения переменной V.
2. Перемещение окна на следующую компоненту.
Однако, иногда удобно эти два действия разделить. Для этого вводится понятие буферной переменной. Она имеет имя: F^. Эту переменную не надо описывать, она определяется автоматически, как только описывается файл F. Тип F^ совпадает с типом компоненты файла. С переменной F^ можно выполнять все действия, как над данными типа компонент файла.
Если выполнена процедура RESET(F), то происходит установка окна на первую компоненту и значение этой компоненты идет в F^:
F
X
F^
^
окно
Если выполнен RESET(F), а файл F пуст, т.е. EOF(F)=TRUE, то значение F^ неопределенно. Окно файла указывает на его конец. Для передвижения окна файла и заполнения (чтения) буферной переменной используются в некоторых версиях Паскаля специальные процедуры-операторы GET и PUT:
а) GET(F) - передвижение окна на следующую компоненту и засылка значения этой компоненты в переменную F^.
F^
7
f
3
5
7
8
^
окно
после GET(F):
F^
8
f
3
5
7
8
^
окно
б) PUT(F) - запись в файл значения F^ и сдвиг вправо. Здесь до PUT(F) надо F^ присвоить очередное значение. В режиме записи значений в файл F^ служит поставщиком значений компонент. После процедуры REWRITE(F) окно устанавливается на первую компоненту, значение F^ не определено. Затем надо определить значение F^ с помощью команды присваивания: F^:=3. Если теперь написать процедуру PUT(F), то значение F^ идет в компоненту, где стоит окно, после чего значение F^ становится неопределенным:
F^
3
f
6
4
7
8
^
окно
PUT(F)
F^
f
6
4
7
8
3
^
окно
ПРИМЕР 2. Запись чисел v1 - v5 в файл BUFFER и последующий их вывод на печать
program KVADRKOREN;
var R: real; I: integer; BUFFER: file of real;
begin
¦ rewrite(BUFFER);
¦ for I:=1 to 5 do
¦ begin
¦ ¦ BUFFER^:=sqrt(I); put(BUFFER);
¦ end;
¦ reset(BUFFER);
¦ for I:=1 to 5 do
¦ begin
¦ ¦ R:=BUFFER^;
¦ ¦ get(BUFFER); writeln(R);
¦ end;
end.
ЗАМЕЧАНИЕ. В некоторых версиях процедуры GET и PUT не существуют (в частности, это имеет место для Турбо-Паскаля). Но без них можно обойтись, т.к. существуют эквивалентные им операторы READ и WRITE. Им эквивалентны следующие составные операторы:
Известно существование многих версий Паскаля, каждая из которых имеет свои особенности и отличия от стандарта Паскаля. Рассмотрим некоторые приемы работы с файлами в системах Turbo-Pascal для ПЭВМ "Ямаха" и IBM PC.
Перед началом работы с файлами (до первого обращения к файлу) должна быть выполнена процедура ASSIGN. Эта процедура отождествляет имя файла с соответствующей файловой переменной.
СИНТАКСИС: assign(var F: file; NAME: string), где NAME - имя файла на диске, F - имя файловой переменной.
После выполнения этой процедуры NAME и F отождествляются, например, ASSIGN(F,'nomfile') отождествляет файловую переменную F с его именем на диске. В качестве имени файла может быть указаноего полное имя, т.е. путь к этому файлу, например:
ASSIGN(F,'С:\WORK\ MIM\nomfile').
После окончания работы с файлом он должен быть закрыт процедурой CLOSE, иначе результат может быть потерян, т.к. директория не будет обновлена.
СИНТАКСИС: CLOSE(var F:file), где F - имя файловой переменной.
Процедуры ASSIGN и CLOSE взаимосвязаны и работают в паре друг с другом. Как уже сказано выше, перед началом работы с файлом выполняется процедура ASSIGN(F, 'nomfile'), которая для логического файла F готовит (ищет) на диске в указанной директории файл с именем NOMFILE. При окончании работы с файлом по выполнению процедуры CLOSE происходит его обновление (в случае записи) и закрытие (в случае чтения).
В программе надо уметь задавать исходные файлы. Эти файлы надо делать в цикле, используя при этом формирование компонент, либо в форме некоторого выражения по RANDOMIZE, либо задействовать обычную команду READ для ввода данных с клавиатуры. Цикл можно делать FOR, если формирование файла идет по RANDOMIZE, или WHILE (REPEAT), если файл формируется по признаку конца ввода.
Напомним, что RANDOMIZE - процедура инициализации генератора случайных величин; RANDOM - функция генерации случайных чисел.
Рассмотрим все эти особенности на примере формирования, обработки и вывода файлов.
ПРИМЕР 2. Для двух целочисленных файлов F и G одинаковой длины образовать третий целочисленный файл H, компоненты которого определяются по правилу: Hi=MAX{Fi,Gi}. В программе предусмотреть вывод на экран все трех файлов
program MAXELEM;
type FT = file of integer;
var F,G,H: FT;
I,J: integer;
procedure VIVODFILE(var A:FT);
begin
¦ reset(A);
¦ while not eof(A) do
¦ begin
¦ read(A,I); write(I:4);
¦ end; writeln;
end;
begin { формирование исходных файлов }
¦ assign(F,'F'); assign(G,'G');
¦ randomize; rewrite(F); rewrite(G);
¦ for I:=1 to 10 do
¦ begin
¦ J:= random(10)-5; write(F,J);
¦ ¦ J:= random(10)-5; write(G,J);
¦ end;
¦ VIVODFILE(F); close(F);
¦ VIVODFILE(G); close(G);
¦ assign(H,'H');
¦ { формирование файла результата }
¦ reset(F); reset(G); rewrite(H);
¦ while not eof(F) do
¦ begin
¦ ¦ read(F,I); read(G,J);
¦ ¦ if I > J then write(H,I) else write(H,J);
¦ end; VIVODFILE(H);
¦ close(H);
end.
5. Файл в данный момент времени открыт либо для чтения, либо для записи. Поэтому для добавления к файлу новых элементов необходимо сначала переписать во вспомогательный файл исходный, затем добавить к нему новые элементы. При этих двух операциях вспомогательный файл открыт для чтения. После заполнения вспомогательного файла он переписывается в исходный, при этом начальные элементы исходного файла заносятся туда во второй раз. Все эти операции представлены в виде следующей процедуры:
Среди всех файлов особое место занимают текстовые файлы. Особенностью текстовых файлов является объединение в них символов в строки. Каждая строка кончается специальным символом конца строки. Этот специальный символ (литера) не входит в стандартный тип CHAR и не имеет графического представления. Нас и не интересует вид этого символа. Главное, что с ним связана логическая функция EOLN (конец строки). EOLN(F) = TRUE, если окно указывает на признак конца строки. Заметим, что если EOLN(F) = TRUE, то при чтении элементов из файла в символьную переменную она принимает значение пробела (пробел - аналог конца строки). Для записи в файл признака конца строки служит стандартная процедура WRITELN.
Текстовые файлы, т.е. файлы с делением на строки, описываются с помощью слова TEXT, например, VAR X, D: TEXT.
ПРИМЕР 3. Определить количество строк в файле с именем BOOK
program NOMBRELINE;
var K: integer; BOOK: text; S: char;
begin { Формированиефайла BOOK }
¦ assign(BOOK,'f1'); rewrite(BOOK); read(S);
while S<> '.' do begin
¦ while S <> '#' do begin
¦ write(BOOK,S); read(S); end;
¦ writeln(book);read(S); end; close(BOOK);
¦ { Подсчет числа строк в текст; BOOK }
¦ K:= 0; reset(BOOK); writeln;
¦ while not eof(BOOK) do
¦ begin
¦ if eoln(BOOK) then K:=K+1; read(BOOK,S); write(S);
¦ end;
¦ writeln('В текстовом файле BOOK ', K,' - строк');
end.
ПОЯСНЕНИЕ. В программе сначала формируется текстовый файл, у которого строки кончаются символом "$", а сам текст – символом ".". Текст вводится с клавиатуры в виде непрерывной цепочки, например:
Наша Маша громко плачет,Уронила в речку мячик.$Тише, Машенька, не плачь,$Не утонет в речке мяч.$.
Во второй части программы с помощью функции EOLN подсчитывается число строк текста и он выводится на экран построчно, т.е. в виде:
Наша Маша громко плачет,
Уронила в речку мячик.
Тише, Машенька, не плачь,
Не утонет в речке мяч.
Итак, для записи литеры "конец строки" используется процедура WRITELN(F), где F находится в режиме записи.
T
a
g
…
c
d
^
окно
WRITELN(T):
T
a
g
…
c
d
#
^
окно
Таким образом сформированный файл легко выводится на печать построчно с помощью оператора WRITE, т.к. признак конца строки в файле иницирует переход на другую строку экрана (эффект оператора WRITELN).
В режиме чтения для работы с литерой "конец строки" есть процедура READLN. По этой процедуре окно файла устанавливается на первый элемент следующей строки файла.
T
d
…
b
c
d
#
e
f
^
окно
READLN(T):
T
d
…
b
c
d
#
e
f
^
окно
ПРИМЕР 4. Дано некоторое стихотворение в виде текстового файла ACROSTIH. Напечатать слово, образованное первыми буквами строк стихотворения (акростих)
program SLOVO(ACROSTIH); program FORMFIL;
var L:char; T: text; var F: text; S: char;
begin begin
¦ assign(T,'ACROSTIH'); ¦ assign(F,'ACROSTIH');
reset(T); ¦ rewrite(F); read(S);
¦ while not eof(T) do ¦ while S <> '?' do
¦ ¦ begin
¦ begin ¦ while S <> '#' do
¦ ¦ begin
read(T,L); write(L); ¦ write(F,S); read(S);
¦ ¦ end;
¦ readln(T); ¦ writeln(F);read(S); end;
¦ end; ¦ close(F);
end. end.
ПОЯСНЕНИЕ. Программа FORMFIL формирует текстовый файл ACROSTIH как было показано в примере 3. В программе SLOVO файл ACROSTIH выступает как внешний. Ему соответствует файловая переменная T. Оператор READLN(T) последовательно устанавливает окно файла на начало строк текста.
Файлы, как переменные величины, могут выступать в качестве аргументов и результатов при создании функций-процедур, причем эти переменные должны быть всегда оформлены как параметры-переменные, даже если файл в процедуре играет роль аргумента.
ПРИМЕР 5. Посчитать число знаков препинания в указанном текстовом файле
function PUNCTUATION(var CHARFILE: text): integer;
var SYMBOLNOMB: integer;
SYMBOL: char;
begin
SYMBOLNOMB:=0; reset(CHARFILE);
while not eof(CHARFILE) do
begin
read(CHARFILE, SYMBOL);
if SYMBOL in ['.',',',' ',':','...] then
SYMBOLNOMB:= SYMBOLNOMB + 1
end;
PUNCTUATIОN:= SYMBOLNOMB
end.
С помощью этой функции можно теперь произвести подсчет числа вхождений знаков препинания в любой текст, представленный некоторым текстовым файлом. Рассмотрим в качестве примера фрагмент программ для файла с именем FIL:
assign(FIL,'FIL');
reset(FIL);
n:=PUNCTUATION(FIL);
close(FIL);
writeln('число знаков препинания в тексте FIL =', n).
До сих пор мы рассматривали только так называемые статические программные объекты, т.е. объекты, порожденные в процессе компиляции программы и существующие в течение всего времени ее выполнения, размеры которых (объем машинной памяти для их размещения)не изменяются. Статические объекты определяются с помощью соответствующих описаний в разделе объявлений Паскаль-программ.
НАПРИМЕР:
а) с помощью описания VAR A, B: INTEGER в программе вводятся в употребление две статические переменные с именами А и В, значениями которых будут целые числа;
б) описание VAR X: ARRAY[1..10] OF REAL oпределяет (порождает) переменную регулярного типа (массив), значением которой может быть упорядоченная последовательность из десяти вещественных чисел.
Для большего понимания нового типа данных следует обратить внимание на связь между переменной и ячейкой памяти. Мы уже знаем, что вся информация хранится в оперативной памяти ЭВМ, состоящей из конечного числа пронумерованных ячеек. Эти номера называются их адресами. Поэтому, если мы говорим о переменных, то находимся в рамках программы, записанной на алгоритмическом языке.
При трансляции Паскаль-программа превращается в программу на машинном языке (в цифровых кодах), где аналогом переменной является ячейка, а имя переменной превращается в адрес ячейки. Появление этого адреса происходит в результате работы специального оператора языка (NEW), однако его значение в большинстве случаев не используется при программировании на алгоритмических языках типа Паскаль.
Условимся считать, что адрес ячейки, которая будет хранить переменную А, есть А. Или, другими словами, А - это общее имя переменной и соответствующей ячейки памяти.
Так, например, при описании VAR A, B: INTEGER в памяти ЭВМ резервируются две ячейки, которые маркируются соответственно А и В.
Будем считать, что до начала работы программы эти ячейки пусты (на самом деле они содержат "мусор" или 0). Если теперь в программе переменным А и В присвоить значения А:= 1 и В:= 2, то эти ячейки заполнятся соответствующими данными значениями.
При описании VAR X: ARRAY[1..10] OF REAL в памяти ЭВМ резервируются подряд 10 ячеек памяти, которые идентифицируются соответственно X[1], X[2],..., X[10].
Еслитеперьсделать
FOR I:= 1 TO 10 DO READ(X[I]),
то эти ячейки заполнятся десятью числами, вводимыми с клавиатуры. При упоминании в программе имен А и В фактически указывается на содержимое ячеек А и В, т.е. на значение переменных. Так, если следует оператор WRITE(A), то печатается не А, а значение переменной А, т.е. число 2.
Из этих рассуждений следует, что для таких переменных (статических) область памяти закрепляется на все время работы программы. Поэтому ячейка с адресом А всегда будет хранить только целые числа, а группа ячеек с адресами Х[1],...,X[10] - 10 вещественных чисел. Ничто другое в эти части памяти не может быть помещено.
Однако такое постоянное распределение памяти удобно для быстродействия и хорошо, когда объемы информации невелики или заранееизвестны. На практике же бывают ситуации, когда программные объекты могут возникнуть только в процессе выполнения программы или когда такие объекты известны, но их размер определится только в процессе работы программы.
Мы уже сталкивались с такой ситуацией:
CONST N =.....
VAR X: ARRAY [1..N];
или
VAR Y: STRING [N].
В последнем случае нужно указать заранее длину, что ведет к нерациональному расходу памяти, т.к. длина на практике может оказаться излишней. Для разрешения этой проблемы и вводят динамические объекты, необходимость порождения которых возникает в следующих случаях.
1. Пусть в заданном тексте из слов произвольной длины требуется найти первое по порядку слово, которое обладает некоторым свойством (не содержит, например, букву "а").
Очевидно, что такого слова может и не быть, тогда соответствующая переменная не появится, а если такое слово есть, то его длина неизвестна. Это можно сделать в рамках статической переменной, но тогда надо задать ей максимально возможную длину.
2. Бывает, что какой-то программный объект (например, массив чисел, множество, список) нужен не на все время работы программы, а только на какую-то часть. Хотелось бы после отработки данного объекта разместить на этом месте памяти другой объект.
Для работы с динамическими объектами статические переменные не подойдут, здесь предусматривается специальный тип значений - ссылочный. Значением данного типа является ссылка на какой-либо программный объект, осуществляющая непосредственный доступ к этому объекту. На машинном языке такая ссылка указывает на место памяти, т.е. адрес соответствующего объекта. А так как ссылочная переменная есть переменная, то возможно изменение значения ссылок и одна и та же переменная может указывать на любую ячейку памяти.
Итак, теперь нам предстоит иметь дело с переменными (а значит, с ячейками), которые обладают именами, но их содержимым является адрес ячейки памяти, где хранится значение некоторой другой переменной:
Имя ячейки
Такие переменные называются переменными типа указатель (переменными ссылочного типа) или просто указателями (ссылками).
Итак, слова - синонимы:
Значение указателя есть адрес объекта (ссылка на объект), посредством которого он и доступен в программе.
Итак, указываемый объект есть динамический объект. Он хранится в ячейке, которая не имеет своего собственного имени (не обозначается именем переменной), а используется лишь ссылка на эту ячейку. Здесь для сравнения можно привести ситуацию, когда называют зрителя в зале театра: "Зритель, сидящий на 3-м месте в 5-м ряду".
Обращение к динамической переменной происходит посредством указателя, являющегося статической переменной, которая имеет имя и может быть явно упомянута в программе. Динамическая переменная - "невидимая переменная", т.к. она не обозначается самостоятельным идентификатором. Память для значений такой переменной резервируется и освобождается в процессе работы программы (с помощью специальных процедур).
Как задать ссылочный тип, т.е. как описать указатель? Указатель обозначают обычным идентификатором. О том, что это указатель, говорит присутствие символа "^".
Значениями переменных такого ссылочного типа являются ссылки на динамические объекты, а сами динамические объекты имеют указанный в описании тип.
НАПРИМЕР:
TYPE MAS = ARRAY [1..100] OF INTEGER;
DINMAS = ^MAS;
VAR P: ^INTEGER; Q: ^CHAR;
RABMAS: DINMAS.
ЗДЕСЬ: P - ссылка на динамический объект целого типа, Q - ссылка на динамический объект литерного типа, RABMAS - ссылка на динамический объект, значением которого является массив из 100 чисел.
Описание переменных P и Q ссылочного типа в разделе объявлений еще не резервирует память для записи значений динамической переменной соответствующего типа.
Здесь вводятся в употребление статические переменные P и Q (транслятор резервирует место в памяти, необходимое для размещения ссылки). Пустые клетки в схеме означают, что пока переменные P и Q не имеют никаких ссылок на динамические объекты.
Для порождения самого динамического объекта (создания динамических переменных) используется стандартная процедура NEW, которая называется процедурой динамического размещения.
Это процедура с параметром - ссылочной переменной, сопоставленной порождаемому динамическому объекту.
Итак, по процедуре NEW (R) выполняется резервирование участка в определенном месте памяти для последующего размещения значений динамической переменной и помещение адреса этого участка в ссылочную переменную R. При этом выделяется столько ячеек памяти, сколько требует значение динамической переменной, на которую указывает R. Количество отводимых ячеек зависит от типа динамической переменной. Динамические переменные, созданные посредством NEW, называют указанными переменными.
ЗАМЕЧАНИЕ. Резервирование места для динамической переменной идет уже в ходе выполнения программы, а не при ее трансляции, как для статических переменных. Говорят, что NEW устанавливает водораздел между статическими и динамическими переменными.
КАРТАПАМЯТИ
MSX-DOS
Библиотека PASCAL
TURBO-система
Исходный текст программы
Объектный ход программы
Указатель ®
-----------------
Куча
ПРИМЕЧАНИЕ. Здесь указана примерная схема карты памяти при работе системы Турбо-Паскаль.
11.3 Переменные с указателями
При использовании в программе ссылочных переменных естественно возникает вопрос, как работать с динамическим объектом, т.е. как присваивать ему то или иное значение и распоряжаться им? Другими словами, как в программе на языке Паскаль ссылаться на динамический объект? Ведь мы знаем, что динамическим переменным, в отличие от статических, не дается имени в обычном понимании. Поэтому для работы с динамическим объектом в языке используется понятие "переменная с указателем".
Имя динамической переменной складывается из имени статической переменной типа указатель, поставленной в программе в соответствие данному динамическому объекту, и символа "^" после ссылочной переменной, свидетельствующего о том, что здесь речь идет не о ее значении, а о значении того программного объекта, на который эта ссылочная переменная указывает.
НАПРИМЕР:
Р - указатель: 5 ряд, 6 место,
Р^ - человек, сидящий в 5 ряду на 6 месте;
или
А - указатель,
А^ - имя динамической переменной, на которую указывает А.
Короче, А^ - переменная "старого" типа, которой можно присваивать конкретные значения.
Итак, пусть в программе содержатся:
VAR P: ^INTEGER; Q: ^CHAR;
NEW (P); NEW (Q).
Теперь в программе порождаются динамические переменные типов INTEGER и CHAR, которым с помощью оператора присваивания можно давать конкретные значения: Р^:= 58; Q^:= 'a'.
Переменная с указателями (она синтаксически играет роль динамической переменной) используется в любых конструкциях языка как обычная переменная, в зависимости от ее типа. Так, если R есть тоже переменная типа INTEGER, то синтаксически правильно написание следующих операторов присваивания:
R:= R + P^ + 2; P^:= P^ div 3.
В качестве ссылочной переменной может использоваться и более сложная конструкция, являющаяся частичной переменной, имеющей соответствующий ссылочный тип. Так, если в программе есть описания ссылочного типа TYPE REFREAL = ^REAL и переменной этого типа VAR A: ARRAY[1..50] OF REFREAL (в силу которого значением переменной А может быть массив элементов ссылочного типа, причем каждая из ссылок указывает на вещественное значение), то в качестве ссылочной переменной может фигурировать переменная с индексом, например, А[2]^ или А[K+5]^. Значением этих переменных с указателями будут вещественные числа. Иначе, определив
TYPE P = ARRAY[1..50] OF INTEGER; VAR B: ^P,
переменная В будет указателем на массив типа Р и в этом случае элементы массива обозначаются так - В^[2], B^[K+5].
ПРИМЕР 1. Поиск буквы во множестве букв и печать общих букв двух множеств
programm SETUK;
type MN = set of char;
var A,B: ^MN; C: MN; I,D: char;
begin
¦ new(A); A^:= ['a','c','o'];
¦ write('введите букву, которую надо найти:'); rеаdln(d);
¦ if D in A^ then writeln('да')
¦ else writeln('нет');
¦ new(B); B^:= ['g','c','o']; C:= A^ * B^;
¦ writeln('общие буквы множеств:');
¦ for I:= 'a' to 'z' do
¦ if I in C then write (I,' ')
end.
ПОЯСНЕНИЕ. В этой программе используются два динамических множества А и В, а также статическое множество С. Место, занимаемое в памяти под запись множеств A и B может быть освобождено после получения множества C.
ВЫВОДЫ (отличия динамической переменной от статической):
1. Вместо описания самих динамических переменных в программе дается описание указателей, поставленных в соответствие с ними.
2. В определенном месте программы должно быть предусмотрено порождение каждой из динамических переменных с помощью процедуры NEW.
3. Для идентификации значения динамической переменной используется переменная с указателем.
Значение одного указателя можно присваивать другому указателю того же типа.
Пусть объявлены переменные VAR Q, R: ^INTEGER и указатель R содержит адрес динамической переменной, значение которой равно 1, а Q - адрес динамической переменной, значение которой равно 2:
NEW(Q); NEW(R); Q^:= 2; R^:= 1.
Тогда оператор Q:= R перешлет в Q тот же адрес, что хранится в R, т.е. теперь Q будет "показывать" на то же значение (ту же ячейку памяти), что и R, а значение, на которое показывало Q раньше, будет навсегда утеряно. Этот процесс представлен схемой:
VAR Q,R:^INTEGER;
R
Q
NEW(R);
R
*
®
R^
NEW(Q);
Q
*
®
Q^
R^:=1;
R
*
®
1
R^
Q^:=2;
Q
*
®
2
Q^
Q:=R
R
*
1
R^ или Q^
Q
*
2
Потеряно
Можно присваивать значения одной динамической переменной другой, но того же типа. В этом случае значения обеих динамических переменных становятся равными, но значения указателей при этом не изменяются. Например, выполнена команда присваивания Q^:= R^, в результате получим одинаковое значение у двух переменных, как это показано на схеме:
До
После
R
*
®
1
R
*
®
1
Q
*
®
2
Q
*
®
1
Обмен значениями динамических переменных не изменяет значения ссылочных переменных. В этом случае, в отличие от оператора Q:=R, после выполнения которого Q и R "смотрят" на одну и ту же динамическую переменную, содержащую 1, каждая переменная Q и R указывает на свою динамическую переменную, хотя они обе содержат 1.
ЗАМЕЧАНИЕ. Следует различать пустой и неопределенный указатели. Так, при объявлении с помощью VARнекоторой переменной P(VARP: ^INTEGER), ее значение является неопределенным. Если же имеет место оператор NEW(P), то ссылочная переменная получает свое конкретное значение - адрес ячейки памяти соответствующей динамической переменной P^. Переменная P может получить значение без оператора NEWтолько в случае присваивания пустой ссылки P:=NIL или ссылки, уже ранее получившей свое значение с помощью оператора NEW.
Итак, никакие действия со ссылочными переменными нельзя производить до действия оператора NEW. В примере
VAR I,J: ^ INTEGER;
NEW (I);
оператор I:= J не законен, т.к. J еще не определена, но допустим оператор J:=I.
ПРИМЕР 2. Подсчет числа вхождений заданной буквы в первое по порядку слово максимальной длины из заданного текста, заканчивающегося точкой
program FINDLITER;
type MAS = array [1..100] of string[1];
LINK = ^MAS;
var R, REZSLOVO, TEKSLOVO: LINK;
max,i,k,j: integer;
S: string[100]; BUKWA: string[1];
begin
¦ max:= -1; i:= 0; new(TEKSLOVO); new(REZSLOVO);
¦ writeln('Введитетекст: '); readln(S);
repeat
¦ for j:= 1 to length(S) do
¦ begin
¦ ¦ BUKWA:= copy(S,j,1);
¦ ¦ if (BUKWA <> ' ') and (BUKWA <> '.')
¦ then begin i:= i+1;
¦ ¦ TEKSLOVO^[i]:= BUKWA; end
¦ ¦ else if i > max then
¦ ¦ begin max:= i; R:= REZSLOVO;
¦ ¦ REZSLOVO:= TEKSLOVO;
¦ ¦ TEKSLOVO:= R; end;
¦ ¦ i:=0;
¦ end;
¦ until BUKWA = '.';
¦ writeln('Введитебукву: '); read(BUKWA); k:= 0;
¦ for i:= 1 to max do
¦ if BUKWA = REZSLOVO^[i] then k:= k+1;
¦ writeln;
¦ write(' В слово максимальной длины: ');
¦ for j:= 1 to max do write(REZSLOVO^[j]); writeln;
¦ writeln (' буква ',BUKWA,' входит', k,' раз');
end.
Заметим также в заключение, что ссылки, которые указывают на идентичные типы, можно сравнивать друг с другом с помощью знаков "=" и "< >", при этом P = Q, если:
а) P = NIL, Q = NIL;
b) P и Q указывают на один и тот же динамический объект.
Мы рассмотрели вопрос, когда речь шла о действиях над ссылочными переменными (указателями). Теперь обратимся к действиям над динамическими переменными.
Как уже говорилось выше, динамические переменные призваны более рационально использовать память в процессе работы программы. Рациональность заключается, прежде всего, в том, чтобы убирать из памяти уже ненужные данные. Это достигается с помощью оператора DISPOSE, который имеет вид DISPOSE (R), где DISPOSE - имя процедуры стирания, а R - имя ссылочной переменной, указывающей на динамическую переменную R^, подлежащую удалению.
Итак, DISPOSE освобождает память для нового использования. Динамические переменные, не стертые с помощью DISPOSE, продолжают занимать место в "куче" после окончания работы фрагмента программы (становятся "мусором"), их надо убирать.
ПРИМЕР 3. Порождение и последующее стирание двух динамических объектов
program UKAZATEL;
var A,B: ^integer;
K: integer;
begin
new(A); new(B); A^:= 1; B^:= 2;
K:= A^ + B^; write(K);
dispose(B); dispose(A);
end.
ПРИМЕР 4. Нахождение в вещественном массиве RA элемента с индексом, равным значению наименьшего элемента массива IA
program MINPOISK;
type RA = array[1..10] of real;
IA = array[1..10] of integer;
PR = ^RA; PI = ^IA;
var k,i: integer;
F: PR;
G: PI;
begin
{порождение динамического массива IA, поиск в нем наименьшего элемента с последующим уничтожением}
new(G); randomize;
G^[1]:= random(12) + 6; k:= G^[1];
for i:= 2 to 10 do begin G^[i]:= random(12) + 6;
rite(G^[i],' '); if G^[i] < k then k:= G^[i] end; writeln;
writeln('Вот значение искомого индекса = ', k); dispose(G);
{порождение динамического массива RA, поиск в нем k-го элемента}
new(f); for i:= 1 to 10 do
begin F^[i]:= random(12);
write(F^[i]:5:1) end; writeln;
writeln('Искомый элемент равен ',F^[k]:5:1);
end.
ПРИМЕР 5. Нахождение наибольшего из чисел, на которые ссылаются элементы массива указателей
ЗАМЕЧАНИЕ. В отличие от примера 4, где были образованы массивы, на которые указывали соответствующие ссылки (одна ссылка на весь массив), здесь весь массив состоит из ссылок, каждой из которых соответствует свой элемент порождаемого с помощью RANDOM массива. Поэтому для уничтожения массива примера 4 понадобился всего один оператор DISPOSE, а в примере 5 уже требуется уничтожать каждый элемент массива в отдельности.
11.6 Динамические структуры данных. Обработка цепочек
Структуры данных являются важным понятием в информатике как науке, что находит свое выражение в описании любого языка программирования. Особенно это касается структурированных языков, каким является язык Паскаль. В этом языке сильно развит институт организации данных, причем для работы с этими данными имеются несколько типов данных и способов их включения в сложные структуры.
Чаще всего переменные этих типов используются самостоятельно (обособленно), однако можно создавать на их основе другие типы данных более высокого уровня сложности, которые принято называть комбинированными. Мы уже знаем пример такого типа - RECORD, позволяющего объединить в единое целое данные практически всех указанных выше типов (поля записи имеют разный тип данных).
Введение ссылочных переменных дает возможность усилить этот прием, а ссылки в сочетании с регулярными (массивами и типом STRING) и комбинированными (RECORD) типами позволяют образовать так называемые динамические структуры данных в виде цепочек, очередей, стеков, деков и пр.
С понятием "цепочка" связано понятие строки - упорядоченной последовательности данных алфавита языка. Строка - самая универсальная структура данных, с ней связаны решения многих задач.
Есть три классические задачи работы со строками:
1) поиск вхождения заданной литеры в строку;
2) вставка заданной литеры в указанное место строки;
3) исключение литеры из указанного места строки.
Решение этих задач зависит от способа представления строки:
1) векторное представление;
2) представление строки в виде цепочки с использованием ссылочного и комбинированного типов.
Сюда относятся типы STRING и символьный массив. Например, слово PASCAL можно представить двумя способами:
VAR S1: STRING[6]; S2: ARRAY[1..6] OF CHAR.
В этом случае S1[1]='P', S2[4]='C'.
Итак, мы имеем непосредственный доступ к литере, и это удобно для решения первой задачи. Сложнее обстоит вопрос с решением задачи вставки элемента в строку (или удаления из строки).
Например, в слово PASAL нужно вставить пропущенную букву C ® PASCAL. Здесь элементы, идущие за вставкой, увеличивают свои индексы, т.е. после вставки надо проводить переиндексацию программным путем. Такая же ситуация и при удалении элемента.
При вставке и при удалении длина строки меняется. Следовательно, нужно заказывать длину объекта чуть больше реального и предусматривать указатель конца строки, например, знак "#".
ПРИМЕР 6. Удаление в литерном векторе элемента, следующего за указанным индексом
program UDAL;
const N =...
var ST: array[1..N] of char;
K, IND: integer;
begin {ввод строки, последний элемент = '#'}
¦...................
¦ writeln('индекс?'); read(IND); K:=IND+1;
¦ while ST[K]<>'#' do
¦ begin ST[K]:=ST[K+1]; K:=K+1; end;
end.
Эта задача решается гораздо проще, если представить литерный вектор с помощью типа STRING и применить процедуру DELETE, однако и здесь надо заранее заказывать длину вектора.
При работе со строками важно понятие "следующий элемент". В векторном представлении оно тесно связано с местом расположения предыдущего элемента. В этом случае следующий элемент физически находится рядом с предыдущим (в соседней ячейке памяти). Однако, сплошное расположение строки в памяти не всегда удобно и эффективно. Переменные типа указатель позволяют реализовывать так называемые связанные структуры данных, среди которых наиболее распространены линейные списки - цепочки, где элемент вызывается с помощью указателя на предшествующий или последующий элементы.
Эту ситуацию можно сравнить с очередью на прием к врачу: в приемной пациенты не обязательно сидят друг за другом, но каждый субъект (элемент списка) знает, за кем или перед кем он "стоит".
При такой организации, если кто-то покидает очередь, то это не требует физического перемещения остальных: просто стоящий за ушедшим теперь запоминает другого человека (меняются ссылки).
Геометрически это можно представить так:
*
*
*
*
Исключенный элемент можно использовать для других целей.
С помощью ссылок легче вставить новую компоненту в цепочку данных. Для этого достаточно изменить две ссылки: вновь пришедший в очередь запоминает впередистоящего, а стоящий сзади теперь запоминает вновь пришедшего.
Схематически это выглядит так:
*
*
*
*
Новый элемент при этом может быть размещен в любом свободном месте памяти.
Итак, в цепочке для каждого элемента надо знать, где находится следующий. Чтобы реализовать эту идею, следует представить каждый элемент (звено) связанного списка (цепочки) в виде записи, состоящей из двух полей. В первом поле находится сам элемент (данное какого-то типа, в нашем случае - типа CHAR), второе содержит ссылку на следующее звено цепочки (тип - ссылка). Конец списка (цепочки) помечается указателем NIL, а начало формируется переменной типа указатель, содержащей ссылку на первый элемент списка.
Пусть в памяти ЭВМ находится цепочка (строка) 'PASCAL', которая инициализируется (связывается) с переменной-ссылкой STR. Это можно представить в виде схемы:
STR
*
®
P
*
®
A
*
®
S
*
®
C
*
®
A
*
®
L
Nil
1) CHAR
- для обозначения самого элемента цепочки;
2) RECORD
- для образования звеньев цепочки из двух полей;
3) ссылку (^)
- для установления связи между звеньями.
Обозначим тип ссылочной переменной через SVYAZ, а тип динамической переменной через ZVSTR (звено строки). Этот факт описывается следующим образом: type SVYAZ = ^ZVSTR. Говорят, что тип SVYAZ указывает (ссылается) на компоненты типа ZVSTR, или тип SVYAZ связан с типом ZVSTR.
Чтобы объединить динамические переменные в цепочку, надо в каждой компоненте иметь ссылку на следующую. Исходя из этого, заключаем, что тип данных ZVSTR есть запись с двумя полями - полем символьного значения ELEM и полем ссылки SLED:
type ZVSTR = record
elem: char;
sled: SVYAZ;
end.
Мы видим, что здесь при описании типов происходит перекрытие имен. Возникает вопрос, какой тип поставить первым и возможно ли это в принципе, ведь прежде чем упомянуть идентификатор, необходимо описать его тип. Однако правила языка Паскаль делают исключение при описании ссылок, поэтому допускается использование идентификатора ZVSTR до его описания:
type SVYAZ = ^ZVSTR;
ZVSTR = record
elem: char;
sled: SVYAZ;
end.
Теперь остается с помощью VAR ввести ссылочную переменную (в нашем примере STR), в которую нужно записать ссылку на первое звено цепочки. Следовательно, эта переменная также должна иметь тип SVYAZ.
Итак, VAR STR: SVYAZ.
С точки зрения техники программирования выход на цепочку осуществляется через его заглавное (нулевое) звено. Отсюда имеем:
STR - ссылочная переменная, указывающая на первое звено;
STR^- сама динамическая переменная;
STR^.elem - поле символьного значения (информационное поле);
STR^.sled - поле ссылки.
ПРИМЕР 7. Схема образования цепочки динамических данных
1. Зарезервировать место в памяти для указателей
2. Зарезервировать место в памяти для значений динамических переменных и поместить их адреса в указатели UKZV и UKSTR:
NEW(UKZV); NEW(UKSTR);
UKSTR
*
®
UKZV
*
®
3. Заполнить поля ELEM значениями UKSTR^.ELEM:='P';
UKZV^.ELEM:='A':
UKSTR
*
®
P
UKZV
*
®
A
4. Заполнить поля SLED значениями UKSTR^.SLED:=UKZV;
UKZV^.SLED:=NIL:
UKSTR
*
®
P
*
®
A
Nil
Это пример построения цепочки из двух звеньев. Если же звеньев много, то все следует делать в цикле. Рассмотрим пример образования и распечатки цепочки, состоящей из последовательности букв и заканчивающейся ".".
Несколько предварительных соображений по данному примеру:
1) для ссылки на цепочку как единое целое введен указатель UKSTR;
2) для ссылки на очередное звено в цепочке введен указатель UKZV;
3) для продвижения по цепочке от одного звена к другому нужно текущему указателю UKZV присваивать в качестве значения ссылку на это следующее звено: UKZV:= UKZV^.SLED;
4) т.к. поле SLED имеет тип SVYAZ, т.е. ссылку на запись, то можно записать UKZV^.SLED^.SLED, что означает переход на звено, находящееся через звено от исходного;
5) при организации цепочки будем использовать "нулевое" (заглавное) звено, которое указывает на первое звено цепочки и не содержит никакого элемента. Так поступают для удобства обработки цепочки в цикле.
ПРИМЕР 8. Формирование и распечатка цепочки символов
program SOZDANIE_ZEPOCHKI;
type SVYAZ = ^ZVSTR;
ZVSTR = record
elem: char; sled: SVYAZ;
end;
var UKSTR, UKZV: SVYAZ; SYM: char;
begin { Создание головного (нулевого) звена }
¦ new(UKSTR); UKZV:= UKSTR; UKZV^.sled:= nil;
¦ read(SYM);
¦ { Создание всей цепочки}
¦ while SYM <> '.' do
¦ begin
¦ ¦ new(UKZV^.sled); UKZV:= UKZV^.sled;
¦ ¦ UKZV^.elem:= SYM; UKZV^.sled:= nil;
¦ ¦ read(SYM);
¦ end;
¦ UKZV:= UKSTR^.sled; writeln; {Печатьцепочки}
¦ while UKZV <> nil do
¦ begin
¦ ¦ write(UKZV^.elem,' ');
¦ ¦ UKZV:= UKZV^.sled;
¦ end;
end.
ПРИМЕР 9. Процедура удаления из списка SP элемента, содержащего в качестве данных некоторую букву
¦ if SP = nil then writeln('Неттакогоэлемента!') else
¦ if SP^.elem <> BUKVA then UDALENIE(SP^.sled, BUKVA)
¦ else begin ZV:=SP; SP:=SP^.sled;
¦ dispose(ZV); end;
end.
ПОЯСНЕНИЕ. Данная процедура является рекурсивной. Выход из рекурсии осуществляется либо по нахождению и удалению соответствующей буквы, либо по достижению конца цепочки (обнаружение ссылки NIL). При удалении звена освобождается место в памяти с помощью DISPOSE.
Последний пример показывает, что для удаления одного элемента из цепочки достаточно применение одного оператора:
SP:= SP^.SLED.
И это действительно так, ибо устранение звена не есть его "физическое" уничтожение, а переброска ссылки на следующее звено, как это показано на схеме
SP
*
elem1
*
elem2
*
…
elemN
Nil
ПРИМЕР 10. Процедура удаления первого элемента цепочки
procedure UDALENIE_NACHALO(var SP: SVYAZ);
var Q: SVYAZ;
begin
¦ if SP^.sled <> nil then
¦ begin
¦ ¦ Q:= SP;
¦ ¦ SP:= SP^.sled;
¦ ¦ dispose(Q);
¦ end
¦ else writeln('Списокпуст!');
end.
ПОЯСНЕНИЕ. Здесь введена вспомогательная переменная Q для временного хранения ссылки на удаляемое звено, прежде чем уничтожить его с помощью DISPOSE.
Вставка нового звена в цепочку занимает уже больше операций, т.к. для этого надо сделать две переброски: одну - из предыдущего звена на новое, вторую - из нового на следующее звено. Кроме того, необходимо образовать само это звено. Названные операции видны в следующей процедуре.
ПРИМЕР 11. Процедура вставки в список элемента, содержащего в качестве данных D, после элемента, содержащего X
¦ else if SP^.elem <> X then VSTAVKA(SP^.sled,X,D)
¦ else begin
¦ ¦ new(Q); Q^.elem:= D;
¦ ¦ Q^.sled:= SP^.sled; SP^.sled:= Q
end. end;
ПОЯСНЕНИЕ. Как и в примере 9, данная процедура является рекурсивной и по ней производится сначала поиск по цепочке звена, содержащего элемент Х, а затем сама вставка (если такое звено найдено).
ПРИМЕР 12. Процедура вставки звена в начало цепочки
Информатика
- наука о способах сбора, хранения, переработки, передачи (распределения) и использования информации. Понятие "информация" является основным (базовым), и здесь можно говорить только о некоторых ее характерных чертах (сравните с понятием алгоритма, которое тоже не является определяемым).
В наиболее общем смысле информация есть неотъемлемое свойство взаимодействия систем. При любом взаимодействии систем всегда идет обмен информацией. Всякая система всегда погружена в какую-либо внешнюю информационную среду, получает из нее информацию, перерабатывает и выдает новую, которая, в свою очередь, может быть получена на входе какой-либо другой системы. Понятие системы может быть многозначным: человек, животное, робот, ЭВМ и пр.
В 40-х гг. XX в. ученый К.Шеннон попытался количественно описать информацию. Он ввел определение количества информации как меры определенности и упорядоченности. Шеннон считал, что с каждой порцией информации, полученной тем или иным объектом (системой), у объекта уменьшается неопределенность по какому-либо вопросу.
Под данными понимаются все объекты, с которыми оперирует информатика, в частности, вычислительная система, представленная комплексом аппаратных и программных средств. Вычислительные системы (или просто ЭВМ) работают под управлением программы, которую можно рассматривать как описание множества операций, применяемых к некоторым данным в некоторой последовательности. Данные, существующие во время выполнения программы, можно грубо разбить на два класса:
1. Данные программиста
- он их определяет и ими манипулирует - простые данные, массивы, файлы и пр.
2. Данные системы
- образуются для служебных целей во время выполнения программ - стеки точек возврата в процедурах, среда ссылок в динамических объектах, списки свободного пространства в памяти, сборка "мусора" и пр. Они создаются операционной системой без участия программиста.
В языках программирования существует большое разнообразие форм данных, которые может определить программист. Непосредственно с данными соприкасается понятие структуры данных, которое представляется как некоторая совокупность объектов, объединенных по какому-либо набору признаков и определенным образом связанных между собой.
Разные классы решаемых на ЭВМ задач характеризуются и разными структурами данных, что находит отражение и в соответствующих языках программирования. Каждый язык программирования ориентирован на определенный набор таких структур:
Структуры
Языки программирования
данных
РАЯ
BASIC
PASCAL
массивы
+
+
+
литеры
+
+
+
множества
-
-
+
файлы
-
+
+
списки
-
-
+
Языки, ориентированные на решение различных классов задач, используют и различные способы представления и обработки структур данных. Однако следует заметить, что любая структура данных отображается на структуру машинной памяти, которая представляет собой линейную последовательность адресуемых ячеек (байтов).
Почти все вопросы, касающиеся данных, тесно переплетаются с операциями, при помощи которых данные обрабатываются. Одним из важных вопросов по работе с данными является доступ к элементам структуры. Некоторые типы данных доступны только целиком, например, числа, логические величины и указатели (ссылки), их называют простыми элементами данных. Другие типы данных разрешают доступ к частям элемента данных, например, массивы, списки, стеки и файлы. Они называются структурированными элементами данных.
Различие между простыми и структурированными элементами данных зависит от языка и типа разрешенных операций доступа. Например, цепочка литер в некоторых языках является простым элементом данных и доступна только целиком в операциях ввода - вывода и при передаче в подпрограммы (данные типа STRING в Паскале). В других же языках индивидуально доступна каждая подцепочка внутри цепочки литер, причем последняя является структурированным элементом данных (литерный массив).
По способу доступа принято выделять структурированные элементы данных трех типов:
1. Прямого доступа. Эта структура позволяет в любой момент времени получить доступ к любому элементу (массив, индексный файл).
2. Последовательного доступа. В этой структуре доступ к произвольному N-му элементу возможен только после перебора предыдущих N-1 элементов (цепочка, файл).
3. Древовидные структуры. Данные этой структуры следуют друг за другом, образуя при этом ответвления.
4. Рассмотрим теперь по порядку существующие типы данных с указанием характерных особенностей с точки зрения расположения их в памяти, средств доступа и обработки.
Простые переменные описывают структуры, состоящие из одного элемента, поэтому каждая простая переменная характеризуется одним значением указанного типа. При отображении на память ЭВМ имени простой переменной ставится в соответствие номер (адрес) ячейки (байта) памяти, в которой хранится значение этой переменной.
Иногда оно занимает более одной ячейки (байта) памяти, но простая переменная идентифицируется с первым адресом этой цепочки ячеек.
Доступ к простой переменной осуществляется через ее имя (адрес), и характерной особенностью является то, что операция доступа и изменения выполняется над всем элементом целиком.
К простым типам данных относятся: числа (INTEGER, REAL), логические величины (BOOLEAN), символы (CHAR), цепочки литер (STRING), цепочки битов (BIT), указатели (POINTER). Последние два типа относятся к типам данных, образуемых самой системой, а не программистом.
Очевидно, что простые переменные можно условно отнести к структуре прямого доступа, т.к. всегда можно выйти на значение переменной по ее имени.
Массивы фиксированного размера являются наиболее распространенными структурами данных. Большинство языков обеспечивают такие массивы в качестве основного встроенного типа структур данных.
Как правило, представление в памяти этих массивов и доступ к ним обеспечивается аппаратурой машин с помощью индексных регистров и операций индексирования.
В языках программирования массивы фиксированного размера представляются переменными с индексами, причем в зависимости от типа индексов различают массивы одномерные, двумерные и т.д. Одномерный массив иногда называют линейной таблицей или вектором. Логически вектор организован как последовательность элементов данных, к каждому из которых возможен индивидуальный доступ с помощью целого индекса, указывающего позицию элемента в последовательности.
Значения элементов вектора хранятся физически в памяти также в виде последовательности, т.е. структура вектора однозначно отображается на структуру памяти ЭВМ. При этом индекс элемента массива означает адрес ячейки памяти, содержащей значение этого элемента, относительно адреса ячейки памяти, хранящей значение первого элемента данного массива.
Память
101
102
103
104
105
106
107
(ячейки)
Вектор Х
X[1]
X[2]
X[3]
X[4]
X[5]
X[6]
X[7]
Переменные с двумя и более индексами служат для описания многомерных массивов. Двумерный массив состоит из элементов, образующих прямоугольную таблицу. При отображении двумерного массива в память его элементы располагаются в виде последовательности (строка за строкой или столбец за столбцом).
[1,1]
[1,2]
[1,3]
[1,4]
Двумерный массив
[2,1]
[2,2]
[2,3]
[2,4]
(матрица)
[3,1]
[3,2]
[3,3]
[3,4]
[4,1]
[4,2]
[4,3]
[4,4]
Память
[1,1]
[1,2]
[1,3]
[1,4]
[2,1]
[2,2]
[2,3]
[2,4]
[3,1]
[3,2]
…
Массив как структура данных характерен тем, что с помощью индексов обеспечивается прямой доступ к любому его элементу, поэтому операции выбора элемента массива или записи в массив сводятся к вычислению значений индексов.
Данные могут поступать либо с устройства ввода в неизвестном заранее количестве, либо генерироваться внутри программы непредсказуемым образом. Для представления таких данных и манипулирования ими допускаются линейные массивы, которые способны динамически расти и сокращаться во время работы программы. Для массивов переменной размерности существуют различные виды представлений, такие как очереди, стеки, деки, списки, таблицы, деревья.
Логическая организация этих массивов близка к логической организации массивов фиксированного размера, однако, здесь использовано другое представление в памяти и другие методы доступа. При организации массивов переменного размера учитывается, прежде всего, тот факт, что они (эти массивы) могут расти и сокращаться. Поэтому здесь используются так называемые связанные представления.
Если в массиве фиксированного размера главной операцией был доступ к элементу, то здесь уже в качестве основных операций фигурируют включение новых элементов и исключение существующих. Доступ к элементам массивов чаще всего относительный: найти элемент, следующий (или предыдущий) по отношению к данному, найти первый (последний) элемент и т.д.
Очереди
- это структуры данных, организованные по принципу "первым пришел - первым ушел". Обработка элементов очереди ведется последовательно, причем элемент, который первым попал в очередь, первым обрабатывается и покидает ее. Добавление новых элементов производится в конец очереди.
Элементы, находящиеся в середине очереди, недоступны для обработки. Следовательно, доступными являются только два элемента:
первый ("голова") и последний ("хвост"). Над первым элементом выполняются операции чтения и обработки, над последним – операция записи в очередь. Для отображения очереди используются как последовательные, так и связанные представления.
Для последовательного представления можно использовать одномерный массив А[1], А[2],..., А[N], причем длина N этого массива выбирается с таким запасом, чтобы длина очереди не превышала N.
При отображении очереди на массив поступают так: первый элемент очереди хранят в первом элементе массива, а вновь поступающие записывают в следующие свободные элементы массива. После обработки первый элемент удаляется из очереди и на его место переписывается следующий за ним (второй) элемент. Это приводит к перемещению и всех следующих элементов очереди: на место второго будет переписан третий, на место третьего - четвертый и т.д. Этот способ не очень эффективен, хотя и отражает реальный процесс движения очереди.
На практике для отображения очереди применяют способ введения двух указателей (индексов), один из которых ссылается на элемент массива, хранящий "голову" очереди, а другой - на элемент массива, предназначенный для записи очередного элемента очереди ("хвост").
Пусть I - индекс элемента массива, хранящего "голову" очереди, а J - индекс первого свободного элемента массива, куда поступает новый элемент очереди ("хвост"). Тогда выборка очередного элемента очереди для обработки сводится к выполнению операций:
X:=А[I]; I:=I+1.
После этого индекс I указывает на следующий элемент очереди, т.е. "головой" ее становится следующий по порядку элемент. Запись нового элемента Y в очередь сводится к выполнению операций:
А[J]:=Y; J:=J+1.
Теперь индекс J снова указывает на первый свободный элемент массива.
Элементы очереди могут поступать и обрабатываться неравномерно, поэтому длина ее будет изменяться. В частности, возможен случай, когда очередь окажется пустой. Признаком этого может служить равенство I = J после чтения головного элемента очереди.
В процессе обработки очереди ее элементы будут смещаться к концу массива, т.к. J увеличивается после каждой записи в очередь. Поэтому возможен случай J > N после записи в очередь очередного элемента. При этом надо сместить очередь в начало массива, т.е. положить I = 1 и последовательно переписать все элементы очереди в элементы массива, начиная с А[1].
Чтобы избежать этой работы, можно замкнуть массив (очередь) по кольцу, т.е. элементом, следующим за последним элементом массива, считать его первый элемент:
I голова
.
.
.
хвост
J
.
.
.
A[1]
A[2]
A[3]
A[N-2]
A[N-1]
A[N]
При такой закольцовке просто определить переполнение очереди. Признаком этого факта является условие J = I, т.е. признак того, что "хвост" совпал с "головою" очереди.
Связанное представление очереди позволяет разбрасывать ее элементы по памяти. Здесь необходимо вместе с каждым элементом хранить указатель на местоположение следующего. Помимо этих двух указателей есть еще два дополнительных: указатели на начало и конец очереди. Последний служит для облегчения включения элементов в конец очереди.
Очередь
Указатель начала
Указатель конца
…
Стек
- это структура данных, организованная по принципу "последним пришел - первым ушел". В стеке, в отличие от очереди, доступен только один элемент, называемый вершиной стека. При записи в стек очередной элемент заносится в его вершину, а остальные продвигаются вниз без изменения порядка. При выборке из стека удаляется элемент из его вершины, а все остальные сдвигаются вверх без изменения порядка, так что в вершину попадает элемент, поступивший в стек предпоследним. Пример для аналогии: стопка книг на столе, обойма (магазин) автомата.
Для стеков используют два представления - ПОСЛЕДОВАТЕЛЬНОЕ и СВЯЗАННОЕ.
ПОСЛЕДОВАТЕЛЬНОЕ представление требует резервирования блока памяти - одномерного массива А[1], А[2],..., А[N] - по тому же принципу, что и очередь. Величина N должна быть такой, чтобы стек мог расти до своего максимального размера без переполнения блока. Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение I = 0 перед чтением из стека служит признаком его пустоты, а значение I = N перед записью в стек - признаком переполненности стека.
Представление стека в памяти:
I - вершина
.
.
.
D[K]
D[K-1]
D[3]
D[2]
D[1]
указатель
вершины стека
Связанное представление стека осуществляется путем введения указателя на местоположение следующего (предыдущего) элемента. Указатель на первый элемент стека должен находиться в указателе вершины. Включение и исключение элементов осуществляется, как показано на рисунке:
СТЕК
D0
СТЕК
D1
D0
новый элемент
D2
D1
…
D2
…
СТЕК
СТЕК
Свободное
пространство
D1
D1
D2
D2
…
…
Стек удобен для вычисления значения арифметического выражения, представленного в обратной польской (бесскобочной) записи. Такие вычисления с помощью стека реализуются, например, во многих калькуляторах. Стек используют в обращениях к процедурам, а также при реализации рекурсий в Паскале.
Линейный массив переменного размера, в котором включение и исключение элементов может выполняться в произвольных точках, обычно называется списком
(или связанным списком). Доступ к элементам списка, как правило, ограничивается первым и следующим (или иногда предыдущим) по отношению к данному. Следовательно, возможен доступ к любому элементу списка, но только путем "прокручивания" списка, начиная с первого элемента.
Поскольку вероятны произвольные включения и исключения элементов, то для списков используется только связанное представление, главным образом, две его формы:
1. Представление с одной связью: каждый элемент списка соединен со следующим; имеется указатель на первый элемент, который обычно находится в отдельной ячейке, называемой головой списка. Это представление идентично представлению очереди, рассмотренное нами ранее:
Список
С1
С2
Сn
…
Nil
0-звено
1-звено
2-звено
n-звено
(голова)
2. Представление с двумя связями: каждый элемент списка соединен с последующим и предыдущим; в голове списка имеются указатели и на первый, и на последний элементы. Такие двусвязные списки принято называть деками.
СХЕМА ПРЕДСТАВЛЕНИЯ ДВУХСВЯЗНОГО СПИСКА
Список
С1
Ук. 1-го эл-та
Ук. 2-го эл-та
С2
…
…
Сn-1
Cn
Связанное представление с одной связью имеет тот недостаток, что список можно просматривать только в одном направлении. Для движения в обе стороны нужны двусвязные списки (деки), однако они занимают много памяти (содержат две ссылки), поэтому их надо использовать, если движение в обе стороны очень необходимо.
Если последнее звено списка имеет ссылку на первое звено как на следующее, а первое звено ссылается на последнее как на предыдущее, то такой список оказывается замкнутым по кольцу и называется кольцевым.
Часто списки строят по иерархическому принципу. В этом случае его записи могут иметь внутреннюю структуру, организованную также по принципу списка (основной список оказывается состоящим из записей-подсписков). В этом случае приходят к многомерным массивам переменного размера.
Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.
Рассмотрим несколько способов упорядочивания одномерных массивов по возрастанию величин их элементов. Такая задача называется сортировкой массива.
При решении ее возможны два подхода: использование промежуточного (вспомогательного) массива и сортировка внутри самого массива.
Первый способ, хотя в какой-то степени и проще, неэффективен, т.к. требует увеличения памяти и лишних операций пересылки элементов из одного массива в другой. Поэтому рассмотрим способы сортировки внутри самого массива.
Выделяют 3 основных способа сортировки:
1. Прямое включение.
2. Прямой выбор.
3. Прямой обмен.
Каждый из перечисленных способов имеет свои достоинства и недостатки. Поэтому стараются эти способы улучшить (модернизировать), хотя в принципе все они находятся в рамках одного из указанных направлений.
Суть этого способа такова: в массиве берется i-й элемент и включается (вставляется) на свое место между 1-м и i-м элементами. Эта идея может быть выражена в виде следующего цикла:
FOR I:=2 TO N DO
BEGIN X:=A[I];
<включить X на свое место между A[1] и A[I]> END.
Из указанного видно, что на каждом шаге i все элементы с 1-го до (I-1)-го уже упорядочены, следовательно, при I = N произойдет последняя сортировка и N-й элемент встанет на свое место. Алгоритм должен быть таким, что если I-й элемент стоит в ряду, т.е. не нарушает порядка, то никаких действий совершать не надо, а следует перейти к I+1-му элементу.
Например, рассмотрим сортировку следующего массива:
-3
2
4
1
6
3
1
2
3
4
5
6
Здесь все элементы до четвертого уже упорядочены и сортировка должна произойти при I = 4. Суть метода состоит в том, что среди элементов с 1-го по 4-й ищется такой, который меньше четвертого, равного 1. В нашем случае этим элементом является первый, равный -3. В ходе поиска четвертый элемент 1 запоминается в специальной переменной X, а все элементы циклически сдвигаются на одну позицию вправо:
1-й шаг: 1<4? - да => сдвиг
-3
2
4
4
6
3
2-й шаг: 1<2? - да => сдвиг
-3
2
2
4
6
3
3-й шаг: 1<-3? - нет
-3
1
2
4
6
3
На третьем шаге сдвига не происходит и после него запомненный элемент ставится на свое место, т.е. на место второго элемента ставится четвертый из исходного массива. Поиск и сдвиг идут по циклу WHILE, в котором в качестве условия берется сравнение X < А[I-1].
Продолжая наш пример, заметим, что на пятом шаге никаких действий происходить не будет, а на шестом элемент А[6]=3 должен пойти на четвертое место, сдвигая пятый элемент на шестое место, а четвертый элемент - на пятое место:
3<6? - да => сдвиг
-3
1
2
4
6
6
3<4? - да => сдвиг
-3
1
2
4
4
6
3<2? - нет=>
-3
1
2
3
4
6
Прежде чем переходить к самой программе, заметим, что если I-й элемент должен передвинуться на 1-е место, то в нашем алгоритме для окончания процесса сдвига нужно иметь элемент слева от А[1] для сравнения (барьер). Таким элементом является А[0]. Отсюда заключаем, что в цикле FOR от 2 до N нужно для каждого шага I предусмотреть засылку в А[0] сортируемого элемента.
procedure PRVKLUCH (var MM:MAS);
var I,J,X: integer;
begin
¦ for I:= 2 to N do
¦ begin
¦ ¦ X:=MM[I]; MM[0]:=X; J:=I;
¦ ¦ while X < MM[J-1] do
¦ ¦ begin
¦ ¦ ¦ MM[J]:=MM[J-1]; J:=J-1;
¦ ¦ end;
¦ ¦ MM[J]:=X;
¦ end;
end.
Из этой процедуры видно, что выход из нее происходит тогда, когда (J-1)-й элемент становится меньше I-го элемента. Слева от I-го уже не может быть меньшего элемента, т.к. на каждом шаге все элементы до него уже отсортированы ранее в цикле FOR.
Суть метода состоит в том, что среди всех элементов массива выбирается наименьший и ставится на первое место, а элемент, занимавший первое место, перемещается на место наименьшего. Затем среди оставшихся элементов от второго до N-го проводится та же операция, а именно: среди элементов массива от второго до N-го выбирается наименьший и перемещается на второе место, а элемент, стоящий на втором месте, занимает место наименьшего.
Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.
ОБЩАЯСХЕМАПРОГРАММЫ:
for I:=1 to N-1 do
begin
¦ {Запоминание индекса и самого I-го элемента}
¦ for J:=I+1 to N do
¦ begin
¦ {Поиск минимального элемента от I+1 до N}
¦ end;
¦ {Перестановка I-го и минимального элементов}
end.
ОБЩИЙВИДПРОГРАММЫ:
procedure SELECTION (var MM:MAS);
var I,J,K,X: integer;
begin
¦ for I:= 1 to N-1 do
¦ begin
¦ ¦ { Это тело внешнего цикла }
¦ ¦ K:= I; X:= MM[I];
¦ ¦ { Внутренний цикл - поиск MIN элемента }
¦ ¦ for J:= I+1 to N do
¦ ¦ if X > MM[J] then
¦ ¦ begin
¦ ¦ ¦ { Запоминание номера и значения
¦ ¦ ¦ минимального элемента }
¦ ¦ ¦ X:= MM[J];
¦ ¦ ¦ K:= J;
¦ ¦ end;
¦ ¦ { Минимальный и I-й элементы меняются местами}
¦ ¦ MM[K]:= MM[I]; MM[I]:= X;
¦ end;
end.
Проследим работу этой программы на следующем примере:
I=0
-3
2
4
1
6
3
® исходный массив
I=1
-3
2
4
1
6
3
® 1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте
I=2
-3
1
4
2
6
3
® 2-й шаг: 2-й и 4-й поменялись местами
I=3
-3
1
2
4
6
3
® 3-й шаг: 3-й и 4-й поменялись местами
I=4
-3
1
2
3
6
4
® 4-й шаг: 4-й и 6-й поменялись местами
I=5
-3
1
2
3
4
6
® 5-й шаг: 5-й и 6-й поменялись местами
Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.
Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.
В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:
for I:= 2 to N do
for J:= N downto I do
{ Обмен местами (всплытие) более легкого элемента }
end;
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure BUBLESORT (var MM: MAS);
var I,J,X: integer;
begin
¦ for I:=2 to N do
¦ for J:= N downto I do
¦ if MM[J-1] > MM[J] then
¦ begin
¦ ¦ X:= MM[J-1];
¦ ¦ MM[J-1]:= MM[J];
¦ ¦ MM[J]:= X
end;
end.
Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:
I=2
I=3
J=6
-3
2
4
1
3
6
J=6
-3
1
2
4
3
6
J=5
-3
2
4
1
3
6
J=5
-3
1
2
3
4
6
J=4
-3
2
1
4
3
6
J=4
-3
1
2
3
4
6
J=3
-3
1
2
4
3
6
J=3
-3
1
2
3
4
6
J=2
-3
1
2
4
3
6
Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.
Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи:
1. Массив уже отсортирован (но мы не знаем об этом).
Здесь самым быстрым и эффективным следует считать метод прямого включения, т.к. никаких передвижек не произойдет (за счет цикла WHILE, который формально просто не будет работать), а останется только проход по внешнему циклу.
2. Исходный массив упорядочен по убыванию.
Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):
ПРИМЕР:
1 шаг:
8
6
4
2
0
2 шаг:
0
6
4
2
8
Результат:
0
2
4
6
8
3. Массив дан случайным образом.
Здесь два метода - "включение" и "выбор" - равнозначны. Метод "пузырька" наиболее медленный из всех. Здесь при каждом проходе чаще всего идет обмен соседних элементов. Даже в случае уже отсортированного массива, хотя сами перестановки и не совершаются, внутренний цикл сравнивает все соcедние элементы.
Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.
Суть метода - в середине массива выбирается некоторый граничный элемент, разбивающий весь массив на левую и правую части. Производится одновременное движение слева и справа; если слева находится элемент, больший граничного, то они меняются местами и поиск таких элементов продолжается дальше до границы. Подобная операция повторяется отдельно с левой и правой частями и т.д.
Эта идея приводит к тому, что нужно построить процедуру, которая допускает обращение самой к себе, т.е. рекурсивную процедуру, имеющую входными параметрами номера элеметов:
1-ый - левый элемент: L,
2-ой - правый элемент: R.
На начало процедуры эти параметры должны получить значения:
L = 1; R = N.
В процедуре используется цикл REPEAT по сближению левой и правой границ.
procedure QUICKSORT (L, R: integer; var M: MAS);
var I,J,W,X: integer;
begin
¦ {Установка границ, от которых идет движение к середине}
¦ I:= L; J:= R;
¦ {Выбор граничного элемента}
X:= M[(L+R) div 2];
¦ repeat
¦ ¦ { Поиск слева элемента, большего X }
¦ ¦ while X > M[I] do I:= I+1;
¦ ¦ { Поиск справа элемента, меньшего X }
¦ ¦ while X < M[J] do J:= J-1;
¦ ¦ if I <= J then
¦ ¦ begin
¦ ¦ ¦ W:= M[I]; {Обменместами
¦ ¦ ¦ M[I]:= M[J]; I-гои J-го
¦ ¦ ¦ M[J]:= W; элементов,
¦ ¦ ¦ I:=I+1; дальнейшее продвижение
¦ ¦ ¦ J:=J-1; вперед (назад)}
¦ ¦ end;
¦ ¦ {Выход из цикла, если левый край перевалил за правый}
¦ until I > J;
¦ { Повтор обмена для левой части }
¦ if L < J then QUICKSORT (L,J,M);
¦ { Повтор обмена для правой части }
¦ if R > i then QUICKSORT (I,R,M);
¦
end;
ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:
6
4
3
2
7
1
5
1
2
3
4
5
6
7
Здесь имеем значения L=1; I=1; J=7; R=7. Цикл WHILE X > M[I] при Х = 2 дает сразу же отказ и значение I остается старым, т.е. I = 1. Цикл WHILE X < M[J] при Х = 2 дает J = 6. Сравнение IF I <= J дает 1 <= 6, т.е. истина, отсюда идет обмен между I-м и J-м элементами - первый элемент 6 меняется местом с шестым элементом 1:
1
2
3
4
7
6
5
1
2
3
4
5
6
7
и индекс I (J) увеличивается (уменьшается):
I:=I+1, т.е. I = 2;
J:=J-1, т.е. J = 5.
Сравнение I > J, т.е. 2 > 5, является ложным, поэтому идет возврат наверх. Циклы WHILE доводят значения переменной I до 2, а значение J становится равным 4. Так как I=2 <= J=4, то идет обмен между 2-м и 4-м элементами:
1
2
3
4
5
6
7
1
2
3
4
5
6
7
и индексы получают значения: I = 3, J = 3.
При таких значениях индексов имеем M[I]=M[J]=3, что в результате работы циклов WHILE дает I=3 и J=2. Сравнение I<=J будет ложным, поэтому обмена элементов нет, кроме того, становится истинным условие проверки окончания работы цикла REPEATE (I>J) и происходит переход на рекурсивное обращение к самой процедуре.
Из двух условий истинным является первое (сравнение L < J дает 1< 2), поэтому идет обращение к процедуре при параметрах L=1 и R=2. Однако для этих праметров упорядочивание уже произошло. Затем формируется отрезок [3,7], где происходит обмен между 5-м и 7-м элементами:
1
2
3
4
5
6
7
1
2
3
4
5
6
7
В результате этой работы массив уже упорядочен, однако затем формируются отрезки [3,6] и [5,6], при которых никаких обменов не происходит, но параметры I, J получают значения: I=6, J=4. Ни одно из сравнений L<J (5<4) и R>I (6>6) не является истинным, поэтому рекурсия завершается и процедура заканчивает свою работу.
ЗАМЕЧАНИЕ. Данная процедура очень медленно обрабатывает уже упорядоченный массив.
14.
СТРУКТУРЫ ПОСЛЕДОВАТЕЛЬНОГО ДОСТУПА. ЛИНЕЙНЫЕ СПИСКИ
Наиболее простыми динамическими структурами данных являются линейные списки. Мы уже познакомились ранее с примером такого списка: цепочка. Существуют цепочки с нулевым звеном и без него. Характерной особенностью цепочки является то, что при ее формировании очередной элемент всегда записывается в конце, а добавление и исключение элементов производится в любом ее месте. Однако это не всегда удобно для работы, поэтому цепочки организуют специальным образом, в результате чего образуются структуры специального вида: очереди, стеки, деки.
Итак, рассмотрим теперь более подробно эти виды динамических структур.
14.1 Очередь
Очередь
- это линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) - на другом. Очередь иногда называют циклической памятью или списком типа FIFO (от первых букв английской фразы "First Input First Output"): первым включается - первым исключается.
При работе с очередью мы говорим о ее начале и конце – объекты вставляются в конце очереди и удаляются в начале:
ИСКЛЮЧИТЬ
ВКЛЮЧИТЬ
*
®
*
®
*
®
*
НАЧАЛО
ВТОРОЙ
ТРЕТИЙ
КОНЕЦ
Для характеристики работы с очередью необходимо рассмотреть процедуры ее формирования, добавления, исключения элементов.
Условимся в дальнейшем, что будем составлять линейные списки, элементами которых будут числа типа INTEGER. Очевидно, что для организации этих данных необходимо задать описание:
type SS = ^ZVENO;
ZVENO = record
elem: integer;
next: SS;
end.
Рассмотрим сначала алгоритм формирования очереди. Для этого введем три указателя - на начало очереди, на ее конец и текущий указатель:
VAR L: SS; {начало очереди}
R: SS; {конец очереди}
K: SS; {рабочий указатель}
el1,el2: integer;{рабочие элементы}
Алгоритм формирования очереди представлен на следующей схеме:
ОПЕРАТОРЫ
ПОЯСНЕНИЕ
new(K);
el:=random(10);
K
*
el
nil
K^.next:=nil;
K^.elem:=el;
L:=K;
L
*
K
*
el
nil
R:=K;
R
*
el:=random(10);
while el<>0
do begin
K
*
el
nil
new(K);
K^.elem:=el;
K^.next:=nil;
L
*
el
*
R^.next:=K;
R
*
K
el
nil
R:=K;
L
*
el
*
R
*
el
nil
el:=random(10); end;
K
Запишем теперь полностью процедуру формирования очереди:
procedure FORMIR_OTCHERED_1 (var L, R: SS);
var K: SS; EL: integer;
begin
¦ { Формирование первого звена очереди }
¦ randomize; EL:= random(10);
¦ new(K); L:= K; R:= K;
¦ K^.elem:= EL; K^.next:= nil;
¦ EL:= random(10);
¦ { Помещение очередного элемента в очередь }
¦ while EL <> 0 do
¦ begin
¦ ¦ new(K);
¦ ¦ K^.elem:= EL; K^.next:= nil;
¦ ¦ R^.next:= K; R:= K;
¦ ¦ EL:= random(10);
¦ end;
end.
ЗАМЕЧАНИЕ. Из программы видно, что L всегда хранит начало очереди, а R - ее конец. Процедура имеет два возвращаемых параметра, которые идентифицируют получаемую с ее помощью очередь. Первый параметр L позволяет начать просмотр очереди или удалить из нее элемент, а второй R - добавить новый элемент (согласно правилу работы с очередями).
Заметим также, что эта процедура формирует очередь из однозначных чисел и признаком конца очереди является число 0. Она предполагает формирование пустой очереди, состоящей из одного нулевого звена:
L,R
*
0
nil
Если пустой очередью считать очередь без единого звена, то процедура принимает вид:
procedure FORMIR_OTCHERED_2 (var L, R: SS);
var K: SS;
EL1, EL2: integer;
begin
¦ {Формирование первого звена очереди }
¦ randomize; EL1:= random(10);
¦ if EL1= 0 then begin L:= nil; R:= L end
¦ else begin new(K);
¦ L:= K; R:= K; K^.next:= nil;
¦ K^.elem:= EL1;
¦ { Помещение очередного элемента в очередь }
¦ EL2:=random(10);
¦ while EL2<>0 do
¦ begin
¦ new(K);
¦ K^.elem:= EL2; K^.next:= nil;
¦ R^.next:= K; R:= K; EL2:= random(10);
¦ end; end;
end.
Одним из приемов работы с очередями является доступ к ее элементу, в частности, сравнение элемента с каким-то числом или вывод его на печать. Исходя из идеологии построения очереди видно, что выборка любого элемента, как и в файле последовательного доступа, возможна только путем просмотра всех элементов очереди, начиная с ее начала. Это легко сделать, зная ссылки на начало и конец очереди. Наличие двух ссылок очень удобно для просмотра очереди (поиска нужного элемента или вывода его на печать). Действительно, в этом случае достаточно организовать цикл с изменением некоторой ссылочной переменной от значения L до значения R.
Таким образом, если необходимо обработать очередь, то следует указать для нее две переменные, где хранятся ссылки на начало и конец. Эти переменные берутся либо непосредственно из программы формирования очереди, либо как выходные параметры процедуры формирования, рассмотренной выше. Ниже следует процедура распечатки элементов очереди, сформированной процедурой пункта 14.1.1:
procedure VIVOD_OTCHERED (var L, R: SS);
var K: SS;
begin
¦ if (L^.elem= 0) or (L= nil) then
¦ writeln('Очеpедьпуста ! ')
¦ else begin
¦ ¦ K:= L;
¦ ¦ write('Элементы очереди: ');
¦ ¦ while K <> R^.next do
¦ ¦ begin
¦ ¦ ¦ write (K^.elem, ' ');
¦ ¦ ¦ K:= K^.next;
¦ ¦ end;
¦ end;
end.
ЗАМЕЧАНИЕ. В данной процедуре знание ссылки R на конец очереди совсем не обязательно. Здесь можно обойтись только ссылкой на начало, а в цикле WHILE в качестве условия взять сравнение значения переменной K с NIL: WHILE K <> NIL.
Добавление нового звена EL к очереди происходит справа (используется указатель R). Рассмотрим сначала алгоритм: