18c0693f

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



Рисунок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) у нас копируются сразу целые блоки. Если в блоке исходной строки были неиспользуемые места, то они будут и в блоке результирующей строки. Посимвольное копирование позволило бы устранить избыток памяти в строке-результате. Оптимизация памяти, занимаемой данными строки может производится как слиянием соседних полупустых блоков, так и полным уплотнением данных. В дескриптор строки может быть введено поле - количество блоков в строке. Зная общее количество блоков и длину строки можно при выполнении неко- торых операций оценивать потери памяти и выполнять уплотнение, если эти потери превосходят какой-то установленный процент.





Все публикации раздела