Приложение д Алгоритмы операций для хеш-таблицы с открытой адресацией Алгоритм вставки элемента

Hash_Insert (T, k, data)

1. T[{state, key, data}] – массив хеш-таблицы

2. state[T[j]] – состояние ячейки таблицы (free / busy / deleted)

3. key[T[j]] – ключ поиска элемента таблицы

4. data[T[j]] – данные элемента таблицы

5. i← 0

6. pos ← -1

7. repeat j ← h(k, i)

8. if state[T[j]] = deleted

9. then pos ← j

10. if key[T[j]] = k

11. then return FALSE

12. i ← i+1

13. until i = m or state[T[j]] = free

14. if i = m and pos = -1

15. then return FALSE

16. if pos = -1

17. then pos ← i

18. key[T[pos]] ← key

19. data[T[pos]] ← data

20. state[T[j]] ← busy

21. return TRUE

Алгоритм удаления элемента

Hash_Delete (T, k)

1. T[{state, key, data}] – массив хеш-таблицы

2. state[T[j]] – состояние ячейки таблицы (free / busy / deleted)

3. key[T[j]] – ключ поиска элемента таблицы

4. data[T[j]] – данные элемента таблицы

5. i← 0

6. repeat j← h(k, i)

7. if key[T[j]] = k

8. then state[T[j]] ← deleted

9. return TRUE

10. i← i + 1

11. until state[T[j]] = free или i=m

12. return FALSE

Алгоритм поиска элемента

Hash_Search (T, k)

1. T[{state, key, data}] – массив хеш-таблицы

2. state[T[j]] – состояние ячейки таблицы (free / busy / deleted)

3. key[T[j]] – ключ поиска элемента таблицы

4. data[T[j]] – данные элемента таблицы

5. i← 0

6. repeat j← h(k, i)

7. if key[T[j]] = k

8. then return data[T[j]]

9. i← i + 1

10. until state[T[j]] = free или i=m

11. return nil

ОГЛАВЛЕНИЕ

Введение 3

1. Технология проектирования и реализации коллекций данных. 3

1.1. Постановка задачи. 4

1.2. Разработка структур данных и алгоритмов 7

1.3. Кодирование 15

1.4. Отладка и тестирование 20

1.5. Сопровождение 23

2. Лабораторная работа «Сортировка коллекции» 27

2.1. Алгоритмы внутренней сортировки 27

2.2. Задание к лабораторной работе 34

2.3. Контрольные вопросы и упражнения. 37

3. Лабораторная работа «Коллекция данных - список». 39

3.1. Структуры списков 39

3.2. Задание к лабораторной работе 44

3.3. Контрольные вопросы и упражнения. 47

4. Лабораторная работа «Коллекция данных - дерево поиска». 49

4.1. Структуры BST - деревьев 51

4.2. Задание к лабораторной работе 53

4.3. Контрольные вопросы и упражнения. 57

5. Лабораторная работа «Коллекция данных - сбалансированное дерево поиска» 59

5.1. Структуры сбалансированных деревьев 59

5.2. Задание к лабораторной работе 65

5.3. Контрольные вопросы и упражнения. 69

6. Лабораторная работа «Коллекция данных - хеш – таблица» 71

6.1. Функции хеширования 72

6.2. Разрешение коллизий и структуры хеш-таблиц 74

6.3. Трудоёмкость операций 78

6.4. Задание к лабораторной работе 79

6.5. Контрольные вопросы и упражнения. 84

Литература 85

Приложение A: 86

Псевдокод. Основные правила и соглашения псевдокода 86

Приложение Б: 88

Алгоритмы внутренней сортировки. 88

Приложение В 98

Алгоритмы операций для BST – дерева 98

Приложение Г 110

Алгоритмы операций для сбалансированных деревьев. 110

Приложение Д 129

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

132