Реализация операций над строками-цепочками
Рассмотрим реализацию основных операций над строками в случае их представления в виде цепочек. Напомним, что в виде цепочек представляем динамические строки литер. Поэтому сначала приведем описания типов значений и переменных, которые будут использоваться в описаниях процедур, реализующих основные операции над строками:
type
типэлем=сйаг;
связь=ТЗвстр;
Звстр=гесогЦ Элем: типэлем;
След: связь
end;
динстр=связь ;
var
str: динстр
Далее будем считать, что любая (в том числе и пустая) строка в виде цепочки имеет рассмотренное выше заглавное звено (у пустой строки поле След заглавного звена содержит ссылку nil).
Поиск заданного элемента в строке.
Как и в случае векторного представления строки, алгоритм выполнения этой операции зададим в виде описания логической процедуры-функции, которая в качестве побочного эффекта определяет ссылку на первое вхождение заданного элемента в указанную строку (ссылку на соответствующее звено цепочки).
Алгоритм поиска очень прост: будем просматривать (с использованием ссылок) последовательные звенья цепочки и сравнивать значение поля Элем каждого звена с заданным элементом. Этот процесс заканчивается в двух случаях:
- а) очередное звено цепочки содержит заданный элемент; в этом случае функция должна принять значение true, а в качестве побочного эффекта выдается ссылка на это звено;
- б) цепочка будет исчерпана (в поле След очередного обработанного звена окажется ссылка nil); в этом случае функция должна принять значение false, а в качестве побочного эффекта будет выдавать значение nil.
Описание такой логической процедуры-функции может иметь вид:
function поиск(st: динстр; эл: типэлем; var res: связь): boolean;
var q: связь; begin
поиск:=false; res:=nil; q:=stT.Cnefl; while (q*nil) and (res=nil) do begin
if qT.3neM=3n then
begin поиск:=true; res:=q end; q: =цТ.След
end
end;
Заметим, что за счет повторных обращений к этой процедуре можно найти все вхождения в строку заданного элемента — для нахождения очередного его вхождения достаточно снова обратиться к процедуре, задав в качестве первого фактического параметра ссылку на звено, которое содержало предыдущее вхождение заданного элемента (другими словами, задав в качестве исследуемой строки ту часть исходной строки, которая следует за этим звеном). Этот процесс следует завершить, когда при очередном обращении к процедуре будет выработано значение функции, равное false.
