Лабораторная работа №
Лабораторная работа № 3
Встроенные структуры данных
Цель работы: Изучение базовых типов данных на примере языка Turbo-Рascal как структур данных (СД)
Задание
1. Для типов данных (см. вариант индивидуального задания)
определить:
1.1. Характер организованности.
1.2. Тип доступа к элементам.
1.3. Характер изменчивости.
1.4. Схему хранения.
1.5. Объём памяти, занимаемый экземпляром СД.
1.6. Формат внутреннего представления СД и способ
его интерпретации.
1.7. Количество и множество допустимых значений.
1.8. Способ описания СД и экземпляра СД на языке
программирования.
1.9. Набор допустимых операций.
2. Для заданных типов данных определить набор значений,
необходимый для изучения внутреннего представления.
3. Преобразовать значения в двоичный код.
4. Преобразовать двоичный код в значение.
5. Разработать и отладить программу, выдающую двоич-
ное представление значений заданных СД.В программе ис-
пользовать процедуры PrintByte и PrintVar.
Спецификация процедуры PrintByte.
Заголовок процедуры:
procedure PrintByte(a:byte)
Назначение:
выводит на экран монитора двоичное представле-
ние переменной a типа byte.
Входные параметры: a:byte.
Выходные параметры: нет.
Рекомендации:
использовать битовые операции сдвига и логичес-
кого умножения.
Спецификация процедуры PrintVar.
Заголовок процедуры:
procedure PrintVar(var a; size:word)
Назначение:
выводит на экран монитора двоичное представле-
ние переменной a произвольного типа размером
size байт.
Входные параметры:
a – переменная произвольного типа, значение ко-
торой выводится на экран в двоичном пред-
ставлении (нетипизованный параметр);
size: word – объём памяти (в байтах) занимаемый
переменной a.
Выходные параметры: нет.
Рекомендации:
нетипизованную переменную a привести к типу “массив байт”, значение каждого элемента которого выводить на экран в двоичном представ-лении процедурой PrintByte.
6. Обработать программой значения п.3. Сделать выводы.
7. Разработать и отладить программу, определяющую значе-
ние переменной по её двоичному представлению.
Алгоритм.
1.Ввести двоичный код в переменную S строкового типа.
2. Преобразовать S в вектор B типа “массив байт”.
3. Привести B к заданному типу. Вывести значение.
4. Конец.
8. Обработать программой значения п.4. Сделать выводы.
Содержание отчета
1. Тема лабораторной работы.
2. Цель работы.
3. Индивидуальное задание.
4. Характеристика каждого заданного типа данных как СД в
соответствии с п.1 задания.
5. Набор значений заданных типов, порядок их преобра-
зования в двоичное представление, двоичное представле-
ние значений.
6. Набор двоичных векторов, порядок их преобразования в
значения заданных типов, значения заданных типов.
7. Спецификация алгоритма, текст программы, результаты
работы программы, выводы (п.5, 6 задания).
8. Спецификация алгоритма, текст программы, результаты
работы программы, выводы (п.7, 8 задания).
ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Простые типы данных
Целые типы. Диапазон возможных значений целых типов зависит от их внутреннего представления. В таблице 1.1 приводится название целых типов, длина их внутреннего представления в байтах и диапазон возможных значений.
Таблица 1.1
Название типа | Диапазон значений | Длина, байт |
shortint | -128..127 | 1 |
integer | -32768..32767 | 2 |
longint | -2147483648..2147483647 | 4 |
byte | 0..255 | 1 |
word | 0..65535 | 2 |
В первом байте типа integer, word располагается младшая часть числа, во втором – старшая.
Символьный тип.
Диапазон возможных значений этого типа является мно-жество всех символов. Каждому символу приписывается целое число от 0..255. Для кодировки используют код ASCII.
Название типа | Диапазон значений | Размер, байт |
Char | коды ASCII 0..255 | 1 |
Логический тип.
Множество значений: true(1) и false(0). Логический тип занимает в памяти один байт. Тип упорядочен.
Перечисляемый тип.
Он задается перечислением тех значений, которые он может получать. Каждое значение именуется некоторым идентификатором и располагается в списке, обрамленном круглыми скобками, например:
type
colors = (red, yellow, green);
Соответствие между значениями перечисляемого типа и порядковыми номерами этих значений устанавливается порядком перечисления: первое значение в списке получает порядковый номер 0, второе – 1 и т.д. Максимальная мощность перечисляемого типа составляет 65536 значений, поэтому фактически перечисляемый тип является подмножеством целого типа word.
Тип-диапазон.
Тип-диапазон есть подмножество своего базового типа, в качестве которого может выступать любой порядковый тип, кроме типа-диапазона. Он задается границами своего базового типа, например:
type
date=1..31;
month=1..12;
Вещественные типы.
Значения этих типов определяют произвольное число лишь с некоторой конечной точностью, зависящей от внут-реннего формата вещественного числа.
Название типа | Диапазон значений | Длина, байт |
real | 2.9e-39..1.7e+38 | 6 |
single | 1.5e-45..3.4e+38 | 4 |
double | 5.0e-324..1.7e+308 | 8 |
extended | 3.4e-4932..1.1e+4932 | 10 |
Внутримашинное представление вещественных типов.
Real
1 39 8
-
s
M
e
Здесь s – знак, m - мантисса, e - порядок.
Формула для вычисления значения, хранящегося в памяти:
v=(-1)s2e-1291.m, если 0
v=0, если e=0.
Точность 11-12 знаков.
Single
1 8 23
-
S
e
m
Формула для вычисления значения, хранящегося в памяти:
v=(-1)s2e-1271.m, если 0
v=(-1)s21260.m, если e=0 и m<>0
v=(-1)s0., если e=0 и m=0
v=(-1)sInf, если e=255 и m=0
v=NaN, если e=255 и m<>0
Точность 7-8 знаков.
Double
1 11 52
-
s
e
m
Формула для вычисления значения, хранящегося в памяти:
v=(-1)s2e-10231.m, если 0
v=(-1)s210220.m, если e=0 и m<>0
v=(-1)s0., если e=0 и m=0
v=(-1)sInf, если e=2047 и m=0
v=NaN, если e=2047 и m<>0
Точность 15-16 знаков.
Extended
1 15 63
-
s
e
m
Формула для вычисления значения, хранящегося в памяти:
v=(-1)s2e-163831.m, если 0
v=(-1)s2163820.m, если e=0 и m<>0
v=(-1)s0., если e=0 и m=0
v=(-1)sInf, если e=32767 и m=0
v=NaN, если e=32767 и m<>0
Точность 19-20 знаков.
Сложный тип.
Comp
1 63
-
s
d
Значение v=NaN, если s=1 и d=0, иначе v представляет
собой 64-битовое значение,являющееся дополнением до двух.
Структурированные типы данных
Массив.
Массив – последовательность элементов одного типа, называемого базовым. На абстрактном уровне массив пред-
ставляет собой линейную структуру.
На физическом уровне массив реализован последова-тельной (прямоугольной) схемой хранения. Располагаться он может в статической или динамической памяти. Размер памя-ти, выделяемый под массив, зависит от базового типа эле-мента массива и от количества элементов в массиве и опре-деляется формулой Vмас = Vэл * k, где Vмас – объём памяти для массива, Vэл- объём памяти одного элемента, k – количество элементов.
На логическом уровне СД типа массив можно описать следующим образом.
1. Type T_ar = array [T1] of T2; {T1-тип индекса }
Var Ar : T_ar; {T2-тип элемента}
Массив Ar типа T_ar располагается в статической
памяти.
2. Type TP_ar = ^T_ar;
Var P_ar : TP_ar;
Массив типа T_ar будет располагаться в динамичес-
кой памяти после обращения к процедуре new(P_ar).
Адрес массива запишется в переменную P_ar.
Массив – это статическая структура. В процессе выпол-
нения программы количество элементов массива не изменяет-ся. Доступ к элементу массива прямой,осуществляется через индекс элемента, например Ar[i] или P_ar^[i].
Кардинальное число для массива T_ar:
Car(T_ar) = [Car(T2)] Car(T1).
Набор допустимых операций для СД типа массив:
1. Операция доступа (доступ к элементам массива – прямой;
от размера структуры время выполнения операция не
зависит).
2. Операция присваивания.
СД типа запись.
Запись – это множество элементов (полей), которые могут быть различных типов.
На абстрактном уровне запись представляет собой структуру множество – отношения между элементами отсут-ствуют.
На физическом уровне запись реализована последова-тельной схемой хранения. Располагаться она может в стати-ческой или в динамической памяти. Размер памяти, выделяе-мый под запись, зависит от типов полей и от их количества и определяется формулой Vзап = Vii=1,k , где Vзап-объём памяти для записи, k-количество полей, Vi-объём памяти для i-го поля.
На логическом уровне СД типа запись можно записать следующим образом:
Type Т_rec = Record
S1: T1;
S2: T2;
……..
Sn: Tn;
End;
Var Rec: T_rec;
Здесь: S1, …, Sn – идентификаторы полей; Т1, …, Tn – типы полей; Rec – идентификатор записи; T_rec – тип записи.
Если DT1 – множество значений элементов типа Т1, DТ2 – множество значений элементов типа Т2, … , DТn – множество значений элементов типа Тn, то DTrec – множество значений элементов типа Т_rec будет определяться с помощью прямого декартова произведения: DTrec = DT1 DT2 … DТn.
Допустимые операции для СД типа запись аналогичны операциям для СД типа массив.
По характеру изменчивости запись – это статическая структура. Доступ к элементам записи прямой, осуществляется по имени поля.
СД типа множество.
Множество – это массив битов, в котором каждый бит указывает, является ли элемент принадлежащим множеству или нет. Максимальное число элементов множества – 256, так что множество никогда не может занимать более 32 байтов. Число байтов, занимаемых отдельным множеством, вычисляется как ByteSize = (Max div 8)-(Min div 8)+1, где Min и Max – нижняя и верхняя граница базового типа этого множества. Номер байта для конкретного элемента E вычис-ляется по формуле ByteNumber=(E div 8)-(Min div 8), а но-мер бита внутри этого байта по формуле BitNumber=E mod 8.
На логическом уровне множество можно описать так
Type T_set = set of T; {T - базовый тип множества}
Значениями типа множество являются все подмножества базового типа. Число элементов базового типа ограничено и не должно превышать 256. Базовый тип является перечисляемым типом или поддиапазоном перечисляемого ти-па. Кроме того, объём памяти, занимаемой значением базо-вого типа,- один байт.
Допустимыми операциями для множества являются:
1) пересечение (*);
2) объединение (+);
3) вычитание (-);
4) операции отношения:
1) равенство множеств (=);
2) неравенство множеств (<>);
3) левый операнд-подмножество правого (<=);
4) правый операнд-подмножество левого (>=);
5) принадлежность элемента множеству (in).
Варианты индивидуальных заданий
№ п/п | тип 1 | тип 2 | тип 3 |
1 | integer | real | (red, yellow, green) |
2 | longint | real | массив [1..3,1..3] char |
3 | word | double | set of byte |
4 | byte | single | 1000..2000 |
5 | integer | extended | 'A'..’Z’ |
6 | shortint | single | массив [1..5] real |
7 | longint | comp | (cat, dog,mouse,tiger) |
8 | byte | real | -300..300 |
9 | word | double | (winter,spring,summer,autumn) |
10 | shortint | real | set of 'a'..'h' |
11 | byte | single | -1..1 |
12 | word | comp | 1..256 |
13 | integer | double | set of 50..100 |
14 | byte | extended | 'a'..'h' |
15 | longint | double | -256..-1 |
16 | shortint | extended | (one,two,three,four,five,six) |
17 | word | real | 256..511 |
18 | integer | single | 1..50 |
19 | longint | extended | (a, b, c, d, e, f, g, h) |
20 | byte | double | массив [1..8] char |
21 | shortint | comp | -10..10 |
22 | word | single | запись |
23 | integer | extended | массив [1..6] boolean |
24 | byte | comp | (winter,spring,summer,autumn) |
25 | longint | double | 35000..35001 |
26 | shortint | real | set of 200..250 |
27 | word | extended | запись |
28 | integer | comp | 1..256 |
29 | byte | single | массив [1..2,1..4] integer |
30 | shortint | double | (day, night) |
страница 1
скачать
Другие похожие работы: