Подскажите, как отсортировать структуры в бинарном файле не используя буфер.
-
В смысле, читая их по одной и не храня в памяти, или что?– bipll20 мая 2018 в 14:17
-
Не совсем, у меня есть одна перемененная в которой хранится новая запись, и вторая переменная которую записываем структуру– user29734120 мая 2018 в 14:19
-
я понимаю что надо использовать fseek– user29734120 мая 2018 в 14:20
-
Ну то есть за O(1) пространства, как ни крути.– bipll20 мая 2018 в 14:20
-
Суть задания добавить новую структуру не нарушив упорядоченности(они отсортированы лексикографически). Сложность возникла в том как сместить все остальные записи после того как я добавил новую– user29734120 мая 2018 в 14:27
1 ответ
Ну да, fseek, чтобы можно было читать и писать по произвольному адресу.
По идее, сгодится любой in-place-алгоритм (bubble sort, insertion sort, даже quicksort или heapsort можно 0_o), только вместо ОЗУ структуры хранятся в файле.
Например, insertion.
Читаем текущую структуру по адресу n (то есть начиная с байта
n * sizeof(Struct)
, n >= 0).Сдвигаем file pointer на размер сруктуры влево и читаем предыдущую, по адресу n - 1. Если она не больше текущей, оставляем все как есть. Если больше — записываем по адресу n и сдвигаемся вправо, на адрес n - 2. Когда мы дошли до структуры по адресу k - 1, которая не больше текущей, записываем текущую по адресу k.
Повторить для следующей, по адресу n + 1, и далее, пока файл не кончится.
-
Спасибо, сейчас попробую реализовать– user29734120 мая 2018 в 14:42
-
Получилось, спасибо за помощь)– user29734120 мая 2018 в 16:27
-