В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 61
Текст из файла (страница 61)
Так, если имеется фрагмент цепочкито вставка литеры Р после литеры Т должна привести к следующему изменению этого фрагмента:Из этой схемы видно, что именно надо сделать для вставки нового звенапосле заданного:1. Создать новый динамический объект, которым будет представленовставляемое звено; этот объект должен иметь тип Звстр, т.е. запись.2. В поле Элем этой записи занести заданную литеру.3.
В поле След этой записи занести ссылку, взятую из поля След тогозвена, за которым должно следовать вставляемое звено.4. В поле След того звена, за которым должно следовать вставляемоезвено, занести ссылку на это вставляемое звено.Таким образом, описание процедуры вставки в строку заданного элемента может выглядеть следующим образом:procedure вставка(звено: связь; элемент: типэлем);var q:Звстр;beginnew(q);q + .Элем:«элемент; q t.След:=звено+.След;звено + .След:=qendЕще раз обратим внимание на то обстоятельство, что при описании всехприведенных выше процедур мы исходили из того, что любая строка-цепочка должна иметь заглавное, т.е нулевое звено. Это позволило добитьсякомпактности описания процедур, особенно процедур удаления и вставки,с помощью которых можно производить и удаление первого элементастроки, и вставку перед первым ее элементом — для этого в качествесоответствующего фактического параметра в операторе процедуры надозадать ссылку на заглавное звено цепочки.В заключение данной главы приведем пример работы с динамическимистроками с использованием рассмотренных выше операций над ними.П р и м е р 13.4.
Дано слово, состоящее из букв, за которым следуетточка, причем в слове не содержится более девяти одинаковых букв подряд. Требуется перед каждой группой одинаковых букв вставить цифру,изображающую число букв в этой группе, удалив из этой группы повторные вхождения буквы. Например, словоППАСССККАЛЛЛЛЬЬ264должно быть преобразовано в слово2П1АЗС2К1А4Л2ЬПоскольку в процессе преобразования слова из него придется удалятьлитеры и вставлять в него новые литеры, то при вводе задаваемого словапредставим его в виде цепочки.
Эту частную задачу мы уже рассматривалив предыдущем примере, поэтому не будем на ней останавливаться. Заметим лишь, что для формирования цепочки удобно использовать процедурувставки литеры.Для разработки алгоритма преобразования слова предположим, что частьслова уже переработана по заданному правилу, например, в указанном выше слове обработаны две первые группы букв, в результате чего полученопромежуточное его состояние2П1АСССККАЛЛЛЛЬЬ.Далее подлежит обработке группа букв ССС.Перед этой группой букв придется вставлять цифру (в данном случае 3 ) .Для использования процедуры вставки элемента в строку-цепочку намнадо иметь указатель на звено, вслед за которым вставляется новый элемент.
Обозначим этот указатель через УК — к началу обработки группыбукв ССС этот указатель должен указывать на звено с литерой А. Нам,естественно, понадобится указатель на начало обрабатываемой группыбукв, который обозначим через УКГР. Для сравнения двух последовательных литер строки удобно ввести в употребление указатель УКТ на текущееанализируемое звено. Обработку очередной группы одинаковых букв можно производить по следующей схеме (вместо слов "звено, на которое ссылается указатель Р", будем говорить кратко "звено Р") :к: =1;while <литеры в звеньях УКГР и УКТ совпадают} dobegin {продвинуть указатель УКТ на следующее звено};{удалить звено, следующее за звеном УКГР}к: =к.+1endВ результате от группы повторяющихся букг. будет оставлена только одна, а значение к будет равно числу букв этой группы в исходном слове.Заметим, что значение к есть целое число, а нам надо вставить литеруцифру, изображающую это число. Преобразование целочисленного значения к в соответствующую литеру, которая будет присвоена в качествезначения символьной переменной sym, можно осуществить, например,с помощью оператора варианта видаcase k o-f1: sym: = ' 1 ';2: sym: = '2 ';3: sym:='3';4: sym: = ' 4 ';5: sym:='5';o: sym: = '6 ';265endП о л у ч е н н у ю л и т е р у — значение п е р е м е н н о й sym — в с т а в и м после з в е н аУК с п о м о щ ь ю п р о ц е д у р ы в с т а в к и .Д л я перехода к о б р а б о т к е с л е д у ю щ е й г р у п п ы б у к в у к а з а т е л ь УК прод в и н е м на з в е н о , на к о т о р о е у к а з ы в а е т у к а з а т е л ь УКГР, а у к а з а т е л ьУ К Г Р — на с л е д у ю щ е е по п о р я д к у з в е н о .О с т а л ь н ы е части а л г о р и т м а о б р а б о т к и с л о в а трудностей н е в ы з ы в а ю т ,поэтому приведем окончательный текст паскаль-программы.{Пример 13.4.Волкова И.
А. Ф-т ВМиК МГУ 8.3.87г.В слове,состоящем из букв и заканчивающимся точкой,перед каждой группой одинаковых букв вставить цифру,изображающую число букв в этой группе, а от группыоставить одну букву}{Строка-цепочка.programВставка и удаление элементов строки}слово(input,output);typeтипэлем=с1"1аг;связь=*звстр;3BCTP=record элем:типэлем;след: связьend;динстр=связь;varstr,ук,укгр,укт:динотр;k: 1..9;sym: char;procedure удал(звено:связь);begin звено!.след:=звено+.след*.след end;procedure вст(звено:связь;var q:элемент:типэлем);звстр;begin new(q>;q t.элем:'элемент; q + . след:=звено*.след;звено*.след:=qend;{}begin{Печатьзаголовка}writeln('ИСХОДНОЕ_СЛОВО: ' > ;266{Ввод исходного слова, его печать и представление ввиде цепочки}{Формирование заглавного звена цепочки}new(str);strt.след:=ni1;{Подготовка к вставке литеры после заглавного звена}укт:-str;{Цикл ввода очередной литеры, ее включениев цепочку, печать}repeatread(sym); write(sym); вот(укт,sym);укт:=укт+.следunti1 sym= ' .
';writeln;{Завершение вывода на печать исходного слова}{Исходная строка - в виде цепочки str}{Заданное преобразование слова:}yK:=str;укгр:=укt.след;while у к г р э л е м * ' . 'dobegin{Подготовка к обработке очередной группы букв}к: = 1; у к т : = у к г р с л е д ;{Обработка очередной группы одинаковых букв}while укгр *.элем—укт f•элем dobegin укт:=укт+.след;удал(укгр);k:=k+l end;{Преобразование целочисленного значения к в цифру}case кo-f1: sym: = ' 1 '5 2: sym:='2' ? 3: sym: = '3' ;4: sym: = '4' 5 5: sym:='5 » 6: sym: = '<b' ;7: sym: = '7' ? 8: sym:='8' 5 9: sym: = ' О 'end;{Вставка полученной цифры перед оставленной буквой}вст(ук,зут);{Переход к обработке следующей группы букв}ук:=укгр; укгр: =.укгр+ .
следend;{Переработка слова закончена}{Печать результата}writeln('ПРЕОБРАЗОВАННОЕ_СЛОВО: ');ук:=str;repeatук:=ук+.след;wri te(sym)sym:=ук+.элем;unti1 sym= '. ' 5wr i telnend.Этим примером мы закончим главу о ссылочных типах в паскале. Следует заметить, что с помощью приема создания динамических структур,продемонстрированного на примере динамических строк, можно создаватьдинамические структуры произвольной природы, отражающие те объекты,в терминах которых наиболее просто формулируется алгоритм решениязадачи.
Такими динамическими структурами, широко используемымив программировании, являются стеки, очереди, различного вида списочные структуры, деревья и т.д. Рассмотрению этих структур данных посвящена следующая глава.ГЛАВА14ДИНАМИЧЕСКИЕ ОБЪЕКТЫ СЛОЖНОЙ СТРУКТУРЫВ предыдущей главе был рассмотрен ссылочный тип значений и показаноего использование для создания динамических программных объектови работы с ними. В качестве простейшего объекта подобного рода быларассмотрена строка, представленная в виде цепочки.
Используя аналогичную методику, можно создавать динамические структуры данных самогоразличного характера. Настоящая глава посвящена рассмотрению болеесложных динамических структур данных, достаточно часто используемыхв практике программирования.14.1. Двунаправленные спискиЗаметим прежде всего, что рассмотренная нами ранее строка, представленная в виде цепочки, является частным случаем динамической структуры,называемой в программировании линейным однонаправленным списком.В случае строки информационными элементами такого списка являютсяотдельные литеры, т.е. значения стандартного типа char.
В общем случаеинформационными элементами списка могут быть значения любого типа:вещественные числа, массивы, записи и т.д. Принцип организации отдельных элементов в единую структуру данных — линейный однонаправленныйсписок — тот же самый, что и в случае строки-цепочки: каждый информационный элемент, входящий в очередное звено списка, снабжается ссылкойна следующее за ним звено:СП•ЕЬnilЭлемент 1Элемент 2Элемент кСледуя приему, использованному в предыдущей главе, в списке предусмотрено заглавное звено. Указатель списка, значением которого является ссылка на заглавное звено, представляет список как единый объект.В один список естественно объединять однотипные элементы - хотя быпотому, что в противном случае существенно затруднится циклическаяобработка элементов списка.
Кроме того, в случае разнотипных элементовбудет весьма трудно определить такую структуру данных средствамипаскаля. Поэтому везде далее будем считать, что элементами спискаявляются значения одного и того же типа.269Если исходить из того, что в программе дано описание значений элементов списка и этому типу дано имя Элемсписка, то однонаправленныйсписок можно определить с помощью следующих описаний типов:Связь = *звено1;звено1 «• record След: Связь;Элем: ЭлемспискаendВсе определенные в предыдущей главе процедуры и функции, предназначенные для работы со строками-цепочками, легко модифицируются дляработы со списками, поэтому мы не будем приводить их описаний.Отметим, что использование однонаправленных списков при решенииряда задач может вызвать определенные трудности.
Дело в том, что по однонаправленному списку можно двигаться только в одном направлении,от заглавного звена к последнему звену списка. Между тем нередко возникает необходимость произвести какую-либо обработку элементов, предшествующих элементу с заданным свойством. Однако после нахожденияэлемента с этим свойством в однонаправленном списке у нас нет возможности получить достаточно удобный и быстрый доступ к предшествующим ему элементам — для достижения этой цели придется усложнитьалгоритм, и при этом заведомо придется еще раз последовательно перебирать элементы списка, начиная с его заглавного звена, что и неудобно,и нерационально.Для устранения этого неудобства добавим в каждое звено списка ещеодно поле (дадим ему имя Пред) типа Связь, значением которого будетссылка на предыдущее звено списка.
В этом случае структура звена будетопределяться следующим описанием типа, которому дадим имя звено2:связь2 = +звено2;звено2 = record След: связь2;Пред:связь2;Элем:ЭлемспискаendДинамическая структура, состоящая из звеньев такого типа, называетсядвунаправленным списком, который схематично можно изобразить следующим образом:nil"V1nilЭлемент 1Элемент 2ЛЭлемент кНаличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигатьсяпо списку в любом направлении. По аналогии с однонаправленным спискомздесь введено в употребление заглавное звено. В поле Пред этого звенафигурирует пустая ссылка nil, свидетельствующая о том, что у заглавногозвена нет предыдущего (так же, как у последнего звена списка нет следующего) .270В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля След последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Пред заглавного звена — ссылку на последнее звено:Как видно, здесь список замыкается в своеобразное "кольцо": двигаясьпо ссылкам, можно от последнего звена переходить к заглавному звену,а при движении в обратную сторону — от заглавного звена переходитьк последнему звену.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
