В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 60
Текст из файла (страница 60)
След; Укзвt.Элем:=sym;Укзв t.След:=ni1(Читателю предлагается ответить на такой вопрос: можно ли здесь в качестве фактического параметра оператора процедуры new использовать указатель Укзв, и если нет, то почему?)После сделанных замечаний реализация первого этапа схемы нашей программы трудностей не вызывает.Что касается второго этапа, на котором приходится последовательноперебирать все звенья цепочки, то здесь очень важно понять способ перехода от одного звена к следующему по порядку звену. Если имеется указатель р, значением которого является ссылка на какое-либо звено, то дляприсваивания этому указателю в качестве нового значения ссылки на следующее звено надо выполнить оператор присваиванияр:=р +.Следявляющийся аналогом оператора к: = к + 1, который исполнялся для получения индекса к следующего элемента при векторном представлениистроки.Теперь приведем полный текст паскаль-программы, предназначеннойдля решения поставленной задачи.<Прммер 13.3.
Вариант 1. Фролов Г.Д. МГПИ2.5.87г.Подсчитать число вхождений буквы t в заданноеслово,завершающееся точкой}{Представление строки в виде цепочки.указателей}program числовхбкв(i nput,output) ;const 6KB='t';258Использованиеtype Связь=+3встр;Звстр= record Элем:char;След: Связьend;varУкстр,Укзв:Связь;sym: char;Ь: integer;begin{Печать заголовка результата}writeln('В_СЛОВО') ;{Ввод исходного слова, его представление в видецепочки, распечатка}{Формирование первого звена}read(sym); write(sym);пем(Укстр); Укстр*.Элем:=sym;Укстрt.След:=nil;{Подготовка к циклу формирования остальных звеньев}Укзв:=Укстр;{Цикл обработки последовательных литер строки}while sym#'.' dobegin read(sym);write(sym);new(Укзв t.След);Укзв:=Укзв t.След;Укзв + .Элем:=sym; Укзв + .След:=ni1;end;{Исходное слово представлено в виде цепочки}{Подсчет числа вхождений буквы бкв в слово}К:=0;УКЗВ:=УКСТР;while Укзв#п11 dobegin i-f Укзв t.
Элем=бкв then k:-k+l;Укзв:=Укзв t.Следend;{Печать результата}writeln;writeln('БУКВА_',бкв,'_ВХОДИТ_',k,"_PA3')end.И з приведенной п р о г р а м м ы в и д н о , что ф о р м и р о в а н и е з в е н а , соответств у ю щ е г о п е р в о м у э л е м е н т у с т р о к и , п р и х о д и т с я делать н е с т а н д а р т н ы мс п о с о б о м — иначе, чем ф о р м и р о в а н и е о с т а л ь н ы х з в е н ь е в . И в о о б щ е , прит а к о м представлении ц е п о ч к и о б р а б о т к а п е р в о г о звена будет отличатьсяот обработки других звеньев.Д л я устранения этих н е д о с т а т к о в , а т а к ж е д л я у д о б с т в а п о с л е д у ю щ е йр а б о т ы с ц е п о ч к о й , в нее у д о б н о в к л ю ч и т ь з а г л а в н о е , " н у л е в о е " з в е н о ,17*259в п о л е С л е д к о т о р о г о с о д е р ж и т с я с с ы л к а на п е р в о е з в е н о , с о д е р ж а щ е еп е р в у ю л и т е р у с т р о к и , а п о л е Э л е м м о ж н о и с п о л ь з о в а т ь д л я хранениян е к о т о р о й д о п о л н и т е л ь н о й и н ф о р м а ц и и о с т р о к е .
П р и т а к о м способеп р е д с т а в л е н и я с т р о к и в в и д е ц е п о ч к и п р о г р а м м а н а ш е г о п р и м е р а будетлогичнее и проще:{Пример 13.3. Вариант 2. Руднев И.А. ф-т ВМиК МГУ 4.4.87г.Подсчитать число вхождений буквы t в заданноеслово,завершающееся точкой}{Представление строки в виде цепочки.Использованиеуказателей}program числовхбкв(i nput,output);const6 K B = ' T ' ;t y p e Связь=+3встр;Звстр= record Элем:char;След: Связьend;varУкстр,Укзв:Связь;sym: char;k: integer;begin{Печатьзаголовка результата}writeln('В_СЛ0В0');{Ввод исходного слова, его представление в видецепочки, распечатка}{Формирование заглавного звена}new(Укстр); Укзв:=Укстр; Укзвt.
След:»ni1;read(sym);{Чтение первой литеры}{Циклическая обработка литер, если слово не пусто}while sym*'.' dobegin write(sym);{Печать введенной литеры}new(УкзвСлед);Укзв:=Укзв t.След;Укзв + .Элем:=sym; Укзв+.След:=п11;read(sym)end;{Исходное слово представлено в виде цепочки}{Подсчет числа вхождений в слово заданной буквы}К:=0;Укзв:=УКСТР;while У к з в С л е д * п 1 1dobegin Укзв:=Укзвt.След;if У к з в Э л е м = б к в then k:=k+l260end;{Печать результата}writeln;wri teln('БУКВА_',бкв,'_ВХОДИТ_',k,'_PA3'>end.13.3.3.
Реализация операций над строками-цепочкамиРассмотрим реализацию основных операций над строками в случае ихпредставления в виде цепочек. Напомним, что в виде цепочек мы представляем динамические строки литер. Поэтому сначала приведем описания тех типов значений и переменных, которые будут использоватьсяниже в описаниях процедур, реализующих основные операции над строками:typeтипэлем=сЬаг;связь=+3встр;Звстр=гесогс1 Элем; типэлем;След: связьend;динстр=связь;varstr: динстрВезде далее будем считать, что любая (в том числе и пустая) строкав виде цепочки имеет рассмотренное выше заглавное звено (у пустойстроки поле След заглавного звена содержит ссылку nil).Поиск заданного элемента в строке.
Как и в случае векторного представления строки, алгоритм выполнения этой операции зададим в видеописания логической процедуры-функции, которая в качестве побочногоэффекта определяет ссылку на первое вхождение заданного элементав указанную строку (ссылку на соответствующее звено цепочки).Алгоритм поиска очень прост: будем просматривать — с использованием ссылок — последовательные звенья цепочки и сравнивать значениеполя Элем каждого звена с заданным элементом. Этот процесс заканчивается в двух случаях:а) очередное звено цепочки содержит заданный элемент; в этом случаефункция должна принять значение true, а в качестве побочного эффектавыдается ссылка на это звено;б) цепочка будет исчерпана (в поле След очередного обработанногозвена окажется ссылка nil); в этом случае функция должна принять значение false, а в качестве побочного эффекта будет выдавать значение nil(впрочем, это значение можно считать и неопределенным).Описание такой логической процедуры-функции может иметь вид:•function поиск (st: динстр; эл:типэлем;var гез:овязь):boolean;var q:связь;beginпоиск: =-f alse; res:=nil; q ^ s t + .След;261while <q*.nil) and(res^ni 1) dobegini-f qt.3/ieM=3fl thenbegin поиск!=true;res:=q end;q:<=q*.Следendend;Заметим, что за счет повторных обращений к этой процедуре можно найтивсе вхождения в строку заданного элемента — для нахождения очередногоего вхождения достаточно снова обратиться к процедуре, задав в качествепервого фактического параметра ссылку на звено, которое содержалопредыдущее вхождение заданного элемента (другими словами, задавв качестве исследуемой строки ту часть исходной строки, которая следуетза этим звеном).
Этот процесс следует завершить, когда при очередномобращении к процедуре будет выработано значение функции, равное false.Удаление из строки заданного элемента. Здесь прежде всего необходиморешить вопрос о том, как следует задавать элемент строки, подлежащийудалению, поскольку это можно сделать разными способами. Например,удаляемый элемент можно было бы задать его порядковым номеромв строке, но в случае строки-цепочки по номеру элемента невозможеннепосредственный доступ к нему, так что для поиска этого элемента пришлось бы последовательно перебирать звенья цепочки, начиная с заглавногозвена. Гораздо удобнее исключаемый элемент задать с помощью ссылкина то звено, за которым следует этот элемент. К тому же и на практикенаиболее типичен случай, когда надо исключить элемент, следующий за элементом, найденным с помощью рассмотренной выше функции поиска.При рассмотрении процедуры исключения элемента важно вспомнить,что в случае строки-цепочки доступ к ее последовательным элементамосуществляется только по ссылкам, содержащимся в каждом звене цепочки, начиная с ее заглавного звена.
Если же какое-либо звено и существует,но на него нет ссылки из другого звена, то оно недоступно при последовательном переборе звеньев цепочки и потому это звено в цепочку не входит. На этом факте и основывается идея быстрого исключения элементаиз строки. Эту идею схематически можно проиллюстрировать следующимобразом. Пусть имеется фрагмент исходной цепочки, в котором представлены звенья с литерами Д, В и Аи пусть требуется исключить из строки литеру, следующую за литерои Д.Учитывая связь звеньев в цепочку с помощью ссылок, звено с литерой Вбудет исключено из цепочки, если звено с литерой Д будет ссылаться на звено с литерой А, минуя звено с литерой В:нань1 ва-^ЕЕЬЗначит, для исключения из строки элемента В достаточно изменить ссылку262у предшествующего ему элемента, причем в качестве новой ссылки у этогоэлемента надо принять ссылку, содержащуюся в исключаемом элементе.Таким образом, описание процедуры исключения элемента из строкицепочки можно описать следующим образом:procedure удаление(звено:связь);begin звено*.След:=звено*.След*.След endПри описании этой процедуры сделано предположение, что исключаемоезвено в строке существует, т.е.
что звено, задаваемое в качестве фактического параметра в операторе процедуры (в виде ссылки на него), не является последним в строке — в противном случае результат выполнения процедуры будет неопределенным. Чтобы избежать такой ситуации, в описаниипроцедуры можно предусмотреть контроль корректности задания фактического параметра и принять, например, решение о том, что если фактический параметр указывает на последнее звено строки, то строка остаетсябез изменения:procedure удаление1(звено:связь);begin if звено*. С л е д и т 1 thenзвено*.След:=звено*.След*.СледendРазумеется, эта процедура снизит быстродействие программы, посколькупри каждом выполнении процедуры будет затрачиваться дополнительноевремя на проверку содержащегося в ней условия.Следует обратить внимание на то, что при выполнении каждой из этихпроцедур исключенное из строки звено тем не менее продолжает существовать и занимать место в памяти машины, хотя это звено и становитсянедоступным для использования.
Такой способ может привести к весьманеэффективному использованию памяти за счет хранения в ней исключенных элементов строк. Для устранения этого недостатка в описании процедуры исключения можно предусмотреть уничтожение исключенного из цепочки звена с помощью процедуры dispose:procedure удаление2(звено:связь);var q: связь;begin q:=звено*.След;звено*.След:=звено*.След*.След;di spose(q)end(в этом описании процедуры удаления контроль корректности заданияфактического параметра не предусмотрен').Выполнение этой процедуры также требует дополнительной затратывремени на уничтожение удаленного звена. Вопрос о том, какую из приведенных выше процедур целесообразнее использовать, зависит от того, чтоявляется более важным - быстродействие программы или экономноерасходование памяти.Вставка заданного элемента. Быстрая вставка в строку заданого элемента также основывается на объединении отдельных звеньев в единую цепоч263ку с помощью ссылок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
