Представление строк в памяти

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

- определить новый тип данных «строка» и использовать его для представления средства динамической работы с памятью;

- выбрать язык, ориентированный на обработку текста (SNOBOL, REXX), в котором представление строк базируется на динамическом управлении памятью.

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

Самым простым способом является представление строки в виде вектора постоянной длины. При этом в памяти отводится фиксированное количество байт, в которые записываются символы. Если строка меньше отводимого под нее вектора, то лишние места заполняются пробелами, а если строка выходит за пределы вектора, то лишние (обычно справа строки) символы должны быть отброшены. На рис. 5.3 приведена схема, на которой показано представление двух строк: 'ABCD' и 'PQRSTUVW' в виде вектора постоянной длины на шесть символов.

Рис. 5.3. Представление строк векторами постоянной длины.

Представление строк вектором переменной длины с признаком конца.Данный метод и все последующие учитывают переменную длину строк. Признак конца строки – особый символ, принадлежащий алфавиту (полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все остальные символы. Издержки памяти составляют 1 символ на строку. Такое представление строки показано на рис. 5.4. Специальный символ-маркер конца строки обозначен как 'eos'. В языке C, например, в качестве маркера конца строки используется символ с кодом 0.

Рис. 5.4. Представление строк переменной длины с признаком конца.

Представление строк вектором переменной длины со счетчиком. Счетчик символов – целое число, и для него отводится достаточное количество битов, чтобы их с избытком хватило для представления длины самой длинной строки. Обычно для счетчика отводят от 8 до 16 битов. При таком представлении издержки памяти в расчете на одну строку составляют 1-2 символа.

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

Максимально возможная длина строки ограничена разрядностью счетчика. В PASCAL, например, строка представляется в виде массива символов, индексация в котором начинается с 0. Однобайтный счетчик числа символов в строке является нулевым элементом этого массива. Такое представление строк показано на рис. 5.5. И счетчик символов, и признак конца в предыдущем случае могут быть доступны как элементы вектора.

Рис. 5.5. Представление строк переменной длины со счетчиком.

В двух предыдущих вариантах обеспечивалось максимально эффективное расходование памяти (1-2 «лишних» символа на строку), но изменчивость строки была крайне невысока. Поскольку вектор – статическая структура, каждое изменение длины строки требует создания нового вектора, пересылки в него неизменяемой части строки и уничтожения старого вектора, что сводит на нет преимущества работы со статической памятью. Поэтому наиболее популярным способом представления строк в памяти являются вектора с управляемой длиной.

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

Размер строки может изменяться от 0 до значения максимального индекса вектора. «Лишняя» часть отводимой памяти может быть заполнена любыми кодами – она игнорируется. Поле конечного индекса может быть использовано для контроля превышения строкой объема отведенной памяти. Представление строк в виде вектора с управляемой длиной (при максимальной длине 10) показано на рис. 5.6.

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

Рис. 5.6. Представление строк вектором с управляемой длиной.

Символьно-связное представление строк. Списковое представление строк в памяти обеспечивает гибкость в выполнении разнообразных операций над строками (операций включения и исключения отдельных символов и целых цепочек) и использование системных средств управления памятью при выделении необходимого объема памяти для строки. Однако при этом возникают дополнительные расходы памяти. Другим недостатком спискового представления строки является то, что логически соседние элементы строки не являются физически соседними в памяти. Это усложняет доступ к группам элементов строки по сравнению с доступом в векторном представлении строки.

Однонаправленный линейный список. Каждый символ строки представляется в виде элемента связного списка. Элемент содержит код символа и указатель на следующий элемент (рис. 5.7). Одностороннее сцепление представляет доступ только в одном направлении вдоль строки. На каждый символ строки необходим один указатель, который обычно занимает 2-4 байта.

Рис. 5.7. Представление строки однонаправленным связным списком.

Двунаправленный линейный список. В каждый элемент списка добавляется указатель на предыдущий элемент (рис. 5.8). Двустороннее сцепление допускает двустороннее движение вдоль списка, что может значительно повысить эффективность выполнения строковых операций. При этом на каждый символ строки необходимо два указателя, т.е. 4-8 байт.

Рис. 5.8. Представление строки двунаправленным связным списком.

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

Многосимвольные звенья фиксированной длины. Многосимвольные группы (звенья) организуются в список, так что каждый элемент списка, кроме последнего, содержит группу элементов строки и указатель следующего элемента списка. Поле указателя последнего элемента списка хранит признак конца – пустой указатель.

В процессе обработки строки из любой ее позиции могут быть исключены или в любом месте вставлены элементы, в результате чего звенья могут содержать меньшее число элементов, чем было первоначально. По этой причине необходим специальный символ, который означал бы отсутствие элемента в соответствующей позиции строки. Обозначим такой символ 'emp', он не должен входить в множество символов, из которых организуется строка. Пример многосимвольных звеньев фиксированной длинны по 4 символа в звене показан на рис. 5.9.

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

Рис. 5.9. Представление строки многосимвольными звеньями постоянной длины.

Многосимвольные звенья переменной длины.Переменная длина блока дает возможность избавиться от пустых символов и экономить память для строки. Однако появляется потребность в специальном символе – признаке указателя (на рис. 5.10 он обозначен символом 'ptr').

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

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

Рис. 5.10. Представление строки многосимвольными звеньями переменной длины.

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

Вставка символа может быть выполнена за счет имеющегося в блоке свободного места, а при отсутствии – выделением нового блока. Хотя операции вставки/удаления требуют пересылки символов, диапазон пересылок ограничивается одним блоком. При каждой операции изменения может быть проанализирована степень заполнения соседних блоков, и два полупустых соседних блока могут быть переформированы в один.

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

Рис. 5.11. Представление строки звеньями управляемой длины.

Контрольные вопросы

1. Перечислите свойства полстатических структур данных.

2. Опишите работу стека. Перечислите области применения.

3. Опишите работу кольцевой очереди и очереди с приоритетами.

4. Строки. Способы представления и операции над строками.

6. Динамические структуры данных