Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 74

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 68 69 70 71 72 73 < 74 > 75 76 77 78 79 80 .. 161 >> Следующая

^истингЖз. ПойШ слова в предложении, встречающегося в нем более одного раза /V -- t -
//==========:======::===========:==:==:===:=:================:::===========:=======
// Класс Wordslterator представляет собой простой итератор слов,
// на которые делит заданный текст стандартная функция С strtok.
// Словом считается любая последовательность символов, отделенная // от других слов разделителями: знаками препинания, пробелами и пр. //==============================================:======:==:==========:=
class WordsIterator { private :
char * words; // Для хранения и обработки исходного текста
char * nextWord; // Указатель на очередное слово
const char * delimeters; // Массив символов-разделителей
212
Глава 3
public :
U------------------------------------------------------------------
// Конструктор
//-----------------------------------------------------------------
WordsIterator(const char * phrase, // исходное предложение
const char * delim = \1\"\n\t\f") {
// Исходный текст сохраняется в буфере и обрабатывается // стандартной функцией strtok. words = new char[strlen(phrase)+1]; strcpy(words, phrase);
nextWord = strtok(words, delimeters = delim);
}
//-----------------------------------------------------------------
// Функция проверки наличия следующего слова
//-----------------------------------------------------------------
bool hasMoreElements () const { return nextWord != NULL; }
//-----------------------------------------------------------------
// Сдвиг итератора на слово вперед
//-----------------------------------------------------------------
Wordslterator & operator ++() {
nextWord = strtok(NULL, delimeters); return *this;
}
//-----------------------------------------------------------------
// Доступ к очередному слову
//-----------------------------------------------------------------
char * operator * () const { return nextWord; }
};
// Функция twice ищет в заданном предложении слово, встречающееся // более одного раза. Если такое слово есть - функция его выдает,
// если такого слова нет - функция выдает пустое слово //=——==—=—==—========================—=====================
string twice(const char * text) {
// Определяем словарь для исходного текста HashDictionary diet;
Обработка текстов
213
// Итератор слов текста будет считать разделителями пробелы,
// знаки препинания, кавычки, скобки и другие пустые символы for (Wordslterator iterator(text); iterator.hasMoreElements() ;
++iterator) {
// Выберем очередное слово и преобразуем его к нижнему регистру букв, string nextWord = strlwr(^iterator); if (diet.hasWord(nextWord)) {
return nextWord; // слово уже встречалось
} else {
diet.add(nextWord); // добавляем новое слово
}
}
return string(); // в предложении нет одинаковых слов
}
Например, следующий вызов этой функции:
cout « twice("It was many and many a year ago") « endl; приведет к тому, что будет напечатано слово many.
Вернемся еще раз к названиям функция расстановки и функция хеширования. Первое название отражает цель использования функции — вычисление некоторого индекса, с помощью которого можно расставить слова в словаре. Второе название отражает метод, с помощью которого этот индекс вычисляется— разрезание слова на части и перемешивание получившихся кусочков. Дословно глагол hash можно перевести с английского языка как "крошить", а в качестве существительного это слово можно перевести как ’’путаница”, ’’перефразирование” или даже "мясная окрошка”.
Надо сказать, что выбранный нами в вышеизложенном примере метод разрешения конфликтов при использовании функции расстановки не очень удобен. Во-первых, как уже было упомянуто, при большой загруженности словаря вся выгода, полученная от быстрого вычисления значения хеш-функции, может свестись на нет, и придется перебирать значительную часть слов в словаре как при линейном поиске. Во-вторых, если требуется не только добавлять, но и удалять слова из словаря, метод оказывается вовсе неприемлемым, поскольку дырки в словаре могут прервать поиск несмотря на то, что нужное слово все-таки в нем содержится. Ликвидация же дырок— крайне трудоемкий процесс.
Чаще используется другой метод разрешения конфликтов. Кроме основного массива, содержащего слова, в словаре организуется так называемая область переполнения, куда и помещаются все слова при возникновении конфликтов.
214
Гпава 3
Чаще всего область переполнения организуется в виде списков слов с одинаковым значением функции расстановки.
Еще одно важное замечание. Обычно требуется хранить слова не сами по себе, а связывать с этими словами некоторую информацию, например количество этих слов в тексте, или другую информацию, зависящую от задачи. Так, например, если в компиляторе требуется организовать словарь из всех используемых в тексте программы идентификаторов, то с каждым идентификатором можно связать информацию о его типе, локализации и т. д. Поэтому чаще всего словари (которые еще называют хеш-таблицами) содержат не просто слова, а пары, в которых с каждым словом связан некоторый дополнительный объект. В этом случае слово, по которому происходит поиск, называют ключом поиска, а соответствующий объект — значением, связанным с этим ключом. По смыслу операции поиска в хеш-таблице каждый ключ находится в таблице в единственном экземпляре, однако несколько разных ключей могут иметь одно и то же значение функции расстановки.
Предыдущая << 1 .. 68 69 70 71 72 73 < 74 > 75 76 77 78 79 80 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.