4796

Структурные типы данных

Лекция

Информатика, кибернетика и программирование

Структурные типы данных Статические типы данных: Регулярный тип данных. Массивы. Одномерные массивы. Селекторные изменения. Многомерные массивы и общие типы индексов. Динамические и гибкие массивы. Строки. Комбинированный тип данных. Записи. Раздел ...

Русский

2012-11-27

98 KB

18 чел.

Структурные типы данных

Статические типы данных: Регулярный тип данных. Массивы. Одномерные массивы. Селекторные изменения. Многомерные массивы и общие типы индексов. Динамические и гибкие массивы. Строки. Комбинированный тип данных. Записи.

Раздел типов

Перечисляемый тип

Наряду с стандартными типами данных в языке Паскаль широко используются типы, определяемые программистом. Один из таких типов - это перечисляемый тип. Определение перечисляемого типа задает упорядоченное множество значений путем перечисления имен, обозначаюших эти значения.

Tипы данных, определяемые программистом, описываются в специальном разделе - разделе типов. Раздел типов определен синтаксической диаграммой:

            

Перечисляемый тип данных определяется следующей диаграммой :

Примеры определений перечисляемых типов :

а). Colour = (Red, Orange, Yellow, Green, Blue, Black);

б). Operation = (Plus, Minus, Times, Divide)

Заметим, что стандартный тип Boolean, если бы его нужно было описать, выглядел бы как : type Boolean = (False, True);

Для аргументов перечисляемого типа определены функции:

Succ(x) - значение, следующее за x.

Pred(x) - значение, предыдущее x.

Ord(x)  - порядковый номер x.

К значениям перечисляемого типа применимы отношения:

=, <>, <, <=, >=, > .

Упорядоченность значений определяется порядком перечисления констант в описании типа. Например :

Red < Orange < Yellow < Green < Blue < Black ;

Описание типа переменной может быть дано и в разделе переменных. Например, описание :Type Figure = (Triangle, Circle, Rhombus, Square);

Var f: Figure; эквивалентно описанию Var f: (Triangle, Circle, Rhombus, Square); однако во втором случае описание типа становится анонимным: тип описан, но не имеет имени. Использование этого типа ограничено.  Поэтому 1-ый вариант более соответствует стилю языка.

Ограниченные типы

Ограниченный тип в языке Паскаль можно определить, накладывая ограничения на уже определенный скалярный тип - его называют базовым скалярным типом. Ограничения определяются диапазоном - минимальным и максимальным значениями констант базового скалярного типа. Ограничение стандартного типа Real не допускается.

Синтаксическая диаграмма ограничения имеет вид:

Например:

а) Type Day = 1..30; - ограничение на тип integer;

б) Digit = ‘0’..’9’; - ограничение на тип char;

в) Type Weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

Workday = Monday .. Friday; -  ограничение на скалярный тип Weekday.

Базовый скалярный тип определяет допустимость всех операций и отношений над значениями ограниченного типа. Ограниченые типы дают возможность описывать алгоритм в более наглядной форме. Кроме того, в процессе трансляции и исполнения программы появляется возможность экономить память и осуществлять контроль присваиваний.

Пример.

Program Time_Table;

 Type Weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

        Workday = Monday .. Friday;

   Var i : Workday;

 Begin

   For i := Monday to Friday do

    Case i of

      Monday:                       Writeln(‘физика‘, ’информатика‘, ’история’);

     Tuesday, Friday:           Writeln(‘мат. анализ‘,’педагогика‘, ‘английский’);

     Wednesday, Thursday: Writeln(‘физика ‘,’алгебра‘,’информатика’)

   end

End.

Сложные (составные) типы

В языке Паскаль реализован механизм определения сложных (составных) типов данных. Новый тип данных определяется как структурированная совокупность данных-компонент стандартных или ранее определенных типов. Поскольку типы компонент могут также составными, можно строить сложные иерархии типов. Методы структурирования данных в языке позволяют строить массивы, записи, множества и файлы. Эти методы называют статическими, поскольку их описание осуществляется предварительно. Более сложные структуры можно создавать динамически - в процессе выполнения программы - с помощью ссылок.  При изучении сложных типов основное внимание уделяется способам конструирования данного и способам доступа к компонентам данного.

Простые типы данных либо предопределены как стандартные, либо определяются в программе.


Стандартные типы
 Типы, определяемые программистом 

Integer;   Перечисляемый тип;

Real;    Скалярный тип.

Char:

Boolean.

С понятием простого типа связаны:

имя типа;

множество допустимых значений типа;

набор операций, определенных на типе;

набор отношений, определенных на типе;

набор функций, определенных или принимающих значения на типе;

С понятием сложного типа связаны:

имя типа;

способ объединения данных в данное сложного типа;

