В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 59
Текст из файла (страница 59)
Кроме того, если длина каждой строки фиксиро-вана и не изменяется в процессе выполнения программы, то память, отводимая для хранения строк, используется максимально эффективно.Основные недостатки состоят в следующем. Во-первых, операции вставки и удаления литеры требуют для своего выполнения много времени засчет необходимости сдвига части строки и — при вставке литеры — поискамаркера конца строки. Во-вторых, память, отводимая для хранения строк,может использоваться весьма неэффективно: если реально достигаемаямаксимальная длина строки заранее неизвестна, то память для нее приходится резервировать с запасом, иногда очень большим. Но если даже этадлина известна, неэффективность использования памяти может возникнутьиз-за того, что в процессе выполнения программы длина строки можетбыть значительно меньше ее максимальной длины.По указанным причинам векторное представление строк обычно используют при решении таких задач, когда строки остаются постояннымиили меняются сравнительно редко (например, в информационно-поисковых системах).13.3.2.
Представление строки в виде цепочкиОтмеченные выше недостатки векторного представления строк вытекаютиз того, что в векторе понятие "следующий элемент" жестко связано с местом расположения этого элемента по отношению к предыдущему элемент у — в позиции со следующим по порядку номером, в ячейке памяти соследующим по порядку адресом и т.д. Однако понятие "следующий элемент" вовсе не обязательно связывать с местом его расположения, Элементы строки можно размещать по позициям вектора или в памяти машинысамым произвольным образом, если каждый элемент снабдить явнымуказанием того места, где находится следующий за ним элемент.
При такомпредставлении строки каждый ее элемент будет состоять из двух полей:в одном поле располагается литера строки, а в другом — ссылка на следующий элемент строки. Каждая такая пара называется звеном, а ссылки,содержащиеся в каждом из звеньев, сцепляют звенья в одну цепочку. Такойспособ представления упорядоченной последовательности элементов называется сцеплением — он применяется не только для представления строк,но и для представления более сложных структур данных (списков, деревьев и т.д.).
В этом случае звено всегда состоит из двух частей: сам элемент последовательности (или тело звена) и справочная часть (нпя ссылкана другие элементы структуры).Зададим строку-цепочку с помощью известных нам типов паскаля,Прежде всего необходимо определить отдельное звено этой структуры.Оно должно состоять из двух различных полей, одно из которых содержитв качестве значения собственно элемент строки — литеру, а другое представляет собой ссылку на следующее звено. Чтобы уметь различать последнеезвено цепочки, у которого нет следующего, условимся снабжать его ссылкой nil.
Такое звено может представлять собой значение следующего комбинированного типа с именем Звстр:typeСвязь=ЧЗвстр;Звстр^ч-ecord элем:end;char;след: СвязьЗдесь тип значений с именем Связь представляет собой множество ссылокна программные объекты типа Звстр.При описании звена цепочки возникает такой вопрос: что должно бытьописано раньше, ссылочный тип (в нашем примере тип с именем Связь),или тип программного объекта, представляющего собой звено (тип с именем Звстр)? Если первым описывается тип Связь, то в его задании фигурирует имя типа Звстр, которое еще не описано.
Если же первым описываетсятип с именем Звстр, то в его задании фигурирует имя ссылочного типаСвязь. Получается, что в задании типа приходится неминуемо использоватьимя типа, которое еще не описано. Да, это действительно так. Это единственный случай в паскале, когда разрешено использовать имя типа до егоописания, и это разрешение относится только к ссылочным типам значений.А именно, при описании ссылочных типов можно использовать именатипов, которые описываются после данного типа значений.
В приведенномвыше примере это правило соблюдается: сначала введен в употреблениессылочный тип с именем Связь, и лишь затем описан тип с именем Звстр,которое используется в задании типа с именем Связь.Итак, отдельные звенья цепочки заданы с помощью известных типовзначений. Чтобы иметь возможность оперировать с цепочкой как единымобъектом, введем в употребление статическую ссылочную переменную,которая связана с первым звеном строки.
Значением этой переменнойявляется ссылка на первое звено строки или значение nil (в случае пустойстроки). Тип значений, к которому принадлежит эта ссылочная переменная, совпадает с уже введенным в употребление ссылочным типом с именем Связь. Обычно, для большей наглядности и понятности, вводят специальное имя для ссылочного типа значений, к которому принадлежатпеременные, ссылающиеся на первые звенья строк. Удобнее всего этосделать следующим образом: в разделе типов задать описаниединстрока=Связь;т.е. ввести в употребление тип значений, синонимичный с типом Связь.Введем в употребление ссылочную переменную str с помощью описанияstr:динстрокаЕсли эта ссылочная переменная должна указывать на строку литерПАСКАЛЬ', то представление этой строки в виде цепочки и ее связь с указателем str имеют следующий вид:Strf~*~l"H п ||А||*H5EHZEHZEHEEIДля иллюстрации техники работы со строками, представленными в видецепочки, рассмотрим следующий пример.П р и м е р 13.3.
Подсчитать число вхождений буквы V в заданноенепустое слово, состоящее из литер, не содержащих точки, и завершающееся точкой.Поскольку цель примера — проиллюстрировать технику работы с цепочками, мы не будем стремиться к получению эффективной программыи примем следующую ее схему:1. Ввести исходное слово и представить его в виде цепочки с распечаткойэтого слова.2562. Определить число вхождений заданной буквы в слово.3. Вывести результаты на печать.Примем решение о том, что слово-цепочку будем формировать по мереввода отдельных литер исходного слова.В программе нам придется иметь дело с динамическим объектом, каковым является слово-цепочка.
Для того, чтобы ввести в употреблениеэтот объект, дадим необходимые описания типов:typeСвязь=+Эвстр;3BGTp=recprd Элем;char;След: СвязьendДля ссылки на цепочку как единое целое (а точнее, на ее первое звено,поскольку в каждом звене содержится ссылка на следующее звено) введемв употребление соответствующий указатель:varУкстр: Связь;Указатель Укстр будет всегда ссылаться на начало цепочки. Нам же в процессе формирования цепочки придется ссылаться на последнее из ужесформированных звеньев для присоединения к нему очередного формируемого звена. Поэтому в разделе переменных введем в употреблениееще один рабочий указатель с помощью описанияУкзв: СвязьПроцесс формирования цепочки будет происходить следующим образом(в предположении, что литерная переменная sym в качестве своего значения имеет очередную литеру, которая должна быть включена в цепочку) .Первое звено цепочки можно сформировать с помощью операторовnew(Укстр >; Укстр+.Элем:=sym; Укстр*.След:=ni1;По первому из этих операторов будет выделено в памяти место для размещения вновь формируемого звена, а следующие два оператора формируют значения его полей.
Напомним, что переменная с указателем Укстр!именует сам динамический объект, т.е. звено, а поскольку это звено представляет собой запись, состоящую из двух полей с именами Элем и След,то их именование производится обычным для записей способом: сначалазаписывается имя всей записи, а затем через точку записывается имянужного поля записи.Следующую литеру исходного слова надо размещать в следующемзвене цепочки. Для его порождения надо снова обратиться к процедуреnew, задав в качестве фактического параметра указатель, которому в качестве значения будет присвоена ссылка на порожденное звено.
Но теперьв качестве такого указателя нельзя использовать Укстр. Во-первых, потому,что этот указатель всегда должен ссылаться на начало (первое звено) цепочки. Во-вторых, в этом случае будет "уничтожено" первое звено, а ведьк нему надо присоединить второе порождаемое звено — так, чтобы в полеСлед первого звена была занесена ссылка на второе звено.17. В.Г. Абрамов257Для формирования второго звена можно было бы использовать такуюпоследовательность операторов:new(Укстрt.След) ; Укстр t. След t.
Элем: =»ауш;Укстр t.Следt.След:=ni1Однако очевидно, что этот способ невозможно использовать в циклическомпроцессе. Для достижения единообразия при формировании последующихзвеньев цепочки будем использовать введенный нами в употреблениевспомогательный указатель Укзв, который всегда должен ссылаться напоследнее из сформированных звеньев цепочки. В связи с этим после трехоператоров, формирующих первое звено цепочки, запишем операторУкзв:=УкстрВ результате его выполнения указатель Укзв будет ссылаться на первоезвено, а в дальнейшем мы позаботимся о том, чтобы он всегда ссылалсяна последнее звено цепочки.В этом случае формирование каждого очередного звена будет производиться одной и той же последовательностью операторов:new<yK3B+.Cflefl>5 Укзв:=Укзв+ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
