Структуры и алгоритмы обработки данных

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ

 

Для студентов специальности

1-40 01 01 Программное обеспечение информационных технологий

 

 

Минск 2010

 

 

СОДЕРЖАНИЕ

 

ОБЩИЕ СВЕДЕНИЯ.. 4

Сведения об ЭУМК.. 4

Методические рекомендации по изучению дисциплины.. 4

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА.. 6

ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ.. 15

Лекция 1. 15

1.1 Типы данных, абстрактные типы и структуры данных. 15

1. 2 Классификация структур данных. 16

1.3 Представление типов данных и операции над ними в языке Pascal 18

1.4     Указатели. 22

Лекция 2. 24

2.1. Открытое хеширование. 25

2.2. Закрытое хеширование. 26

2.3. Алгоритмы работы с хеш-таблицами методами открытой адресации. 29

Лекция 3. 33

3.1 Полустатические и динамические структуры данных. 33

3.2 Абстрактный тип данных «список». 34

3.3 Сравнение различных реализаций списков. 36

3.4 Дважды связные списки. 37

Лекция 4. 38

4.1 Абстрактный тип данных «очередь». 39

4.2 Реализация очереди с помощью указателей. 39

4.3. Разновидности очередей. 41

4.4 Абстрактный тип данных «стек». 43

4.5 Реализация стеков с помощью массивов. 43

Лекция 5. 45

5.1 Итерационный вычислительный процесс. 45

5.2 Рекурсивный вычислительный процесс. 46

5.3 Реализация рекурсивного вычислительного процесса. 47

Лекция 6. 48

6.1 Различные формы записи выражений. 48

6.2 Построение выражений в обратной польской записи. 49

6.3 Преобразование скобочных выражений в обратную польскую запись. 51

Лекция 7. 54

7.1 Нелинейные структуры. Деревья. 54

7.2 Обходы дерева. 56

Лекция 8. 58

8.1 Бинарное дерево. Построение бинарного дерева. 58

8.2 Помеченные деревья и деревья выражения. 60

8.3 Реализация деревьев. 62

Лекция 9. 65

9.1 Представление списков в виде БД.. 65

9.2 Прошитые БД.. 66

Лекция 10. 69

10.1 Применение деревьев. Представление сообщений кодами Хаффмана. 69

Лекции 11-12. 74

11.1 Идеально сбалансированные бинарные деревья. 74

11.2 Бинарные деревья поиска. 75

11.3 Сбалансированные деревья поиска. 77

11.4 Операции над деревьями. 77

11.5 Вставка элемента в АВЛ-дерево. 78

Лекция 13. 83

13.1 Основные определения ориентированных графов. 83

13.2 Представление ориентированных графов. 84

13.3 Операторы над ориентированными графами. 86

13.4 Нахождение кратчайшего пути на ориентированном графе. 87

13.5 Нахождение кратчайших путей между парами вершин. 89

Лекция 14. 91

14.1 Транзитивное замыкание. 91

14.2 Нахождение центра ориентированного графа. 92

14.3 Обход ориентированных графов. 93

14.4 Глубинный остовный лес. 95

Лекция 15. 96

15.1 Модель внешних вычислений. 96

15.2 Особенности операций с внешней памятью.. 97

15.3 Организация данных в файлах. 98

15.4 Хешированные файлы.. 99

15.5 Индексированные файлы.. 100

15.6 Несортированные файлы с плотным индексом. 102

Лекция 16. 102

16.1 Внешние деревья поиска. 102

16.2 В-деревья. 103

16.3 Операторы на В-дереве. 104

16.4 Сравнение методов. 106

ПРАКТИЧЕСКИЙ РАЗДЕЛ.. 108

Контрольная работа № 1. 108

Контрольная работа №2. 108

ИНДИВИДУАЛЬНЫЕ ПРАКТИЧЕСКИЕ РАБОТЫ.. 109

Индивидуальная практическая работа №1. 110

Индивидуальная практическая работа №2. 110

 

ОБЩИЕ СВЕДЕНИЯ

Сведения об ЭУМК

