Для многих задач одной из основных проблем является поиск фрагмента или фрагментов информации в больших томах ранее сохраненных данных.
Для поисковых задач данные обычно организуются в ассоциативные множества, элементами которых как правило являются записи, каждая из которых имеет ключ, уникальноидентифицирующий данные во множестве. Поиск данных организуется по этому уникальному ключу. Целью поиска является предоставление доступа пользователю к данным, имеющим заданный ключ. Это может быть отдельный экземпляр данных или группа данных.
Обычно такое множество организуется в структуру, называемую таблицей (таблицей символов, словарем).
Сэджвик дает следующее определение таблицы символов:
Таблица символов- это структура элементов данных с ключами, которая поддерживает две операции- вставку нового элемента и возврат элемента с заданным ключом. Кроме этих основных операций таблица поддерживает операции удаления элементов, изменения элементов, выбор К-го по величине элемента, сортировку элементов в форме отображения всех элементов в порядке их ключей, объединения таблиц.
Таблицу можно определить как абстрактный тип данных, образующий ассоциативные множества с этим набором операций.
Если данные, включаемые в таблицу, имеют нестандартный тип, то для того чтобы включать их в таблицу необходимо для этого типа определить операции запроса ключа, проверки на равенство по ключам, операции >,< по ключам, операции проверки на наличие данных (аналогично особому значению NULL для адресных указателей).
В качестве признака отсутствия данных может быть использован элемент множества с заранее предопределенным ключевым значением, которое не могут иметь элементы с реальными данными.
При разработке таблицы важно решить вопрос о возможности включения элементов с одинаковыми ключами. Некоторые приложения не допускают наличия дублированных ключей, например, база, хранящая сведения о налогоплательщиках, в которой каждый налогоплательщик идентифицируется уникальным идентификационным номером налогоплательщика (ИНН). Наоборот, в других приложениях предполагается множество элементов с одинаковым ключом, например поиск по ключевому слову всех возможных сайтов.
Хранение элементов с одинаковыми ключами можно организовать различными способами. Например, выделить главную таблицу, элементы которой содержат только ключ и ссылку на список данных с этим ключом.
Можно содержать элементы с одинаковыми ключами в главной структуре и при поиске сообщать первый найденный элемент. Но в этом случае этот элемент будет перекрывать доступ к остальным элементам.
Можно усложнить запрос на поиск и задавать дополнительный параметр- номер элемента или вторичный уникальный ключ.
Можно ввести операцию поиска от метки, когда поиск ведется от точки, в которой завершился предыдущий поиск, или поиск ближайшего соседа.
Но все эти усовершенствования усложняют операции над таблицей и замедляют работу со структурой.
Реализация таблицы и набор алгоритмов операций часто зависят от относительной частоты операции поиска, вставки и удаления. Можно выбрать реализацию, обеспечивающую быстрый поиск за счет замедления операции вставки и удаления, либо наоборот
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
