9.1.1. Частотный словарь
В качестве примера использования упорядоченного списка рассмотрим построение частотного словаря. Эта задача возникает при анализе некоторого текста, когда необходимо определить, сколько и каких слов в нем встретилось, то есть определить частоту появления каждого слова. Решение заключается в следующем.
Для каждой буквы создается отдельный список, который будет содержать слова, начинающиеся на данную букву. Если слово встречается первый раз, то оно заносится в список. Если такое слово уже есть в списке, то увеличивается счетчик появления этого слова. Поэтому список опишем следующим образом:
type TInfo = string;
PNode = ^TNode;
TNode = record
Info: TInfo; // слово
cnt : integer; // счетчик повторений слова
Next: PNode
end;
А структуру частотного словаря можно будет выбрать такой:
type alphabet = ’a’..’z’;
TfreqWord = array[alphabet] of PNode
То есть частотный словарь — это массив указателей. Индекс массива — это буква, с которой начинаются все слова данного списка. Когда считывается очередное слово, то по его первой букве определяется соответствующий список.
Примечание
В приведенном описании для простоты предполагается, что слова могут начинаться только с маленькой латинской буквы. В реальном случае alphabet должно содержать все те символы, с которых могут начинаться слова обрабатываемого текста.
Сначала необходимо осуществить поиск слова в списке. А поиск в упорядоченном списке происходит быстрее, чем в неупорядоченном. Для переменных типа string упорядочение понимается в лексикографическом смысле, то есть роза меньше, чем роса, а роса меньше, чем соловей. В этой задаче мы также не касаемся филологического аспекта, то есть мы не приводим различные словоформы к некоторому общему виду, и слова люблю и любит считаем разными.
В основе алгоритма лежит процедура Insert, всегда вставляющая новый элемент в упорядоченный список. Однако теперь требуется дополнительная проверка на наличие в списке слова. Далее для сравнения приведены блок-схемы алгоритмов вставки в упорядоченный список (рис. 9.2, а) и обработки слова в списке частотного словаря (рис. 9.2, б). Дополнительные действия выделены серым цветом.
а б
Рис. 9.2. Блок-схемы алгоритмов вставки в упорядоченный список (а) и обработки слова в списке частотного словаря (б)
Программные дополнения учтены в процедуре InsertWord, приведенной в листинге 9.3.
Листинг 9.3 Вставка слова в список частотного словаря
procedure InsertWord(var p: PNode; e: TInfo);
var q,r : PNode;
Found: Boolean;
begin
if p=nil then begin // список пуст, создание первого элемента
new(p);
with p^ do begin
Info:=e; Next:=Nil;
cnt:=1; // инициализация счетчика
end;
end
else begin // вставка элемента в список
if e<=p^.Info then begin
if e=p^.Info then inc(p^.cnt)
else begin // вставка перед списком
new(q);
with q^ do begin
Info:=e; Next:=p; cnt:=1;
end;
p:=q
end;
end
else begin // поиск и вставка
found:=false; q:=p^.Next; r:=p;
while not found and (q<>Nil) do // поиск места для вставки
if e<=q^.Info then found:=true // место найдено
else begin // двигаемся дальше
r:=q; q:=q^.Next;
end;
if found then begin // найдено место в списке
if e=q^.Info then inc(q^.cnt)
//увеличение счетчика элемента
else begin // вставка нового элемента в список
new(r^.Next); r:=r^.Next;
with r^ do begin
Info:=e; Next:=q; cnt:=1;
end;
end
end
else begin // добавление элемента в конец списка
new(r^.Next); r:=r^.Next;
with r^ do begin
Info:=e; Next:=q; cnt:=1;
end;
end;
end ;
end;
end;
Создадим форму для работы с частотным словарем. Выставим компоненты:
компонент Edit для ввода слова;
кнопка ввода ;
кнопка Очистить;
компонент StringGrid — для вывода слов и частоты их повторений.
Форма показана на рис. 9.3.
Рис. 9.3. Форма для работы с частотным словарем.
Обработчик события Click кнопки считывает слово, вызывает процедуру обработки слова в списке частотного словаря и заново заполняет словами и их частотами ячейки StringGrid.
Листинг 9.4. Заполнение словами и их частотами ячейки StringGrid
procedure TFormFreWord.ButtonInsertClick(Sender: TObject);
var r:PNode;
x:TInfo;
i:integer;
begin
x:=EditInsert.Text;
InsertWord(q,x);
r:=q; i:=1;
while r<>nil do begin // для каждого слова в списке
with StringGridWord do begin
Cells[i,0]:=r^.Info; // слово
Cells[i,1]:=IntToStr(r^.cnt); // счетчик повторений
end;
r:=r^.Next; i:=i+1;
end;
EditInsert.Text:='';
EditInsert.SetFocus;
end;