Представление строки в виде цепочки

Недостатки векторного представления строк вытекают из того, что в векторе понятие «следующий элемент» жестко связано с местом расположения этого элемента по отношению к предыдущему элементу — в позиции со следующим по порядку номером, в ячейке памяти со следующим по порядку адресом и т.д. Однако понятие «следующий элемент» не обязательно связывать с местом его расположения. Элементы строки можно размещать по позициям вектора или в памяти машины самым произвольным образом, если каждый элемент снабдить явным указанием того места, где находится следующий за ним элемент. При таком представлении строки каждый ее элемент будет состоять из двух полей: в одном поле располагается литера строки, а в другом — ссылка на следующий элемент строки. Каждая пара называется звеном, а ссылки, содержащиеся в каждом из звеньев, сцепляют звенья в одну цепочку. Описанный способ представления упорядоченной последовательности элементов называется сцеплением — он применяется не только для представления строк, но и для представления более сложных структур данных (списков, деревьев и т.д.). В этом случае звено всегда состоит из двух частей: собственно элемента последовательности (или тела звена) и справочной части (или ссылки на другие элементы структуры).

Зададим строку-цепочку с помощью уже известных типов паскаля. Прежде всего необходимо определить отдельное звено этой структуры. Оно должно состоять из двух различных полей, одно из которых содержит в качестве значения элемент строки — литеру, а другое представляет собой ссылку на следующее звено. Чтобы уметь различать последнее звено цепочки, у которого нет следующего, условимся снабжать его ссылкой nil. Такое звено может представлять собой значение следующего комбинированного типа с именем Звстр:

type

Связь=ТЗвстр;

Звстр=гесогД элем: char;

след: Связь

end;

Здесь тип значений с именем Связь представляет собой множество ссылок на программные объекты типа Звстр.

При описании звена цепочки возникает вопрос: что должно быть описано раньше — ссылочный тип (в рассматриваемом примере тип с именем Связь) или тип программного объекта, представляющего собой звено (тип с именем Звстр)? Если первым описывается тип Связь, то в его задании фигурирует имя типа Звстр, которое еще не описано. Если же первым описывается тип с именем Звстр, то в его задании фигурирует имя ссылочного типа Связь. Получается, что в задании типа приходится неминуемо использовать имя типа, которое еще не описано. Да, это действительно так. Это единственный случай в паскале, когда разрешено применять имя типа до его описания, и это разрешение относится только к ссылочным типам значений. А именно, при описании ссылочных типов можно использовать имена типов, которые описываются после данного типа значений в том же разделе типов. В приведенном примере это правило соблюдается: сначала введен в употребление ссылочный тип с именем Связь и лишь затем описан тип с именем Звстр, которое используется в задании типа с именем Связь.

Итак, отдельные звенья цепочки заданы с помощью известных типов значений. Чтобы иметь возможность оперировать с цепочкой как единым объектом, введем статическую ссылочную переменную, которая связана с первым звеном строки. Значением этой переменной является ссылка на первое звено строки или значение nil (в случае пустой строки). Тип значений, к которому принадлежит эта ссылочная переменная, совпадает с уже введенным в употребление ссылочным типом с именем Связь. Обычно для большей наглядности и понятности вводят специальное имя для ссылочного типа значений, к которому принадлежат переменные, ссылающиеся на первые звенья строк. Удобнее всего это сделать следующим образом: в разделе типов задать описание

динстрока=Связь;

т.е. ввести в употребление тип значений, синонимичный с типом Связь.

Введем в употребление ссылочную переменную str с помощью описания:

str: динстрока

Если эта ссылочная переменная должна указывать на строку литер 'ПАСКАЛЬ', то представление строки в виде цепочки и ее связь с указателем str имеют следующий вид:

Для иллюстрации техники работы со строками, представленными в виде цепочки, рассмотрим пример.

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

Поскольку цель примера — проиллюстрировать технику работы с цепочками, не будем стремиться к получению эффективной программы и примем следующую ее схему:

  • 1) ввести исходное слово и представить его в виде цепочки с распечаткой этого слова;
  • 2) определить число вхождений заданной буквы в слово;
  • 3) вывести результаты на печать.

Примем решение о том, что слово-цепочку будем формировать по мере ввода отдельных литер исходного слова.

В программе придется иметь дело с динамическим объектом, каковым является слово-цепочка. Для того чтобы ввести в употребление этот объект, дадим необходимые описания типов:

type

Связь=ТЗвстр;

Звстр=гесогД Элем: char;

След: Связь

end

Для ссылки на цепочку как единое целое (а точнее, на ее первое звено, поскольку в каждом звене содержится ссылка на следующее звено) введем в употребление соответствующий указатель:

var

Укстр: Связь;

Указатель Укстр будет всегда ссылаться на начало цепочки. Однако в процессе формирования цепочки придется ссылаться на последнее из уже сформированных звеньев для присоединения к нему очередного формируемого звена. Поэтому в разделе переменных введем в употребление еще один рабочий указатель с помощью описания:

Укзв: Связь

Процесс формирования цепочки будет происходить следующим образом (в предположении, что литерная переменная sym в качестве своего значения имеет очередную литеру, которая должна быть включена в цепочку).

Первое звено цепочки можно сформировать с помощью операторов:

new(Укстр); УкстрТ.Элем:=sym; УкстрТ.След:=nil;

По первому из этих операторов будет выделено в памяти место для размещения вновь формируемого звена, а следующие два оператора формируют значения его полей. Напомним, что переменная с указателем УкстрТ именует сам динамический объект, т.е. звено, а поскольку это звено представляет собой запись, состоящую из двух полей с именами Элем и След, то их именование производится обычным для записей способом: сначала записывается имя всей записи, а затем через точку имя нужного поля записи.

