<< Пред. стр. 9 (из 19) След. >>
Список литературы по разделу
Основная трудность, связанная с преобразованием ключей, заключается в том, что множество возможных значений значительно шире множества допустимых адресов памяти (индексов массива). Возьмем в качестве примера имена, включающие до 16 букв и представляющие собой ключи, идентифицирующие отдельные индивиды из множества в тысячу персон. Следовательно, мы имеем дело с 2616 возможными ключами, которые нужно отобразить в 103 возможных индексов. Поэтому функция Н будет функцией класса «много значений в одно значение». Если дан некоторый ключ k, то первый шаг операции поиска — вычисление связанного с ним индекса h = H(k), а второй (совершенно необходимый) — проверка, действительно ли h идентифицирует в массиве (таблице) Т элемент с ключом k.
7.1. Выбор функции преобразования
Само собой разумеется, что любая хорошая функция преобразования должна как можно равномернее распределять ключи по всему диапазону значений индекса. Если это требование удовлетворяется, то других ограничений уже нет, и даже хорошо, если преобразование будет выглядеть как совершенно случайное. Такая особенность объясняет несколько ненаучное название этого метода — «перемалывание» (хеширование), т. е. дробление аргумента, превращение его в какое-то «месиво». Функция же Н будет называться «функцией расстановки». Ясно, что Н должно вычисляться достаточно эффективно, т. е. состоять из очень небольшого числа основных арифметических операций.
Представим себе, что есть функция преобразования ORD(k), обозначающая порядковый номер ключа k в множестве всех возможных ключей. Кроме того, будем считать, что индекс массива i лежит в диапазоне 0 ... N — 1, где N — размер массива. В этом случае ясно, что нужно выбрать следующую функцию:
H(k) = ORD(k) MOD N
Для нее характерно равномерное отображение значений ключа на весь диапазон изменения индексов, поэтому ее кладут в основу большинства преобразований ключей. Кроме того, при N, равном степени двух, эта функция эффективно вычисляется. Однако если ключ представляет собой последовательность букв, то именно от такой функции и следует отказаться. Дело в том, что в этом случае допущение о равновероятности всех ключей ошибочно. В результате слова, отличающиеся только несколькими символами, с большой вероятностью будут отображаться в один и тот же индекс, что приведет к очень неравномерному распределению. Поэтому на практике рекомендуется в качестве N брать простое число. Следствием такого выбора будет необходимость использования полной операции деления, которую уже нельзя заменить выделением нескольких двоичных цифр.
7.2. Алгоритм
Если обнаруживается, что строка таблицы, соответствующая заданному ключу, не содержит желаемого элемента, то, значит, произошел конфликт, т. е. два элемента имеют такие ключи, которые отображаются в один и тот же индекс. В этой ситуации нужна вторая попытка с индексом, вполне определенным образом получаемым из того же заданного ключа. Существует несколько методов формирования вторичного индекса. Очевидный прием — связывать вместе все строки с идентичным первичным индексом H(k). Превращая их в связанный список. Такой прием называется прямым связыванием (direct chaining). Элементы получающегося списка могут либо помещаться в основную таблицу, либо нет; в этом случае память, где они размещаются, обычно называется областью переполнения. Недостаток такого приема в том, что нужно следить за такими вторичными списками и в каждой строке отводить место для ссылки (или индекса) на соответствующий список конфликтующих элементов.
Другой прием разрешения конфликтов состоит в том, что мы совсем отказываемся от ссылок и вместо этого просматриваем другие строки той же таблицы — до тех пор, пока не обнаружим желаемый элемент или же пустую строку. В последнем случае мы считаем, что указанного ключа в таблице нет. Такой прием называется открытой адресацией. Естественно, что во второй попытке последовательность индексов должна быть всегда одной и той же для любого заданного ключа. В этом случае алгоритм просмотра строится по такой схеме:
h = H(k)
i = 0
repeat
if T(h) = k
then элемент найден
else if T(h) = free
then элемента в таблице нет
else {конфликт}
i := i + 1
h := H(k) + G(i)
endif
endif
until либо найден, либо нет в таблице (либо она полна)
Предлагались самые разные функции G(i) для разрешения конфликтов. Приведенный в работе Морриса (1968) обзор стимулировал активную деятельность в этом направлении. Самый простой прием — посмотреть следующую строку таблицы (будем считать ее круговой), и так до тех пор, пока либо будет найден элемент с указанным ключом, либо встретится пустая строка. Следовательно, в этом случае G(i)==i, а индексы hi, употребляемые при последующих попытках, таковы:
h0 := H(k)
hi := (hi + i) MOD N, i = 1 … N - 1
Такой прием называется линейными пробами, его недостаток заключается в том, что строки имеют тенденцию группироваться вокруг первичных ключей (т. е. ключей, для которых при включении конфликта не возникало). Конечно, хотелось бы выбрать такую функцию G, которая вновь равномерно рассеивала бы ключи по оставшимся строкам. Однако на практике это приводит к слишком большим затратам, потому предпочтительнее некоторые компромиссные методы; будучи достаточно простыми с точки зрения вычислений, они все же лучше линейной функции. Один из них — использование квадратичной функции, в этом случае последовательность пробуемых индексов такова:
h0 := H(k)
hi := (hi + i2) MOD N, i > 0
Если воспользоваться рекуррентными соотношениями для hi = i2 и di = 2i + l при h0 = 0 и d0 = l, то при вычислении очередного индекса можно обойтись без операции возведения в квадрат.
hi+1 = hi + di
di+1 = di + 2 (i > 0)
Такой прием называется квадратичными пробами, существенно, что он позволяет избежать группирования, присущего линейным пробам, не приводя практически к дополнительным вычислениям. Небольшой же его недостаток заключается в том, что при поиске пробуются не все строки таблицы, т. е. при включении элемента может не найтись свободного места, хотя на самом деле оно есть. Если размер N — простое число, то при квадратичных пробах просматривается по крайней мере половина таблицы. Такое утверждение можно вывести из следующих рассуждений. Если i-я и j-я пробы приводят к одной и той же строке таблицы, то справедливо равенство
i2 MOD N = j2 MOD N
или
( i2 – j2 ) = 0 ( MOD N )
Разлагая разность на два множителя, получаем
( i + j )( i - j ) = 0 ( MOD N )
Поскольку i ? j, то либо i, либо j должны быть больше N/2, чтобы было справедливо равенство i + j = cN, где с — некоторое целое число. На практике упомянутый недостаток не столь существен, так как N/2 вторичных попыток при разрешении конфликтов встречаются очень редко, главным образом в тех случаях, когда таблица почти заполнена.
Контрольные вопросы
1. Для чего предназначен метод расстановок ?
2. От чего зависит положение элемента в массива в методе расстановок ?
3. Какую функцию возможно использовать в качестве хэш-функции:
4. Что называется конфликтом ?
5. Какой из методов является методом разрешения конфликтов.
6. Какой из методов разрешения конфликтов позволяет более равномерно распределить элементы по массиву.
7. Почему невозможно применять в качестве H(k) функцию Trunc(sqrt(k5- i*tan(k))) MOD N ?
ЧАСТЬ 2.
ПРАКТИКУМ ПО СРУКТУРАМ И АЛГОРИТМАМ ОБРАБОТКИ ДАННЫХ В ЭВМ
МЕТОДИЧЕСКОЕ РУКОВОДСТВО К ЛАБОРАТОРНЫМ РАБОТАМ
Организационно-методические указания
1. Перед началом лабораторной работы проводится консультация по методике выполнения лабораторных работ по данной дисциплине.
2. Объем каждой лабораторной работы, подготовка и порядок выполнения построены таким образом, чтобы все студенты выполнили работу и сдали отчеты.
3. Студенты готовятся к выполнению очередной работы заблаговременно.
4. Студенты обязаны изучить технику безопасности при работе на лабораторных установках до 1000 В.
5. Готовясь к лабораторному занятию, студент обязан изучить необходимый теоретический материал, пользуясь настоящими указаниями и рекомендованной литературой, произвести необходимые расчеты, заполнить соответствующую часть отчета и дать ответы на контрольные вопросы.
6. Неподготовленные студенты к выполнению лабораторной работы не допускаются.
7. Студенты, не сдавшие отчет во время занятия, сдают его в назначенное преподавателем время.
8. Студент, не выполнивший лабораторную работу, выполняет ее в согласованное с преподавателем время.
9. Каждая лабораторная работа выполняется студентами самостоятельно. Все студенты предъявляют индивидуальные отчеты. Допускается предъявление отчета в виде электронного документа.
10. Проверка знаний студентов производится преподавателем во время лабораторного занятия и при сдаче отчета.
11. При сдаче отчета студент должен показать знание теоретического материала в объеме, определяемом контрольными вопросами, а также пониманием физической сущности выполняемой работы.
Лабораторная работа № 1. "ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ"
Цель работы: исследовать и изучить стеки.
Задача работы: овладеть навыками написания программ по исследованию стеков на языке программирования ПАСКАЛЬ .
Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.
Краткая теория
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание: выбить чек на нужную сумму в кассе магазина, получить нужную информацию в справочном бюро, выполнить очередную операцию по обработке детали на данном станке в автоматической линии и т.д.
В программировании имеется структура данных, которая называется очередь. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик (средняя длина очереди, время пребывания заказа в очереди и т.п.) при данном законе поступления заказов и дисциплине их обслуживания.
По своему существу очередь является полустатической структурой - с течением времени и длина очереди, и набор образующих ее элементов могут изменяться.
Различают два основных вида очередей, отличающихся по дисциплине обслуживания находящихся в них элементов :
1. При первой из дисциплин заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Эту дисциплину обслуживания принято называть FIFO (First input-First output, т.е. первый пришел - первый ушел). Очередь открыта с обеих сторон.
2. Вторую дисциплину принято называть LIFO (Last input - First output, т.е. последний пришел - первый ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Очередь такого вида в программировании принято называть СТЕКОМ (магазином) - это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется ВЕРШИНОЙ стека - эта позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Алгоритм
ОПЕРАЦИИ НАД СТЕКАМИ:
- PUSH ( s , i ) - занесение элемента в стек, где s - название стека, i - элемент, который заносится в стек;
- POP ( s ) - выборка элемента из стека. При выборке элемент помещается в рабочую область памяти, где он используется;
- EMPTY ( s ) - проверка стека на пустоту (true - пуст, false - не пуст);
- STACKTOP ( s ) - чтение верхнего элемента без его удаления.
Фрагмент программы создания стека (необходимые процедуры)
Program STACK;
const
max_st=50;
const
max_st=50;
var
st,st2: array[1..max_st] of integer;
n:integer;
function empty:boolean; {Проверка стека на наличие элементов в нем}
begin
empty:=n=0
end;
procedure push(a:char); {Поместить элемент в стек}
begin
inc(n);
st[n]:=a;
end;
procedure pop(var a:char); {Извлечь элемент из стека}
begin
a:=st[n];
dec(n);
end;
function full:boolean; {Проверка на переполнение}
begin
Full:=n=max_st
end;
procedure stacktop(var a:char); {Узнать верхний элемент}
begin
a:=st[n];
end;
begin {Основная программа}
.
.
end.
Задания
* Ввести символы, формируя из них стек.
Варианты :
1.Поменять местами первый и последний элементы стека.
2.Развернуть стек, т.е. "дно" стека сделать вершиной, а вершину - "дном".
3.Удалить элемент, который находится в середине стека, если нечетное число элементов, а если четное, то два средних.
4.Удалить каждый второй элемент стека.
5.Вставить символ '*' в середину стека, если четное число элементов, а если нечетное, то после среднего элемента.
6.Найти минимальный элемент и вставить после него 0.
7.Найти максимальный элемент и вставить после него 0.
8.Удалить минимальный элемент.
9.Удалить все элементы, равные первому.
10.Удалить все элементы, равные последнему.
11.Удалить максимальный элемент.
12.Найти минимальный элемент и вставить на его место 0.
* Вывести полученный стек на экран.
* Распечатать полученный стек.
Лабораторная работа № 2. "СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ"
Цель работы: исследовать и изучить списковые структуры данных.
Задача работы: овладеть навыками написания программ по исследованию списковых структур на языке программирования ПАСКАЛЬ .
Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.
Краткая теория
До сих пор мы рассматривали только статические программные объекты. Этим термином обозначаются объекты, которые порождаются непосредственно перед выполнением программы, существуют в течение всего времени ее выполнения и размер значений которых не изменяется по ходу выполнения программы.
Поскольку статические объекты порождаются до выполнения программы и размер их значений можно выделить еще на этапе трансляции исходного текста программы на языке машины.
Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы, а такая эффективность бывает чрезвычайно важной при решении ряда задач. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но даже и того, будет существовать этот объект или нет. Такого рода программные объекты , которые возникают уже в процессе выполнения программы, называют динамическими объектами.
В языке ПАСКАЛЬ для работы с динамическими объектами предусматривается специальный тип данных - так называемый ссылочный тип. Значением этого типа является ссылка на какой - либо программный объект, по которой осуществляется непосредственный доступ к этому объекту. На машинном языке такая ссылка как раз и представляется указанием места в памяти соответствующего объекта.
В этом случае для описания действий над динамическими объектами каждому такому объекту в программе сопоставляется статическая переменная ссылочного типа - в терминах этих ссылочных переменных и описываются действия над соответствующими динамическими объектами.
Итак, динамические структуры данных имеют две особенности :
1. Заранее не определимо количество элементов в структуре;
2. Элементы динамической структуры не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.
Чтобы связать элементы динамической структуры между собой, в состав элемента помимо информационного поля входят поля указателей (связок с другими элементами структуры) .
p1, p2 - указатели, содержащие адреса элементов, с которыми данный элемент связан.
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки. В линейных списках связи строго упорядочены. Указатель предыдущего элемента дает адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки.
К нелинейным - многосвязные списки.
Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.
Линейные однонаправленные списки
Под односвязными списками понимают упорядоченную последовательность элементов, каждый из которых имеет 2 поля : информационное поле info и поле указателя ptr .
Особенностью указателя является то, что он дает только адрес последующего элемента списка. У однонаправленных списков поле указателя последнего элемента в списке является пустым nil.
Lst - указатель начала списка. Он представляет список как единое целое. Иногда список может быть пустым, т.е. в данном списке нет ни одного элемента. В этом случае lst = nil.
Алгоритм
Операции с односвязными списками.
1. Вставка элемента в начало односвязного списка.
Вставим в начало данного списка элемент, информационное поле которого содержит переменную D. Чтобы это осуществить, необходимо произвести следующие действия :
а) Создать пустой элемент, на который указывает указатель p.
b) Информационному полю созданного элемента присвоить значение D.
с) Связать новый элемент со списком.
Ptr(p)=lst (lst - уже не указывает на начало списка)
d) Перенести указатель lst на начало списка.
Окончательно:
Удаление элемента из начала односвязного списка
Удалим 1-й элемент списка, но при этом запомним информацию содержащиеся в поле info этого элемента.
Чтобы это осуществить, необходимо произвести следующие действия :
a) Ввести указатель р, который будет указывать на удаляемый элемент.
P=lst
b) Запомнить поле info элемента, на который ссылается указатель р, в некоторую переменную (х).
X=info( P )
c) Перенести указатель lst на новое начало списка.
lst=ptr( P )
d) Удалить элемент на который указывает указатель р.
Freenode( P )
Окончательно:
Вставка элемента в список
Вставим в данный список перед элементом на который указывает указатель р, элемент с информационным полем х.
<< Пред. стр. 9 (из 19) След. >>
Список литературы по разделу