Отдельные строки
На рис. 3.10 показаны разные способы представления отдельных строк на примере слов "Рим" и "Гамбург". Эти способы можно сочетать.
Главная проблема строк - переменная длина. Поэтому в виде векторов фиксированной длины хранятся обычно лишь короткие строки, например, имена в трансляторах и операционных системах. Они дополняются пробелами либо усекаются до некоторой постоянной длины (рис. 3.10а).
Недостатки этого представления - неиспользуемые области памяти для коротких строк и возможность потери информации для слишком длинных строк. Изменение размеров вектора уменьшает вероятность одних потерь, но увеличивает вероятность других.
Для устранения этих недостатков используют векторы переменной длины со счетчиком символов или признаком конца (рис. 3.10б, 3.10в). Признак конца - особый символ (полезный алфавит уменьшается на один символ).
Признак конца удобнее человеку, например, при вводе данных. Во внутреннем представлении счетчик символов дает больше возможностей (обработка строки не только посимвольно, но и целиком; произвольный доступ к символам без опасения выйти за пределы строки), но обычно занимает больше места, чем признак конца (2-4 байта).
Списки удобнее векторов для операций над строками, но требуют памяти для указателей (рис. 3.10г-ж). Двусторонний список поэтому применяется редко. Компромиссом являются списки с многосимвольными элементами (рис. 3.10 е, 3.10 ж).
а) Вектор фиксированной длины
Потери памяти Потери данных
б) Вектор переменной длины со счетчиком символов
в) Вектор переменной длины с признаком конца Ñ
г) Список с односимвольными элементами
д) Двусвязный список с односимвольными элементами
е) Список с элементами фиксированной длины 3
ж) Список с элементами переменной длины и признаком конца Ñ
Рис. 3.10. Способы хранения строк
Дата добавления: 2015-09-27 | Просмотры: 415 | Нарушение авторских прав
|