NetNado
  Найти на сайте:

Учащимся

Учителям



Лабораторная работа №


Лабораторная работа 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)s2e-1291.m, если 0
v=0, если e=0.

Точность 11-12 знаков.
Single

1 8 23

S

e

m

Формула для вычисления значения, хранящегося в памяти:

v=(-1)s2e-1271.m, если 0
v=(-1)s21260.m, если e=0 и m<>0

v=(-1)s0., если e=0 и m=0

v=(-1)sInf, если e=255 и m=0

v=NaN, если e=255 и m<>0

Точность 7-8 знаков.
Double

1 11 52

s

e

m


Формула для вычисления значения, хранящегося в памяти:

v=(-1)s2e-10231.m, если 0
v=(-1)s210220.m, если e=0 и m<>0

v=(-1)s0., если e=0 и m=0

v=(-1)sInf, если e=2047 и m=0

v=NaN, если e=2047 и m<>0

Точность 15-16 знаков.
Extended

1 15 63

s

e

m

Формула для вычисления значения, хранящегося в памяти:

v=(-1)s2e-163831.m, если 0
v=(-1)s2163820.m, если e=0 и m<>0

v=(-1)s0., если e=0 и m=0

v=(-1)sInf, если 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зап = Vii=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


скачать

Другие похожие работы:

Документы

архив: 1 стр.

Документы

архив: 1 стр.

Документы

архив: 1 стр.

Документы

архив: 1 стр.

Документы

архив: 1 стр.

Документы

архив: 1 стр.

Лабораторная работа 1

Лабораторная работа: 6 стр.

Документы

архив: 1 стр.