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

Представление строк в памяти зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче, и средства такого представления варьируются от абсолютно статического до динамического. Универсальные языки программирования в основном обеспечивают работу со строками переменной длины, но максимальная длина строки должна быть указана при ее создании. Если программиста не устраивают возможности или эффективность тех средств работы со строками, которые предоставляет ему язык программирования, то он может либо определить свой тип данных "строка" и использовать для его представления средства динамической работы с памятью, либо сменить язык программирования на специально ориентированный на обработку текста (CNOBOL, REXX), в которых представление строк базируется на динамическом управлении памятью.

ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Представление строк в виде векторов, принятое в большинстве универсальных языков программирования, позволяет работать со строками, размещенными в статической памяти. Кроме того, векторное представление позволяет легко обращаться к отдельным символам строки как к элементам вектора - по индексу.

Самым простым способом является представление строки в виде вектора постоянной длины. При этом в памяти отводится фиксированное количество байт, в которые записываются символы строки и нуль-символ (\0). Нуль-символ – символ с кодом равным 0. По ниму определяется длина строки. Если строка меньше отводимого под нее вектора, то после символов ставится нуль-символ, а лишние места хранят остаточную информацию памяти, которая нас не интересует, а если строка выходит за пределы вектора, то лишние (обычно справа строки) символы должны быть отброшены.

На рис.1.1 приведена схема, на которой показано представление двух строк: 'ABCD' и 'PQRSTUVW' в виде вектора постоянной длины на шесть символов.

P

Q

R

S

T

\0

A

B

C

D

