В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 64
Текст из файла (страница 64)
Если же в момент выбора из строкиочередной закрывающей скобки стек оказался пуст (для этой закрывающей скобки слева от нее не нашлось соответствующей открывающей скобки) или по завершении просмотра строки стек оказался не пуст (для находящихся в стеке открывающих скобок справа от них не нашлось соот280ветствующих закрывающих с к о б о к ) , то не выполнено первое условиесоблюдения баланса скобок.Таким образом, баланс скобок соблюдается в том случае, когда для каждой очередной закрывающей скобки в строке из стека будет выбрана соответствующая открывающая скобка, стек не будет пуст к началу обработкиочередной закрывающей скобки в строке, и по окончании обработки последней из закрывающих скобок в строке стек будет пуст.Обозначим через sym обрабатываемую литеру строки, а через b — логическую переменную, с помощью которой фиксируется факт соответствия(несоответствия) закрывающей скобки из строки с открывающей скобкойиз вершины стека.
С использованием этих обозначений запишем схему алгоритма, основанного на идее использования стека:begin{сформировать пустой стек>;{5уш:=первая литера строки);b:=true;while (sym*'.')and b dobegin{отпечатать литеру sym>;if {sym - открывающая скобка)then {занести sym в стек)elseif tsym - закрывающая скобка)thei.begin if{стек пуст)or{скобка sym не соответствуетскобке из стека) then Вs-falseend{sym:=очередная литера строки)end;if not b or {стек не пуст) then{печать'БАЛАНСА_СКОБОК_НЕТ')el se{печать'БАЛАНС_СКОБОК_ЕСТЬ')end.Читателю рекомендуется проверить правильность предложенного алгоритма на данном уровне его детализации, применив этот алгоритм к различнымситуациям, которые могут иметь место в исходной строке.Для занесения литеры в стек и выбора ее из стека можно использоватьописанные ранее процедуры.
Поскольку в данной задаче проверка на пустоту стека делается в самой программе, а элементами являются скалярныезначения (типа char), требующие мало места в памяти для их хранения, тоцелесообразно использовать более быстрый вариант процедуры выбораиз стека (ИЗСТЕКА).281Дальнейшией детализации требует лишь проверка на соответствие закрывающей скобки, являющейся значением переменной sym, и открывающейскобки в вершине стека. Определенная трудность здесь состоит в том,что в ходе этой проверки приходится выполнять и такое действие, к а кудаление элемента из стека.
Поэтому указанную проверку удобно реализовать с помощью логической функции (дадим ей имя СООТВ), котораяв качестве побочного эффекта удаляет открывающую скобку из стека.В данной программе эту функцию можно не снабжать параметрами, поскольку она применяется к одному и тому же стеку, а выбираемый изстека элемент нигде больше не используется, так что при этом можно использовать локальную переменную. Если учесть, что при обращении к этойфункции значением sym может быть одна из трех литер ' ) ' , ' ] ' , ' } ' , то дляопределения значения функции удобно использовать оператор варианта.Таким образом, описание этой функции может иметь вид (стеку дадим имя s ) :•function СООТВ: boolean;var г: char;beginИЗСТЕКА(s,r >;case sym af') ': COOTB:=r« ' < ';'3': COOTB:=r='С ' ;'}': COOTB:=r='{ 'endendРеализация на паскале остальных частей алгоритма достаточно очевидна,поэтому приведем полный текст программы на паскале.{Пример14.2.Костовский А.Н.Проверка баланса скобок в{ИспользованиеЛьвовГУ9.5.87г.задаваемой строке литер}стека}program балансскобок < i nput,output);typeтипэлвм = char;связь = Фзвеностека;звеностека = record след:связь;элем: типэлемend;стек = связь;var sym: char; s: стек; b: boolean;{}procedure встек (var st: отек; новэл: типэлем);var q: связь:282begin{создание нового звена)new(q);q+.элем:=новзл;{созданное звено сделать вершиной стека}q + .
^ e A : = s t ; st:=qend {процедуры встек};>{procedure изстека (var st: стек; var а: типэлем);begin {а:= значение из вершины стека}a:=st+.элем;{исключение первого звена из стека}st:=st + .следend{процедуры изстека};•function соотв: boolean;var г: char;beginизстека(s,г);case sym o-f' ) ' : соотв:=r=' (';' 1 ' : соотв:=r ='С';' }': соотв:=r='{'endend {функции соотв};{.->{раздел операторов программы}begin {формирование пустого стека}s:=ni1 ;{эут:=первая литера строки; b:=true}read(sym); b:=true;(sym* - .')and b dowhilebegin{печать введенной литеры}wr i te(sym);i-f {sym - открывающая скобка}sym in C'(','t','{'3then {занести symв стек}встек(s,sym)else283if(sym - закрывающая скобка}in С')', ' ] ' , ' } ' }symthenbegini-f {стек пуст или скобки не соответствуют}<s=nil)ог ( n o t соотв)t h e n b:=falseend;{ввести очередную литеру}read(sym)e n d {обработки литер строк}writeln;if {было несоответствие скобок или стек не пуст}n o t b or (s*nil)t h e n writeln('БАЛАНСА_СК0Б0К_НЕТ')elseend.writeln('БАЛАНС_СК0Б0К_ЕСТЬ'>{конец программы}14.3.
ТаблицыШироко распространенным видом услуг, которые особенно эффективнореализуются с помощью ЭВМ, является информационно-справочное обслуживание, которое подразумевает хранение сведений, прием новых сведенийи выдачу хранимых сведений по запросам. Хранимые сведения в общемслучае представляются записями. Для предоставления такого вида услугсоздаются автоматизированные информационные системы (АИС) различного назначения.
Основная задача, которая встает при создании АИС,состоит в том, чтобы организовать совместное хранение большого числаразличных записей и выдавать по запросу любую из них независимо от того,какие записи и в к а к о м порядке выдавались ранее (отсюда уже следует, чторассмотренные в предыдущем разделе очереди и стеки непригодны для.использования в АИС).Наиболее типичной операцией в АИС является поиск и выдача затребованной записи. Для пользователей такой системы было бы обременительнознать и в каждом запросе к системе указывать место хранения нужнойзаписи — тем более, если в системе хранится очень большое количествозаписей.Избежать этих неудобств позволяет. структура данных, называемаят а б л и ц е й , в которой каждой записи соответствует определенное имя.При этом в заказе на выдачу нужной записи достаточно указать только ееимя, а реализация такой структуры данных должна сама обеспечиватьдостаточно быстрый поиск записи с указанным именем.Итак, таблица - это некоторый (вообще говоря неупорядоченный)набор именованных записей.
Имена записей могут выбираться достаточнопроизвольным образом. Однако, чтобы иметь возможность организовать284эффективный поиск записи по заданному ее имени, нужно иметь возможность сравнивать любые два имени записей и устанавливать, какое из них"меньше", а какое "больше". При этом, естественно, подразумевается, чтовсе записи имеют разные имена. Имя записи в таблице часто называют также ключом записи.В качестве ключей чаще всего используются целые положительные числа.В паскале для этих целей удобно использовать и строки литер (одинаковойдлины), поскольку строки, с одной стороны, позволяют давать записямдостаточно естественные имена, а с другой — над ними определены операции сравнения.Таким образом, каждая запись, входящая в таблицу, содержит свойключ и некоторую информацию, связанную с этим ключом (текст записи).Над таблицей как структурой данных определены следующие операции:— поиск в таблице записи с заданным ключом;— включение в таблицу записи с заданным ключом (обычно считается,что если в таблице уже есть запись с таким ключом, то это означает заменустарой записи на новую);— исключение из таблицы записи с заданным ключом.Существует много разных способов организации таблиц, каждый из которых имеет и свои преимущества, и свои недостатки, так что выбор тогоили иного способа должен определяться характером использования даннойтаблицы.14.3.1.
Простая цепочкаПростейший способ представления таблицы — это однонаправленный список, рассмотренный в начале данной главы. Каждое звено цепочки, котораяи образует список, содержит ключ записи, текст записи и ссылку на следующее звено. Этот способ представления таблицы имеет несомненные достоинства. Во-первых, в качестве дополнительной информации в звене используется единственное простое значение — ссылка на следующее звено, такчто память машины используется достаточно эффективно. Во-вторых,алгоритм перебора записей, необходимого для поиска записи с заданнымключом, очень прост. В-третьих, включение в таблицу заведомо новойзаписи (т.е.
записи с ключом, которого в таблице заведомо нет) можнореализовать максимально эффективно, помещая новое звено в началосписка.Основной недостаток этого способа состоит в том, что поиск требуемойзаписи может оказаться довольно длительным. Действительно, для поисказаписи приходится последовательно перебирать звенья списка, пока невстретится запись с заданным ключом или не исчерпается список (еслизаписи с заданным ключом в таблице нет). Таким образом, если таблицасодержит N записей, то в среднем для поиска записи надо просмотреть N/2элементов списка.
Если N сравнительно невелико (порядка десятков илисотен записей), то-такое среднее время поиска может быть вполне приемлемым - с учетом преимуществ данного способа. Если N велико (в таблицесдержатся сотни тысяч или даже миллионы записей, что может, например,иметь место в таблице, представляющей собой каталог достаточно крупнойбиблиотеки), то такое среднее время поиска может оказаться практическинеприемлемым — в этих случаях приходится выбирать иные способы представления таблиц.285Другой недостаток рассматриваемого способа состоит в том, что еслив таблице нет записи с заданным ключом, то для установления этого фактапридется перебрать все N записей: поскольку мы предполагаем, что записиследуют в списке в произвольном порядке, то в отсутствии нужной записиможно убедиться лишь путем просмотра всех без исключения записей.14.3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
