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

Массивы

Строки

Множества

Записи

Неструктурные алгоритмы и их реализация

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

Для организации неструктурных передач управления используют оператор безусловной передачи управления goto и специальные процедуры.

Оператор безусловной передачи управления.Этот оператор передает управление в точку, определенную специальной меткой (рис. 3.20). Все метки в программе должны быть описаны инструкцией объявления меток label (рис. 3.21). Метка ставится перед любым выполняемым оператором программы, причем на один оператор можно поставить несколько меток.

Неструктурную передачу управления также осуществляют следующие процедуры:

Break – реализует выход из цикла любого типа;

Continue – осуществляет переход на следующую итерацию цикла, игнорируя оставшиеся до конца тела цикла операторы;

Halt (<код, завершения>) - осуществляет выход из программы, возвращая операционной системе заданный код завершения. Считается, что программа завершилась нормально, если код завершения равен нулю. Возвращение кода завершения, отличного от нуля, обычно означает, что программа завершена по обнаружении каких-либо ошибок. Коды завершения назначаются программистом, а информация о них помещается в программную документацию;

Exit – осуществляет выход из подпрограммы (см. главу 5). Если процедура использована в основной программе, то она выполняется аналогично Halt.

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

Достаточно часто возникает необходимость программирования обработки однотипных данных: таблиц, текстов, множеств и т.д. Для их представления используют структурные типы данных. В Borland Pascal определены следующие структурные типы данных:

• массивы - для представления однотипных или табличных данных;

• строки- для представления символьной (текстовой) информации;

• множества - для представления абстрактных математических множеств;

• записи - для представления таблиц с данными различных типов.

Массивы

Массив - это упорядоченная совокупность однотипных данных. Каждому элементу массива соответствует один или несколько индексов определяющих положение элемента в массиве. Индексы образуют упорядоченные последовательности.

Синтаксическая диаграмма объявления массива представлена на рис. 4.1.

Тип индекса определяет его допустимые значения. В качестве типа индекса может быть указан любой порядковый тип (boolean, char, integer, перечисляемый тип, а также диапазоны этих типов), кроме типа longint и его производных.

В зависимости от количества типов индексов различают: одномерные, двумерные, трехмерные n-мерные массивы. Двумерные массивы обычно называют матрицами, считая первый индекс - номером строки, а второй - номером столбца.

Тип элементов массива - любой допустимый в Borland Pascal тип (в томчисле и массив), кроме файла.

Объявление переменных типа массив выполняется двумя способами:

• в операторе объявления переменных, например:

• с предварительным объявлением типа, например:

Ограничения на количество индексов в Borland Pascal нет. Однако суммарная длина массива не должна превышать 65537 = 64*1024 байт (32 – 2048, 16 - 4096).

Значения элементов массива в программе можно определить тремя способами.

1. массив может быть инициализирован с использованием типизированных констант или просто присваиванием значений элементам;

2. элементы массива могут быть введены с клавиатуры или из файла;

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

Инициализация массивов. Для объявления инициализированных массивов в Borland Pascal используют типизированные константы. При этом соответствующие значения указывают в скобках через запятую. Значения элементов многомерных массивов перечисляют в порядке возрастания индексов справа налево, заключая в скобки каждый подмассив. Для матриц такой порядок соответствует построчному указанию значений.

Например:

Операции над массивами. Над массивом, в целом, определена единственная операция – операция присваивания.

Присваивание массивов заключается в копировании элементов одного массива в другой. Эту операцию можно выполнять только над массивами одного типа.

Массивы считаются совпадающими по типу, если они объявлены через запятую в одной строке, например:

или, если вначале объявлен тип массива, а затем массивы этого типа:

Доступ к элементам массива. Работа с массивом, как правило, сводится к действиям над его элементами. Для обращения к конкретному элементу массива необходимо указать имя массива и значения индексов элемента в квадратных скобках через запятую. Значения индексов можно указать непосредственно литералом, например а[3], или косвенно, указав идентификатор переменной, которая содержит, значение индекса, например a[i]

