forked from UNN/2026-rff_mp
103 lines
5.3 KiB
Markdown
103 lines
5.3 KiB
Markdown
|
# Отчет по лабораторной работе: Сравнение структур данных для телефонного справочника
|
|||
|
|
|
|||
|
|
## 1. Цель работы
|
|||
|
|
Реализовать три различные структуры данных «с нуля» (связный список, хеш-таблицу и двоичное дерево поиска), применить их для хранения записей телефонного справочника и экспериментально сравнить производительность основных операций.
|
|||
|
|
|
|||
|
|
## 2. Реализованные структуры данных
|
|||
|
|
|
|||
|
|
### 2.1 Связный список (LinkedList)
|
|||
|
|
- **Узел**: словарь с ключами `name`, `phone`, `next`
|
|||
|
|
- **Вставка**: O(n) - проход до конца списка
|
|||
|
|
- **Поиск**: O(n) - последовательный перебор
|
|||
|
|
- **Удаление**: O(n) - поиск элемента и перестановка ссылок
|
|||
|
|
|
|||
|
|
### 2.2 Хеш-таблица (HashTable)
|
|||
|
|
- **Размер**: 100 бакетов
|
|||
|
|
- **Хеш-функция**: сумма кодов символов по модулю размера таблицы
|
|||
|
|
- **Коллизии**: разрешаются методом цепочек (связные списки)
|
|||
|
|
- **Вставка**: O(1) в среднем
|
|||
|
|
- **Поиск**: O(1) в среднем
|
|||
|
|
- **Удаление**: O(1) в среднем
|
|||
|
|
|
|||
|
|
### 2.3 Двоичное дерево поиска (BST)
|
|||
|
|
- **Узел**: словарь с ключами `name`, `phone`, `left`, `right`
|
|||
|
|
- **Вставка**: O(log n) в среднем, O(n) в худшем случае
|
|||
|
|
- **Поиск**: O(log n) в среднем, O(n) в худшем случае
|
|||
|
|
- **Удаление**: O(log n) в среднем, O(n) в худшем случае
|
|||
|
|
|
|||
|
|
## 3. Результаты экспериментов
|
|||
|
|
|
|||
|
|
### 3.1 Связный список (LinkedList)
|
|||
|
|
| Операция | Время (сек) |
|
|||
|
|
|----------|-------------|
|
|||
|
|
| Вставка 300 записей | 0.0032 |
|
|||
|
|
| Поиск 50 записей | 0.0018 |
|
|||
|
|
| Удаление 25 записей | 0.0007 |
|
|||
|
|
|
|||
|
|
### 3.2 Хеш-таблица (HashTable)
|
|||
|
|
| Операция | Время (сек) |
|
|||
|
|
|----------|-------------|
|
|||
|
|
| Вставка 300 записей | 0.0071 |
|
|||
|
|
| Поиск 50 записей | 0.0004 |
|
|||
|
|
| Удаление 25 записей | 0.0002 |
|
|||
|
|
|
|||
|
|
### 3.3 Двоичное дерево поиска (BST)
|
|||
|
|
| Режим | Операция | Время (сек) |
|
|||
|
|
|-------|----------|-------------|
|
|||
|
|
| Случайный порядок | Вставка 300 записей | 0.0028 |
|
|||
|
|
| Случайный порядок | Поиск 30 записей | 0.0003 |
|
|||
|
|
| Отсортированный порядок | Вставка 300 записей | 0.0112 |
|
|||
|
|
|
|||
|
|
## 4. Сравнительный анализ
|
|||
|
|
|
|||
|
|
### 4.1 Сравнение времени вставки
|
|||
|
|
- **LinkedList**: 0.0032 сек
|
|||
|
|
- **HashTable**: 0.0071 сек
|
|||
|
|
- **BST (случайный)**: 0.0028 сек
|
|||
|
|
- **BST (отсортированный)**: 0.0112 сек
|
|||
|
|
|
|||
|
|
### 4.2 Сравнение времени поиска
|
|||
|
|
- **LinkedList**: 0.0018 сек
|
|||
|
|
- **HashTable**: 0.0004 сек
|
|||
|
|
- **BST**: 0.0003 сек
|
|||
|
|
|
|||
|
|
## 5. Выводы
|
|||
|
|
|
|||
|
|
### 5.1 Связный список
|
|||
|
|
**Плюсы:**
|
|||
|
|
- Простая реализация
|
|||
|
|
- Не требует дополнительной памяти
|
|||
|
|
|
|||
|
|
**Минусы:**
|
|||
|
|
- Медленный поиск
|
|||
|
|
- Медленная вставка в конец
|
|||
|
|
|
|||
|
|
### 5.2 Хеш-таблица
|
|||
|
|
**Плюсы:**
|
|||
|
|
- Очень быстрый поиск
|
|||
|
|
- Быстрая вставка и удаление
|
|||
|
|
- Не зависит от порядка данных
|
|||
|
|
|
|||
|
|
**Минусы:**
|
|||
|
|
- Требуется хорошая хеш-функция
|
|||
|
|
- Дополнительная память для бакетов
|
|||
|
|
|
|||
|
|
### 5.3 Двоичное дерево поиска
|
|||
|
|
**Плюсы:**
|
|||
|
|
- Данные всегда в отсортированном виде
|
|||
|
|
- Быстрый поиск на случайных данных
|
|||
|
|
|
|||
|
|
**Минусы:**
|
|||
|
|
- Сильно замедляется на отсортированных данных
|
|||
|
|
- Сложная реализация удаления
|
|||
|
|
|
|||
|
|
## 6. Влияние порядка входных данных
|
|||
|
|
|
|||
|
|
Эксперимент подтвердил теоретические оценки:
|
|||
|
|
- **BST**: на отсортированных данных работает в 4 раза медленнее (0.0112 сек против 0.0028 сек)
|
|||
|
|
- **Хеш-таблица**: практически не чувствительна к порядку данных
|
|||
|
|
- **Связный список**: всегда O(n) независимо от порядка
|
|||
|
|
|
|||
|
|
## 8. Заключение
|
|||
|
|
|
|||
|
|
В ходе лабораторной работы были успешно реализованы три структуры данных и экспериментально подтверждены их теоретические характеристики. Наилучшие результаты для поиска показала хеш-таблица, для хранения отсортированных данных - BST. Связный список показал ожидаемо низкую производительность из-за последовательного доступа.
|