4796

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

Лекция

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

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

Русский

2012-11-27

98 KB

21 чел.

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

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

Раздел типов

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

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

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


 

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

17329. ЕКОНОМІЧНА ДУМКА СТАРОДАВНЬОГО СВІТУ ТА СЕРЕДНЬОВІЧЧЯ. МЕРКАНТИЛІЗМ 263.5 KB
  ЕКОНОМІЧНА ДУМКА СТАРОДАВНЬОГО СВІТУ ТА СЕРЕДНЬОВІЧЧЯ. МЕРКАНТИЛІЗМ Історія економічної думки бере свій початок у глибокій давнині. Уже первісні люди мали якісь зачатки господарських знань котрі були результатом осмислення виробничого досвіду. З розвитком сус
17330. КЛАСИЧНА ШКОЛА ПОЛІТИЧНОЇ ЕКОНОМІЇ 220 KB
  КЛАСИЧНА ШКОЛА ПОЛІТИЧНОЇ ЕКОНОМІЇ Розвиток капіталістичних відносин спричинив занепад меркантилізму передовсім в Англії найбільш економічно розвинутій країні. Інтереси буржуазії переміщуються зі сфери обігу у сферу виробництва. На перший план виходить проми
17331. ЕВОЛЮЦІЯ КЛАСИЧНОЇ ПОЛІТИЧНОЇ ЕКОНОМІЇ В ПЕРШІЙ ПОЛОВИНІ ХІХ СТОЛІТТЯ. ЗАВЕРШЕННЯ КЛАСИЧНОЇ ТРАДИЦІЇ 309 KB
  Еволюція класичної політичної економії в першій половині ХІХ століття. завершення класичної традиції Класична школа політичної економії започаткована Адамом Смітом і Давидом Рікардо справила великий вплив на дальший розвиток економічної науки та формуванн...
17332. КРИТИЧНИЙ НАПРЯМ ПОЛІТИЧНОЇ ЕКОНОМІЇ. ФОРМУВАННЯ СОЦІАЛІСТИЧНИХ ІДЕЙ 97 KB
  КРИТИЧНИЙ НАПРЯМ ПОЛІТИЧНОЇ ЕКОНОМІЇ. ФОРМУВАННЯ СОЦІАЛІСТИЧНИХ ІДЕЙ Початок XIX ст. ознаменувався бурхливим розвитком капіталізму що був прискорений промисловим переворотом. Розвиток капіталістичних відносин супроводжувався занепадом і розкладом дрібного виро
17333. ЕКОНОМІЧНІ ВЧЕННЯ ЗАХІДНОЄВРОПЕЙСЬКИХ СОЦІАЛІСТІВ-УТОПІСТІВ 150 KB
  ЕКОНОМІЧНІ ВЧЕННЯ ЗАХІДНОЄВРОПЕЙСЬКИХ СОЦІАЛІСТІВУТОПІСТІВ Економічна теорія особлива форма переосмислення дійсності з метою її вдосконалення. Вона завжди виходила з того що економічне життя суспільства є базовим щодо інших сторін суспільного буття і виз...
17334. ВИНИКНЕННЯ АЛЬТЕРНАТИВНОЇ ШКОЛИ ПОЛІТИЧНОЇ ЕКОНОМІЇ. НІМЕЦЬКА НАЦІОНАЛЬНА ПОЛІТЕКОНОМІЯ 146 KB
  Виникнення альтернативної школи політичної економії. Німецька національна політекономія У XIX cт. доктрина Адама Сміта користувалася загальним визнанням залишаючи далеко позаду інші економічні теорії. Хоча послідовники класичної школи пропонували власні кор
17335. МАРЖИНАЛІЗМ. СТАНОВЛЕННЯ НЕОКЛАСИЧНОЇ ТРАДИЦІЇ В ЕКОНОМІЧНІЙ ТЕОРІЇ 181.5 KB
  МАРЖИНАЛІЗМ. СТАНОВЛЕННЯ НЕОКЛАСИЧНОЇ ТРАДИЦІЇ В ЕКОНОМІЧНІЙ ТЕОРІЇ В останній третині ХІХ ст. в економічній теорії виникла нова течія маржиналізм яка згодом стала визначальним напрямом розвитку політичної економії. Об’єктивна зумовленість її появи поляга
17336. ЕКОНОМІЧНА ДУМКА В РОСІЇ 174 KB
  ЕКОНОМІЧНА ДУМКА В РОСІЇ На стані російської суспільної у тім числі економічної думки ХІХ ст. позначились особливості історичного розвитку країни. Якщо на Заході економічна думка вирішувала проблеми капіталізму як реально існуючого способу виробництва то прогре...
17337. ЕКОНОМІЧНА ДУМКА В УКРАЇНІ 269.5 KB
  ЕКОНОМІЧНА ДУМКА В УКРАЇНІ Економічна думка в Україні має багатовікову історію. У цьому розділі розглянуто лише економічну думку другої половини ХІХ ст. коли відбувалися величезні зрушення в економіце та соціальній структурі суспільства. Ліквідація кріпацтва при