\0

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

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ КОНЦА. Этот и все последующие за ним методы учитывают переменную длину строк. Признак конца - это особый символ, принадлежащий алфавиту (таким образом полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все остальные символы. Издержки памяти при этом способе составляют 1 символ на строку. Такое представление строки показано на рис.1.2. Специальный символ-маркер конца строки в языке С называется нуль символом, и обозначается ‘\0’.

A

B

C

D

\0

P

Q

R

S

T

U

V

W

\0

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

признаком конца

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ СО СЧЕТЧИКОМ. Счетчик символов - это целое число, и для него отводится достаточное количество битов, чтобы их с избытком хватало для представления длины самой длинной строки, какую только можно представить в данной машине. Обычно для счетчика отводят от 8 до 16 бит. Тогда при таком представлении издержки памяти в расчете на одну строку составляют 1-2 символа. При использовании счетчика символов возможен произвольный доступ к символам в пределах строки, поскольку можно легко проверить, что обращение не выходит за пределы строки. Счетчик размещается в таком месте, где он может быть легко доступен - в начале строки или в дескрипторе строки. Максимально возможная длина строки, таким образом, ограничена разрядностью счетчика. В PASCAL, например, строка представляется в виде массива символов, индексация в котором начинается с 0; однобайтный счетчик числа символов в строке является нулевым элементом этого массива. Такое представление строк показано на рис.1.3. И счетчик символов, и признак конца в предыдущем случае могут быть доступны для программиста как элементы вектора. В языке С, таких строк нет.

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

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

ВЕКТОР С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память под вектор с управляемой длиной отводится при создании строки, и ее размер и размещение остаются неизменными все время существования строки. В дескрипторе такого вектора-строки может отсутствовать начальный индекс, так как он может быть зафиксирован раз и навсегда установленными соглашениями, но появляется поле текущей длины строки. Размер строки, таким образом, может изменяться от 0 до значения максимального индекса вектора. "Лишняя" часть отводимой памяти может быть заполнена любыми кодами - она не принимается во внимание при оперировании со строкой. Поле конечного индекса может быть использовано для контроля превышения строкой объема отведенной памяти. Представление строк в виде вектора с управляемой длиной (при максимальной длине 10) показано на рис.1.4.

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

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

В программном примере 1.1, реализовано представление строк вектором с управляемой длиной, и некоторые операции над такими строками. Для уменьшения объема в примере определены не все стандартные функции работы со строкой. Предоставляем читателю самостоятельно разработать прочие подпрограммы. Дескриптор строки описывается типом StrNode, который в точности повторяет структуру, показанную на рис. 1.6. Функция NewStr выделяет две области памяти: для дескриптора строки и для области данных строки. Адрес дескриптора строки, возвращаемый функцией NewStr - тип String, - является той переменной, значение которой указывается пользователем модуля для идентификации конкретной строки при всех последующих операциях с нею. Область данных, указатель на которую заносится в дескриптор строки, типа _dat_area, описана как массив символов максимально возможного объема 64 Кбайт. Однако, объем памяти, выделяемый под область данных функцией NewStr, как правило, меньший - он задается параметром функции. Хотя индексы в массиве символов строки теоретически могут изменяться от 1 до 65535, значение индекса в каждой конкретной строке при ее обработке ограничивается полем maxlen дескриптора данной строки. Все процедуры/функции обработки строк работают с символами строки как с элементами вектора, обращаясь к ним по индексу. Адрес вектора процедуры получают из дескриптора строки. Внимание. В процедуре CopyStr длина результата ограничивается максимальной длиной целевой строки. Примеримеет две вункции CopyStr, для копирования строк. Одна копирует наши строки из source в dest. Другая копирует в нашу строку, стандартную строку С++, переданную через указатель на первый элемент.

{==== Программный пример 1.1 ====}

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

typedef struct StrNode* String; // тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ

struct StrNode // дескриптор строки

{

unsigned short MaxLen, Len; // максимальная и текущая длины

char* str; // указатель на данные строки

};

// Создание строки; len - максимальная длина строки;

// ф-ция возвращает указатель на дескриптор строки

String NewStr(int len)

{

String s = new StrNode; // выделение памяти для дескриптора

s->MaxLen = len; // занесение в дескриптор начальных значений

s->Len = 0;

s->str = new char[ len+1 ]; // выделение памяти для данных

return s;

}

// уничтожение строки

void DeleteStr(String s)

{

if(s)

{

if(s->Len > 0) delete[] s->st; // уничтожение данных

delete s; // уничтожение дескриптора

}

}

// Определение длины строки, длина выбирается из дескриптора

int LenStr(String s)

{

return s->Len;

}

// присваивание строк dest = source

void CopyStr(String dest, String source)

{

int len; // длина строки-результата м.б. ограничена ее макс. длиной

if(dest->MaxLen < source->Len) len = dest->MaxLen;

else len = source->Len;

// перезапись данных и установка длины результата

for(int i=0; i<len; i++)

dest->str[i] = source->str[i];

dest->str[len] = '\0';

dest->Len = len;

}

// присваивание строк dest = source, где source обычная строка “ABCD”

void CopyStr(String dest, char* source)

{

int len = 0;

while(len < dest->MaxLen && source[len])

{

dest->str[len] = source[len];

len++;

}

dest->str[len] = '\0';

dest->Len = len;

}

// Сравнение строк - возвращает: 0, если s1=s2; 1 - если s1>s2;

// -1 - если s1<s2

char CompStr(String s1, String s2)

{

int i=0; // индекс текущего символа

// цикл, пока не будет достигнут конец одной из строк

while(i<s1->Len && i<s2->Len)

{

// если i-е символы не равны, функция заканчивается

if(s1->str[i] > s2->str[i]) return 1;

else if(s1->str[i] < s2->str[i]) return -1;

i++; // переход к следующему символу

}

// если выполнение дошло до этой точки, то найден конец одной из

// строк, и все сравненные до сих пор символы были равны;

// строка меньшей длины считается меньшей

if(s1->Len < s2->Len) return -1;

else if(s1->Len > s2->Len) return 1;

else return 0;

}

...

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

ОДНОНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. Каждый символ строки представляется в виде элемента связного списка; элемент содержит код символа и указатель на следующий элемент, как показано на рис. 1.5. Одностороннее сцепление предоставляет доступ только в одном направлении вдоль строки. На каждый символ строки необходим один указатель, который обычно занимает 4 байта.

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

ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. В каждый элемент списка добавляется также указатель на предыдущий элемент, как показано на рис. 1.6.

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

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

БЛОЧНО-СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Такое представление позволяет в большинстве операций избежать затрат, связанных с управлением динамической памятью, но в то же время обеспечивает достаточно эффективное использование памяти при работе со строками переменной длины.

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ФИКСИРОВАННОЙ ДЛИНЫ. Многосимвольные группы (звенья) организуются в список так, что каждый элемент списка, кроме последнего, содержит группу элементов строки и указатель следующего элемента списка. Поле указателя последнего элемента списка хранит признак конца - пустой указатель. В процессе обработки строки из любой ее позиции могут быть исключены или в любом месте вставлены элементы, в результате чего звенья могут содержать меньшее число элементов, чем было первоначально. По этой причине необходим специальный символ, который означал бы отсутствие элемента в соответствующей позиции строки. Обозначим такой символ 'emp', он не должен входить в множество символов, из которых организуется строка. Пример многосимвольных звеньев фиксированной длины по 4 символа в звене показан на рис. 1.7.

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

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

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ПЕРЕМЕННОЙ ДЛИНЫ. Переменная длина блока дает возможность избавиться от пустых символов и тем самым экономить память для строки. Однако появляется потребность в специальном символе - признаке указателя, на рис.1.8 он обозначен символом 'ptr'.

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

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

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

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память выделяется блоками фиксированной длины. В каждом блоке помимо символов строки и указателя на следующий блок содержатся номера первого и последнего символов в блоке. При обработке строки в каждом блоке обрабатываются только символы, расположенные между этими номерами. Признак пустого символа не используется: при удалении символа из строки оставшиеся в блоке символы уплотняются и корректируются граничные номера. Вставка символа может быть выполнена за счет имеющегося в блоке свободного места, а при отсутствии такового - выделением нового блока. Хотя операции вставки/удаления требуют пересылки символов, диапазон пересылок ограничивается одним блоком. При каждой операции изменения может быть проанализирована заполненность соседних блоков и два полупустых соседних блока могут быть переформированы в один блок. Для определения конца строки может использоваться как пустой указатель в последнем блоке, так и указатель на последний блок в дескрипторе строки. Последнее может быть весьма полезным при выполнении некоторых операций, например, сцепления. В дескрипторе может храниться также и длина строки: считывать ее из дескриптора удобнее, чем подсчитывать ее перебором всех блоков строки.

Пример представления строки в виде звеньев с управляемой длиной на 18 символов показан на рис. 1.9. В программном примере 1.2, реализовано представление строк звеньями с управляемой длиной. Даже с первого взгляда видно, что он значительно сложнее, чем пример 1.4. Это объясняется тем, что здесь вынуждены обрабатывать как связные (списки блоков), так и векторные (массив символов в каждом блоке) структуры.

Поэтому при последовательной обработке символов строки функция должна сохранять как адрес текущего блока, так и номер текущего символа в блоке. Для этих целей во всех функциях используются переменные cp и bi соответственно. (Функции, обрабатывающие две строки - cp1, bi1, cp2, bi2.) Дескриптор строки - тип StrNode - и блок - тип Block - в точности повторяют структуру, показанную на рис. 1.9. Функция NewStr выделяет память только для дескриптора строки и возвращает адрес дескриптора - тип String - он служит идентификатором строки при последующих операциях с нею. Память для хранения данных строки выделяется только по мере необходимости. Во всех функциях приняты такие правила работы с памятью:

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

· если выходной строке уже выделены блоки, то используются эти уже выделенные блоки;

· если блоки, выделенные выходной строке, исчерпаны, то по мере необходимости выделяются новые блоки;

· если результирующее значение выходной строки не использует все выделенные строке блоки, лишние блоки освобождаются.

Для освобождения блоков определена специальная внутренняя функция DeleteBlock, освобождающая весь список блоков, голова которого задается ее параметром.

Обратите внимание на то, что ни в каких функциях не контролируется максимальный объем строки результата - он может быть сколь угодно большим, а поле длины в дескрипторе строки имеет тип long int (4 байта).

{==== Программный пример 1.2 ====}

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

const int BlkSize = 8; // число символов в блоке

typedef struct Block* BlkPtr; // указатель на блок

struct Block // блок

{

char chFirst, chLast; // номера 1-го и последнего символов

char StrData[ BlkSize ]; // символы

BlkPtr next; // указатель на следующий блок

};

typedef struct StrNode* String; // тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ

struct StrNode // дескриптор строки

{

long len; // длина строки

BlkPtr first, last; // указ.на 1-й и последний блоки

};

// *** Внутр. функция-выделение нового блока

BlkPtr NewBlock()

{

BlkPtr curr = new Block; // выделение памяти

curr->next = NULL; // начальные значения

curr->chFirst = 0;

curr->chLast = 0;

return curr;

}

//*** Внутр.функция - освобождение цепочки блока, начиная со значения bl

BlkPtr DeleteBlock(BlkPtr bl)

{

BlkPtr buf;

while(bl) // движение по цепочке с освобождением памяти

{

buf = bl;

bl = bl->next;

delete buf;

buf = NULL;

}

return NULL; // всегда возвращает NULL

}

// *** создание строки

String NewStr()

{

String str = new StrNode; // выделение памяти для дескриптора

str->len = 0; // занесение в дескриптор начальных значений

str->first = str->last = NULL;

return str;

}

// *** уничтожение строки

void DeleteStr(String str)

{

str->first = DeleteBlock(str->first); // уничтожение блоков

delete str; // уничтожение дескриптора

}

// * ** Определение длины строки, длина выбирается из дескриптора

long LenStr(String str)

{

return str->len;

}

// * ** Присваивание строк s1:=s2

void CopyStr(String dest, String source)

{

BlkPtr cp1, cp2, // адреса текущих блоков для dest и source

pp; // адрес предыдущего блока для dest

cp1 = dest->first;

cp2 = source->first;

pp = NULL;

if(source->len == 0) // если s2 пустая, освобождается вся s1

{

dest->first = DeleteBlock(dest->first);

dest->last = NULL;

}

else

{

while(cp2) // перебор блоков source

{

if(cp1 == NULL) // если в dest больше нет блоков

{

cp1 = NewBlock(); // выделяется новый блок для dest

if(dest->first == NULL) dest->first = cp1;

else if(pp) pp->next = cp1;

}

*cp1 = *cp2; // копирование блока

// к следующему блоку

pp = cp1; cp1 = cp1->next; cp2 = cp2->next;

}

dest->last = pp; // последний блок

// если в s1 остались лишние блоки - освободить их

pp->next = DeleteBlock(pp->next);

} // end else

dest->len = source->len;

}

// *** Сравнение строк - возвращает:

// 0, если s1=s2; 1 - если s1>s2; -1 - если s1<s2 ***

int CompStr(String s1, String s2)

{

char bi1, bi2;

BlkPtr cp1, cp2;

cp1 = s1->first;

cp2 = s2->first;

bi1 = cp1->chFirst;

bi2 = cp2->chFirst;

while(cp1 && cp2)// цикл, пока не будет достигнут конец одной из строк

{ // если соответств. символы не равны, ф-ция заканчивается

if(cp1->StrData[bi1] > cp2->StrData[bi2]) return 1;

else if(cp1->StrData[bi1] < cp2->StrData[bi2]) return -1;

bi1++; // к следующему символу в s1

if(bi1>cp1->chLast)

{

cp1 = cp1->next;

bi1 = cp1->chFirst;

}

bi2++; // к следующему символу в s2

if(bi2>cp2->chLast)

{

cp2 = cp2->next;

bi2 = cp2->chFirst;

}

}

// мы дошли до конца одной из строк,

// строка меньшей длины считается меньшей

if(s1->len < s2->len) return -1;

else if(s1->len > s2->len) return 1;

else return 0;

}

...

Чтобы не перегружать программный пример, в него не включены средства повышения эффективности работы с памятью. Такие средства включаются в операции по выбору программиста. Обратите внимание, например, что в процедуре, связанной с копированием данных (CopyStr), у нас копируются сразу целые блоки. Если в блоке исходной строки были неиспользуемые места, то они будут и в блоке результирующей строки. Посимвольное копирование позволило бы устранить избыток памяти в строке-результате. Оптимизация памяти, занимаемой данными строки, может производиться как слиянием соседних полупустых блоков, так и полным уплотнением данных. В дескриптор строки может быть введено поле - количество блоков в строке. Зная общее количество блоков и длину строки, можно при выполнении некоторых операций оценивать потери памяти и выполнять уплотнение, если эти потери превосходят какой-то установленный процент.

Дата добавления: 2014-01-07