Ввод-вывод массивов. Ввод-вывод массивов выполняют поэлементно, используя циклы с заданным числом повторений.

Символьные массивы. Символьными называют массивы, элементами которых являются символы. Такие массивы традиционно использовались для представления символьной информации, например различных текстов.

Обработка символьных массивов в Borland Pascal имеет некоторые особенности.

1. Объявляя символьный массив как типизированную константу, значения

символов можно указывать поэлементно:

или целиком, используя строковую константу, длина которой должна строго

соответствовать размеру массива:

2. Присвоить значение символьному массиву также можно целиком, используя строковую константу, длина которой должна совпадать с длиной массива:

3. При вводе элементы символьного массива нельзя разделять пробелами, так как пробел будет восприниматься как символ:

4. Символьный массив можно выводить поэлементно в цикле, как обычный одномерный массив, а можно - целиком, одним оператором Write или WriteLn:

5. В операторе вывода допускается использование операции конкатенации (слияния) символьных массивов, обозначаемой символом «+». Результатом этой операции будет новый символьный массив, число элементов которого равно сумме размеров исходных массивов, а значениями элементов - элементы исходных массивов, последовательно записанные друг за другом:

Работа с одномерными символьными массивами осуществляется поэлементно, как с обычными массивами.

Строки

Уже на простом примере обработки символьной информации, рассмотренном в параграфе 4.1, видно, что обработка строк с использованием одномерных массивов представляет собой достаточно специфическую задачу. В то же время большинство операций, которые выполняют со строками текста, повторяются в разных программах: поиск, копирование, удаление и вставка фрагментов строки. Поэтому для упрощения работы со строками в Borland Pascal существует специальный тип данных - строковый, который приспособлен для обработки символьной информации.

Целое без знака - это максимальная длина строки, которая не должна превышать 255 байт. Если длина не указана, то по умолчанию принимается максимальное значение - 255 символов.

Объявление переменных строкового типа, так же как и массивов, можно выполнить двумя способами:

• в операторе объявления переменных, например:

• с предварительным объявлением типов, например:

Внутреннее представление строки показано на рис 4.27, откуда видно, что строка представляет собой одномерный символьный массив, индексы которого изменяются от 0 до максимального значения, указанного при объявлении строкового типа. Следовательно, физическая длина строки на единицу превышает максимальную.

Инициализация строк. Для инициализации строковых переменных, так же как и переменных других типов, можно использовать типизированные константы, причем строка-литерал может быть короче инициализируемой строки, например:

Операции над переменными строкового типа. Над переменными строкового типа помимо операции доступа к символам определены операции присваивания, конкатенации (сцепления) и отношений.

Доступ к символам строки выполняется как к элементам массива символов, т. е. с указанием имени строки и номера элемента, например st[l] или s[i]. Нулевой байт содержит текущее значение длины строки, но так как строка - это массив символов, длина автоматически интерпретируется как символ.

Присваивание строк. Можно присвоить строке значение строки и значение символа.

Отношения. Над строками допускается выполнять операции отношения: = , <> , >, <, >=, <=. Сравнение строк при этом выполняется последовательно слева направо с учетом внутренней кодировки символов до первого несовпадающего символа. Большей считается та строка, код несовпадающего символа которой по таблице ASCII больше. Если длина одной строки меньше другой, то недостающие значения до длины большей строки заполняются символами #0. Результатом операций отношения для строк, как и для чисел, является значение false и true.

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

S4:='ABCD'; S3:='ADFH'; C:='L';

то при выполнении операций отношения:

S4 = S3 {получим false}

S4 > S3 {получим false}

S3 > S4 {получим true}

S3 = С {получим false}

Ввод-вывод строк. Ввод-вывод переменных строкового типа осуществляется

одной операцией Read (ReadLn) или Write (WriteLn).

Процедуры и функции для работы со строками. Все основные действия

над строками и символами реализуют с помощью стандартных процедур