Электронный учебно-методический комплекс по дисциплине (ЭУМКД) «Структуры и алгоритмы обработки данных» (СиАОД) предназначен для студентов вузов специальности «Программное обеспечение информационных технологий» (ПОИТ) всех форм обучения, а также может быть использован преподавателями, аспирантами и практическими работниками предприятий.

Электронный учебно-методический комплекс составлен на основе рабочей учебной программы по курсу СиАОД, утверждённой деканом факультета непрерывного и дистанционного обучения                , регистрационный          № УД              /Р и рабочего учебного плана специальности 1-40 01 01 «Программное обеспечение информационных технологий».

Составитель:

Л.В. Серебряная, доцент кафедры программного обеспечения информационных технологий Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники», кандидат технических наук.

Рассмотрен и рекомендован к изданию на заседании кафедры программного обеспечения информационных технологий, протокол №   28 от 31.05.2010 г.

Одобрен и рекомендован к изданию методической комиссией факультета компьютерных систем и сетей, протокол №  16 от 14.06.2010 г.

 

Методические рекомендации по изучению дисциплины

В соответствии с учебным планом студенты дистанционной формы обучения специальности ПОИТ изучают курс  СиАОД.

Учебным планом по данному курсу предусмотрено изучение теоретических вопросов, выполнение двух лабораторных заданий и двух контрольных работ по наиболее актуальным темам дисциплины. Изучение курса завершается  сдачей зачета. К зачету студенты допускаются только при условии выполненных и защищенных лабораторных и контрольных работ.

Рекомендуется изучать курс СиАОД в соответствии с рабочей программой. Сначала необходимо ознакомиться с содержанием курса, затем изучить теоретический материал по разделам ЭУМКД, используя рекомендуемую литературу. Получив теоретические знания по дисциплине, студенты могут приступать к выполнению индивидуальных практических и контрольных работ, используя указанную учебно-методическую и научную литературу. При подготовке к зачету студентам рекомендуется  ответить на контрольные вопросы, включенные в данный ЭУМКД (вопросы_СиАОД.doc).

Весь теоретический материал излагается в строгой логической последовательности, поэтому при изучении дисциплины рекомендуется придерживаться предложенной здесь последовательности. Изучение курса СиАОД опирается на знания по высшей и дискретной математике, основам алгоритмизации и программирования, а также структурам и алгоритмам обработки данных.

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

Учреждение образования

«Белорусский государственный университет

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

Целью изучения дисциплины является получение студентами теоретических сведений и практических навыков по выбору и разработке конкретных структур данных для представления объектов разработки и преобразования их из одной формы в другую.

В результате изучения курса «Структуры и алгоритмы обработки данных» студенты должны

знать:

- основные методы построения статических и динамических структур данных;

- основные алгоритмы обработки статических и динамических структур данных;

- языки программирования для эффективной организации данных в различных приложениях;

- перспективы развития теории проектирования эффективных структур данных при использовании различных языков программирования;

Уметь характеризовать:

- основные типы структур данных: табличные, списковые, древовидные, сетевые, файловые, а также основные алгоритмы обработки структур: пополнение, удаление, модификация, поиск, упорядочение;

Уметь анализировать:

- эффективность алгоритмов обработки структур данных различных типов;

приобрести навыки:

- в проектировании эффективных структур данных;

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

Программа рассчитана на объем 88 учебных часов, из них 50 – аудиторных. Примерное распределение учебных часов по видам занятий: лекций – 34 часа, практических работ – 16 часов. 

 

 

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

 

№ п.п.п.	Название и содержание тем (по типовой или учебной программе)	Контрольная работа (номер и тема по п.2)		Индивидуальные практические работы (по п.1)		Оснащение контрольных и индивидуальных работ (по п.4)	Литература (по п.3)				Рекомендуемый объ-ем для изучения (в часах)	Форма контроля знаний (зачет по контрольной работе, защита индивидуальной работы, зачет)
Раздел 1. Основные приемы работы с информацией
11.	Тема 1. Представление информации в памяти. Введение. Цели и задачи курса. Адресация памяти. Адресное пространство, базирование, смещение						3.1.1. 3.2.1.				4
22	Тема 2. Базовые структуры данных. Примитивные структуры данных и основные операции над ними: создать, уничтожить, выбрать, обновить.						3.1.1- 3.1.3				6
33	Тема 3. Типы данных и их хранение. Целые и действительные числа. Символьная информация. Логическая информация. Указатели.						3.1.1- 3.1.2, 3.2.3				6

Итого

 

88

Зачет                            

 

УЧЕБНО-МЕТОДИЧЕСКАЯ ЛИТЕРАТУРА

 

3.1. ОСНОВНАЯ

 

3.1.1.   Й. Лэнгсам, М. Огенстайн, А. Тененбаум, Структуры данных для персональных ЭВМ.– М.: Мир, 1989.

3.1.2. А.В. Ахо,   Структуры данных и алгоритмы.– М.: Вильямc. – 2000. 

3.1.3. К. Вирт, Алгоритмы + Структуры данных = Программы – М.: Вильямc. – 2002.

3.1.4. М. Кормен,   Алгоритмы, построение и анализ. 2-изд.– М.: Мир. – 2005.

 

3.2 ДОПОЛНИТЕЛЬНАЯ

 

3.2.1    Д. Кинг, Создание эффективного ПО.– М.: Мир. – 1991.

3.2.2. Л. Кнут,   Искусство программирования. T. 1. 3-изд.– М.: Вильямс. – 2001.

3.2.3. О. Седжвик, Фундаментальные алгоритмы на C++. – М.: Вильямc. – 2001. 

 

 

УЧЕБНО-МЕТОДИЧЕСКИХ ПОСОБИЙ

   4.1. Процессор Pentium IV или более мощный; операционная система Microsoft Windows 2000, Microsoft Windows XP; язык программирования Borland Pascal.

4.2. Учебно-методическое пособие Мариной И.М. «Структуры и алгоритмы организация данных ЭВМ» для студентов специальности ПОИТ.

 

 

         

С ДРУГИМИ ДИСЦИПЛИНАМИ СПЕЦИАЛЬНОСТИ

 

Название дисциплины, c которой требуется согласование	Кафедра, обеспечивающая изучение этой дисциплины	Предложения об изменениях в содержании учебной программы по изучаемой дисциплине	Решение, принятое кафедрой, разработавшей учебную программу (с указанием даты и номера протокола)
1	2	3	4
Методы и алгоритмы принятия решений	ПОИТ	Нет
Языки программирования	ПОИТ	Нет
Операционные системы и системное программирование	ПОИТ	Нет

 

 

Зав. кафедрой ПОИТ                                                                    Бахтизин В.В.               

 

ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

   Лекция 1

План лекции:

1. Типы данных, абстрактные типы и структуры данных.

2. Классификация структур данных.

3. Представление типов данных и операции над ними в языке Pascal.

4. Указатели и работа с ними в языке Pascal.

 

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

 

Указатели

 

Указатель представляет собой адрес ячейки памяти. При решении прикладных задач с использованием языков высокого уровня наиболее частые случаи, когда могут понадобиться указатели, следующие:

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

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

Физическая структура указателей. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. Например, в процессоре i8086 эффективный адрес имеет размер 20 двоичных разрядов, что позволяет адресовать до 1 Мбайт памяти. При этом он состоит из двух частей: сегмента и смещения. В микропроцессоре i386 обе компоненты адреса 32-разрядные; в процессорах семейства S/390 адрес представляется в виде 31-разрядного смещения в одном из 19 адресных пространств; в процессоре Power PC 620 одним 64-разрядным словом может адресоваться вся как оперативная, так и внешняя память.

Все без исключения модели современных процессоров аппаратно выполняют динамическую трансляцию адресов и совместно с операционными системами обеспечивают работу программ в виртуальной памяти. Программа разрабатывается и выполняется в некоторой виртуальной памяти, адреса в которой линейно изменяются от 0 до некоторого максимального значения. Виртуальный адрес представляет собой число – номер ячейки в виртуальном адресном пространстве. Преобразование виртуального адреса в реальный выполняется аппаратно при каждом обращении по виртуальному адресу. Это преобразование происходит совершенно прозрачно для программиста, поэтому структуру виртуального адреса можно считать и его же физической структурой. Виртуальный адрес представляет собой целое число без знака. Большинство современных систем обеспечивают 32-разрядный адрес, позволяющий адресовать до 4 Гбайт памяти, однако активно внедряются системы с 64-разрядными адресами.