способ доступа к данным, образующим сложное данное типа;

Регулярный тип. Массивы

Значениями регулярного типа являются массивы. Массив - это наиболее распространенная структура данных. Во многих языках программирования (Fortran, Algol-60, Basic) это единственный явно определенный сложный тип.

Массив - это последовательность однотипных данных, объединенная общим именем, элементы (компоненты) которой отличаются (идентифицируются) индексами. Индекс элемента указывает место (номер) элемента в массиве. Количество элементов массива фиксировано и определено в его описании.  Доступ к элементу массива осуществляется вычислением значения его индекса. Поэтому массивы - это структуры данных с прямым (случайным) доступом. Все компоненты массива являются одинаково доступными. При определении регулярного типа задается и тип компонент, и тип индексов. Само определение имеет вид:

<имя типа> = Array [< тип индекса>] of <тип компоненты>;

Примеры:

а) Type LinearTable = Array [0..100] of Integer;

б) type   Word = Array [1..20] of Letter;

           Letter = ‘a’..’z’;

            Order = Array [Letter] of Integer;

в) type Matrix = array [1..N] of array [1..M] of Real;

В примере в) M и N - константы целого типа. Обратите внимание на то, что значения типа Matrix - M*N матрицы - определяются как массивы, компонентами которых, в свою очередь, являются массивы из вещественных чисел.

Регулярный тип, значениями которого являются многомерные массивы (например, в) и г)), можно определять в сокращенном виде:

Type <имя> = Array [<Tип> {,<Tип>} ] of <тип компоненты>;


Например
:

а) Type matrica = array [1..N,1..M] of real;

б) Type   Index1 = -10..10;

              Index2 = 0..20;

              Index3 = 0..3;

             Tenzor = Array [Index1, Index2, Index3] of Real;

в) Type   Labyrinth = array [1..100,1..100] of Boolean;

Типы Real и Integer не могут быть типами индексов!

Компонента переменной регулярного типа - компонента массива явно обозначается именем переменной, за которым в квадратных скобках следуют индексы; индексы являются выражениями типа индекса.

Например, Table[1, i+j], T[2*i+1, (j*j) mod i], S[Monday, Friday]. Обратите внимание на то, что в отличие от индексных выражений, границы индексов в переменных - массивах должны быть константами. Значения индексных выражений должны быть значениями типа индекса, т.е. находиться в пределах, определенных границами индексов.

Кроме регулярных типов, в языке определены еще некоторые сложные типы. Каждое такое определение задает свой, характерный механизм объединения данных в единое целое и механизм доступа к данным - компонентам сложного данного.

Это

  •  комбинированный тип (записи),
  •  файловый тип (файлы),
  •  множественный тип (множества)
  •  ссылочный тип (ссылки).

Комбинированный тип. Записи.

Значениями так называемого комбинированного типа данных являются записи. Комбинированный тип задает образ структуры объекта - данного этого типа, каждая часть которой (поле) может иметь совершенно различные характеристики.

Таким образом, запись - это набор разнотипных данных, объединенных общим именем. Более формально, запись содержит определенное число компонент, называемых полями.

В определении типа записи задается имя и тип каждого поля записи:

<комбинированный тип>::= Record < список описаний полей > End

   <список полей>::= <фиксир. часть> | <фиксир. часть>;<вариант. часть> | <вариант. часть>

<фиксированная часть>::= <секция записи> {,<секция записи>}

< секция записи >::= <имя поля>{,<имя поля>}:< тип > <пусто>

Синтаксис записей, содержащих вариантную часть - записей с вариантами - мы определим ниже. Соответствующие синтаксические диаграммы записей с вариантами:


             

              

Примеры.

Type Complex = Record

  Re, Im : Real

 end;

Var z1, z2 : Complex;

Type Name = array [1..15] of Char;

         Student = Record

                F1,F2,F3 : Name;

                Day : 1..31;

                Month : 1..12;

                Year : integer;

                StudDoc : integer

          end;

Var Group : array [1..25] of student;

              S : Student;

При обозначении компоненты записи в программе следом за именем записи ставится точка, а затем имя соответствующего поля. Таким образом осуществляется доступ к этой компоненте Например:

1)   z1.Re := 2;  z1.Im := 3;

            M := sqrt(sqr(z1.Re) + sqr(z1.Im));

2)  S.F1 := Group[i].F1;

          S.Year := Group[i + 1].Year;

          writeln( Group[i].StudDoc);

Запись может входить в состав данных более сложной структуры. Можно говорить, например, о массивах и файлах, состоящих из записей. Запись может быть полем другой записи.

Записи с вариантами.

Синтаксис комбинированного типа включает и вариантную часть, предполагающую, что можно определить тип, содержащий определения нескольких вариантов структуры. Например, запись в компьютерном каталоге библиотеки может иметь следующую структуру:

