В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 67
Текст из файла (страница 67)
При решении данной задачи в качестве ключей выступают фами295лии студентов, которые в программе представлены строками (упакованными массивами литер). В силу этого тип ключа во всех приведенных ранее описаниях будет изменен на packed array [ 1 .. 10] of char. Тела же процедур и функций останутся прежними в силу того, что над строками определены операции сравнения, используемые в этих процедурах и функциях.Более подробно следует остановиться на возникающей при решении задачи проблеме полного обхода дерева.
Действительно, чтобы определитьвсех неуспевающих и всех отличников, необходимо обойти все вершиныдерева. Схематично алгоритм обхода двоичного дерева может выглядеть,например, следующим образом.1. В качестве очередной вершины взять корень дерева, Перейти к пункту 2.2. Произвести обработку очередной вершины в соответствии с требованиями задачи.
Перейти к пункту 3.3. а) Если очередная вершина имеет обе ветви, то в качестве новой очередной вершины выбрать ту вершину, на которую ссылается левая ветвь,а вершину, на которую ссылается правая ветвь, поставить в очередь; перейти к пункту 2;б) если очередная вершина является конечной, то выбрать в качественовой очередной вершины вершину из очереди, если она не пуста, и перейти к пункту 2; если же очередь пуста, то это означает, что обход всегодерева окончен, перейти к пункту 4;в) если очередная вершина имеет только одну ветвь, то в качестве новойочередной вершины выбрать ту вершину, на которую эта ветвь указывает,и перейти к пункту 2.4. Конец алгоритма.Обработка каждой вершины состоит в анализе массива оценок, которыенаходятся в информационной части вершины (напомним, что в звене дерева есть лишь ссылка на информационную часть),Фамилии отличников будем сразу печатать, а фамилии студентов (ссылки на соответствующие звенья дерева), получивших неудовлетворительныеоценки по трем предметам, будем помещать в очередь.
По окончанииполного обхода дерева напечатаем накопленные в очереди фамилии стуцентов, получивших неудовлетворительные оценки.Таким образом, общая схема алгоритма решения задачи выглядит следующим образом:begin {Ввод информации из внешнего Файла с именемСтуд и построение двоичного дерева}{Полный обход дерева,печать Фамилий отличников,отбор и постановка в очередь Фамилий двоечников}{Печать Фамилий двоечников}endДля представления очереди в программе используется изученная ранееструктура данных — стек.
Кроме введенных в употребление ранее процедури функций для работы со стеком и таблицей, представленной в виде двоичного дерева, в программе используется вспомогательная процедураПЕЧФАМ. Эта процедура имеет один формальный параметр, который пред296ставляет ссылку на вершину дерева. Результатом обращения к ней является печать фамилии, указанной в заданной вершине.{Пример14.3.Мальковский М.Г.Ф-т ВМиК МГУ1.5.87г.Ввести информацию о студентах, напечатать Фамилииотличников истудентов, получивших три двойки >{Построение двоичного дерева и его обработка.Использование стека как вспомогательнойструктурыprogramданных}ДЕРЕВОУСПЕВ<Студ,output);const М=3;{число экзаменов в сессию}N=105{максимальное число букв в Фамилии}typeтекст=гесогс1 группа:100.. 699;оценка: array El..
МП o-f 2..5end;{тип значения,представляющего текст записи}Фaм=packed array C1..N3 o-f char;укт=+текст;укзв=1-звено;3eeHO=record ключ:Фам;лев,прав: укзв;ссылка: уктend;{}тпэлст= укзв;{имя или задание типа элементов стека}связьст = t3BeHOCTeKa;звеностека = recordслед:связьст;элем: тпэлстend;стек = связьст;сведения = recordfm: Фам;inf: текстend;varстуд: file of сведения;q: укт; fl: Фам; p,d: укзв;<ст1, ст2, стЗ: стек;>297p r o c e d u r e встек (var s t : с т е к ; ноеэл: т п э л с т ) ;var qs связь;begin{ с о з д а н и е нового з в е н а )new(q); qt.элем:=новэл;{ с о з д а н н о е звено сделать вершиной с т е к а )qt.след:=st; st:=qend;{p r o c e d u r e иэстека (var s t : с т е к ; var а : т п э л с т ) ;b e g i n { a : = значение из вершины с т е к а )a : = s t + .элем;{исключение первого эвена из с т е к а )at:=stследend;{• f u n c t i o n ПОИСК({ключ) ks фам; var {в д е р е в е ) d,{результат) рез: укзв): boolean;v a r р , q : укзв;b; b o o l e a n ;b e g i n {подготовка к циклу)b : ° f a l s e ; p:»d;i-f d # n i l t h e nrepeatq:=p;i f р+.ключ=к t h e n (запиоь найдена) b : = t r u eelseb e g i n {запоминание обраё.
вершины) q:=p;i f к<р+.ключ t h e n р : = р ! . л е в e l s e р»р+.правendu n t i l b or ( p = n i l ) ;ПОИСК:=b; pe3:=qend;{p r o c e d u r e ВТАБЛ ({ключ) k: фам; {в дерево) var d: укзв;{запись) г е е : т е к с т ) ;var r , s : укзв;t : укт;beginif n o t ПОИСК < k , d , r ) t h e n298)begin {занесение в таблицу текста записи}new(t>; t+s=rec;{формирование новой вершины в дереве}new(s);5+.ключ!=к$s*.соылка:=t;s*.flee:=nil; st.правs=ni1;Iif d=nil then {если дерево пусто, то созданноезвено сделать вершиной дерева} d:=selse {подсоединить новую вершину к дереву}if к<г+.ключ then г*.лев:=з else г+.прав:=5endend;procedure ПЕЧФАМ({ссылка на звено} г: укзв);var i: integer;begin for it=l to N do write<rt.ключС13);wri telnend;{}begin {ввод сведений из внешнего Файла Студи создание двоичного дерева}reset(Студ); d:=nil;while not eof(CTyA) dobegin ВТАБЛ(Студt.fm,d,Студ*.inf); get(Студ) end;{обход двоичного дерева и обработка его вершин}{начальная установка вспомогательных стеков}CTl:=nil; cT2:=nil; ps=d;while p#nil dobegin if{студент-отличник}(p t.ссылка +.оценка С 13 =5)and(p +.ссылка t.оценка С 2 3 ~5)and(p t.ссылка*.оценкаСЗЗ=5>then {печать Фамилии} ПЕЧЧ'АМ(р)el sebeginif{студент-двоечник.}(pt.ссылка*.оценкаС13=2>and(p*.ссылка*.oueHKaC23=2)and(p + .ссылка*.оценкаС33=2)then{занесение ссылки на вершину, содержащуюФамилию этого студента, в стек ст2}встек(ст2,р)299end;{определение следующей вершины}if {в вершине обе ветви}(р + .npaB^nil)and(р + .лев*п11>thenbegin встек<ст1,р+.прав);р:=р+.лев endel seif {в вершине нет ветвей}<р t.
npaB=ni 1 >and (р t. л е в = ^ 1)thenbegin if CTl=nil then p:=nilelse изстека(CTI,p>endelse{в вершине только одна ветвь}begin if p+.npae=nil then р!=р+.левelse p:=pt.npaeendend;{конец while}{печатьФамилий двоечников}writeln('СПИС0К_ДВ0ЕЧНИК0В'> ;while cT2#nildobegin изстека<ст2,р) ;{печать очередной Фамилии двоечника}ПЕНФАМ(р)endend.В программе была использована буферная переменная внешнего файлаСтуд.
В качестве упражнения читателю предлагается модифицировать программу так, чтобы в ней не использовалась буферная переменная и стандартные процедуры put и get. Для ввода значений компонент файла использовать стандартную процедуру read.Если у читателя возникнет желание выполнить эту программу на машине, то для этого необходимо подготовить внешний файл с именем Студ изанести туда сведения о студентах (из стандартного файла input).
Это можно сделать, например, с помощью следующей программы:{Пример 14.4. Кауфман В. Id. Ф-т ВМиК МГУ2.6.87г.Ввод сведений из стандартного файла inputво внешний Файл Студ }{Пример подготовки во внешнем Файле информации,которая используется в другой программе}300programВВ0ДИНФ0Р(input,Студ)const M = 3 {число экзаменов в сессию};N = 1 0 {максимальное число букв в Фамилии};шаблон= '';typeтекст=гесогс! группа:100.. 699;оценка: array С1..МЗ erf5end;{тип значения,представляющего т е к с т записи}1>aM=packed array C1..N3 o-f char;сведения = recordfin: фам;i nf: текстend;varСтуд: file of сведения; сим: char;rec: сведения; i,j: integer;begin г е м г И е ( С т у д ) ;w h i l e сим*'.'геасКоим);dobegin {ввод Фамилии}w h i l e сим#','i:=0;Студ*.fm:=шаблон;dobegin i:=i+l; Студ+.fmEi3:=сим; read(сим) e n d ;{ввод номера группы}read(j>;Студt.inf.группа:=j;{ввод оценок}for i:=lto M d obegin read<j>;put(Студ);С т у д i n f .
о ц е н к а С i 3 : = j end;read(сим)endend.Для правильного заполнения файла Студ необходимо, чтобы сведенияо каждом студенте вводились следующим образом:1) первой вводится фамилия, представляющая собой последовательность не более JV=10 литер-букв, которая оканчивается запятой;2) вводится целое число, задающее номер группы;3) последовательно вводятся три целых числа, задающие оценки, полученные студентом в сессию;4) если необходимо ввести новую последовательность сведений об очередном студенте, то действия повторяются с пункта I ) ; если после выполнения пункта 3 необходимо закончить ввод сведений, то нужно ввес301ти литеру ' . ' ( т о ч к а ) , которая является признаком конца вводимой информации.В этой программе использовалась буферная переменная внешнего файла Студ и стандартная процедура put.
В качестве упражнения читателюпредлагается модифицировать эту программу так, чтобы исключить использование буферной переменной и воспользоваться стандартной процедурой записи write.В заключение можно предложить читателю модифицировать программу ДЕРЕВОУСП так, чтобы в ней был предусмотрен ввод сведений неиз внешнего файла Студ, где заранее подготовлена информация с помощью ВВОДИНФОР, а непосредственно из стандартного файла input.ПРИЛОЖЕНИЕСВОДНЫЕ СИНТАКСИЧЕСКИЕ ДИАГРАММЫЯЗЫКА ПАСКАЛЬ1.1. Программа<программа> ::=»-<заголовок программы>^-<блок>«'заголовок программы> :: =- p r o g r a m — и м я п р о г р а м м ы ) — ((——г Кфайла>и иммяя файла> itJ)1.2. Блок<блок> : : =<раздел описаний)Чраэдел операторов)<раэдел описаний) ::-1Сраздел меток><раздел констант)<раздел типов)-<раэдел переменных)» ;|-<раздел функций и процедур><раздел меток) :i«-label—*-<нетка оператора)303<раздел констант>•const::~описаниеразделконстанты)типов•type-описание типа ><раздел п е р е м е н н ы х ) ::=• var<описание переменны;:раздел Функций и процедурTZописаниеФункции)описаниепроцедуры)ираздел операторов.: :: =•<составной'.3.оператор)Операторыо п е р а т о р ) ::=т~меткаггс:;оператора-основнойоператор)•производныйоператоросновной о п е р а т о р ) ;:=• <оператор•«'пустойприсваивания)оператор)(операторперехода)(оператор п р о ц е д у р ы ) -:.праи вводный о п е р а т о р ) :: =—^(составнойоператор)-<выбираюцийоператорчопер атороператороператор)цикла)присоединения)присваивания,"• < переменная >— < и м я304функции >т т * "-чвыражение)-и'пустой оператор >Соператор п е р е х о д а ) :\-goto •-чметка оператора.'< оператор процедуры;- : : =(имя процедуры)-Т(—т*-<фактическийттпараметр > —<Фактический п а р а м е т р ) ::выражение)-< переменная )• <имя Ф у н к ц й и )-<имя п р о ц е д у р ы ) •чсоставнойоператор)-begi п-оператор .=-end •Свыбирающий о п е р а т о р ) :—^-<условныйоператор)операторварианта)<условный о п е р а т о р ) ::=i -f — л о г и ч е с к о е выражение ) — t h e nоператор) -se< оператор )<оператор в а р и а н т а ) s:=-case*-<селектор о п е р а т о р а )Г•<метка варианта)—г*-:<селектор о п е р а т о р а ) ::=индексное20.
В.Г. Абрамоввыражение) —э^-o-fоператор•-end -<меткаварианта)»• <константа>£ <канстанта> - целого, литерного, перечислимого или логического типа ><аператор цикла> s:=оператор цикла с п а р а м е т р о м )операторцикласпостусловием> —<оператор цикла с предусловием ><оператор цикла с параметром> ::"orI»-<параметр цикла >»•: =выражение)-тto^downto•<выра*емие>»-do»-<оператор>—<параметр цикла> : : =*-<имя переменном >{ <параметр цикла>, < в ы р а ж е н и е ) - индексного типа ><оператор цикла с п о с т у с л о в и е м ) ss=— r e p e a t —t—jj»-<т » Ч оператор)—r*-unti1 —»-<логическое выражение > опер агор >—<оператор цикла с предусловием)while—»-<логическоевыражение)—»-do —*-<оператор><оператор присоединения> ::=»-<эаголавок><заголовок>with*-<оператор)::=*-<список переменных)»-do<список переменных) ::=<переменная)С <переменная) - комбинированного типа >3061.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