В программе на языке высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Например, объявления в языке Pascal:

 

Var ipt: ^ integer; cpt: ^ char;

 

означают, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt – адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, компилятор считает указатели ipt и cpt, имеющими разный тип, и в Pascal оператор:

 

cpt:= ipt;

 

будет расценен компилятором как ошибочный. Таким образом, когда речь идет об указателях типизированных, правильнее говорить не о едином типе данных «указатель», а о целом семействе типов: «указатель на целое», «указатель на символ» и т.д. Могут быть указатели и на более сложные, интегрированные структуры данных,  а также указатели на указатели.

Нетипизированный указатель (тип pointer в Pascal) служит для представления адреса, по которому содержатся данные неизвестного типа.

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

Присваивание является двухместной операцией, оба операнда которой – указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя – типизированные, то они оба должны указывать на объекты одного и того же типа.

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

Операция выборки – одноместная, ее операндом является типизированный указатель, результат – данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

Перечисленных операций, как правило, достаточно для решения задач прикладного программирования, поэтому набор операций над указателями, допустимых в языке Pascal, этим и ограничивается.

К указателю можно прибавить целое число или вычесть из него целое число. Поскольку память имеет линейную структуру, прибавление к адресу числа даст адрес области памяти, смещенной на это число байт (или других единиц измерения) относительно исходного адреса. Результат операций «указатель + целое», «указатель – целое» имеет тип «указатель».

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

Необходимо отметить, что сложение указателей не имеет смысла. Поскольку программа разрабатывается в относительных адресах и при разных своих выполнениях может размещаться в разных областях памяти, сумма двух адресов в программе будет давать разные результаты при разных выполнениях. Смещение же объектов внутри программы относительно друг друга не зависит от адреса загрузки программы, поэтому результат операции вычитания указателей будет постоянным, и такая операция является допустимой.

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная ipt определена как указатель на целое число (int *ipt), то выражение ipt+ 1 даст адрес, больший не на 1, а на количество байт в целом числе. Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

Лекция 2

План лекции:

1. Открытое хеширование данных.

2. Закрытое хеширование данных.

3. Алгоритмы работы с хеш-таблицами методами открытой адресации.

 

На сегодняшний день существует множество способов повышения эффективности работы с большими объемами информации. Например, для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей. При этом могут быть использованы методы поиска в упорядоченных структурах данных, что существенно сокращает время поиска данных по значению ключа. Однако при добавлении новой записи требуется переупорядочить таблицу. Потери времени на повторное упорядочивание справочника часто превышают выигрыш от сокращения времени поиска. Рассмотрим способы организации данных, лишенные указанного недостатка. Это – различные формы хеширования данных.

 

Открытое хеширование

