Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 5
Текст из файла (страница 5)
Сутью искусства программирования обычно считается умение составлять операции. Однако мы увидим, что не менее важно умение составлять данные. Важнейшие основные операции — это сравнение и присваивиниг, т. е. проверка равенства (и порядка в случае упорядоченных типов) и команда «установки равенства». Принципиальное различие этих двух операций выражается четким различием их обозначений в тексте (хотя опо, к сожалению, скрыто в таких широко распространенных языках, как Л Фундаментальные структуры денных Фортран и ПЛ/1, которые используют знак равенства в ка. честве оператора присваивания): Прояерка равенства: х = у Присваивание: х:= у Этн основные операции определены для большинства типов данных, но следует заметить, что для данных, име>ощих большой объем и сложную структуру, выполнение этих операций может сопровождаться довольно сложными вычислениями.
Кроме проверки равенства и присваивания имеется еше один класс основных, неявно определенных операций — так называемых операций преобразованию Этн операции отображают одни типы данных в другие. Особенно они важны для составных типов. Составные значения строятся из значеш>й компонент с помощьк> так называемых конструкторов, а значения компонент извлекаются с помощью так называемых селекторов. Таким образом, конструкторы и селекторы — э>о операции преобразования, отображающие типы компонент в составные типы и наоборот.
Каждому методу структурирования соответствует своя пара конструкторов и селекторов, обозначения которых четко различаются. Стандартным простым типам данных соответствует также некоторое множество стандартных простых операций. Следовательно, вместе со стандартными типами данных: числамн и логическими значениями — вводятся также соответствующие арифметические и логические операции.
1.3. ПРОСТЫЕ 1ИПЬ$ ДАНМЫХ Во многих программах целые числа используются в точ случае, когда их собственно числовое значение несущественно и когда целое число указывает на выбор значения из небольшого множества возможных вариантов. В подобных случаях мы вводим новый, простой, неструктурированный тип Т, перечисляя множества всех его возможных значений с>, сь ..., сел (1.1) 1уре Т=-(сь с„., „с„) Кардинальное число Т есть сагй(Т) = и. Примеры: 1уре фигура=(прямоугольник, квадрат, эллипс, круг) 1уре цвет*=(красный, желтый, зеленый) 1уре пол = (мужской, женский) 1уре Воо1еап = ()а1ге, 1тие) дХ Просте~е типы данных 2! Фуре день = (понедельник, вторник, среда, четверг, пятница, суббота, воскресенье) Фуре валюта =- (франк, марка, фунт, доллар, шиллинг, лира, гульден, крона, рубль, крузейро, иена) Фуре обитель=(ад, чистилии(е, раи) Фуре транспорт = (поезд, автобус, автомобиль, пароход, самолет) Фуре звание = (рядовой, капрал, сержант, лейтенант, капитан, майор, полковник, генерал) Фуре объект = (константа, тип, переменная, процедура, функция) Фуре структура=(файл, массив, запись, множество) Фуре состояние=(выключено, пустое, ошибка, перекос) При определении таках типов вводится не только новый иден.
тнфихатор типа, но одновременно — множество идентификаторов, соответствующих значениям этого типа. Эти идентификаторы могут затем использоваться в программе кан константы, при этом программа становится намного понятней. Если, например, мы определим переменные з, с(, г и Ь тагз: пол чагй день наг г: звание наг Ь: Воо1еап то возможны следующие операторы присваивания: з:= мужской й:= воскресенье г:= майор Ь;=!гие Очевидно, что они намного более информативны, чем операторы з:=1 с(:=7 г:=6 Ь:=2 которые будут им соответствовать, если з, д, г и Ь определить как переменные цело~о типа, а соответстнующие константы изображать натуральными числами, определенными поридком перечисления.
В дальнейшем транслятор может выявлять неуместное использование арифметических операций на таких нечисловых типах, каи, например: з:=в+ 1 Однако если тип считается упорядоченным, то полезно определить функции, которые выдают предшествующее и последующее значения для своего аргумента. Эти функции Л Фундаментальные етрунтуры данные обозначаются как зиса(х) (последующее значение) и ргег1(х) (предшествующее значение). Упорядоченность значений типа Т определяется правилом (с, ( сг) — (г < 1) (1.2) ТМ. СТАНДАРТНЫЕ ПРОСТЫЕ ТИПЫ Стандартные простые типы — это типы, которые явлиотся встроенными для большинства ЭВМ.
Они включают целые числа, логические значения и множество символов печати. В крупных вычислительных машинах имеются также вещественные числа и соответствующее множество простых операций. Мы обозначаем этн типы идентификаторами: гигейаг, Воо1еаи, геа1, с)гаг. Тип глгедег содержит подмножество целых чисел, размер которого может быть различным в разных вычислительных системах.
Но предполагается, что все действия с данными этого типа являются точными и выполняются по обычным правилам арифметики и что вычисление прерывается, если результат оказывается за границами допустимого подмножества. Стандартные операции — это четыре действия арифметики: сложение (+), вычитание ( — ), умножение (*) и деление (б)ч). Последнее должно давать целый результат, опуская возможный остаток, так, что для любых т и и т — и < (т б)чи)'п(т.
(1.3) Операция взятия остатка определяется с помощью деления уравнением (т сВ ч и)' и + (т гпоб и) = и. (1.4) Таким оораэом, т б(ч и — это целое от деления т на и, а ги шоб и — остаток от деления. Тип «еа( обозначает подмножество вещественных чисел. В то время как арифметические действия с целыми числами дают точные результаты, для арифметических действий со значениями типа геа1 допускается неточность в пределах ошибок округления, так как в вычислениях участвует конечное число цифр, В этом состоит явное различие между типами гигедег и геа1, существующее в большинстве языков программирования. Деление вещественных чисел, дагощее вещественный результат, мы обозначаем косой чертой (/), а дсление целых чисел — й)ч.
Два значения стандартного типа Воо1еаи (булевское) обозначаются идентификаторами 1гие (истина) и )а)зв (ложь), 1ли Стандартные простые типы 2з Таплнца 1.1. Булевснне операции Операции над булевскими значениями — это логические конъюнкция, дизъюнкция и отрицание, значения которых приведены в табл, !.1. Логическая конъюнкция обозначается символом 'Л (или апт(), логическая дизъюнкция — символом ~/ (или ог), а отрицание — символом 1 (илн по1). Заметим, что операции сравнения дают результат типа Воо(еап. Следовательно, результат сравнения можно присваивать какой- либо булевской переменной или использовать в качестве операнда в булевских выражениях. Например, пусть даны булевские переменные р и д и целые переменные х = 5, у = 8, г = 10, тогда присваивания р:= — х= у д: = (х < у) А (у < з) дают р = )а1зе и д = 1тие. Стандартный тип сйат включает множество печатаемых символов, К сожалению, не существует общего стандартного множества символов, принятого во всех вычислительных системах.
Поэтому использование слова «стандартный» может здесь ввести в заблуждение; его следует понимать в смысле «стандартный для вычислительной системы, на которой должна выполняться данная программа». По-видимому, наиболее широко используется множество символов, определенное Международной организацией по стандартизации (150), и особенно его американская версия АЬСП (американский стандартный код для обмена информацией). Поэтому в приложении А дана таблица символов АБСП.
Она включает 95 печатаемых (графи«еских) символов и 33 управляющих символа; последние используются в основном для передачи данных и для управления печатающим устройством. Широко распространено подмножество из 64 печатаемых символов (только прописные буквы), которое называется ограниченным множеством АЯСП, Для того чтобы описывать алгоритмы, работающие с символами, т. е. значениями типа сйат, независимо от вычислительной системы мы определим некоторые свойства Д Фундннентальньи структура данных множества символов, делающие его связным. Это следующие свойства: ! 1. Тнп сйаг содержит 26 латинских букв, !О арабских цифр и некоторое количество других графических символов таких, как знаки препинания. 2.
Подмножества букв и цифр упорядочены и связны, т, е. ('Л' к х) Л (х < '2') = — х — буква, (О ~~х) Л (х.=. 9')= — х — цифра. (1.5) 3, Тип сйаг содержит непечатаемый, пустой символ (пробел), который может использоваться как разделитель. (На рис. 1.1 пробелы обозначаются как .) Для написания программ в машинно-независимом виде особенно важно наличие функций преобразования между Рве. !.!. Представление текста. двумя стандартными типами сйаг и 1»т1едсг. Мы называем эти функции огс((с) — порядковый номер символа с в множестве сйаг и сйг(1) — 1-й символ множества сйаг. Таким образом, сй» вЂ” это обратная функция от огЫ и наоборот, т.
е. огс((сй»Я) = с (если сй»Я определена), сйг(гг»с1(с)) = с. Особого внимания заслуживают функции те (с) = о»4с) — огс(('О') = положение с среди цифр, й (1) = сйг(! + о»4'О')) = с-я цифра. Например, 1('3') = З„д(5) = '5'. Таким образом, 1 — обратная функция от д и наоборот, т. е.
К(д(1))=1 (Оч='1~~9), д'~(с))=с ('О'~(с:- '9'). Эти функции преобразования используются для перевода внутреннего представления чисел в последовательности цифр и наоборот. Они фактически и представляют собой такой пе« ревод на простейшем уровне — для одной цифры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
