Н. Вирт - Программирование на языке Модула-2 (1160777), страница 8
Текст из файла (страница 8)
Они читают или печатают элементы, взятые из некоторогоФиксированного множества литер. Это множество образует диапазон значений типа CHAR. Ксожалению, различные типы вычислительных машин могут использовать различные множествалитер, что делает связь между машинами (т.е. обмен программами и данными) трудной изапутанной.Существует, однако, международный стандартизированный набор литер, такназываемый набор ISO. Стандарт ISO определяет, набор из 128 литер, причем 33 из них -такназываемые управляющие литеры. Оставшиеся 95 - видимые печатаемые (или графические)литеры, показанные в следующей таблице.
Набор литер упорядочен, и каждая литера имеетФиксированное порядковое число. Например, латинская буква А -это 66-я литера; она имеетпорядковое число 65. Стандарт ISO оставляет, однако, в таблице несколько мест незаполненными,их можно заполнять различными литерами в соответствии с национальными стандартами.Наиболее широко применяется американский стандарт, называемый ASCII (American StandartCode for Information Interchange - американский стандартный код для обмена информацией). Здесьмы приводим именно набор литер ASCII. Порядковое число литеры получается сложениемчисел, соответствующих столбцу и строке, которые содержат нужную литеру.
Эти числа обычноприводятся в восьмеричном виде, и мы тоже последуем этому правилу. Первые два столбцасодержат управляющие литеры, они обычно обозначаются сокращениями, указывающими на ихпредполагаемую Функцию. Их смысл, однако, не заложен в код, а определяется только ихинтерпретацией конкретным устройством. Поэтому достаточно просто помнить, что эти литерыобычно не печатаются.Константы типа CHAR обозначаются литерой, заключенной в кавычки или апострофы.Литерные значения могут быть только присвоены переменным типа CHAR, но не могутиспользоваться в арифметических операциях.
Арифметические операции можно применять лишьк порядковым числам, получаемым с помощью Функции преобразования ORD(ch). И наоборот,литера, имеющая порядковый номер n, может быть получена Функцией преобразования CHR(n).Эти две взаимно обратные функции связаны уравнениямиCHR(ORD(ch)) = ch и ORD(CHR(n)) = nкоторые верны при 0 <= n < 128. Они позволяют получить числовое значение цифры ch какORD(ch) - ORD("0") и вычислить цифру, представляющую числовое значение п, как CHR(n+ ORD("0"))Эти две Формулы используют сплошное расположение цифр в стандарте ISO, причемORD("0") = 60В = 48. Они, как правило, применяются в подпрограммах преобразования32последовательностей цифр в числа и наоборот, чисел в последовательности цифр. СледующийФрагмент программы читает цифры и присваивает значение числа, представленного ими вдесятичной Форме, переменной х.х := 0; Read(ch);WHILE ("0" <= ch) & (ch <= "9") DOx := 10*x + (ORD(ch) -ORD("0")>: Read(ch)ENDТаблица литер кода ASCII020 40 60 100 120 140 1600nul dle0 &P"p1soh del t1AQ аq2stx dc2 "2В Rbr3etx dc3 #3С Sсs4eot dc4 $4D Tdt5enq nak %5E Ue6ack syn &6F Vf7bel etb '10bscan (8H11htem )9IY12Ifsub *:JZ j13vtesc +;К[k14ffTs,<L\l15crgs-=M]16sors.>N^17sius7/?G0U sXvwhxi уz{|m }n_u~оdelУправлявшие литеры используются для различных целей, в основном для управленияфункционированием внешних устройств, но, кроме того, для разбиения текста на строки и егоструктуризации.
Важная функция управляющих литер - указывать конец строки или конецстраницы текста. Нет никакого общепринятого стандарта на их использование в этих целях. Мыобозначим управляющую литеру, отмечающую конец строки текста, идентификатором EOL (EndOf Line - конец строки): ее конкретное значение зависит от используемой вычислительнойсистемы.Для представления невидимых символов Модула использует их порядковое число ввосьмеричном представлении, за которым следует буква С (латинская). Например, 14С - значениетипа CHAR, обозначающее управляющую литеру ff (перевод Формата), имеющую порядковоечисло 14В.337.6.
Тип BITSETВеличины, принадлежащие типу BITSET, - множества целых чисел между 0 и N-1, где N константа, определяемая конкретной вычислительной машиной. Это обычно либо длинамашинного слова, либо небольшое кратное ей число. Константы этого типа обозначаются какмножества (см. также раздел, посвященный типу множество). Вот примеры:{5.7,11} {0} {8..15} {0..3,11,15} {}Обозначение m ..
n - сокращение для m,m+l, ... ,n-l,n.$Множество = [КвалИдент]$"{" [Элемент {"," Элемент}] "}".$Элемент = Выражение [".." Выражение].Над множествами определены операции:+объединение множеств-разность множеств*пересечение множеств/симметрическая разность множествСчитая, что i обозначает элемент множества, a u, v - множества, эти операции можноопределить в терминах принадлежности к множеству следующими равенствами:i IN (u + v) - (i IN и) OR (i IN v)i IN (и - v) - (i IN и) AND NOT (i IN v)i IN (u * v) - (i IN u) AND (i IN v)i IN (u / v) - ((i IN u) # (i IN v))Операция проверки принадлежности элемента множеству считается операцией сравнения.Выражение i IN u имеет тип BOOLEAN. Оно принимает значение TRUE, если i - элементмножества u.
Тип BITSET представляется в машине как множество битов, т.е. характеристическойфункцией множества. Например, i-й бит в u равен 1, если i принадлежит u, и равен 0 в противномслучае. Следовательно, множественные операции реализованы как логические операции над Nчленами множественной переменной.
Поэтому такие операции очень эффективны, и время ихвыполнения обычно даже меньше, чем при сложении целых чисел.8. ОПИСАНИЯ КОНСТАНТ И ПЕРЕМЕННЫХУже упоминалось, что все идентификаторы, используемые в программе, должны бытьописаны в ее заголовке (или импортированы из некоторого другого модуля). Это не касаетсястандартных идентификаторов, известных во всех программах.Если идентификатор должен обозначать константное значение, то его можно ввестиописаниям константы, которое указывает, какую величину будет заменять этот идентификатор.Описание константы имеет вид$ОписаниеКонстанты = Идентификатор "=" КонстВыражение.$КонстВыражение = Выражение.34КонстВыражение - выражение, содержащее только константы. Более точно, оно должнобыть вычислимо без выполнения программы, простым просмотром ее текста.
Последовательностиописаний констант предшествует ключевое слово CONST. Пример:CONST N = 16;EOL = 36С;пусто = {};М = N - 1;Константы с явными именами облегчают чтение и разбор программ лишь в том случае,когда им даны подходящие имена. Если, например, идентификатор N используется вместозначения константы по всей программе, то эту константу можно изменить, исправив текстпрограммы только в одном месте, а именно в описании N. Это предотвращает распространеннуюошибку, когда при изменении константы некоторые ее вхождения остаются незамеченными исохраняют старое значение, что ведет к несоответствиям в программе.Описаниe переменной похоже на описание константы. Вместо значения константыставится тип переменной, который в некотором смысле может считаться константным свойствомпеременной. Вместо знака равенства используется двоеточие.$ОписаниеПеременной = СписИдент ":" Тип.$СписИдент = Идентификатор {"," Идентификатор}.В одном описании могут быть перечислены несколько переменных одного и того же типа.Последовательности описании переменных предшествует слово VAR.
Пример:VAR i,j,k: CARDINAL;x,y,z: REAL;ch: CHAR9. МАССИВЫДо сих пор мы давали каждой переменной отдельное имя. Однако это неудобно, когдамного переменных одного типа нужно обрабатывать одинаковым образом, как, например, присоздании некоторой таблицы данных. В этом случае хотелось бы дать всему множествупеременных единственное имя и обозначать отдельный элемент идентифицирующим его номером,так называемым индексом. Такой тип данных называют структурированным (более точно:структурированный тип массив). В следующем примере переменная а состоит из N элементов,имеющих тип CARDINAL, а индексы меняются от 0 до N—1.VAR a: ARRAY [1..N-1] OF CARDINALЭлемент в этом случав обозначается идентификатором массива, за которым следуетвыбирающий индекс, например а[i], где i -выражение, значение которого должно лежать внутридиапазона изменения индекса, заданного в описании массива.
Синтаксически, а[i] - обозначения, авыражение i - индексное выражение. Если, например, всем элементам массива а нужно присвоитьнулевое значение, то это удобно выразить оператором цикла, в котором индекс при каждомповторении получает новое значение.i := 0;REPEAT а[i] := 0; i := i + 1UNTIL 1 = N35Этот пример иллюстрирует ситуацию, возникающую настолько часто, что Модулапредлагает специальную управляющую конструкцию, выражающую то же самое более лаконично.Она называется оператором цикла с шагом:FOR i := 0 ТО N-l DOa[i] := 0ENDОбщая Форма этого оператора такова:$ЦиклСШагом = "FOR" Идентификатор ":=" Выражение$"ТО" Выражение ["BY" КонстВыражение]$"DO" ПослОператоров "END".Выражения, стоящие до и после ключевого слова ТО, определяют соответственноначальную и конечную границы диапазона изменения так называемой управляющей переменнойили параметра цикла (i).
Необязательная конструкция, начинающаяся с ключевого слова BY,определяет шаг увеличения (или уменьшения, если он отрицателен) параметра цикла. Поумолчанию значение шага принимается равным единице.Рекомендуется использовать цикл с шагом только в простых случаях; в частности,операнды выражений, определяющих диапазон, и в особенности сам параметр цикла, не должныменяться повторяемыми операторами. Значение параметра цикла после завершения цикла следуетсчитать неопределенным.Дополнительные примеры призваны продемонстрировать использование массивов иоператоров цикла с шагом.
В первом примере вычисляется сумма N элементов массива.сумма := 0;FOR i := 0 ТО N-l DOсумма := а[i] + суммаENDВо втором примере требуется найти минимальный элемент в массиве и его индекс.Инвариантом цикла является условие mln минимум(а[0],...,а[i-1]).min := а[0]; k := 0;FOR i := 1 ТО N-1 DOIF а[i] < min THEN k := i; min := a[k]ENDENDВ третьем примере алгоритма сортировки массива в возрастающем порядке мы используемвторой пример как Фрагмент.FOR i := 0 ТО N-2 DOmin := a[i]; k := i;FOR j := i TO N-l DO36IF a[j] < min THENk := j; min := a[k]ENDEND;a[k] := а[i]; а[i] := minENDПусть нужно скопировать массив а в массив b.
Можно попробовать записать это так:FOR i := 0 ТО N-l DOЬ[i] := а[i]ENDХотя это и правильно, однако то же самое выражается проще оператором а : = Ь. Отсюдавидно, что оператор присваивания можно применять и непосредственно к массивам.Очевидно, что цикл с шагом хорошо соответствует случаям обработки всех элементоввнутри заданного диапазона. Но если, например, мы хотим найти индекс элемента, равногозаданной величине х, то нам неизвестно заранее, сколько элементов массива придетсяпросмотреть. Следовательно, здесь рекомендуется использовать цикл с условием продолженияили с условием окончания. Этот алгоритм называется линейным поиском.i := 0;WHILE (i < N) & (а[i] # х) DOi := i + 1ENDВзяв отрицание условия продолжения и применяя закон де Моргана, мы получим, что призавершении цикла будет удовлетворяться условие (i = N) OR (а[i] = х).
Если второе подвыражениеистинно, то это значит, что искомый элемент найден, а ш - его индекс; если же i = N, то все а[i] неравны х.Обратим внимание на то, что условие завершения составное. Известен стандартный способего упрощения. Вспомним, что повторение должно завершиться, если либо найден нужныйэлемент, либо достигнут конец массива. Хитрость состоит в пометке конца массива специальнымэлементом, равным х, на котором поиск автоматически прекратится. Для этого нужно всего лишьдобавить в конец массива вспомогательный элемент a[N], который будет служить ограничителем.a: ARRAY [0..N1 OF CARDINAL;a[N] := x; i := 0;WHILE a[i] # x DO i := i + 1 ENDЕсли после завершения приведенного фрагмента программы i = N то ни один исходныйэлемент не равен х, если же i не равно N, то i - нужный индекс.Более сложная задача - поиск элемента, равного х, в упорядоченном массиве, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
