Учебно-методические цели работы

Таблицы являются одними из наиболее распространенных структур данных, используемых при создании системного и прикладного математического обеспечения. Таблицы широко применяются в трансляторах (таблицы идентификаторов) и операционных системах, могут рассматриваться как программная реализация схемы ассоциативной памяти и т.п. Выполнение работы ориентировано на достижение следующих учебно-методических целей:

• знакомство с проблематикой и методами организации доступа по имени;

• развитие практических навыков по созданию структур хранения для динамических структур данных (на примере таблиц);

• изучение и практическое освоение методов поиска в таблицах с различными типами организации данных.

2. Рекомендации по выполнению работы 1.Понятие таблицы 2.Анализ способов организации таблииц.

Анализ способов организации таблиц.

Способ построения таблицы должен приводить к быстрому выполнению табличных операций. В зависимости от способов размещения записей в таблице возможно использование различных методов выполнения операций обработки таблиц. Эффективность применяемых способов организации может быть оценена, например, в количестве просматриваемых записей таблицы при выполнении операций поиска, вставки и удаления.

Далее в описании лабораторной работы следует характеристика основных способов построения таблиц. Рассматриваемые способы имеют разные показатели по эффективности; для всех перечисленных способов могут быть выделены области приложений, в которых рекомендуемые способы являются наиболее целесообразными.

1. Просматриваемые таблицы

Простейшим способом отыскания нужного элемента является метод полного просмотра (сканирования), когда искомый ключ сравнивается по очереди со всеми ключами таблицы, начиная с первого, вплоть до отыскания совпадающего элемента или до исчерпания записей. Если ключи в таблице расположены в произвольном порядке (неупорядоченная таблица), этот способ является единственно возможным.

Операция вставки в неупорядоченную таблицу может быть выполнена путем добавления новой записи в конец таблицы с корректировкой номера последней занятой строки. Операция удаления строки может быть реализована при помощи переписывания последней записи таблицы на место удаляемой и соответствующей корректировки номера последней строки.

Среднее количество просматриваемых записей таблицы при поиске записи по ключу при предположении равной вероятности использования ключей определяется следующим соотношением

k = pN/2 + (1-p)N, (1)

где

p- вероятность того, что искомая запись имеется в таблице;

N- количество записей в таблице.

2. Упорядоченные таблицы

При большом количестве записей в таблице (N>>1) затраты на выполнение полного просмотра становятся значительными. Эффективность процедуры поиска можно повысить при размещении записей в таблице в порядке возрастания (или убывания) ключей (упорядоченная, или сортированная таблица). Для поиска нужной записи в таких таблицах может быть использован быстрый метод бинарного (двоичного) поиска. Вместе с тем, в упорядоченных таблицах усложняется реализация операций вставки и удаления записей, при выполнении которых для сохранения упорядоченности становится необходимой перепаковка записей таблицы.

Среднее количество просматриваемых записей таблицы при использовании бинарного поиска определяется как

k = log2N. (2)