4796

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

Лекция

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

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

Русский

2012-11-27

98 KB

20 чел.

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

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

Раздел типов

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

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

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


 

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

21570. Средства общения 17.46 KB
  Средства общения Лисина М. В данной статье рассматривается проблемы общения взаимосвязь и психологического развития личностного становления ребенка Ключевые слова: Мимические средства общения Речь Позы Предметные движения Внимание Вокализация Три категории средств общения перечислены в том порядке в котором они появляются в онтогенезе; они составляют основные коммуникативные операции в дошкольном детстве Экспрессивномимические средства общения. Своеобразие выразительных средств общения в том что они служат проявлением эмоциональных...
21571. Закономерности поуровневого развития личности в онтогенезе 25.07 KB
  [6;110] Выделяют две социальные позиций ребенка по отношению к обществу условно названные я в обществе и я и общество . Целенаправленное рассмотрение в качестве объекта исследования особенностей социального развития детей условий становления их социальной зрелости и анализ ее формирования на разных этапах современного детства позволили вычленить два основных типа реально существующих позиций ребенка по отношению к обществу условно названных нами я в обществе и я и общество [6;111] Первая позиция где акцент делается на себя отражает...
21572. Комплексная характеристика развития игры 50.5 KB
  Комплексная характеристика развития игры . Изучение развития ролевой игры интересно в двояком отношении: вопервых при таком исследовании глубже раскрывается сущность игры; вовторых раскрытие взаимосвязи отдельных структурных компонентов игры в их развитии может помочь в педагогическом руководстве в формировании этой важнейшей деятельности ребенка [9;202] Структура игр претерпевает также большие изменения: от бессюжетных состоящих из ряда часто не связанных друг с другом эпизодов у детей трехчетырех лет они превращаются в игры с...
21573. Этапы формирования личности в онтогенезе 21.28 KB
  [1;180] Формирование личности ребенка происходит под влиянием социума. психическое развитие ребенка формирование его личности может быть понятно лишь в рамках его социализации т.[1;181] Биологические предпосылки так же играют значительную роль в формировании личности ребенка. Следует признать что не существует ни одной врожденной особенности организма которая была бы полностью нейтральной для психического развития ребенка.
21574. Краткий словарь психологических терминов 86.51 KB
  telegraphic speech один из ранних этапов развития детской речи переходный к овладению речью взрослых Л. Специальная речевая работа с детьми правильная речь окружающих взрослых исключающая подстраивание под несовершенную речь ребенка служат средством профилактики а также коррекции если этот этап развития речи затянулся А. В случаях ее развития у близнецов рекомендуется кроме того их временное разъединение АНАЛЬНАЯ СТАДИЯ англ. Фрейда 2я стадия психосексуального развития в возрасте ок.
21575. Проблема культурного развития ребенка 20.61 KB
  Ключевые слова : Психологические процессы Память Примитивный ребенок Линии психологического развития Культурный прием поведения Стадия Для правильной постановки проблемы культурного развития ребенка имеет большое значение выделенное в последнее время понятие детской примитивности. Выделение детской примитивности как особой формы недоразвития может способствовать правильному пониманию культурного развития поведения. задержка в культурном развитии ребенка бывает связана большей частью с тем что ребенок по какимлибо внешним или...
21576. Фрейд З. Я И ОНО. Сознание и бессознательное 18.78 KB
  Я И ОНО. Напротив характерно то что состояние осознательности быстро проходит; осознанное сейчас представление в следующий момент делается неосознанным но при известных легко осуществимых условиях может снова вернуться в сознание в промежутках оно было бессознательным. К этому Я прикреплено сознание оно владеет подступами к разрядке раздражений во внешний мир. сознательным может стать только то что когдато уже было СЗ восприятием и что помимо чувств изнутри хочет стать сознательным; оно должно сделать попытку превратиться во...
21577. Развитие личности: психосексуальные стадии по З. Фрейду 21.44 KB
  Ключевые слова: Стадии: оральной анальной фаллической и генитальной. В акте сосания эротический компонент получавший удовлетворение при кормлении грудью становится самостоятельным отказываясь от постороннего объекта и замещая его какимнибудь органом собственного тела [7;163] В течение второй половины первого года жизни начинается вторая фаза оральной стадии – оральноагрессивная или оральносадистическая фаза. Фрейд утверждал что все будущие формы самоконтроля и саморегуляции берут начало в анальной стадии.
21578. КАРСТ И КАРСТОВЫЕ ФОРМЫ РЕЛЬЕФА 42 KB
  КАРСТ И КАРСТОВЫЕ ФОРМЫ РЕЛЬЕФА 6. Поверхностные карстовые формы 6. Подземные карстовые формы 6. КАРСТ И КАРСТОВЫЕ ФОРМЫ РЕЛЬЕФА Карст совокупность специфических форм рельефа и особенностей наземной и подземной гидрографии свойственной областям сложенным растворимыми горными породами каменная соль гипс известняк доломит и др.