 |
Динамические структуры данных
|
|
|
|
Формы представления алгоритмов.
На практике наиболее распространены следующие формы представления алгоритмов:
· словесная (записи на естественном языке);
· графическая (изображения из графических символов);
· псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
· программная (тексты на языках программирования).
Понятие типа данных в Турбо Паскаль
Для обработки ЭВМ данные представляются в виде величин и их совокупностей. С понятием величины связаны такая важная характеристика, как ее тип.
Тип определяет:
- возможные значения переменных, констант, функций, выражений, принадлежащих к данному типу;
- внутреннюю форму представления данных в ЭВМ;
- операции и функции, которые могут выполняться над величинами, принадлежащими к данному типу.
В языке Паскаль тип величины задают заранее. Все переменные, используемые в программе, должны быть объявлены в разделе описания с указанием их типа. Обязательное описание типа приводит к избыточности в тексте программ, но такая избыточность является важным вспомогательным средством разработки программ и рассматривается как необходимое свойство современных алгоритмических языков высокого уровня.
Иерархия типов в языке Паскаль такая:
- Простые
- Порядковые
- Целые
- Логические
- Символьные
- Перечисляемые
- Интервальные
- Вещественные
- Структуированные
- Массивы
- Строки
- Множества
- Записи
- Файлы
- Указатели
Простые типы данных
В таблице приведены простые типы данных Турбо Паскаль, объем памяти, необходимый для хранения одной переменной указанного типа, множество допустимых значений и применимые операции.
|
|
|
| Идентификатор | Длина (байт) | Диапазон значений | Операции |
| Целые типы | |||
| integer | -32768..32767 | +, -, /, *, Div, Mod, >=, <=, =, <>, <, > | |
| byte | 0..255 | +, -, /, *, Div, Mod, >=, <=, =, <>, <, > | |
| word | 0..65535 | +, -, /, *, Div, Mod, >=, <=, =, <>, <, > | |
| shortint | -128..127 | +, -, /, *, Div, Mod, >=, <=, =, <>, <, > | |
| longint | -2147483648..2147483647 | +, -, /, *, Div, Mod, >=, <=, =, <>, <, > | |
| Вещественные типы | |||
| real | 2,9x10-39 - 1,7x1038 | +, -, /, *, >=, <=, =, <>, <, > | |
| single | 1,5x10-45 - 3,4x1038 | +, -, /, *, >=, <=, =, <>, <, > | |
| double | 5x10-324 - 1,7x10308 | +, -, /, *, >=, <=, =, <>, <, > | |
| extended | 3,4x10-4932 - 1,1x104932 | +, -, /, *, >=, <=, =, <>, <, > | |
| Логический тип | |||
| boolean | true, false | Not, And, Or, Xor, >=, <=, =, <>, <, > | |
| Символьный тип | |||
| char | все символы кода ASCII | +, >=, <=, =, <>, <, > |
Тип переменной и тип выражения должны совпадать кроме случая, ког- да выражение относится к целому типу, а переменная - к действительно- му. При этом происходит преобразование значения выражения к действительному типу.
4. Оператор выбора позволяет выбрать одно из нескольких возможных продолжений программы. Параметром, по которому осуществляется выбор, служит ключ выбора -выражение любого порядкового типа (любого из рассмотренных, кроме типов REAL и STRING, см. гл. 4).
Структура оператора выбора такова:
CASE <ключ_выбора> OF <список_выбора> [ELSE <операторы>] END
Здесь CASE, OF, ELSE, END - зарезервированные слова (случай, из, иначе, конец);
<ключ_выбора> - ключ выбора;
<список_выбора> - одна или более конструкций вида:
<константа_выбора>: <оператор>;
<константа_выбора> - константа того же типа, что и выражение<ключ_выбopa>;
<операторы> - произвольные операторы Турбо Паскаля.
Оператор выбора работает следующим образом. Вначале вычисляется значение выражения <ключ_выбора>, а затем в последовательности операторов <список_выбора> отыскивается такой, которому предшествует константа, равная вычисленному значению. Найденный оператор выполняется, после чего оператор выбора завершает свою работу. Если в списке выбора не будет найдена константа, соответствующая вычисленному значению ключа выбора, управление передается операторам, стоящим за словом ELSE. Часть ELSE <оператор> можно опускать. Тогда при отсутствии в списке выбора нужной константы ничего не произойдет и оператор выбора просто завершит свою работу.
|
|
|
Любому из операторов списка выбора может предшествовать не одна, а несколько констант выбора, разделенных запятыми. Например, следующая программа при вводе одного из символов: у или Y выведет на экран слово «Да», а при вводе n или N - слово «Нет»:
5. Операторы повторений
В языке Турбо Паскаль имеются три различных оператора, с помощью которых можно запрограммировать повторяющиеся фрагменты программ.
Счетный оператор цикла FOR имеет такую структуру:
FOR <пар_цик>:= <нач_знач> ТО <кон_знач> DO <оператор>.
Здесь FOR, TO, DO - зарезервированные слова (для, до, выполнить);
<пар_цик> - параметр цикла - переменная типа INTEGER (точнее, любого порядкового типа, см. гл.4);
<нач_знач> - начальное значение - выражение того же типа;
<кон_знач> - конечное значение - выражение того же типа;
<оператор> - произвольный оператор Турбо Паскаля.
При выполнении оператора FOR вначале вычисляется выражение <нач_знач> и осуществляется присваивание <пар_цик>: = <нач_знач>. После этого циклически повторяется:
- проверка условия <пар_цик> <= <кон_знач>; если условие не выполнено, оператор FOR завершает свою работу;
- выполнение оператора <оператор>;
- наращивание переменной <пар_цик> на единицу.
В качестве иллюстрации применения оператора FOR рассмотрим программу, осуществляющую ввод с клавиатуры произвольного целого числа N и вычисление суммы всех целых чисел от 1 до N
6. Это массивы -формальное объединение нескольких однотипных объектов (чисел, символов, строк и т.п.), рассматриваемое как единое целое. К необходимости применения массивов мы приходим всякий раз, когда требуется связать и использовать целый ряд родственных величин. Например, результаты многократных замеров температуры воздуха в течение года удобно рассматривать как совокупность вещественных чисел, объединенных в один сложный объект - массив измерений.
|
|
|
При описании массива необходимо указать общее число входящих в массив элементов и тип этих элементов. Например:
var
а: array [1..10] of Real;
b: array [0..50] of Char;
с: array [-3..4] of Boolean;
Как видим, при описании массива используются зарезервированные слова ARRAY и OF (массив, из). За словом ARRAY в квадратных скобках указывается тип-диапазон, с помощью которого компилятор определяет общее число элементов массива. Тип-диапазон (подробнее см. в гл.4) задается левой и правой границами изменения индекса массива, так что массив А состоит из 10 элементов, массив В - из 51, а массив С - из 8 элементов. За словом OF указывается тип элементов, образующих массив.
Доступ к каждому элементу массива в программе осуществляется с помощью индекса - целого числа (точнее, выражения порядкового типа, см. гл.4), служащего своеобразным именем элемента в массиве (если левая граница типа-диапазона равна 1, индекс элемента совпадает с его порядковым номером). При упоминании в программе любого элемента массива сразу за именем массива должен следовать индекс элемента в квадратных скобках, например:
var
a: array [1..10] of Integer;
b: array [0..40] of Char;
c: array [-2..2] of Boolean;
k: Integer; begin
b[17]:= 'F1;
c[-2]:= a[l] > [2];
for k: = 1 to 10 do a[k]:= 0;
...
end.
В правильно составленной программе индекс не должен выходить за пределы, определенные типом-диапазоном. Например, можно использовать элементы А[1], В[38], С[0], но нельзя A[0] или С[38] (определение массивов см. выше). Турбо Паскаль может контролировать использование индексов в программе на этапе компиляции и на этапе счета программы.
Для иллюстрации приемов работы с массивами составим программу (пример 2.9), которая создает массив случайных целых чисел, подсчитывает их среднее арифметическое, а также определяет и выводит на экран минимальное и максимальное из этих чисел.
7. Сортировка заключается в перестановке элементов массива в порядке возрастания или убывания их значений. Методы сортировки основаны на сравнении элементов массива в проверяемой части и перестановке наибольшего, либо наименьшего элемента в начало, либо в конец этой части массива. Процесс перестановок повторяется до полного упорядочения значений элементов массива. Известно несколько методов сортировки, обладающих различной эффективностью при решении конкретных задач. Пусть заданы значения элементов массива "X". Приведем алгоритмы и блоки операторов, выполняющие некоторые наиболее распространенные методы сортировки.
|
|
|
Сортировка выбором основана на определении наибольшего (наименьшего) элемента, который переносится в начало или конец массива в зависимости от вида сортировки (по возрастанию или по убыванию). Затем эта процедура применяется ко всем оставшимся элементам, кроме уже перемещенных элементов, всего (N - 1) раз. Приведем пример операторов для сортировки элементов массива “Х” по возрастанию:
for j: = 1 to N-1 do begin { цикл по числу "проходов" }
k:= N-j+1; { k - номер последнего элемента в проверяемой части массива }
m:= k; { m - номер элемента с наибольшим значением }
for i:= 1 to N-j do {цикл сравнения элементов в оставшейся части массива}
if x[i] > x[m] then m: = i; { запоминаем значение "m" }
b:= x[k]; x[k]:= x[m]; x[m]:= b { переставляем элементы }
end;
Здесь полагается, что последний элемент, расположенный в сортируемой части массива, имеет наибольшее значение. Это условие проверяется для оставшейся части массива и запоминается номер (индекс) элемента с действительно наибольшим значением. Затем производится перестановка наибольшего элемента с последним элементом в проверяемой части массива. Далее процесс повторяется с уменьшением числа рассматриваемых элементов на единицу.
Сортировка обменом (метод пузырька) основана на последовательном сравнении пары соседних элементов x[i] и x[i+1]. Если пара расположена не в требуемом порядке, то элементы переставляются. Например, при сортировке по возрастанию после первого "прохода" массива от первого до последнего элемента на последнем месте окажется наибольший элемент массива. Далее сортируется оставшаяся часть массива. С каждым очередным "проходом" наибольший элемент массива в оставшейся части массива будет занимать последнее место в проверяемой части массива. Наибольшее число проходов j равно "N - 1", причем число проверок при очередном проходе уменьшается на единицу:
for j:= 1 to N-1 do { цикл по числу "проходов" }
for i:= 1 to N-j do { цикл сравнения элементов в оставшейся части массива }
if x[i] > x[i+1] then begin { запоминаем значение x[i] и }
b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end; { переставляем элементы }
|
|
|
Поскольку при сортировке сравниваются каждые два соседних элемента массива, то для упорядочения данных общее число "проходов" может быть меньше, чем "N - 1". Избежать лишних проходов можно используя оператор цикла с условием:
j:= 0;
repeat j:= j+1; pr:= 0; { pr - признак необходимости "прохода" }
for i:= 1 to N-j do {цикл сравнения элементов в проверяемой части массива}
if x[i] > x[i+1] then begin pr:= 1; { изменяем значение признака }
b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end; { переставляем элементы }
until pr = 0;
Если при проходе проверяемой части массива не было перестановок, то pr=0 и процесс заканчивается. Оптимальным с математической точки зрения считается алгоритм с наименьшим числом перестановок. Однако при программировании необходимо учитывать также, что время выполнения логических операций, как правило, значительно превышает время выполнения арифметических операций. Таким образом, время выполнения программы определяется не только числом перестановок, но существенно зависит от количества выполнений логических операций.
Сортировка вставками основана на внедрении в отсортированную часть массива элемента следующего за этой частью, если он удовлетворяет условию сортировки. На первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и т. д. Среди уже отсортированных i - 1 элементов массива вставляют i - й элемент без нарушения порядка, т. е. при вставке i - го элемента на j - е место (j < i) элементы с индексами >j и <i увеличивают свой номер на единицу. Приведем пример операторов для сортировки данных по возрастанию:
for i:= 2 to N do begin { цикл по числу шагов }
b:=x[i]; {значение элемента, следующего за отсортированной частью массива}
j:= 1;
while b > x[j] do j:= j+1; { определение номера j для вставки элемента}
for k:=i downto j+1 do x[k]:=x[k-1]; { увеличение индексов элементов }
x[j]:= b { вставка значения b на место j - го элемента }
end;
В отличие от рассмотренных методов сортировки здесь процесс сравнения элементов заканчивается как только вставляемый элемент удовлетворяет условию сортировки, т. к. элемент вставляется в отсортированную часть массива.
8 Var <идентификатор>: string[<максимальная длина строки>];
Например:
Var Name: string[20].Параметр длины может и не указываться в описании. В таком случае подразумевается, что он равен максимальной величине — 255. Например: Var slovo: string.
Строковая переменная занимает в памяти на 1 байт больше, чем указанная в описании длина. Дело в том, что один (нулевой) байт содержит значение текущей длины строки. Если строковой переменной не присвоено никакого значения, то ее текущая длина равна нулю. По мере заполнения строки символами ее текущая длина возрастает, но она не должна превышать максимальной по описанию величины.
Символы внутри строки индексируются (нумеруются) от единицы. Каждый отдельный символ идентифицируется именем строки с индексом, заключенным в квадратные скобки. Например: N[5], S[i], slovo[k+l]. Индекс может быть положительной константой, переменной, выражением целого типа. Значение индекса не должно выходить за границы описания.
Тип string и стандартный тип char совместимы. Строки и символы могут употребляться в одних и тех же выражениях.
Строковые выражения строятся из строковых констант, переменных, функций и знаков операций. Над строковыми данными допустимы операции сцепления и операции отношения.
Операция сцепления (конкатенации) (+) применяется для соединения нескольких строк в одну результирующую строку. Сцеплять можно как строковые константы, так и переменные.
Пример: 'Мама ' + 'мыла ' + 'раму'. В результате получится строка: 'Мама мыла раму'. Длина результирующей строки не должна превышать 255.
Операции отношения: =, <, >, <=, >=, <>. Позволяют произвести сравнение двух строк, в результате чего получается логическое значение (true или false). Операция отношения имеет приоритет более низкий, чем операция сцепления. Сравнение строк производится слева направо до первого несовпадающего символа, и та строка считается больше, в которой первый несовпадающий символ имеет больший номер в таблице символьной кодировки. Если строки имеют различную длину, но в общей части символы совпадают, считается, что более короткая строка меньше, чем более длинная. Строки равны, если они полностью совпадают по длине и содержат одни и те же символы.
9 ПРОЦЕДУРЫ И ФУНКЦИИ
Процедуры и функции представляют собой важный инструмент Турбо Паскаля, позволяющий писать хорошо структурированные программы. В структурированных программах обычно легко прослеживается основной алгоритм, их нетрудно понять любому читателю, они проще в отладке и менее чувствительны к ошибкам программирования. Все эти свойства являются следствием важной особенности процедур (функций), каждая из которых представляет собой во многом самостоятельный фрагмент программы, связанный с основной программой лишь с помощью нескольких параметров. Самостоятельность процедур (функций) позволяет локализовать в них все детали программной реализации того или иного алгоритмического действия и поэтому изменение этих деталей, например, в процессе отладки обычно не приводит к изменениям основной программы.
Многие примеры в этой книге невелики по размерам (не более 30-40 строк), поэтому написать такие программы можно и без процедур. Иное дело - создание крупных программ в сотни, тысячи и десятки тысяч строк. Писать такие программы как нечто единое целое, без расчленения на относительно самостоятельные фрагменты, т.е. без структурирования, просто невозможно. Практически во всех языках программирования имеются средства структурирования. Языки, в которых предусмотрены такие механизмы, называются процедурно-ориентированными. К их числу принадлежит и Турбо Паскаль.
Процедурой в Турбо Паскале называется особым образом оформленный фрагмент программы, имеющий собственное имя. Упоминание этого имени в тексте программы приводит к активизации процедуры и называется ее вызовом. Сразу после активизации процедуры начинают выполняться входящие в нее операторы, после выполнения последнего из них управление возвращается обратно в основную программу и выполняются операторы, стоящие непосредственно за оператором вызова процедуры (рис.2.2).
Рис.2.2. Взаимодействие вызывающей программы и процедуры
Для обмена информацией между основной программой и процедурой используется один или несколько параметров вызова. Как мы увидим дальше (см. гл. 8), процедуры могут иметь и другой механизм обмена данными с вызывающей программой, так что параметры вызова могут и не использоваться. Если они есть, то они перечисляются в круглых скобках за именем процедуры и вместе с ним образуют оператор вызова процедуры.
Функция отличается от процедуры тем, что результат ее работы возвращается в виде значения этой функции, и, следовательно, вызов функции может использоваться наряду с другими операндами в выражениях.
С примерами процедур и функций мы уже сталкивались - это стандартные процедуры чтения И записи READ, READLN, WRITE, WRITELN, функции ORD, CHR, математические функции и др. Стандартными они называются потому, что созданы одновременно с системой Турбо Паскаль и являются ее неотъемлемой частью. В Турбо Паскале имеется много стандартных процедур и функций. Наличие богатой библиотеки таких программных заготовок существенно облегчает разработку прикладных программ. Однако в большинстве случаев некоторые специфичные для данной прикладной программы действия не находят прямых аналогов в библиотеках Турбо Паскаля, и тогда программисту приходится разрабатывать свои, нестандартные процедуры и функции.
Нестандартные процедуры и функции необходимо описать, чтобы компилятор мог установить связь между оператором вызова и теми действиями, которые предусмотрены в процедуре (функции). Описание процедуры (функции) помещается в разделе описаний и внешне выглядит как программа, но вместо заголовка программы фигурирует заголовок процедуры (функции).
Не вдаваясь в дальнейшие подробности, попробуем составить собственную процедуру, чтобы пояснить сказанное. Пусть в этой процедуре преобразуется некоторая символьная строка таким образом, чтобы все строчные буквы заменялись соответствующими прописными. В Турбо Паскале имеется стандартная функция UPCASE (см. гл.4), которая выполняет аналогичные действия над одиночным символом. Наша процедура (назовем ее UPSTRING) будет преобразовывать сразу все символы строки, причем сделаем ее пригодной не только для латинских букв, но и для букв русского алфавита.
Разработку программы проведем в два этапа. Сначала сконструируем основную (вызывающую) часть программы. Ее действия очень просты: она должна ввести входную строку (назовем ее Sinp) с клавиатуры, преобразовать ее с помощью процедуры UpString в выходную строку Sout и напечатать результат. Эти действия нетрудно запрограммировать
10. Существует два механизма передачи параметров в процедуру или функцию.
1. Передача параметра по значению. В этом случае значение фактического параметра копируется в формальный параметр, и, следовательно, по окончании работы функции или процедуры значение фактического параметра не меняется. При передаче по значению фактический параметр может быть выражением.
2. Передача параметра по ссылке (по имени). В этом случае ссылка на фактический параметр копируется в формальный параметр. Все действия, которые процедура или функция осуществляет над формальным параметром, выполняются над фактическим. Следовательно, во время работы процедуры или функции значение фактического параметра, переданного по ссылке, изменяется. При передаче по ссылке фактический параметр не может быть выражением, а только переменной.
Параметры, передаваемые по ссылке, называют параметрами-переменными, а параметры, передаваемые по значению, - параметрами-значениями.
Для указания передачи параметра по ссылке в списке формальных параметров перед ним надо разместить служебное слово (var), например:
function rtt(var x:real; y:real):integer;
Здесь x передается по ссылке, а y - по значению. Синтаксис описания функции будет рассмотрен ниже.
procedure myproc(var x, y: real);
Здесь оба параметра (x) и (y) передаются по ссылке. При составлении списка параметров и выборе способа их передачи необходимо учитывать их назначение. Выходные параметры должны быть переданы по ссылке, а входные могут быть переданы по ссылке и по значению.
Одна и та же подпрограмма может вызываться неоднократно, выполняя одни и те же действия с разными наборами входных данных. Параметры, использующиеся при записи текста подпрограммы в разделе описаний, называют формальными, а те, что используются при ее вызове - фактическими.
11Введение файлового типа в язык ПАСКАЛЬ вызвано необходимостью обеспечить возможность работы с периферийными (внешними) устройствами ЭВМ, предназначенными для ввода, вывода и хранения данных.
Файловый тип данных или файл определяет упорядоченную совокупность произвольного числа однотипных компонент.
Общее свойство массива, множества и записи заключается в том, что количество их компонент определено на этапе написания программы, тог- да как количество компонент файла в тексте программы не определяется и может быть произвольным.
Понятие файла достаточно широко. Это может быть обычный файл на диске, коммуникационный порт ЭВМ, устройство печати, клавиатура или другие устройства.
При работе с файлами выполняются операции ввода - вывода. Операция ввода означает перепись данных с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл).
Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид:
'A:LAB1.DAT' 'c:\ABC150\pr.pas' 'lab3.pas'.Операционная система MS-DOS не делает особого различия между фай- лами на дисках и лентах и устройствами ЭВМ и портами коммуникаций. В TURBO PASCAL могут использоваться имена устройств и портов, опреде- ленные в MS-DOS, например:
'CON', 'LPT1', 'PRN', 'COM1', 'AUX', 'NUL'.С файловой системой TURBO PASCAL связано понятие буфера ввода - вывода. Ввод и вывод данных осуществляется через буфер. Буфер - это область в памяти, которая выделяется для каждого файла. При записи в файл вся информация сначала направляется в буфер и там накапливается до тех пор, пока весь объем буфера не будет заполнен. Только после этого или после специальной команды сброса происходит передача данных на внешнее устройство. При чтении из файла данные вначале считываются в буфер, причем данных считывается не столько, сколько запрашивается, а сколько поместится в буфер.
Механизм буферизации позволяет более быстро и эффективно обмени- ваться информацией с внешними устройствами.
Для работы с файлами в программе необходимо определить файловую переменную. TURBO PASCAL поддерживает три файловых типа: текстовые файлы, компонентные файлы, бестиповые файлы.
Описание файловых переменных текстового типа производится с по- мощью служебного слова Text, например:
var tStory: Text;Описание компонентных файлов имеет вид:
var fComp: File of T;где T - тип компоненты файла. Примеры описания файловой переменной компонентного типа:
type M= array[1..500] of Longint; var f1: File of Real; f2: File of Integer; fLi: File of M; Бестиповые файлы описываются с помощью служебного слова File: var f: File;Файловые переменные, которые описаны в программе, называют логи- ческими файлами. Все основные процедуры и функции, обеспечивающие ввод - вывод данных, работают только с логическими файлами. Физичес- кий файл должен быть связан с логическим до выполнения процедур отк- рытия файлов.
TURBO PASCAL вводит ряд процедур и функций, применимых для любых типов файлов: Assign, Reset, Rewrite, Close, Rename, Erase, Eof, IOResult.
Процедура Assign(var f; FileName: String) связывает логический файл f с физическим файлом, полное имя которого задано в строке FileName.
Процедура Reset(var f) открывает логический файл f для последую- щего чтения данных или, как говорят, открывает входной файл. После успешного выполнения процедуры Reset файл готов к чтению из него пер- вого элемента.
Процедура Rewrite(var f) открывает логический файл f для после- дующей записи данных (открывает выходной файл). После успешного вы- полнения этой процедуры файл готов к записи в него первого элемента.
Процедура Close(var f) закрывает открытый до этого логический файл. Вызов процедуры Close необходим при завершении работы с файлом. Если по какой-то причине процедура Close не будет выполнена, файл все-же будет создан на внешнем устройстве, но содержимое последнего буфера в него не будет перенесено. Для входных файлов использование оператора закрытия файла необязательно.
Логическая функция EOF(var f): Boolean возвращает значение TRUE, когда при чтении достигнут конец файла. Это означает, что уже прочи- тан последний элемент в файле или файл после открытия оказался пуст. Процедура Rename(var f; NewName: String) позволяет переименовать физический файл на диске, связанный с логическим файлом f. Переимено- вание возможно после закрытия файла.
Процедура Erase(var f) уничтожает физический файл на диске, ко- торый был связан с файловой переменной f. Файл к моменту вызова про- цедуры Erase должен быть закрыт.
Функция IOResult: Integer возвращает целое число, соответствующее коду последней ошибки ввода - вывода. При нормальном завершении опе- рации функция вернет значение 0. Значение функции IOResult необходимо присваивать какой - либо переменной, так как при каждом вызове функ- ция обнуляет свое значение. Функция IOResult работает только при вык- люченном режиме проверок ошибок ввода - вывода или с ключом компиля- ции {$I-}.
12Запись представляет собой совокупность ограниченного числа логи- чески связанных компонент, принадлежащих к разным типам. Компоненты записи называются полями, каждое из которых определяется именем. Поле записи содержит имя поля, вслед за которым через двоеточие указывает- ся тип этого поля. Поля записи могут относиться к любому типу, допус- тимому в языке Паскаль, за исключением файлового типа.
Описание записи в языке ПАСКАЛЬ осуществляется с помощью служебного слова RECORD, вслед за которым описываются компоненты за- писи. Завершается описание записи служебным словом END.
Например, записная книжка содержит фамилии, инициалы и номера те- лефона, поэтому отдельную строку в записной книжке удобно представить в виде следующей записи:
type Row=Record FIO: String[20]; TEL: String[7] end; var str: Row;Описание записей возможно и без использования имени типа, напри- мер:
var str: Record FIO: String[20]; TEL: String[7] end;Обращение к записи в целом допускается только в операторах присва- ивания, где слева и справа от знака присваивания используются имена записей одинакового типа. Во всех остальных случаях оперируют отдель- ными полями записей. Чтобы обратиться к отдельной компоненте записи, необходимо задать имя записи и через точку указать имя нужного поля, например:
str.FIO, str.TELТакое имя называется составным. Компонентой записи может быть так- же запись, в таком случае составное имя будет содержать не два, а большее количество имен.
Обращение к компонентам записей можно упростить, если воспользо- ваться оператором присоединения with.
Он позволяет заменить составные имена, характеризующие каждое по- ле, просто на имена полей, а имя записи определить в операторе присо- единения:
with M do OP;Здесь М - имя записи, ОР - оператор, простой или составной. Оператор ОР представляет собой область действия оператора присоедине- ния, в пределах которой можно не использовать составные имена.
Иногда содержимое отдельной записи зависит от значения одного из ее полей. В языке ПАСКАЛЬ допускается описание записи, состоящей из общей и вариантной частей. Вариантная часть задается с помощью конс- трукции
case P of,где Р - имя поля из общей части записи. Возможные значения, прини- маемые этим полем, перечисляются так же, как и в операторе варианта. Однако вместо указания выполняемого действия, как это делается в опе- раторе варианта, указываются поля варианта, заключенные в круглые скобки. Описание вариантной части завершается служебным словом end. Тип поля Р можно указать в заголовке вариантной части, например:
case P: Integer ofИнициализация записей осуществляется с помощью типизированных констант:
type RecType= Record x,y: Word; ch: Char; dim: Array[1..3] of Byte end; const Rec: RecType= (x: 127; y: 255; ch: 'A'; dim: (2, 4, 8));13 Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.
Например, приведенное ниже определение двоичного кода является рекурсивным:
<двоичный код>::= <двоичная цифра> | <двоичный код><двоичная цифра> <двоичная цифра>::= 0 | 1Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".
Вообще, в рекурсивном определении должно присуствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Приведём другие примеры рекурсивных определений.
Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...* n. С другой стороны, 
Граничным условием в данном случае является n <=1.
Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n: 
Задание. По аналогии определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.
Пример 3. Функция C(m, n), где 0 <= m <= n, для вычисления биномиального коэффициента 
по следующей формуле 
является рекурсивной.
Ниже будут приведены программные реализации всех этих (и не только) примеров.
Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.
Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновренно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов:
Begin Begin Begin P; операторы; операторы; операторы; P P;End; End; операторы End; рекурсивный подъём рекурсивный спуск и рекурсивный спуск, и рекурсивный подъёмЗдесь P — рекурсивная подпрограмма. Как видно из рисунка, действия могут выполняться либо на одном из этапов рекурсивного обращения, либо на обоих сразу. Способ организации действий диктуется логикой разрабатываемого алгоритма.
Реализуем приведённые выше рекурсивные определения в виде функций и процедур на языке Pascal и в виде функций на языке C.
Ханойская башня
Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый.
Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.
Построим рекурсивное решение задачи, состоящее из трех этапов:
a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.
Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1 диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких nдисков с одного стержня на другой.
Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.
Оформим алгоритм решения задачи о переносе башни из n дисков сs1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.
Программа на языке Паскаль:
type st = (left, middle, right); nat = 1..maxint; var m: nat; {m – число дисков} procedure move(n: nat; s1, sw, sk: st); {перемещение n дисков с s1 на sk} procedure step; {перемещение одного диска с s1 на sk} procedure print(s: st); begin case s of left: write(' лев. '); middle: write(' средн. '); right: write(' прав. ') end; end; begin {step} write(' снять диск с '); print(s1); write(' надеть на '); print(sk); writeln end; begin {move} if n = 1 then step else begin move(n - 1, s1, sk, sw); step; move(n-1, sw, s1, sk) end end; begin read(m); {число дисков} writeln('для ', m:3, ' дисков следует произвести ', 'следующие действия:'); move(m, left, middle, right); readln end. 14 не нашоль(15 Обращение к динамической переменной происходит посредством ссылочной переменной, которая содержит адрес соответствующей динамической переменной.
Под ссылочную переменную транслятор отводит место в памяти машины; эта переменная имеет имя и явно упоминается в программе. Ссылочные переменные образуют новый тип данных – "ссылки" (указатели).
Динамические переменные, как правило, имеют тип "запись" (record), т.к. должны содержать, помимо значения (целого, вещественного и т.п.), ссылку на другую динамическую переменную связанной структуры.
Пример. Пусть в памяти машины имеется динамическая переменная, содержа
|
|
|