Следующую литеру исходного слова надо размещать в следующем звене цепочки. Для его порождения надо снова обратиться к процедуре new, задав в качестве фактического параметра указатель, которому в качестве значения будет присвоена ссылка на порожденное звено. Но теперь в качестве такого указателя нельзя использовать Укстр. Во- первых, потому что этот указатель всегда должен ссылаться на начало (первое звено) цепочки. Во-вторых, в этом случае будет уничтожено первое звено, а ведь к нему надо присоединить второе порождаемое звено так, чтобы в поле След первого звена была занесена ссылка на второе звено.

Для формирования второго звена можно было бы использовать такую последовательность операторов:

new(УкстрТ.След); УкстрТ.СледТ.Элем:= sym;

УкстрТ.СледТ.След:=nil

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

Укзв:=Укстр

В результате его выполнения указатель Укзв будет ссылаться на первое звено, а в дальнейшем позаботимся о том, чтобы он всегда ссылался на последнее звено цепочки.

В этом случае формирование каждого очередного звена будет производиться одной и той же последовательностью операторов:

new(УкзвТ.След); Укзв:=УкзвТ.След; УкзвТ.Элем:=sym;

УкзвТ.След:=nil

(Читателю предлагается ответить на вопрос: можно ли здесь в качестве фактического параметра оператора процедуры new использовать указатель Укзв, и если нет, то почему?)

После сделанных замечаний реализация первого этапа схемы программы трудностей не вызывает.

Что касается второго этапа, на котором приходится последовательно перебирать все звенья цепочки, то здесь очень важно понять способ перехода от одного звена к следующему по порядку звену. Если имеется указатель р, значением которого является ссылка на какое-либо звено, то для присваивания этому указателю в качестве нового значения ссылки на следующее звено надо выполнить оператор присваивания

являющийся аналогом оператора к := к + 1, который исполнялся для получения индекса к следующего элемента при векторном представлении строки.

Теперь приведем полный текст паскаль-программы, предназначенной для решения поставленной задачи.

{Пример 13.3. Вариант 1. Фролов Г.Д. МГПИ 2.5.09 г. Подсчитать число вхождений буквы t в заданное слово, завершающееся точкой}

{Представление строки в виде цепочки. Использование указателей}

program числовхбкв(input,output); const бкв='t'; type Связь=Тзвстр;

Звстр= record Элем: char;

След: Связь

end;

var

Укстр,Укзв: Связь; sym: char; k: integer;

begin

{Печать заголовка результата} writeln(1В_СЛОВО1);

{Ввод исходного слова, его представление в виде цепочки, распечатка}

{Формирование первого звена} read(sym); write(sym);

new(yKCTp); УкстрТ.Элем:=Бут; УкстрТ.След:=nil; {Подготовка к циклу формирования остальных звеньев}

Укзв:=Укстр;

{Цикл обработки последовательных литер строки} while syitv*' . ' do

begin read(sym); write(sym);

new(УкзвТ.След); Укзв:=УкзвТ.След; УкзвТ.Элем:=sym; УкзвТ.След:=nil;

end;

{Исходное слово представлено в виде цепочки} {Подсчет числа вхождений буквы бкв в слово} к:=0; Укзв:=Укстр; while Укзв^пИ do

begin if УкзвТ.Элем=бкв then k:=k+l;

Укзв:=УкзвТ.След

end;

{Печать результата}

writeln; writeln(1БУКВА_', бкв, '_ВХОДИТ_', к, '_РАЗ1)

end.

Из приведенной программы видно, что формирование звена, соответствующего первому элементу строки, приходится делать нестандартным способом — иначе, чем формирование остальных звеньев. И вообще, при таком представлении цепочки обработка первого звена будет отличаться от обработки других звеньев.

Для устранения этих недостатков, а также для удобства последующей работы с цепочкой в нее удобно включить заглавное, «нулевое» звено, в поле След которого содержится ссылка на первое звено, содержащее первую литеру строки, а поле Элем можно использовать для хранения некоторой дополнительной информации о строке. При таком способе представления строки в виде цепочки программа примера будет логичнее и проще:

{Пример 13.3. Вариант 2. Руднев И.А. ф-т ВМиК МГУ 4.4.09 г.

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

{Представление строки в виде цепочки. Использование указателей}

program числовхбкв(input,output); const бкв='t'; type Связь=Тзвстр;

Звстр= record Элем: char;

След: Связь

end;

var

Укстр,Укзв: Связь; sym: char; k: integer;

begin

{Печать заголовка результата} writeln(1В_СЛОВО1);

{Ввод исходного слова, его представление в виде цепочки, распечатка}

{Формирование заглавного звена} new(yKCTp); Укзв:=Укстр; УкзвТ.След:=nil; read(sym); {Чтение первой литеры}

{Циклическая обработка литер, если слово

не пусто}

while sym*'.' do

begin write(sym); {Печать введенной литеры}

new(УкзвТ.След); Укзв:=УкзвТ.След;

УкзвТ.Элем:=sym; УкзвТ.След:=nil; read(sym)

end; {Исходное слово представлено в виде цепочки}

{Подсчет числа вхождений в слово заданной буквы} к:=0; Укзв:=Укстр; while УкзвТ.След^пИ do

begin Укзв:=УкзвТ.След;

if УкзвТ.Элем=бкв then k:=k+l end;

{Печать результата}

writeln; writeln('БУКВА_', бкв,

'_ВХОДИТ_’, к, 1_РАЗ')

end.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >