0

Подскажите, как отсортировать структуры в бинарном файле не используя буфер.

6
  • В смысле, читая их по одной и не храня в памяти, или что?
    – bipll
    20 мая 2018 в 14:17
  • Не совсем, у меня есть одна перемененная в которой хранится новая запись, и вторая переменная которую записываем структуру
    – user297341
    20 мая 2018 в 14:19
  • я понимаю что надо использовать fseek
    – user297341
    20 мая 2018 в 14:20
  • Ну то есть за O(1) пространства, как ни крути.
    – bipll
    20 мая 2018 в 14:20
  • Суть задания добавить новую структуру не нарушив упорядоченности(они отсортированы лексикографически). Сложность возникла в том как сместить все остальные записи после того как я добавил новую
    – user297341
    20 мая 2018 в 14:27

1 ответ 1

1

Ну да, fseek, чтобы можно было читать и писать по произвольному адресу.

По идее, сгодится любой in-place-алгоритм (bubble sort, insertion sort, даже quicksort или heapsort можно 0_o), только вместо ОЗУ структуры хранятся в файле.

Например, insertion.

  1. Читаем текущую структуру по адресу n (то есть начиная с байта n * sizeof(Struct), n >= 0).

  2. Сдвигаем file pointer на размер сруктуры влево и читаем предыдущую, по адресу n - 1. Если она не больше текущей, оставляем все как есть. Если больше — записываем по адресу n и сдвигаемся вправо, на адрес n - 2. Когда мы дошли до структуры по адресу k - 1, которая не больше текущей, записываем текущую по адресу k.

  3. Повторить для следующей, по адресу n + 1, и далее, пока файл не кончится.

3
  • Спасибо, сейчас попробую реализовать
    – user297341
    20 мая 2018 в 14:42
  • Получилось, спасибо за помощь)
    – user297341
    20 мая 2018 в 16:27
  • Пожалуйста. :-)
    – bipll
    20 мая 2018 в 16:28

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.