Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 9
Лекция 15
4.3.2. Концепции строк и реализация
Существует несколько проектных решений, связанных с длиной строковых величин. Во-первых, длина может быть статической и задаваться в объявлении. Подобные строки суще ствуют в языках FORTRAN 77. FORTRAN 90, COBOL, Pascal и Ada. Например, сле дующий оператор языка FORTRAN 90 объявляет переменные NAME1 и NAME2 символь ными строками длины 15:
CHARACTER (LEN =15) NAME1, NAME2
Строки со статической длиной всегда заполнены: если переменной присваи вается строка меньшей длины, свободные места заполняются нулем.
Альтернативой является переменная длина строки, ограничиваемая заданным при объявлении максимальным размером. Так сделано в языках C и C++, где вместо хранения длины используется спе циальный символ для указания конца символьной строки.
Еще одним вариантом являются строки с переменной и неограниченной длиной (SNOBOL4, Perl, Object Pascal). Подобное решение требует дополнительных расходов на динамическое размещение строк в памяти и удаление их из памяти, но обес печивает максимальную гибкость.
Строковые типы значительно влияют на легкость написания программ. Обращение со строками как с массивами более громоздко, чем с элементарным строковым типом. Использование символьных строк в качестве элементарного типа не ус ложняет язык или компилятор. Их отсутствие в ряде современных языков программирования (C, C++) объясняется стремлением к эффективности языка. Отсутствие таких типов компенсируется стандартными библиотеками для работы со строками.
Операции со строками, например, простое сопоставление с образцом или конкатенация, необходимы.
Символьные строки иногда поддерживаются аппаратурой, но в большинстве случаев для хранения строк в памяти, поиска в строке и обработки строк используется программное обеспечение. Если символьные строки представляются в виде массивов символов, то язык часто довольствуется небольшим числом операций.
Дескриптор статического строкового типа – единственное, что требуется от такой строки во время компиляции. Для статических символьных строк одно из полей дескриптора содер жит длину типа (в символах). Другое поле является адресом начального символа. Строки с ограниченной дина мической длиной требуют наличия динамического дескриптора, содержащего текущую и максимально возможную длины строки. Строкам с неограниченной динамической длиной достаточно более простого динамического дескриптора, поскольку он должен содержать лишь текущую длину.
Строки в языках C и C++ не требуют динамических дескрипторов, поскольку конец строки помечается нулем. Также им не нужна и максимальная длина, поскольку в этих языках индексы при обращении к массиву не проверяются на предмет выхода за пределы интервала.
Строки со статической и ограниченной динамической длиной не требуют ди намического распределения памяти. Для строк с ограниченной динамической длиной память, достаточная для содержания строки максимальной длины, выделяется при свя зывании переменной с памятью, таким образом, выполняется только однократное раз мещение в памяти. Максимальная длина строки фиксируется во время компиляции.
Строки с динамической длиной требуют более сложного управления памятью. Длина строки (соответственно память, с которой она связывается) должна расти и умень шаться динамически.
Существует два возможных подхода к решению проблемы динамического распреде ления памяти. Во-первых, строки могут храниться в связных списках. Таким образом, при увеличении строки дополнительные ячейки будут выделяться в новой динамической памяти. Не достатком этого способа является большое количество памяти, занимаемое ссылками. Альтернативный вариант – хранение полных строк в смежных ячейках памяти. Осложнения появляются при их увеличении, так как строка может соседствовать с уже занятой ячейкой. В таких случаях строка целиком перемещается в новую область, при этом текущая память освобождается.
Несмотря на то, что использование метода связных списков требует большего объема памяти, происходящие при этом процессы размещения в памяти и удаления из нее про сты. Однако некоторые операции со строками замедляются из-за необходимости отслеживания указателей. С другой стороны, хранение полных строк в смежных ячейках памяти приводит к ускоре нию выполнения многих операций над строками и требует значительно меньшего объема памя ти. Несмотря на это, сам процесс размещения в памяти выполняется медленнее. Метод смежных ячеек памяти порождает общую проблему управления распределением и осво бождением ячеек памяти переменного размера.
4.4. Порядковые типы, определяемые пользователем
Порядковым называется тип, в котором область значений может быть легко связана с последовательностью натуральных чисел. В языках Pascal и Ada, например, основными порядковыми типами являются целый, символьный и булевский типы. Во многих языках пользователи сами могут определять две разновидно сти – перечислимые и ограниченные типы.
4.4.1. Перечислимые типы
Перечислимым называется тип, в описании которого перечислены все его возможные значения, являющиеся обычно символьными константами (в языке Ada они также могут быть символьными литералами). Обычный перечислимый тип показан в следую щем примере из языка Ada:
type DAYS is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
Основным характерным для перечислимых типов вопросом разработки является следующий: может ли одна и та же литеральная константа появляться в нескольких описаниях типов, и если да, то как проверяется в программе тип конкретного литерала?
В языке Pascal литеральную константу в данной среде ссылок нельзя использовать в не скольких описаниях перечислимого типа. Переменные, принадлежащие к перечислимым типам, могут использоваться в качестве индексов массивов, переменных цикла for, выра жений оператора ветвления case, но не могут вводиться или выводиться. Значения одного типа могут сравниваться с помощью операторов отношений, при этом результат сравнения определяется их относи тельными положениями в объявлении. Например, во фрагменте программы
type
TColor = (red, blue, green, yellow);
var
color: TColor;
color := blue;
if color > red ...
булевское выражение в операторе if будет вычислено как истинное.
В языках ANSI C, C++, Pascal одна литеральная константа не может появляться в нескольких описаниях перечислимого типа в общей среде ссылок. Пере числимые величины языков ANSI C и C++ неявно преобразуются в целые, так что они подчиняются только правилам использования целых чисел.
Перечислимые типы языка Ada подобны соответствующим типам языка Pascal, за ис ключением того, что литералы могут появляться в нескольких объявлениях в одной и той же среде ссылок. Такие литералы называются перегруженными. Правило разрешения перегрузки (то есть определения типа данного эк земпляра литерала) состоит в том, что тип должен определяться контекстом, в котором появляется литерал. Например, если сравниваются перегруженный литерал и переменная перечислимого типа, то тип литерала считается совпадающим с типом данной переменной.
В некоторых случаях при появлении перегруженного литерала программист обязан указать спецификацию типа. Предположим, что в программе есть два следующих пере числимых типа:
type LETTERS is ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z');
type VOWELS is ('A', 'E', 'I', 'O', 'U');
Предположим также, что в программе имеется цикл for, переменные которого сле дующим образом принимают значения типа VOWELS:
for LETTER in 'A' .. 'O' loop
В языке Ada тип переменной цикла for неявно определяется компи лятором. Она получает тип заданного в операторе дискретного диапазона. В данном случае компилятор не сможет корректно определить тип пере менной LETTER, поскольку дискретный диапазон 'А'..'U' опреде лен неоднозначно. Решением является следующее использование спецификатора типа для литералов дис кретного диапазона:
for LETTER in VOWELS' ( 'A') .. VOWELS' ( 'O') loop
Переменные перечислимых типов могут выводиться, а перечислимые литералы могут вводиться при наличии пакета TEXT_IO языка Ada. Эти операции требуют настраивае мых реализаций встроенных пакетов для специфических перечислимых типов.
Типы BOOLEAN и CHARACTER языка Ada фактически являются встроенными перечислимыми типами. Обычными операциями с перечислимыми типами являются оп ределение предшествующего и последующего элементов, позиции в списке величин и значения данной позиции. В Pascal эти операции предоставляются встроенны ми функциями. Например, значение функции Pred (blue) равно red. В Ada эти операции являются атрибутами. Например, значение LETTERS'PRED ('В') равно 'А'.
Перечислимые типы способствуют повышению читабельности и надежности про грамм. Читабельность улучшается непосредственно: именованные значения легко разли чаются, тогда как закодированные – нет. Закодированные элементы бессмысленны для всех, кроме автора программы. Предположим, что программе на языке FORTRAN потребуется переменная, принимающая значения десяти различных цветов. Скорее всего, названия цветов будут закодированы в виде целых чисел 1, 2, ... , 10. Использованные для коди ровки целочисленные значения малоосмысленны. Если, например, константа 4 обозначает голубой цвет, и это значение присваивается переменной, то этот факт будет далеко не очевидным чита телю программы.
С точки зрения надежности перечислимые типы предоставляют два преимущества. Во-первых, если целая переменная используется программистом для кодирования, тре бующего небольшого диапазона целых значений, то может появиться ошибка выхода из диапазона, которая не будет обнаружена системой поддержки исполнения программ. Во-вторых, допускается применение любого арифметического оператора к закодированным дням и любым це лым числам, поскольку типы этих величин будут совпадать. Это исключает обнаружение компилятором многих логических ошибок и опечаток, связанных с закодированными данными. Поскольку в языках ANSI C и C++ перечислимые переменные рассматрива ются как целые, то ни одного из этих преимуществ данные языки не имеют.
Таким образом, использование вместо целого типа перечислимых типов, подобных определенному выше типу LETTERS, ограничивающих присваиваемые значе ния небольшим диапазоном, улучшает читабельность и обеспечивает проверку типов.
В силу указанных недостатков типы enum (перечислимые типы) языков C и C++ не включены в язык Java. Они имеются в C#, но подчиняются более строгим правилам. Для использования числовых значений членов перечисления в C# необхо димо явно приводить их к соответствующему целочисленному типу, например:
public enum Numbers
{
zero, one, two
}
…………………………………………..
MessageBox.Show ( ( (int) Numbers.two * 2).ToString() );
4.4.2. Ограниченные типы
Ограниченным типом называется непрерывная подпоследователь ность порядкового типа. Например, тип 12..14 является ограниченным целым типом. Впервые ограниченные типы появились в языке Pascal, также они имеются в языках Modula-2 и Ada.
В языке Pascal объявление ограниченного типа выглядит следующим образом:
type
TUpperCase = 'A'..'Z'; TIndex = 1..100;
Связь ограниченного типа с его родительским типом устанавливается путем сопоставле ния величин в определении ограниченного типа с соответствующими величинами в ра нее объявленном или встроенном порядковом типе. Тип TUpperCase в приведенном выше примере определен как ограниченный встроенный тип отдельных символов. Тип TIndex определен как ограниченный тип целых чисел.
В языке Ada ограниченные типы относятся к классу подтипов. Они не являются новыми типами, но лишь дают новые имена ограниченным версиям существующих типов. Предположим, что тип DAYS определен как в предыдущем разделе, и запишем следующее:
subtype WEEKDAYS is DAYS range Mon..Fri;
subtype INDEX is INTEGER range 1..100;
В этих примерах сужение существующих типов касается диапазона возможных значе ний. Все операции, определенные для породившего типа, определены и для подтипа, за исключением операции присваивания значений, не входящих в заданный диапазон. В следующих командах
DAY1: DAYS;
DAY2: WEEKDAYS;
DAY2 := DAY1;
присваивание разрешено только в случаях, когда значение переменной DAY1 не равно Sat или Sun. В языках Pascal и Modula-2, как и в языке Ada, подтипы наследуют все разрешенные родительскому типу опера ции.
Определяемые пользователем порядковые типы часто используются в качестве индексов массивов. Они также могут использовать ся переменными циклов. В языке Ada, например, подтипы порядковых типов яв ляются единственным способом указания переменных цикла for.
Отметим также, что в Ada ограниченные типы значительно отличаются от производных типов. Рассмотрим следующие объявления:
type DERIVED_SMALL_INT is new INTEGER range 1..100;
subtype SUBRANGE_SMALL_INT is INTEGER range 1..100;
Переменные обоих типов, DERIVED_SMALL_INT (производный тип) и SUBRANGE_SMALL_INT (подтип – ограниченный тип), наследуют область значений и операции над переменными типа INTEGER. Тем не менее, переменные типа DERIVED_SMALL_INT не совместимы ни с каким типом INTEGER, тогда как перемен ные типа SUBRANGE_SMALL_INT совместимы с величинами типа INTEGER и любого его подтипа.
Ограниченные типы улучшают читабельность программ, показывая, что переменные подтипа могут содержать только определенный диапазон значений. Надежность при ис пользовании ограниченных типов повышается, поскольку присвоение переменной такого типа некоторого значения, лежащего вне разрешенного диапазона, диагностируется компиля тором (если присваиваемое значение является литеральной величиной) или системой под держки выполнения (если это переменная или выражение) как ошибка.
4.4.3. Реализация порядковых типов
Для реализации перечислимых типов необходимо установить соответствие между неотрицательными целым числами и символьными константами. Обычно по умолчанию первое из перечисляемых значений представляется числом 0, второе – числом 1 и так далее. Операции с переменными перечислимых типов значительно отличаются от операций с целыми числами, исключением являются только операторы отношений, идентичные для обоих случаев. Как указывалось ранее, перечислимые типы языков ANSI C и C++ рассматриваются как целые типы.
Ограниченные типы реализуются так же, как и породившие их типы, за исключением того, что в каждом операторе присваивания и в каждом выражении, которые содержат переменную ограниченного типа, компилятор должен выполнять неявную проверку вы хода значения переменной за пределы допустимого диапазона. Это увеличивает размер программы и время ее выполнения, однако хорошо оптимизированный компилятор может минимизировать количество проверок.