Фиксированная часть

Фамилия   Имя   Отчество

{автора}

Название

{книги}

Издательство

{его атрибуты}

Шифр

{библиотеки}

Состояние

(выдана, в фонде,  в архиве)

 

Вариантная часть

Значение признака 

выдана

в фонде

в архиве

Поля вариантной части

Фамилия И.О

N% {чит.билета}

Дата {выдачи}

адрес {хранения}

имя {архива}

адрес {хранения}

дата {архивации)

Синтаксис вариантной части:

<вариантная часть >::= case <поле признака> <имя типа> of < вариант > {;<вариант>}

<вариант>::=<список меток варианта>:(<список полей>) _ <пусто>

<список меток варианта>::=<метка варианта>{;<метка варианта>}

<метка варианта>::=<константа>

<поле признака>::=<имя>:<пусто>

Описание типа записи в рассмотренном примере может иметь вид:

Пример

 Book = record

  Author : FullName; {фиксированная часть}

  BookName: String;   BookCode: Code;

  Station : (Readed, inFile, inArchive);

  case Station of {поле признака}

  Readed: Reader : FullName; {вариантная часть}

  ReadCode : Integer;

  ReadDate : Date;

  inFile: FilAdress : Adress;

  inArc : ArcName : Srting;

  ArcAdress: Adress

     end

 end;

В примере на варианты указывает поле Station. В зависимости от значения этого поля запись имеет ту или иную структуру. Это частая ситуация. Обычно на вариант записи указывает одно из полей фиксированной части этой записи. Поэтому синтаксисом допускается сокращение: описание определяющей вариант компоненты, называемой полем признака (дискриминантом), включается в сам заголовок варианта.

Type BookStation = (Readed, inFile, inArc);

Book = record

Author : FullName;

BookName : String;

BookCode : Code;

case Station : BookStation of

Readed : Reader : FullName;

ReadCode : Integer;

ReadDate : Date;

inFile : FilAdress: Adress;

inArc : ArcName : String;

ArcAdress: Adress

  end

end;

 

Все имена полей должны быть различными, даже если они встречаются в различных вариантах. (Например, Author, Reader - имена людей, а FilAdress и ArcAdress - адреса, указывающие на местонахождение книги на полках хранилища). В случае, когда один из вариантов не содержит вариантной части, он должен быть оформлен следующим образом:

EmptyVariant :( ) {EmptyVariant - метка пустого варианта}

Оператор присоединения.

Если A - переменная типа Student из примера 1, ee значение можно изменить группой операторов:

A.F1 := 'Иванов '; A.F2 := 'Илья '; A.F3 := 'Иннокентьевич ';

A.Day := 14; A.Month := 9; A.Year := 1976;

 A.StudDoc := 123;

Приведенные выше обозначения можно сократить с помощью оператора присоединения. Заголовок этого оператора открывает область действия "внутренних" имен полей записи, которые могут быть использованы как имена переменных. Оператор присоединения имеет вид:

With <переменная-запись> {,<переменная-запись>} do <оператор>

Пример

 with A do begin

   F1 := 'Иванов ';  F2 := 'Илья '; F3 := 'Иннокентьевич ';

   Day := 14; Month := 9; Year := 1976;

   StudDoc := 123;

 end { оператора with }

 Более того, в группе операторов обработки переменной StudGroup[i] (пример 3) запись может быть сформирована следующим образом:

 With StudGroup[3], StudName do begin

  Name1 := 'Иннокентьева'; Name2 := 'Инна '; Name3 := 'Ивановна ';

  BirthDay.Day := 14; BirthDay.Month := 9; BirthDay.Year := 1976;

  StudDoc := 123

 end;

Таким образом, оператор вида  

With r1,...,rn do S  

эквивалентен оператору

 With r1 do with r2 ... with rn do S.

 

Замечание: В операторе With R do S выражение R не должно содержать переменных, изменяемых в операторе S. Например, оператор With S[j] do j := j + 1 недопустим!

Строки и средства их обработки

Значением строкового типа данных являются строки. Стандарт языка предусматривает использование строк только как констант, используемых в операторах вывода Write, Writeln.  В расширении языка Turbo-Паскаль строковый тип данных определен гораздо полнее.

Определение строкового типа следует диаграмме:

Здесь целое принадлежит диапазону 1..255 и означает максимальное количество символов в строке этого типа. Если описание типа String используется без указания максимального количества символов, это (по умолчанию) означает, что под этот тип резервируется 255 символов.

Например:

  Type Name = String[20]; { строки из 20-ти символов }

  Post = String; { строки из 255-ти символов }

Процедуры и функции типа String.

Над строками определена операция конкатенации "+", результат которой - строка, в которой операнды соединены в порядке их сле-дования в выражении. Например:

'Turbo' + 'Паскаль' = 'TurboПаскаль';     'Turbo_' + 'Паскаль ' + 'System' = 'Turbo_Паскаль System';

Поэтому результатом выполнения серии операторов

X := 'Пример'; У := 'сложения'; Z := 'строк';

Writeln(X + Y + Z); Writeln(Y + ' ' + Z + ' ' + X)

будут выведенные на экран строки

Примерсложениястрок

сложения строк Пример

Тип String допускает и пустую строку - строку, не содержащую символов: EmptyStr := '' {подряд идущие кавычки}. Она играет роль нуля (нейтрального элемента) операции конкатенации: EmptyStr + X = X + EmptyStr = X

Над строками определены также отношения (операции логического типа)

" = ", " <> ", " < ", " > ", " <= ", " >= ".

Таким образом, каждый из строковых типов упорядочен, причем лексикографически. Это означает, что

а) порядок на строках согласован с порядком, заданным на символьном типе (Char);

б) сравнение двух строк осуществляется посимвольно, начиная с первых символов;

в) если строка A есть начало строки B, то A < В;

г) пустая строка - наименьший элемент типа.

Например:

а) 'с' < 'k', так как Ord(‘c’) < Ord(‘k’);

б) 'abс' < 'abk', так как первые два символа строк совпадают, а сравнение третьих дает   Ord(‘c’) < Ord(‘k’);

в) 'abс' < 'abkd', так как первые два символа строк совпадают, а сравнение третьих дает Ord(‘c’) < Ord(k);

г) 'ab' < 'abсd', так как строка 'ab'- начало строки 'abсd'.

На строковом типе данных определены:

Функции:

a) Length(X: String): Byte; - длина строки X; { Length(EmptyStr) = 0 }

б) Pos(Y:String; X:String):Byte; - позиция первого символа первого слева вхождения подстроки Y в строку X. Если X не содержит Y, Pos(Y, X) = 0.

в) Copy(X:String; Index, Count: Integer):String - подстрока строки X, начинающаяся с позиции Index и содержащая Count символов.

г) Concat(X1, X2, .., Xk: String): String; - конкатенация строк Х1, X2, .., Xk. Другая форма записи суммы X1+X2+ .. +Xk.


Процедуры:

д) Delete(var X: String; Index, Count: Integer); Из строки X удаляется Сount символов, начиная с позиции Index. Результат помещается в переменную X.

e) Insert(Y:string; var X: String; Index: Integer); В строку X вставляется строка Y, причем вставка осуществляется начиная с позиции Index.

Стандартные процедуры ввода-вывода Паскаля расширены для ввода-вывода строк. Отметим, однако, что для ввода нескольких строковых данных следует пользоваться оператором Readln. Оператор Read в этих случаях может вести себя непредсказуемо.


Type

Имя типа

=

Описание типа

;

Раздел

типов

(

)

мя данного

,

Перечисляемый 

тип

MinConst

MaxConst

. .

Ограниченный

тип

Фиксированная

часть

Фиксированная

часть

Вариантная

часть

Вариантная

часть

  ;

 End

Record

Комбинированный

тип

 Секция записи

;

Фиксированная часть

Имя поля

,

 Тип

:

Секция

записи

Имя типа

=

 String

 Целое

[

 ]

Тип

String


 

А также другие работы, которые могут Вас заинтересовать

63693. Правовой статус личности: понятие, структура, виды, принципы 209.64 KB
  Правовой статус личности это правовое положение человека отражающее его фактическое состояние во взаимоотношениях с обществом и государством Перевалов В. Под правовым статусом личности в широком смысле понимается юридически закрепленное положение...
63694. Основные категории статистики 173.31 KB
  Основные категории статистики Статистика оперирует определенными категориями т. Задача статистики установить общие свойства единиц совокупности изучить имеющиеся взаимосвязи и закономерности развития. Задача статистики используя адекватную систему показателей дать...
63697. ЛОГІКА ПРАВА 335.5 KB
  Логiка в структурi права i право як логiчна система. Форомальна логiка юридична логiка дiалектична логiка права. Логiка норми права.
63700. Организация инженерной защиты населения от поражающих факторов 966.5 KB
  В зависимости от защитных свойств их подразделяют на убежища и противорадиационные укрытия; для защиты людей применяют и простейшие укрытия. Укрываемые должны содержать в готовности средства индивидуальной защиты: противогазы респираторы...
63701. Соціально-економічна природа витрат виробництва 161.05 KB
  Діяльність більшості суб’єктів господарювання пов’язана з виробництвом продукції, виконанням робіт чи наданням послуг, їх реалізацією задля забезпечення конкурентоспроможності, фінансової рівноваги й економічного розвитку в нестабільному ринковому середовищі.