4.7. Сводный указатель
В этом разделе мы создадим приложение, использующее концепции словаря и множества наряду с классом string, представленным в разделе 2.12. Это будет программа сводный указатель, берущая в качестве входных данных любой текстовый файл и для каждого слова в файле показывающая номера строк, в которых встречается это слово. Если слово встречается более одного раза на строчке, для этого слова номер строчки появится только один раз; сами слова будут перечислены в алфавитном порядке. Слово определяется как последовательность букв. Заглавные буквы будут заменены строчными. Для примера в качестве входного файла выберем текст первой программы в этой книге из раздела 1.1:
// ftempi.cpp: A template function, ttinclude <iostream.h>
template <class T>
T f(T x)
{ T x2 = 2 * x;
return x2 + (x * x + l)/x2; }
int main()
{ cout « f(5.0) << endl « f(5) << endl;
return 0; }
Как мы видим, во входном файле могут встречаться любые символы. Для него наша программа сводный указатель выдаст следующий результат:
Enter name of input file: ftempi.cpp
a 1
class 4
cout 11
cpp 1
endl 11
f 5 11
ftempl 1
function 1
h 2
include 2
int 10
iostream 2
main 10
return 7 12
t 4 5 6
template 1 4
x 5 6 7
С помощью контейнера STL map (словарь) мы можем хранить все слова в сбалансированном двоичном дереве поиска (что делает поиск очень быстрой операцией), не программируя самостоятельно функциональность такого дерева. Каждый узел дерева содержит слово (используемое в качестве ключа) вместе с множеством номеров строк. В терминологии STL каждый элемент словаря является парой (first, second), где
first = слово; представляется типом string; second = множество номеров строк; представляется типом set<int>.
Имя входного файла также будет содержаться в переменной типа string; полностью программа приведена ниже:
// concord.срр: Сводный указатель, использующий словари,
// множества и строки.
<< назад вперед >>