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


 

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

36911. Файлы и папки 185 KB
  Скопируйте этот файл с заданием в свою сетевую папку на studdc1 Загрузить программу Проводник. Создайте на своем рабочем столе структуру папок: Для этого щелкните правой кнопкой мыши для вызова контекстного меню выберите команду Создать Папку. Откройте текстовый файл и наберите текст: Переместите файл МОЙ ТЕКСТ в папку SUB. В любой папке доступной на Вашем компьютере выберите три файла вразброс используя для выделения клавишу Ctrl и скопируйте их в папку SUB.
36912. Операционная система MS DOS, конфигурирование и настройка 58.5 KB
  ОС MSDOS основные системные команды. Системные команды MS DOS MSDOS сокр. MSDOS самая известная ОС из семейства DOS ранее устанавливаемая на большинство PCсовместимых компьютеров.
36913. Исследование характеристик ТТЛ элемента 49.5 KB
  Исследование характеристик ТТЛ элемента. Цель лабораторной работы: исследовать основные свойства стандартного ТТЛ элемента переходную характеристику входную характеристику и выходные характеристики. На рабочем столе собрать принципиальную электрическую схему логического элемента ТТЛ. На вход элемента подключить источник напряжения изменяющегося по треугольному закону.
36914. Выделение и перемещение фрагментов изображения, кадрирование изображений 158.5 KB
  dobe Photoshop Тема: Выделение и перемещение фрагментов изображения кадрирование изображений Цель: приобрести навыки работы с инструментами выделения фрагментов изображений научиться перемещать и копировать выделенные фрагменты. Краткие теоретические сведения В данном уроке используются следующие инструменты: Инструмент Zoom Масштаб позволяет получать изображение на экране в увеличенном или в уменьшенном виде. Инструмент Crop Рамка позволяет выделить прямоугольный фрагмент изображения и удалить ту его часть которая осталась за...
36915. КОМПЬЮТЕРНАЯ СИСТЕМА PROJECT EXPERT. ФОРМИРОВАНИЕ ФИНАНСОВОЙ МОДЕЛИ ПРОЕКТА 47.5 KB
  ФОРМИРОВАНИЕ ФИНАНСОВОЙ МОДЕЛИ ПРОЕКТА Цель: изучить систему команд Project Expert формирования финансовой модели инвестиционного проекта для предприятия. Построив с помощью Project Expert финансовую модель собственного предприятия или инвестиционного проекта можно получить такие возможности: разработать детальный финансовый план и определить потребность в денежных средствах на перспективу; определить схему финансирования предприятия оценить возможность и эффективность привлечения денежных средств из различных источников; разработать...
36916. Структура управления регионального международного аеропорта (РМА) 55 KB
  Непосредственно генеральному директору аэропорта подчиняются его замы и директора по направлениям а также самостоятельные структурные подразделения и службы. Типовая структура РМА представлена на схеме: Деятельность отдельных подразделений и служб аэропорта Основные функции службы качества: 1. разработка перспективных направлений повышения качества услуг авиакомпаниям и клиентам аэропорта; 2.
36917. Исследование статической и динамической характеристики термопары 188 KB
  Исследование статической и динамической характеристики термопары. Ознакомиться со схемами включения измерительного прибора в цепь термопары. Экспериментально получить статическую и динамическую характеристики термопары. Определить математическую модель термопары.
36918. Знакомство с математическим пакетом Scilab 141.5 KB
  Знакомство с математическим пакетом Scilb Scilb это система компьютерной математики которая предназначена для выполнения инженерных и научных вычислений таких как: решение нелинейных уравнений и систем; решение задач линейной алгебры; решение задач оптимизации; дифференцирование и интегрирование; обработка экспериментальных данных интерполяция и аппроксимация метод наименьших квадратов; решение обыкновенных дифференциальных уравнений и систем. Кроме того Scilb предоставляет широкие возможности по созданию и редактированию...
36919. ОРГАНИЗАЦИЯ РАБОЧЕГО ПРОСТРАНСТВА MS EXCEL. ВВОД И ФОРМАТИРОВАНИЕ ДАННЫХ. СОРТИРОВКА И ФИЛЬТРАЦИЯ ДАННЫХ 730.5 KB
  ВВОД И ФОРМАТИРОВАНИЕ ДАННЫХ. СОРТИРОВКА И ФИЛЬТРАЦИЯ ДАННЫХ Цель работы: изучить рабочее пространство приложения MS Excel научиться применять различные параметры форматирования к данным сортировать данные и проводить их фильтрацию по заданным условиям. Изучить параметры форматирования данных в MS Excel и научиться их настраивать. Научиться создавать последовательности данных.