МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ.

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

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

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

В программном примере 4.5 приведен модуль, реализующий представление строк звеньями с управляемой длиной. Даже с первого взгляда видно, что он значительно сложнее, чем пример 4.4. Это объясняется тем, что здесь вынуждены обрабатывать как связные (списки блоков), так и векторные (массив символов в каждом блоке) структуры. Поэтому при последовательной обработке символов строки процедура должна сохранять как адрес текущего блока, так и номер текущего символа в блоке. Для этих целей во всех процедурах/функциях используются переменные cp и bi соответственно. (Процедуры и функции, обрабатывающие две строки - cp1, bi1, cp2, bi2.) Дескриптор строки - тип _strdescr - и блок - тип _block - в точности повторяют структуру, показанную на рис.4.10. Функция NewStr выделяет память только для дескриптора строки и возвращает адрес дескриптора - тип varstr - он служит идентификатором строки при последующих операциях с нею. Память для хранения данных строки выделяется только по мере необходимости. Во всех процедурах/функциях приняты такие правила работы с памятью:

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

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

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

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

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

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

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

Unit Vstr;

Interface

const BLKSIZE = 8; { число символов в блоке }

type _bptr = ^_block; { указатель на блок }

_block = record { блок }

i1, i2 : byte; { номера 1-го и последнего символов }

strdata : array [1..BLKSIZE] of char; { символы }

next : _bptr; { указатель на следующий блок }

end;

type _strdescr = record { дескриптор строки }

len : longint; { длина строки }

first, last : _bptr; { указ.на 1-й и последний блоки }

end;

type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ }

Function NewStr : varstr;

Procedure DispStr(s : varstr);

Function LenStr(s : varstr) : longint;

Procedure CopyStr(s1, s2 : varstr);

Function CompStr(s1, s2 : varstr) : integer;

Function PosStr(s1, s2 : varstr) : word;

Procedure ConcatStr(var s1: varstr; s2 : varstr);

Procedure SubStr(var s : varstr; n, l : word);

Implementation

Function NewBlock :_bptr; {Внутр.функция-выделение нового блока}

var n : _bptr;

i : integer;

begin

New(n); { выделение памяти }

n^.next:=nil; n^.i1:=0; n^.i2:=0; { начальные значения }

NewBlock:=n;

end; { NewBlock }

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

Function FreeBlock(c : _bptr) : _bptr;

var x : _bptr;

begin { движение по цепочке с освобождением памяти }

while c<>nil do begin x:=c; c:=c^.next; Dispose(x); end;

FreeBlock:=nil; { всегда возвращает nil }

end; { FreeBlock }

Function NewStr : varstr; {** Создание строки }

var addr : varstr;

begin

New(addr); { выделение памяти для дескриптора }

{ занесение в дескриптор начальных значений }

addr^.len:=0; addr^.first:=nil; addr^.last:=nil;

Newstr:=addr;

end; { Function NewStr }

Procedure DispStr(s : varstr); {** Уничтожение строки }

begin

s^.first:=FreeBlock(s^.first); { уничтожение блоков }

Dispose(s); { уничтожение дескриптора }

end; { Procedure DispStr }

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

Function LenStr(s : varstr) : longint;

begin

LenStr:=s^.len;

end; { Function LenStr }

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

Procedure CopyStr(s1, s2 : varstr);

var bi1, bi2 : word; { индексы символов в блоках для s1 и s2 }

cp1, cp2 : _bptr; { адреса текущих блоков для s1 и s2 }

pp : _bptr; { адрес предыдущего блока для s1 }

begin

cp1:=s1^.first; pp:=nil; cp2:=s2^.first;

if s2^.len=0 then begin

{ если s2 пустая, освобождается вся s1 }

s1^.first:=FreeBlock(s1^.first); s1^.last:=nil;

end

else begin

while cp2<>nil do begin { перебор блоков s2 }

if cp1=nil then begin { если в s1 больше нет блоков }

{ выделяется новый блок для s1 }

cp1:=NewBlock;

if s1^.first=nil then s1^.first:=cp1

else if pp<>nil then pp^.next:=cp1;

end;

cp1^:=cp2^; { копирование блока }

{ к следующему блоку }

pp:=cp1; cp1:=cp1^.next; cp2:=cp2^.next;

end; { while }

s1^.last:=pp; { последний блок }

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

pp^.next:=FreeBlock(pp^.next);

end; { else }

s1^.len:=s2^.len;

end; { Procedure CopyStr }

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

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

Function CompStr(s1, s2 : varstr) : integer;

var bi1, bi2 : word;

cp1, cp2 : _bptr;

begin

cp1:=s1^.first; cp2:=s2^.first;

bi1:=cp1^.i1; bi2:=cp2^.i1;

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

while (cp1<>nil) and (cp2<>nil) do begin

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

if cp1^.strdata[bi1] > cp2^.strdata[bi2] then begin

CompStr:=1; Exit;

end;

if cp1^.strdata[bi1] < cp2^.strdata[bi2] then begin

CompStr:=-1; Exit;

end;

bi1:=bi1+1; { к следующему символу в s1 }

if bi1 > cp1^.i2 then begin cp1:=cp1^.next; bi1:=cp1^.i1; end;

bi2:=bi2+1; { к следующему символу в s2 }

if bi2 > cp2^.i2 then begin cp2:=cp2^.next; bi2:=cp2^.i1; end;

end;

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

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

if s1^.len < s2^.len then CompStr:=-1

else if s1^.len > s2^.len then CompStr:=1

else CompStr:=0;

end; { Function CompStr }

.

.

END.

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