Лабораторная: Внешняя сортировка через битовый массив

Задание 1.1

Описание подхода к решению

Определение структуры записи файла

Размер записи в байтах можно определить с помощью оператора sizeof

Организация прямого доступа к записям в бинарном файле

Алгоритмы, которые реализуются в форме функций

Код программы

Пример тестирования программы отображен на рисунке 1

Задание 1.2

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

Алгоритм линейного поиска записи в файле можно представить в виде следующего псевдокода

Код функции линейного поиска выглядит следующим образом

Полный код программы с функцией линейного поиска выглядит следующим образом

Результат тестирования программы для 100 записей

Результаты с замерами времени поиска записи по заданному ключу для файла из 100 и 1000 записей

Задание 1.3

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

Описание алгоритма доступа к записи в файле посредством таблицы

Алгоритм поиска записи с указанным ключом в файле может быть представлен в виде следующего псевдокода

Код функции поиска записи в файле выглядит следующим образом

Полный код программы с реализацией поиска записи в бинарном файле

Результат тестирования программы для 100 записей

Результаты замеров времени поиска записи по заданному ключу для файла из 100 и 10000 записей

Анализ эффективности рассмотренных алгоритмов поиска в файле



Задание 1.а: Реализуйте вышеприведённый пример, проверьте правильность результата в том числе и на других значениях х.

Задание 1.б: Реализуйте по аналогии с предыдущим примером установку 7-го бита числа в единицу.

Задание 1.в: Реализуйте код листинга 1, объясните выводимый программой результат.

Задание 2.а: Реализуйте вышеописанный пример с вводом произвольного набора до 8-ми чисел (со значениями от 0 до 7) и его сортировкой битовым массивом в виде числа типа unsigned char. Проверьте работу программы.

Задание 2.а: Адаптируйте вышеприведённый пример для набора из 64-х чисел (со значениями от 0 до 63) с битовым массивом в виде числа типа unsigned long long.

Задание 2.в: Исправьте программу задания 2.б, чтобы для сортировки набора из 64-х чисел использовалось не одно число типа unsigned long long, а линейный массив чисел типа unsigned char.

Задание 3.а: Реализуйте задачу сортировки числового файла с заданными условиями. Добавьте в код возможность определения времени работы программы.

Задание 3.б: Определите программно объём оперативной памяти, занимаемый битовым массивом.



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

Ход работы:
a. Формулировка задачи
b. Математическая модель решения (описание алгоритма)
c. Код программы с комментариями
d. Результаты тестирования


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

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

Подсчет количества вхождений данной подстроки в тексте с использованием эффективного алгоритма Рабина-Карпа.Показать/скрыть дополнительное описание