while Assigned(p) and Assigned(p^.mNext) and (p^.mNext^.mWord <= aWord)
do p:=p^.mNext;
{ Если конец списка не достигнут и слово совпадает… }
if Assigned(p) and (p^.mWord = aWord)
then Find:= p { … то успешно! }
else Find:= nil; { … а иначе не нашли }
end;
{ Размещение нового элемента в сортированном списке слов }
procedure AddToSortList(const aWord : string);
var p, q : PRec;
begin
New(p); { Создаем динамическую переменную-запись }
{ Размещаем данные в полях записи }
p^.mCount:= 1; p^.mWord:= aWord; p^.mNext:=nil;
{ Если список пуст… }
if not Assigned(List)
then List:= p { …голова указывает на первую запись }
else begin
q:= List; { Поиск места вставки начинаем с головы }
{ Двигаемся по списку, пока следующий элемент существует
и его номер меньше вставляемого }
while Assigned(q^.mNext) and (q^.mNext^.mWord < aWord)
do q:=q^.mNext;
if q^.mWord > aWord then begin
{ вставка на первое место }
p^.mNext:=List; { первый становится вторым }
List:=p; { а текущий- первым }
end else begin
{ вставка в середине или в конце списка }
p^.mNext:=q^.mNext; { связываем текущий со следующим }
q^.mNext:=p; { связываем предыдущий с текущим }
end
end
end;
{ Добавление слова либо увеличение его счетчика }
procedure AddWord(const aWord : string);
var P : PRec;
begin
P:= Find(aWord);
if Assigned(p)
then Inc(P^.mCount)
else AddToSortList(aWord);
end;
{ Выделение и добавление слов из прочитанной строки }
procedure AddLine(S: string);
const CLetter = ['A'..'Z','_'];
CDigits = ['0'..'9'];
var W : string; i : integer;
begin
{ переводим все буквы строки в верхний регистр }
for i:=1 to Length(S) do S[i]:= UpCase(S[i]);
while Length(S)>0 do begin
{ удаляем все небуквы в начале строки }
while (Length(S)>0) and not (S[1] in CLetter) do Delete(S,1,1);
if Length(S)>0 then begin
W:='';
{ копируем все буквы и цифры в слово W и удаляем из строки }
while (Length(S)>0) and (S[1] in CLetter+CDigits) do begin
W:= W+S[1];
Delete(S,1,1);
end;
if Length(W)>1 then AddWord(W); { Если не буква, вставляем в список }
end;
end;
end;
{ Распечатка списка }
procedure PrintList(var F: text);
var P : PRec;
begin
Rewrite(F); P:= List;
while Assigned(P) do begin
Writeln(F, P^.mWord, '':(20-Length(P^.mWord)), P^.mCount:5 );
P:= P^.mNext;
end;
Close(F);
end;
var S: string; F: text;
begin {--- Главная программа ---}
List:= nil;
Assign(F, 'P_55_1.pas');
Reset(F);
while not Eof(F) do begin
Readln(F, S);
AddLine(S);
end;
Close(F); Assign(F, 'P_55_1.OUT');
PrintList(F); { Распечатка списка }
end.
Полагаю, что моих комментариев и вашего опыта хватит для понимания программы. Обязательно проверьте её. Вот результат исследования программой своего собственного текста (приведена только часть слов).
ADDLINE 2
ADDTOSORTLIST 2
ADDWORD 2
AND 6
ASSIGN 2
ASSIGNED 7
AWORD 10
BEGIN 14
CLETTER 3
А слабо?А) Дополните программу средствами для подсчета:
• общего количества слов в файле;
• общего количества разных слов.
Напишите для этого подобающие функции.
Б) Измените программу так, чтобы при распечатке списка выводилась относительная частота слов в процентах от общего их количества с двумя знаками после точки.
В) Создайте программу для подсчета в файле слов, составленных из одних и тех же символов: цифр и букв, например: «end» и «deen», «121» и «221». Для каждой такой группы слов программа должна напечатать перечень входящих в них символов (каждый символ – по разу) и количество обнаруженных слов этой группы, например, для приведенных выше слов будет напечатано:
1 2 – 2
d e n – 2
Подсказка: воспользуйтесь списком, записи которого включают в себя множество символов. Для слов, составленных из одинаковых символов, эти множества совпадают.
Глава 56И снова очереди, и снова стеки…
Новейшая версия полицейской базы данных и частотный анализатор текста укрепили ваш опыт по части динамических переменных. И все-таки, один момент нами упущен. Пока мы лишь добавляли данные в кучу, не утруждая себя её очисткой, – в решаемых задачах этого не требовалось. Но так будет не вечно, когда-то придется освобождать кучу от ненужных переменных. В этой главе мы рассмотрим два таких случая на примере знакомых нам очередей и стеков.
Шутить изволите?Однажды, это было 1-го апреля, придворный программист Ник получил от приятеля странную «электрошку». Письмо содержало загадочный текст, очень похожий на программу, вот несколько его первых строк.
end.
Close(F);
while Pop(S) do Writeln(F, S);
{ Пока стек не пуст, извлекаем и печатаем строки }
Assign(F, 'P_56_1.out'); Rewrite(F);
{ Открываем выходной файл }
Close(F);
end;
Приятель умолял Ника найти здесь ошибку.
Приняв во внимание 1-е апреля, Ник заподозрил розыгрыш и всмотрелся в эту абракадабру внимательней. Вскоре он сообразил, что строки в файле следуют в обратном порядке: последняя стоит первой, а первая – последней. Достойным ответом приятелю, – рассудил Ник, – будет правильный текст этой же программы. Но как переставить строки? Вручную, редактором текста? «Не царское это дело! – возмутился его разум, – пусть этим займется компьютер». И Ник написал программу для преобразования файла. Последуем за Ником.
Вы уже знакомы со стеком – временным хранилищем данных, из которого последний вставленный элемент извлекается первым (сообразно с дисциплиной LIFO). Стек – отличное средство для перестановки данных шиворот навыворот и задом наперед. Хранилищем данных в нашем первом стеке была строка, а хранимыми элементами – символы (загляните в главу 45). Скромные возможности того стека не помешали нам решить задачу о сортировочной горке.
Но чаще в стеке надо сохранять не символы, а крупные и сложные элементы данных. Так будет и в программе Ника, где элементом данных является строка. Как организовать стек из строк?
Вспомним порядок элементов при вставке их в список: последний элемент оттесняет соседей, становясь на первое место. А это значит, что, извлекая элементы от головы к хвосту списка, мы получим их в обратном порядке (рис. 127).
Рис.127 – Порядок следования в стеке первых трех строк