5. Варианты заданий

1. Разработать программу, реализующую следующие операции над полиномами: ввод, вывод, удаление, сложение полиномов.

2. Разработать программу, реализующую следующие операции над полиномами: ввод, вывод, удаление, сложение полиномов.

3. Разработка программы, обеспечивающей диалоговый способ задания последовательности операций над полиномами.

4. Разработать программу, реализующую организацию доступа к полиномам по имени

6. Контрольные вопросы.

1. Что такое полином?

2. Какие структуры данных удобно использовать для операций с полиномами?

3. Как динамически выделить и освободить память?

Лабораторная работа №4 Организация доступа в таблицах по имени

1. Цель работы

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

2. Теоретические сведения

Под таблицей следует понимать динамическую структуру данных, которая в каждый момент выполнения вычислений состоит из конечного набора элементов (записей); записи таблицы могут подразделяться на несколько полей; при этом количество и тип полей является одинаковыми для всех записей таблицы. Первое поле всех записей таблицы обычно называют ключом, поля записи без ключевого поля образуют тело записи. Например, задавая соответствие между идентификаторами переменных (именами) и их адресами в памяти ЭВМ, мы можем построить простейшую таблицу вида:

Имя	Адрес
Item	3745
…	…
Summ	3800

В этой таблице каждая строка-запись состоит из двух полей: поля ключа (имени) и поля тела записи (адреса).

Основные операции, выполняемые над таблицами:

• поиск записи (по одному или нескольким ключам);

• вставки записи (с контролем возможных повторений);

• удаления записи.

Операции вставки и удаления записей служат для формирования требуемого набора записей; операция поиска записи по ключу обеспечивает доступ по имени (ключу) к записям таблицы.

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

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

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

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

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

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

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

,

где

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

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

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

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

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

k = log₂N

3. Таблицы с вычисляемыми адресами

Иной возможный способ построения таблиц при большом количестве записей состоит в предварительном (перед непосредственным поиском по таблице) вычислении возможного месторасположения искомой записи. Данный метод предполагает наличие некоторой простой функции h(key), которая отображает множество имен на множество номеров строк таблицы. Эта функция называется функцией хеширования или расстановки; таблицы, получаемые при таком способе построения, называются таблицами с вычисляемыми адресами или перемешиваемыми таблицами.

Функции расстановки могут быть построены разными способами. Например, можно в качестве номера строки, в которой хранится или будет храниться при вставке некоторый ключ, взять код первого символа имени, либо сумму всех кодов символов ключа по модулю числа M, где M - длина таблицы (размер массива, отведенного для ее хранения).

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

1. Метод открытого перемешивания состоит в добавлении к вычисленному занятому номеру некоторого фиксированного смещения (повторное перемешивание):

Если новый адрес k₁ также является занятым, следует повторить процедуру повторного перемешивания до тех пор, пока не обнаружится свободная строка, либо таблица не будет исчерпана (если значения p и N являются взаимно-простыми, открытое перемешивание обеспечивает нахождение свободной строки массива).

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

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

,

где

? - коэффициент заполненности таблицы ( );

M- количество строк в массиве для хранения записей;

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

Следует отметить, что количество сравнений при поиске в перемешиваемых таблицах согласно приведенной формуле зависит не от количества записей в таблице, а от заполненности памяти, отведенной для размещения записей. Для примера, при заполненности массива на 75% (? = 0.75) количество сравнений равно 2.5.