На рис. 3 показана базовая структура данных при открытом хешировании. Основная идея метода заключается в том, что множество данных (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В-1, строится хеш-функция h такая, что для любого элемента x исходного множества функция h(x) принимает целочисленное значение из интервала 0, …, В-1, которое соответствует классу, которому принадлежит элемент x. Элемент x называют ключом, h(x) – хеш-значением х, а классы – сегментами. Массив (таблица сегментов), проиндексированный номерами сегментов 0, 1, … В-1, содержит заголовки для В списков. Элемент х i -го списка – это элемент исходного множества, для которого h(x)= i.

Если сегменты приблизительно равны по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/ B элементов. Если удается оценить величину N и выбрать B как можно ближе к этой величине, то в каждом списке будет один-два элемента. Тогда время выполнения операций с данными будет малой постоянной величиной, зависящей от N или от В. Однако не всегда ясно, как выбрать хеш-функцию h так, чтобы она примерно поровну распределяла элементы исходного множества по всем сегментам.

 

 

Рис. 3 – Организация данных при открытом хешировании

 

Идеальной хеш-функцией является такая, которая для любых двух неодинаковых ключей выдает неодинаковые адреса, т.е.

 

 

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

Рассмотрим хеш-функцию, определенную на символьных строках, которая не является совершенной, однако значения h(x) будут «хорошими» (Пример 1).

 

Пример 1. Хеш-функция, определенная на символьных строках.

 

 

Закрытое хеширование

 

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

Рассмотрим пример заполнения хеш-таблицы в случае закрытого хеширования (рис. 4).  

Рис. 4 – Частично заполненная хеш-таблица

 

Здесь В=8 и ключи a, b, c, d имеют хеш-значения h(a)=3, h(b)=0, h(c)=4, h(d)=3. Для добавления в таблицу элемента d применим методику линейного хеширования, когда  Тогда, если сегмент 3 уже занят, то проверяются на занятость сегменты 4, 5, 6, 7, 0, 1, 2 (именно в таком порядке). 5-ый сегмент оказался первым пустым сегментом, поэтому элемент d был вставлен в него

При поиске элемента х необходимо просмотреть все адреса  пока не будет найден х, или пока не встретится пустой сегмент. Покажем это, введя условие, что в словаре не допускается удаление элементов. Пусть  – первый пустой сегмент. В такой ситуации невозможно нахождение элемента х в сегментах  и далее, т.к. х вставляется в первый свободный сегмент, следовательно, он находится до сегмента .

При заполнении таблицы могут возникать коллизии, для борьбы с которыми разработаны специальные методы, которые в основном сводятся к методам "цепочек" и "открытой адресации". Ключи, выдающие одинаковые адреса в таблице, называются ключи-синонимы.

В методе цепочек для разрешения коллизий во все записи вводятся указатели, используемые для организации списков – "цепочек переполнения". В случае возникновения коллизии при заполнении таблицы в список для требуемого адреса хеш-таблицы добавляется еще один элемент.

Поиск в хеш-таблице с цепочками переполнения осуществляется следующим образом. Сначала вычисляется адрес по значению ключа. Затем осуществляется последовательный поиск в списке, связанном с вычисленным адресом. Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения. На рис. 5 показана схема разрешения коллизий методом цепочек при добавлении элемента.

Рис. 5 –  Разрешение коллизий при добавлении элементов

 

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

Линейное опробование сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом

a=h(key) + c* i,

где i – номер попытки разрешить коллизию. При шаге равном единице происходит последовательный перебор всех элементов после текущего.

Квадратичное опробование отличается от линейного тем, что шаг перебора элементов нелинейно зависит от номера попытки найти свободный элемент

a = h(key2) + c* i + d* i ² .

Благодаря нелинейности такой адресации уменьшается число проб при большом числе ключей-синонимов. Однако даже относительно небольшое число проб может быстро привести к выходу за адресное пространство небольшой таблицы вследствие квадратичной зависимости адреса от номера попытки. На рис. 6 показано разрешение коллизий методом открытой адресации.

Рис. 6 –  Разрешение коллизий при добавлении элементов методами

открытой адресации

 

2.3. Алгоритмы работы с хеш-таблицами методами открытой адресации

 

Опишем алгоритмы вставки и поиска элементов для метода линейного опробования.

Вставка

i = 0

a = h(key) + i*c

Если t(a) = свободно, то t(a) = key, записать элемент, стоп элемент добавлен

i = i + 1, перейти к шагу 2

Поиск

i = 0

a = h(key) + i*c

Если t(a) = key, то стоп элемент найден

Если t(a) = свободно, то стоп элемент не найден

i = i + 1, перейти к шагу 2

 

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

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

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

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

Существует подход, который свободен от перечисленных недостатков. Его суть состоит в том, что для элементов хеш-таблицы добавляется состояние удалено. Данное состояние в процессе поиска интерпретируется как занято, а в процессе записи как свободно.

Рассмотрим алгоритмы вставки, поиска и удаления для хеш-таблицы, имеющей три состояния элементов.

Вставка

i = 0

a = h(key) + i*c

Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

i = i + 1, перейти к шагу 2

Удаление

i = 0

a = h(key) + i*c

Если t(a) = key, то t(a) =удалено, стоп элемент удален

Если t(a) = свободно, то стоп элемент не найден

i = i + 1, перейти к шагу 2

Поиск

i = 0

a = h(key) + i*c

Если t(a) = key, то стоп элемент найден

Если t(a) = свободно, то стоп элемент не найден

i = i + 1, перейти к шагу 2

 

Алгоритм поиска для хеш-таблицы, имеющей три состояния, практически не отличается от алгоритма поиска без учета удалений. Разница заключается в том, что при организации самой таблицы необходимо отмечать свободные и удаленные элементы. Это можно сделать, зарезервировав два значения ключевого поля. Другой вариант реализации может предусматривать введение дополнительного поля, в котором фиксируется состояние элемента. Длина такого поля может составлять всего два бита, что вполне достаточно для фиксации одного из трех состояний. На языке TurboPascal данное поле удобно описать типом Byte или Char.

Очевидно, что по мере заполнения хеш-таблицы будут происходить коллизии, и в результате их разрешения методами открытой адресации очередной адрес может выйти за пределы адресного пространства таблицы. Чтобы это явление происходило реже, можно пойти на увеличение длины таблицы по сравнению с диапазоном адресов, выдаваемым хеш-функцией. С одной стороны это приведет к сокращению числа коллизий и ускорению работы с хеш-таблицей, а с другой – к нерациональному расходованию адресного пространства. Даже при увеличении длины таблицы в два раза по сравнению с областью значений хеш-функции нет гарантии того, что в результате коллизий адрес не превысит длину таблицы. При этом в начальной части таблицы может оставаться достаточно свободных элементов. Поэтому на практике используют циклический переход к началу таблицы.

Рассмотрим этот способ на примере метода линейного опробования. При вычислении адреса очередного элемента можно в качестве адреса взять остаток от целочисленного деления адреса на длину таблицы n.

Вставка

i = 0

a = (h(key) + c*i) mod n

Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

i = i + 1, перейти к шагу 2

 

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

Вставка

i = 0

a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

i = i + 1, перейти к шагу 2

a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

 

При большой заполненности таблицы возникают частые коллизии и циклические переходы в начало таблицы. При неудачном выборе хеш-функции происходят аналогичные явления. В наихудшем случае при 100% заполнении таблицы алгоритмы циклического поиска свободного места приведут к зацикливанию. Поэтому при использовании хеш-таблиц необходимо стараться избегать очень плотного заполнения таблиц. Обычно длину таблицы выбирают из расчета двукратного превышения предполагаемого максимального числа записей. Не всегда при организации хеширования можно правильно оценить требуемую длину таблицы, поэтому в случае большой заполненности таблицы может понадобиться рехеширование. В этом случае увеличивают длину таблицы, изменяют хеш-функцию и переупорядочивают данные.

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

Вставка

i = 0

a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

Если i > m, то стоп требуется рехеширование

i = i + 1, перейти к шагу 2

Удаление

i = 0

a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

Если t(a) = key, то t(a) =удалено, стоп элемент удален

Если t(a) = свободно или i>m, то стоп элемент не найден

i = i + 1, перейти к шагу 2

Поиск

i = 0

a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

Если t(a) = key, то стоп элемент найден

Если t(a) = свободно или i>m, то стоп элемент не найден

i = i + 1, перейти к шагу 2

 

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

Лекция 3

План лекции:

1. Полустатические и динамические структуры данных.

2. Абстрактный тип данных «список».

   3. Сравнение различных реализаций списков.

  4. Дважды связные списки.

 

Дважды связные списки

 

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

 

Рис. 10 – Дважды связный список

 

Важным преимуществом является то, что можно использовать указатель ячейки, содержащей i -й элемент, для определения i -й позиции вместо использования указателя предшествующей ячейки. Однако при этом появляются дополнительные указатели и, следовательно, удлиняются некоторые процедуры. Ниже приведен код объявления дважды связного списка.

      

  На рис. 11 приведены процедура и схема удаления элемента из дважды связного списка. Ниже приведена процедура удаления.

 

Рис. 11 – Удаление элемента из дважды связного списка

 

Здесь предполагается, что удаляемая ячейка не является ни первой, ни последней в списке. Сплошными линиями показаны указатели до удаления, а пунктирными – после удаления элемента. Сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой ячейки устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.

 

Лекция 4

План лекции:

1. Абстрактный тип данных «очередь».

2. Реализация очереди с помощью указателей.

   3. Разновидности очередей.

  4. Абстрактный тип данных «стек».

  5. Реализация стеков с помощью массивов.

 

Разновидности очередей