5.4.2. Представление строк в памяти
Представление строк в памяти зависит от требований изменчивости строки и средства такого представления варьируются от абсолютно статических до динамических. Универсальные языки в основном обеспечивают работу со строками переменной длины, но максимальная длина строки должна быть указана при ее создании. Если возможностей, предоставляемых языком, недостаточно следует:
определить новый тип данных «строка» и использовать его для представления средства динамической работы с памятью;
выбрать язык, ориентированный на обработку текста (SNOBOL, REXX), в котором представление строк базируется на динамическом управлении памятью.
Векторное представление строк. Представление строк в виде векторов, принятое в большинстве универсальных языков, позволяет работать со строками, размещенными в статической памяти. Кроме того, векторное представление позволяет обращаться к отдельным символам строки как к элементам вектора – по индексу.
Самым простым способом является представление строки в виде вектора постоянной длины. При этом в памяти отводится фиксированное количество байт, в которые записываются символы. Если строка меньше отводимого под нее вектора, то лишние места заполняются пробелами, а если строка выходит за пределы вектора, то лишние (обычно справа строки) символы должны быть отброшены. На рис. 5.3 приведена схема, на которой показано представление двух строк: 'ABCD' и 'PQRSTUVW' в виде вектора постоянной длины на шесть символов.
A
B D P
Q R S T U
Рис. 5.3. Представление строк векторами постоянной длины.
Представление строк вектором переменной длины с признаком конца. Данный метод и все последующие учитывают переменную длину строк. Признак конца строки – особый символ, принадлежащий алфавиту (полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все остальные символы. Издержки памяти составляют 1 символ на строку. Такое представление строки показано на рис. 5.4. Специальный символ-маркер конца строки обозначен как 'eos'. В языке C, например, в качестве маркера конца строки используется символ с кодом 0.
A
B D eos P
Q R S T U W eos
Рис. 5.4. Представление строк переменной длины с признаком конца.
Представление строк вектором переменной длины со счетчиком. Счетчик символов – целое число, и для него отводится достаточное количество битов, чтобы их с избытком хватило для представления длины самой длинной строки. Обычно для счетчика отводят от 8 до 16 битов. При таком представлении издержки памяти в расчете на одну строку составляют 1-2 символа.
При использовании счетчика символов возможен произвольный доступ к символам в пределах строки, поскольку можно легко проверить, что обращение не выходит за пределы строки. Счетчик размещается в таком месте, где он может быть легко доступен – в начале строки или в дескрипторе.
Максимально возможная длина строки ограничена разрядностью счетчика. В PASCAL, например, строка представляется в виде массива символов, индексация в котором начинается с 0. Однобайтный счетчик числа символов в строке является нулевым элементом этого массива. Такое представление строк показано на рис. 5.5. И счетчик символов, и признак конца в предыдущем случае могут быть доступны как элементы вектора.