Учебное пособие по дисциплине Разработка языков программирования высокого уровня
 Скачать 1.74 Mb.
|
3.7. Порядковые типы, определяемые пользователем3.7.1. Перечислимый типПеречислимый тип данных – это такой тип, который имеет следующие характеристики: – задается набором элементов, – в качестве элементов используются строковые константы, – количество элементов не должно быть больше 256, – внутреннее представление каждого элемента совпадает с типом byte. Формат описания: Type <имя типа>=(<стр.константа1>,<стр.константа 2>,…,<стр.константа k>) Пример 2. Type A = (красный, синий, зеленый); var auto: A; begin avto := синий end Операции над данным типом также могут быть как встроенные (сравнения на «=», «≠», так и реализованные в виде функций: определение номера по значению; определение значения по номеру; определение последующего (предыдущего) значения; определение min/max значений. Однако, если операции «=», «≠» вводятся всегда, т.к. они семантически оправданы, то другие операции отношения могут не иметь смысла. Поэтому вопрос о том, какие операции будут представлены в ЯП, для разработчиков данного языка представляет определенную сложность. Кроме того, возникают также и другие проблемы, требующие нестандартных субъективных подходов, например, может ли одна и та же символьная константа появиться в разных типах. Одним из таких решений может быть следующее правило: чтобы разрешить использовать в разных типах одну и ту же символьную константу, необходимо указывать имя типа перед значением константы по формату <имя типа>.<стр.константа>. 3.7.2 Ограниченный типОграниченным типом называется такой тип, который образуется на основе порядкового путем задания минимального и максимального значений (в языке Pascal такой тип называется тип-диапазон). Формат описания: Type <имя типа>= Пример 3. Type T1 = ‘0’ , ‘1’ , … , ‘9’, Type T2 = 0,1,2, … ,9; Этот тип наследует все операции своего базового типа. При реализации такого типа компилятор должен выполнять проверку выхода значений за границу допустимого диапазон типа. 3.8 Структурные типыВ отличие от простых типов данных, структурные типы данных имеют следующую специфику: такой тип представляет собой абстракцию области памяти, всегда имеет внутреннюю организацию и эта организация для каждого типа различна. Кроме того, структурные типа обладают свойством ортогональности, поэтому пользователь имеет возможность конструировать структурные типа под потребности своей задачи. Именно поэтому они еще называются «Типы, определяемые пользователем». 3.8.1. МассивыМассив – это поименованная область оперативной памяти (ОП), ячейки в области пронумерованы и являются переменными одного типа. Элемент массива представляет собой индексированную переменную: var <имя> : array [нач.зн. . . кон. зн] of <тип>; Тип массива включает в себя тип элемента и тип индекса. Обращение к каждому элементу массива осуществляется по общему имени и индексу элемента: A[i]. Категории массивов Массивы делятся на 4 категории, которые указывают когда и где выделяется память. 1. Статический массив. Это массив, в котором диапазоны значений индексов в связываются статически, размещение в памяти также статическое и осуществляется в период компиляции. Пример описания: A : array[1…100] of integer; 2. Фиксированный автоматический массив. Диапазон значений связывается в статике, а размещение в памяти происходит динамически, во время выполнения: const n=10, m=100; procedure SSS(A(n,m)); 3. Автоматический массив. Размещение в памяти происходит динамически. Но после связывания индексов и размещения в памяти и диапазоны, и адрес массива не изменяется в течение всей жизни переменной: var A(n,m); … read(m,n); 4. Динамический массив. Это массив, в котором связывание индексов и размещение в динамической памяти происходит только при выполнении программы. Для этого используются специальные функции, а также механизмы на основе указателей (см. п.п.3.6). Пример описания: A = new float(100); Операции над массивами Операцией над массивом называется действие, при выполнении которого массив считается единым целым. В языке Fortran-90 операции линейной алгебры над массивами реализованы как встроенные функции (операции с матрицами, векторами). В языке Pascal возможны операции присваивания: A,B : array[1…10] of real; A :=B; В языке Ada реализованы: – присваивание; – операции отношения; – конкатенация (сцепление) массивов. Операция инициализации массива – это заполнение его начальными значениями. В языке Pascal инициализация не допускается. В языке Fortran для этого служит специальный оператор: INTEGER A(3), B(3); DATA A| 1,5,7 | B | 2..4 | ; В языке Ada инициализация осуществляется следующим образом: A:array(1..4) of int=(1,2,3,4); A:array(1..4) of int (1>=3,2>=4, other >=0); В языке C операция инициализации может быть реализована различными способами: int a[3]= {1,5,3}; int a[3][5]= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; int a[3] [5]= {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}}; Если инициализаторов меньше, то оставшиеся элементы массива не определяются. В этих языках есть особенность – компилятор сам может устанавливать длину массива на основании инициализатора: int list [] = {4,6,10,7}, тогда длина массива устанавливается в четыре элемента. В некоторых языках есть операция сечения, т.е. выделение из структуры массива некоторой подструктуры. Если М – матрица, то сечение может быть строка или столбец. Сечение не является новым типом, это просто способ обращения к части массива: vector(1..10),mat(1:3,1:3) {*Массивы vector(3:6), {*Сечение – часть одномерного массива Mat(1:3,2) {*Сечение: 2-й столбец матрицы Mat(3,1:3) {*Сечение: 3-я строка матрицы Сечения могут быть и нерегулярными: vector ((/3, 2, 1, 8/)) это массив, содержащий 3,2,1 и 8 элементы массива vector. Функции доступа к элементам массива Команды, осуществляющие доступ к элементам массива формируются при компиляции. Эти команды вычисляют адреса элементов массива. Для одномерного массива функция доступа к адресу элемента k следующая: Адрес(Массив[k])=Адрес(Массив[1]+(k-1))*(размер элемента)= =Адрес(Массив[1]) – (размер элемента) + (k*размер элемента) Дескриптор однородного массива:
Пусть имеется массив А типа integer длиной в 10 элементов, следует определить адрес 5-го элемента. Так как размер элемента массива 4 байта, то Адрес(А[5])=0+4*4 байта = 16-й байт. Для двумерного массива с длиной строки n функция доступа к элементу A[i,j] выглядит следующим образом: Адрес(А(i,j)) = Адрес(A[1,1])+(((число строк над i-ой)*(размер строки) + (число элементов слева от j-ого столбца))*(размер элемента))= Адрес(A[1,1])+(((i-1)*n)+(j-1))*(размер элемента) Однако, в памяти двумерные массивы располагаются не в виде матрицы, а в виде вектора. При этом, вектор может формироваться либо из строк исходной матрицы (языки C, Pascal, Бэйсик), либо из столбцов (язык ФОРТРАН). Поэтому результат вычисления адреса элемента по приведенной формуле даст различные значения элемента в зависимости от того, как реализовао хранение в памяти элементов двумерного массива для того или иного ЯП. Пример 4. Определить адрес элемента A[3,2] для двумерного массива A[1..3,1..3] типа integer
Адрес(A[3,2])=Адрес(A[1,1]+(((2*3)+(2-1))*4))=28. Однако в ячейке с адресом 28 для языка с расположением элементов в памяти по строкам будет храниться значение 5, а для реализации языка FORTRAN – значение 6. Ассоциативные массивы Ассоциативный массив – это массив с неупорядоченным множеством элементов, индексированных таким же количеством величин, называемых ключами. Ключи должны содержаться в структуре массива, т.е. каждый элемент здесь является парой: ключом и величиной. Такие массивы используются в таких языках, как Perl, Java. В языке Perl ассоциативные чертежи называются хэшами, создаются и удаляются с помощью функций хэширования. Размер хэша всегда динамический. Хэшированные переменные обозначаются специальным символом «%»: %salaries = («Bacy»=>3600, «Petr»=>42000, «Masha»=>6000); Обращение к элементу производится через знак $: $salaries {«Bacy»} = 70000. 3.8.2 МножестваДанные множественного типа представляют собой неупорядоченную совокупность отдельных величин некоторого порядкового или перечислимого типа: type <имя типа>=set of<значения базового перечислимого порядкового типа>; Таким образом, переменная типа множество является объектом, содержащим неупорядоченный набор значений, которые принадлежат некоторому базовому типу. Пример 5. type T1 = set of ’0’ .. ‘9’; T2 = set of 0 .. 9; T3 = (красный, сильный, зеленый); Т4 = set of T3; Var s1, s2, s3 : T1; s4, s5, s6 : T2; s7 : T4; begin s1 = [‘1’, ‘2’, ‘3’]; s2 = [‘3’, ‘2’, ‘1’]; s3 = [‘2’, ‘3’]; s4 = [0..3, 6]; s5 = [4, 5]; s6 = [3..9]; s7 = [синий, зеленый]; Реализация множеств осуществляется битами машинного слова, которое может включать различное количество байт в разных архитектурах ЭВМ. Поэтому при переносе пользовательской программы, включающей множества, на другой компьютер возникает проблема совместимости. Мощность множества определяется величиной машинного слова. Операции над переменными множественного типа по смыслу идентичны операциям над математическими множествами: Умножение переменных есть пересечение двух множеств s4 * s6 = [3, 6]; Сложение переменных представляет собой объединение множеств s4 + s5 = [0 .. 6]; Разность переменных – это элементы 1-ого множества, которые не принадлежат 2-ому. s6 – s5 = [3, 6, 7, 8, 9]; 4. Эквивалентность. Две переменные множественного типа эквивалентны, если все их элементы одинаковы, причем порядок следования безразличен (true, если множества эквивалентны). 5. Неэквивалентность <, >. Результат операции есть true, если множества не эквивалентны. 6. Включение <= дает true, если первое множество включено во 2-ое. s5 <= s6; 7. Принадлежность элемента in. Результат операции равен true, если элемент или выражение принадлежит множеству, иначе – false. 4 in s6 = true 1 in s6 = false Реализован множественный тип только в семействе языка Pascal. 3.8.3. ЗаписьЗапись – это совокупность данных различных типов, в которой отдельные элементы идентифицируются символьными именами. Каждый элемент называется полем записи. В силу того, что запись позволяет модерировать таблицы со столбцами различных по типу данных, впервые они были введены в язык Cobol, ориентированный на программирование бухгалтерских задач. В языке С записи называются структурами. Формат записи: type<имя> = record; <имя поля 1>.<тип>;  <имя поля n>.<тип>; end; Обращение к элементу осуществляется по формату: <имя переменной>.<имя поля>; В качестве поля может быть описана другая запись, т.е. можно спроектировать иерархию записей. Тогда, если при обращении к полю записи указываются имена всех уровней иерархии, то это называется полностью определенной ссылкой на поле; если все или некоторые имена иерархии опущены – эллиптическая ссылка. Эллиптическая ссылка используется в операторах with: type student = record; fio : string; ball : int; end; Var b : student; begin with b do fio := ‘Иванов’; ball := 5; end. Над записями осуществляются следующие виды операций: 1. Сравнение на  .2. Копирование полей: из записи источника – в запись результат. 3. Над полями записей определены все операции, присущие объявленному типу. Дескриптор имеет следующий вид
В языке С существуют специальные записи, которые называются битовыми полями. Их формат следующий: struct <имя поля>{ <тип><поле 1> : длина в битах; . . . . . . <тип><поле n> : длина в битах; } В одной структуре могут быть объединены как обычные поля, так и битовые. 3.8.4. ОбъединенияОбъединение – представляет собой ячейку оперативной памяти, которая в разные моменты времени выполнения программы, может хранить данные различных типов. Реализуются в Fortran в виде оператора EQUIVALENCE: INTEGER <имя1> REAL <имя2> EQUIVALENCE (имя1, имя2) В языке С введен специальный тип – объединение union: union u { int I; char c; float r; }. Под переменную типа объединение всегда выделяется ячейка памяти в соответствии с элементом максимальной длины. Для переменной типа union определены операции сравнения на равенство и неравенство. Это довольно ненадежный тип данных, т.к. проверку типа в объединении можно осуществить только на стадии выполнения программы, что требует к тому же больших временных затрат. Вариантная запись В системе данных языка Pascal тип объединение как таковой отсутствует. Однако, начиная с 5-ой версии, в нем декларированы вариантные записи, которые реализованы как размеченные объединения. Появилась метка (переменная), которая хранит тип варианта поля записи. Когда метка принимает конкретное значение, выбирается тот или иной вариант: type rec2 = record c : longint; Case aaa byte of 1 : (d : word); 2 : (e : single) end. Варианты оформляются конструкцией Case … of и примечательны тем, что память под них отводится одна и та же (как в объединениях).
Наличие вариантных записей в Pacsal позволило обойти отсутствие блоков в Pascal (напомним, что блок позволяет объявлять новые переменные в теле программы). Program AAA; type rec : record; c : longint; case k : byte of 1: (d : word); 2: (e : record); case s : integer of 3 : (f : int); 5 : (g : real); ‘3’ : (c : word); end; var r : rec; begin k := 1; s := ‘3’; r.e.c = 1000; end. Контрольные вопросы: 1. Охарактеризовать простые типы данных: целочисленный, вещественный, логический, символьный. Привести форматы оператором описаний, диапазоны изменений, операции, проблемы, возникающие при использовании данных типов. 2. Привести внутреннее представление целочисленного и вещественного типа. 3. Охарактеризовать строковый тип данных. 4. Что такое указатель? Операции над указателями. Какие существуют проблемы при использовании указателей? 5. Дать определение массива. Какие существуют категории массивов? Операции над массивами. Привести функции доступа к элементам одно- и двумерного массива. 6. Для чего используется перечислимый и ограниченный типы данных? 7. Охарактеризовать такие структурные типы, как множество, запись, объединение. |