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


 

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

80261. Світове господарство та основні напрямки економічної думки на етапі інформаційно-технологічної революції ( кінецьXX - початок XXI ст.) 82 KB
  Динаміка світового господарського розвитку другої половини ХХ – початку ХХІ ст. Динаміка світового господарського розвитку другої половини ХХ – початку ХХІ ст. для економічно розвинутих країн характеризується якісно новим етапом економічного розвитку. Найважливішим фактором економічного розвитку є науковотехнічний прогрес.
80262. Економічний розвиток України в умовах радянської економічної системи та його трактування в економічній думці 134 KB
  Економічний розвиток України в умовах радянської економічної системи та його трактування в економічній думці 1. Соціальноекономічний стан Західної України в 20-30х роках ХХ ст. Господарство України в роки Другої світової війни та післявоєнної відбудови. Перша світова війна мала руйнівний вплив на економіку України.
80263. Формування засад ринкового господарства в Україні (90-ті роки ХХ ст.) 46.5 KB
  Участь України в світовому господарстві. Проблеми соціальноекономічного реформування української економіки в перші роки незалежності Проголошення незалежності України відкрило нову еру в історії нашої країни. Верховна Рада України затвердила Основи національної економічної політикиrdquo;. У цьому документі передбачалася структурна перебудова господарства України.
80264. Особливості розвитку ринкового господарства й основні напрямки економічної думки в Україні (друга половина ХІХ - початок ХХ ст.) 82.5 KB
  Особливості розвитку ринкового господарства й основні напрямки економічної думки в Україні друга половина ХІХ початок ХХ ст. Промисловий переворот в Україні. Суть індустріалізації в Україні. Загальні умови і основні напрямки розвитку економічної думки в Україні наприкінці ХІХ – початку ХХ ст.
80265. Господарство та економічна думка в період державно-монополістичного розвитку суспільств Європейської цивілізації (перша половина ХХ ст.) 97.5 KB
  Обновлялися основні галузі економіки: хімічна електрична приладобудівна автомобільна радіотехнічна. Одним з найбільших недоліків її післявоєнної економіки була залежність від імпорту сільськогосподарської продукції та промислової сировини. Німеччина втратила зовнішні ринки через розвал економіки звузилися її внутрішні ринки. Катастрофічне становище в основних галузях економіки було причиною краху кредитнофінансової системи Німеччини.
80266. ПІДГОТОВКА ПІД-ПРИЛАДУ МОДЕЛЮВАННЯ ЗМІНИ ТЕМПЕРАТУРИ - SIMULATED TEMPERATURE 681.5 KB
  Підготовка під приладу Моделювання зміни температури Simulted Temperture. Віртуальний прилад що моделює зміну температури: а контрольна панель; б блоксхема приладу. Vi для моделювання зміни температури починається з контрольної панелі на яку слід вивести дев’ять задавачів зміни температури об’єднавши їх у одномірний масив рисунок 7.
80267. Основні функції для підготовки віртуального приладу дослідження температури 322.5 KB
  Основні функції для підготовки віртуального приладу дослідження температури Для виведення функції Rdio Button на контрольну панель Controls ModernClssic Boolen 12 Boolen Rdio Button.– Меню для виведення функції Rdio Button на контрольну панель Вигляд функції Rdio Button яку названо Шкала температур на контрольній і функціональній панелі показано на рисунку 7.8 Функція Rdio Button яку названо Шкала температур на контрольній а і функціональній б панелі ЛІТЕРАТУРА 1 Большая советская енциклопедія Т3 стр.
80268. ВІРТУАЛЬНИЙ ПРИЛАД ДОСЛІДЖЕННЯ ВТРАТИ ТИСКУ НА ДІЛЯНЦІ ТРУБОПРОВОДУ 75.5 KB
  Склад та принцип дії насосної установки УНБ1 – 400х40 Установка змонтована на автомобілі КрАЗ–250 складається із силового агрегату карданного і проміжного валів коробки передач плунжерного насоса з навісним редуктором маніфольда допоміжного трубопроводу водоподавального блока цементного бачка поста керування з фарою для освітлення зубчастої муфти та випускної труби двигуна автомобіля. Технічна характеристика установки УНБ1400х40 Двигун Чотирикратний...
80269. АЛГОРИТМ СТВОРЕННЯ ВІРТУАЛЬНОГО ПРИЛАДУ ВИМІРЮВАННЯ ТИСКУ НА ДІЛЯНЦІ ТРУБОПРОВОДУ 1.99 MB
  Для вибору і розміщення необхідних на лицьовій панелі приладу елементів слід у верхній горизонтальній лінійці піктограм (ВГ-ЛП) обрати передостанню зліва закладку Вікно – Window і натиснути ЛКМ.