и функций.

1. Функция Length(st):word- возвращает длину строки st.

2. Процедура Delete(st, index, count) - удаляет count символов строки st, начиная с символа с номером index.

3. Процедура Insert(St2,Stl,index) - вставляет подстроку символов St2 в строку Stl, начиная с символа с номером index.

4. Процедура Str(x[:w [:d]], St) - преобразует результат выражения x в строку st, содержащую запись этого числа в виде последовательности символов.

5. Процедура Val(St, х, Code) - преобразует строку St с записью числа в виде последовательности символов во внутреннее представление целого или вещественного числа и помещает его в переменную х. В целочисленной переменной Code процедура возвращает код ошибки: О, если преобразование прошло успешно, и номер ошибочного символа, если строка st не являлась допустимой формой записи числа. Процедура обычно используется, если необходимо предотвратить некорректный ввод чисел.

6. Функция Copy(St,index,count):string - возвращает фрагмент строки St длиной count символов, начиная с символа с номером index.

7. Функция UpCase(ch):char - возвращает символ, соответствующий символу верхнего регистра для ch, если таковой имеется, либо сам символ ch, если для него не определен символ верхнего регистра.

Множества

Понятие множество является одним из основных в современной математике и трактуется как неупорядоченная совокупность неповторяющихся объектов. В общем случае множество может не содержать ни одного элемента. Такое множество называется пустым.

В Borland Pascal предусмотрен структурный тип, предназначенный для представления множеств. Данные множественного типа представляют собой совокупности однотипных элементов, каким-либо образом связанных друг с другом. Характер связей между элементами только подразумевается программистом и никак не контролируется.

Множественный тип объявляется как совокупность элементов некоторого базового типа (рис. 4.31). Допускается объявлять только конечные множества, количество элементов которых может меняться от 0 до 255.

В качестве базового типа могут использоваться только диапазоны значений этих типов.

Порядок расположения элементов во множестве никак не фиксируется. Это соответствует принятой в математике трактовке множества.

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

Множественный тип можно определить и непосредственно при объявлении переменных программы, например:

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

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

Инициализация множеств. Возможна инициализация переменных множественного типа с использованием типизированных констант. Например:

Операции над множествами. Для работы со значениями множественного типа предусмотрены специальные операции, в основном соответствующие операциям, определенным в теории множеств: объединение, пересечение и дополнение множеств. Это двуместные операции, операндами которых являются данные множественного типа - множества и выражения, принимающие значение множественного типа. Оба операнда должны принадлежать одному и тому же множественному типу. Обозначения этих операций в Borland Pascal и их геометрическая интерпретация представлены в табл. 4.1

Операции отношения. Наряду с рассмотренными выше операциями над значениями множественного типа определены и операции отношения. Операндами отношений в этом случае являются переменные или выражения множественного типа. В табл. 4.2 показано соответствие между математическими операциями сравнения множеств и операциями отношения, определенными в Borland Pascal.

Особое место занимает операция проверки вхождения элемента во множество, обозначаемая служебным словом in (рис. 4.32). В отличие от операций отношения, в операции in первый операнд должен принадлежать базовому типу элементов данного множественного типа. Результатом операции in, как во всех операциях отношения, является логическое значение.

Записи

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

В Borland Pascal определены записи двух типов: записи с фиксированными полями и вариантные записи (рис. 4.33).

Записи с фиксированными полями. Синтаксическая диаграмма записи с фиксированными полями представлена на рис. 4.34.

Как любой тип данных языка, записи можно определить двумя способами:

· при объявлении переменных, например:

· предварительно объявив тип записи, например:

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

Const

BirthDay: Data = (Year: 1973; Month:6; Day:30); ...

Операции над записями. Над записями возможно выполнение следующих операций:

· доступ к полям записи;

· обращаться к полям записи с использованием оператора присоединения with (рис. 4.36).

Присваивание записей. Операция возможна при совпадении типов записей и выполняется последовательно поле за полем.