Модели и структуры данных




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



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


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

В программном примере 4.4 приведен модуль, реализующий представление строк вектором с управляемой длиной и некоторые операции над такими строками. Для уменьшения объема в примере в секции Implementation определены не все процедуры/функции. Предоставляем читателю самостоятельно разработать прочие объявленные в секции Interface подпрограммы. Дескриптор строки описывается типом _strdescr, который в точности повторяет структуру, показанную на рис.4.6. Функция NewStr выделяет две области памяти: для дескриптора строки и для области данных строки. Адрес дескриптора строки, возвращаемый функцией NewStr - тип varstr - является той переменной, значение которой указывается пользователем модуля для идентификации конкретной строки при всех последующих операциях с нею. Область данных, указатель на которую заносится в дескрипторе строки - тип _dat_area - описана как массив символов максимального возможного объема - 64 Кбайт. Однако, объем памяти, выделяемый под область данных функцией NewStr, как правило, меньший - он задается параметром функции. Хотя индексы в массиве символов строки теоретически могут изменяться от 1 до 65535, значение индекса в каждой конкретной строке при ее обработке ограничивается полем maxlen дескриптора данной строки. Все процедуры/функции обработки строк работают с символами строки как с элементами вектора, обращаясь к ним по индексу. Адрес вектора процедуры получают из дескриптора строки. Обратите внимание на то, что в процедуре CopyStr длина результата ограничивается максимальной длиной целевой строки.

{==== Программный пример 4.4 ====} { Представление строк вектором с управляемой длиной } Unit Vstr; Interface type _dat_area = array[1..65535] of char; type _strdescr = record { дескриптор строки } maxlen, curlen : word; { максимальная и текущая длины } strdata : ^_dat_area; { указатель на данные строки } end; type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ } Function NewStr(len : word) : varstr; Procedure DispStr(s : varstr); Function LenStr(s : varstr) : word; 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 s1 : varstr; n, l : word); Implementation {** Создание строки; len - максимальная длина строки; ф-ция возвращает указатель на дескриптор строки } Function NewStr(len : word) : varstr; var addr : varstr; daddr : pointer; begin New(addr); { выделение памяти для дескриптора } Getmem(daddr,len); { выделение памяти для данных } { занесение в дескриптор начальных значений } addr^.strdata:=daddr; addr^.maxlen:=len; addr^.curlen:=0; Newstr:=addr; end; { Function NewStr } Procedure DispStr(s : varstr); {** Уничтожение строки } begin FreeMem(s^.strdata,s^.maxlen); { уничтожение данных } Dispose(s); { уничтожение дескриптора } end; { Procedure DispStr } {** Определение длины строки, длина выбирается из дескриптора } Function LenStr(s : varstr) : word; begin LenStr:=s^.curlen; end; { Function LenStr } Procedure CopyStr(s1, s2 : varstr); { Присваивание строк s1:=s2} var i, len : word; begin { длина строки-результата м.б. ограничена ее макс. длиной } if s1^.maxlen s2; -1 - если s1 < s2 } Function CompStr(s1, s2 : varstr) : integer; var i : integer; begin i:=1; { индекс текущего символа } { цикл, пока не будет достигнут конец одной из строк } while (i s2^.strdata^[i] then begin CompStr:=1; Exit; end; if s1^.strdata^[i] < s2^.strdata^[i] then begin CompStr:=-1; Exit; end; i:=i+1; { переход к следующему символу } end;

{ если выполнение дошло до этой точки, то найден конец одной из строк, и все сравненные до сих пор символы были равны; строка меньшей длины считается меньшей }

if s1^.curlens2^.curlen then CompStr:=1 else CompStr:=0; end; { Function CompStr } . . END.









Начало    Назад    Вперед