Сортировка данных в бинарных файлах
Есть такая задачка:
Данные о треугольниках хранятся в бинарных файлах. Необходимо скопировать их в файлрезультат, упорядочивая по возрастанию/убыванию (в ОП все данные не загружать):
информация о треугольниках хранится в виде трех целых чисел (длины сторон треугольника). Считаем, что каждая тройка чисел образует треугольник;
сортировку осуществляем по площадям треугольников. В исходных файлах данные о треугольниках упорядочены по возрастанию/убыванию площадей;
количество исходных файлов заранее неизвестно – функции с переменным количеством параметров;
сортировка по возрастанию/убыванию – указатели на функции
В одном файле может храниться как один, так и несколько треугольников. Для их хранения используется массив структур, для определения его размера в конец записывается -1 для всех членов структуры. Структура выглядит следующим образом:
struct Triangle // структура для хранения длин сторон треугольника
{
int a;
int b;
int c;
};
Подскажите, как можно отсортировать данные в бинарных файлах, не загружая все данные в ОП. Используется язык C.
Ответы (1 шт):
Насколько я понял, речь всё-таки идёт о написании программы, а не об использовании существующих команд сортировки.
В условии задачи сказано, что исходные файлы уже отсортированы. Значит, необходимо выполнить не сортировку, а только лишь слияние, что гораздо проще.
Напишите функцию слияния с такой сигнатурой:
int merge(int left, int right, int out)
// left - файловый дескриптор левого входного файла
// right - файловый дескриптор правого входного файла
// out - файловый дескриптор выходного файла
Эта функция сливает два входных файла в один выходной. Алгоритм её работы абсолютно тривиальный - считываем по записи из каждого файла. Та запись, которая "больше" идёт в выходной. В том входном, из которого записали в выходной, считываем следующую. Если записи кончились в одном из входных - тупо копируем оставшиеся записи из другого файла.
Имея такую функцию легко пишем функцию main() - он представляет собой цикл перебора всех входных файлов. На первом шаге берём два первых входных и сливаем их в первый рабочий.
На втором и последующем шагах берём очередной входной и предшествующий рабочий и сливаем их в новый рабочий.
Процесс повторяется до тех пор, пока не слили последний входной с предпоследним рабочим. Результат этого слияния и будет результатом работы всей программы.
Читать файлы надо не по байтам или строкам, а по записям. Соответственно, открывать файлы нужно в двоичном режиме:
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
int left, right, out;
struct Triangle a;
size_t len;
left = open("Первый_файл", O_RDONLY);
right = open("Второй_файл", O_RDONLY);
out = open("wrk", O_WRONLY | O_CREAT);
len = read(left, &a, sizeof(a));
len = write(out, a, sizeof(a));