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



         

Представление строк в памяти. - часть 5


ограничена ее макс. длиной } 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.

СИМВОЛЬНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.

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

ОДНОНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК.

Каждый символ строки представляется в виде элемента связного списка; элемент содержит код символа и указатель на следующий элемент, как показано на рис.4.7. Одностороннее сцепление представляет доступ только в одном направлении вдоль строки. На каждый символ строки необходим один указатель, который обычно занимает 2-4 байта.

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

ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК.

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


Содержание  Назад  Вперед