2011-09-24 11 views
0

Я делаю слияние k-отсортированных потоков, используя системные вызовы write write.Дескрипторы файлов и системные вызовы

После того, как вы прочитали первые целые числа из файлов и отсортировали их, снова нужно получить файл с наименьшим элементом. Я не уверен, как это сделать. Я думал, что могу использовать структуру вроде:

struct filePointer { 
int ptr; 
int num; 
}fptr[5]; 

Может кто-нибудь сказать мне, как это сделать.

Благодаря

ответ

1

Хотя чтение целые числа один за другим не является эффективным способом сделать это, я буду стараться писать решение, которое вы ищете. однако это не реальная реализация, просто идея.

Ваша структура должна выглядеть так:

struct filePointer { 
FILE * fp; 
int num; 
} fptr[k]; /* I assume k is constant, known at compile time */ 

Вы должны иметь очереди приоритета (http://en.wikipedia.org/wiki/Priority_queue) и prioities определяются accourding к NUM.

Сначала прочитайте первые числа из всех файлов и вставьте их в очередь приоритетов (pq).

Затем, пока pq не пуст, поместите первый элемент, который содержит наименьшее целое число по сравнению с другими элементами в pq.

Напишите целое число, которое первый элемент хранит в файле.

Использование указателя файла (fp) пытается прочитать новое целое из входного файла.

Если EOF (конец файла), то ничего не делать

еще вставить новый элемент в PQ, установив Num для считывания одного.

Когда цикл закончен, закройте все файлы, и у вас будет новый файл, содержащий все элементы из входных файлов, и он будет отсортирован.

Надеюсь, это поможет.

Смежные вопросы