Сортировка файлов естественным слиянием и сбалансированное многопутевое слияние.

ВВЕДЕНИЕ
АНАЛИЗ ПОСТАВЛЕННОЙ ЗАДАЧИ
МЕТОД РЕШЕНИЯ
ОПИСАНИЕ ПРОГРАММЫ
РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
РЕЗУЛЬТАТЫ РАЗРАБОТКИ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ

Сортировка файлов естественным слиянием и сбалансированное многопутевое слияние.

FILE *fp; /* указатель на файл */
char name[LNAME]; /* имя файла */
recType rec; /* последняя прочитанная запись */
int dummy; /* номер холостых проходов */
bool eof; /* флаг конца пробега end-of-file */
bool eor; /* флаг конца прохода end-of-run */
bool valid; /* верно, если запись - годная */
int fib; /* идеальное число Фибоначчи */
} tmpFileType;
static tmpFileType **file; /* массив информации о временных файлах */
static int nTmpFiles; /* количество временных файлов */
static char *ifName; /* имя входного файла */
static char *ofName; /* имя выходного файла */
static int level; /* уровень проходов */
static int nNodes; /* количество узлов для дерева выбора */
void deleteTmpFiles(void) {
int i;
/* удалить сливаемые файлы и освободить ресурсы */
if (file) {
for (i = 0; i < nTmpFiles; i++) {
if (file[i]) {
if (file[i]->fp)
fclose(file[i]->fp);
if (*file[i]->name) remove(file[i]->name);
free (file[i]);
}
}
free (file);
}
}
/* Записать сортировки в выходной файл result.txt*/
void outputFile() {
FILE * output = fopen(ofName, "rb");
FILE * outputData = fopen("result.txt", "w+");

rewind(outputData);
rewind(output);
recType oneRec;
while (!feof(output)) {

if (fread(&oneRec, sizeof(recType), 1,output) != 1) {
perror("io6");
} else {
fprintf (outputData,"%d ",oneRec.key);

}
}

fclose (outputData);
}
void termTmpFiles(int rc) {
/* очистить файлы */
remove(ofName);
if (rc == 0) {
int fileT;
/* file[T] содержит результаты */
fileT = nTmpFiles - 1;
fclose(file[fileT]->fp); file[fileT]->fp = NULL;
if (rename(file[fileT]->name, ofName)) {
perror("io1");
deleteTmpFiles();
exit(1);
}

outputFile();
*file[fileT]->name = 0;
}
//deleteTmpFiles();
}
void cleanExit(int rc) {
/* очистить временные файлы и выйти */
termTmpFiles(rc);
exit(rc);
}
void *safeMalloc(size_t size) {
void *p;
/* Безопасно выделить память и инициализоваться */
if ((p = calloc(1, size)) == NULL) {
printf("error: malloc failed, size = %d\n", size);
cleanExit(1);
}
return p;
}
void initTmpFiles(void) {
int i;
tmpFileType *fileInfo;
/* инициализовать файлы для слияния */
if (nTmpFiles < 3) nTmpFiles = 3;
file = (tmpFileType**)safeMalloc(nTmpFiles * sizeof(tmpFileType*));
fileInfo = (tmpFileType*)safeMalloc(nTmpFiles * sizeof(tmpFileType));
for (i = 0; i < nTmpFiles; i++) {
file[i] = fileInfo + i;
sprintf(file[i]->name, FNAME, i);
if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
perror("io2");
cleanExit(1);
}
}
}
recType *readRec(void) {
typedef struct eNodeTag { /* внешний узел */
struct iNodeTag *parent;/* предок внешнего узла */
recType rec; /* вводимая запись */
int run; /* номер прохода */
bool valid; /* вводимая запись годна */
} eNodeType;
typedef struct iNodeTag { /* внутренний узел */
struct iNodeTag *parent;/* предок внутреннего узла */
struct eNodeTag *loser; /* внешний проигравший */
} iNodeType;

typedef struct nodeTag {
iNodeType i; /* внутренний узел */
eNodeType e; /* внешний узел */
} nodeType;
static nodeType *node; /* массив узлов дерева выбора */
static eNodeType *win; /* новый победитель */
static FILE *ifp; /* входной файл */
static bool eof; /* верно, если конец входного файла */
static int maxRun; /* максимальное число проходов */
static int curRun; /* номер текущего прохода */
iNodeType *p; /* указатель на внутренние узлы */
static bool lastKeyValid; /* верно, если lastKey годен */
static keyType lastKey; /* последний ключ lastKey записан */
/* Прочитать следующую запись путем выбора с замещением */
/* Проверка на первый выхов */
if (node == NULL) {
int i;
if (nNodes < 2) nNodes = 2;
node =(nodeType*) safeMalloc(nNodes * sizeof(nodeType));
for (i = 0; i < nNodes; i++) {
node[i].i.loser = &node[i].e;
node[i].i.parent = &node[i/2].i;
node[i].e.parent =(::iNodeTag*) &node[(nNodes + i)/2].i;
node[i].e.run = 0;
node[i].e.valid = false;
}
win = &node[0].e;
lastKeyValid = false;
if ((ifp = fopen(ifName, "rb")) == NULL) {
printf("error: file %s, unable to open\n", ifName);
cleanExit(1);
}

}


while (1) {
/* заместить предыдущего победителя новой записью */
if (!eof) {
int op1;
/*Читаем входной файл */
if ( fscanf(ifp,"%u", &op1)!= EOF ) {
win->rec.key = op1;
if ((!lastKeyValid || compLT(win->rec.key, lastKey))
&& (++win->run > maxRun))
maxRun = win->run;
win->valid = true;
} else if (feof(ifp)) {
fclose(ifp);
eof = true;
win->valid = false;
win->run = maxRun + 1;
} else {
perror("io4");
cleanExit(1);
}
} else {
win->valid = false;
win->run = maxRun + 1;
}
/* привести в порядок предков победителя и проигравшего */
p = (iNodeTag*)win->parent;

do {
bool swap;
swap = false;
if (p->loser->run < win->run) {
swap = true;
} else if (p->loser->run == win->run) {
if (p->loser->valid && win->valid) {
if (compLT(p->loser->rec.key, win->rec.key))
swap = true;
} else {
swap = true;
}
}
if (swap) {
/* p должно быть победителем */
eNodeType *t;
t = p->loser;
p->loser = win;
win = t;
}
p = p->parent;
} while (p != &node[0].i);
/* конец прохода ? */
if (win->run != curRun) {
/* win->run = curRun + 1 */
if (win->run > maxRun) {
/* конец вывода */
free(node);
return NULL;
}
curRun = win->run;
}
/* вывести верх дерева */
if (win->run) {
lastKey = win->rec.key;
lastKeyValid = true;
return &win->rec;
}
}
}
void makeRuns(void) {
recType *win; /* победитель */
int fileT; /* прошлый файл */
int fileP; /* следующий за прошлым файлом */
int j; /* выбираем file[j] */
/* Сделать инициализационные проходы через выбор с замещением.
* Проходы напианы с использованием распределения Фибоначчи.
*/
/* инициализовать файловые структуры */
fileT = nTmpFiles - 1;
fileP = fileT - 1;
for (j = 0; j < fileT; j++) {
file[j]->fib = 1;
file[j]->dummy = 1;
}
file[fileT]->fib = 0;
file[fileT]->dummy = 0;
level = 1;
j = 0;
win = readRec();
while (win) {
bool anyrun;
anyrun = false;
for (j = 0; win && j <= fileP; j++) {
bool run;
run = false;
if (file[j]->valid) {
if (!compLT(win->key, file[j]->rec.key)) {
/* добавить к существующему проходу */
run = true;
} else if (file[j]->dummy) {
/* начать новый проход */
file[j]->dummy--;
run = true;
}
} else {
/* первый проход в файле */
file[j]->dummy--;
run = true;
}
if (run) {
anyrun = true;
/* полный проход */
while(1) {
if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
perror("io3");
cleanExit(1);
}
file[j]->rec.key = win->key;
file[j]->valid = true;
if ((win = readRec()) == NULL) break;
if (compLT(win->key, file[j]->rec.key)) break;
}
}
}
/* Если нет места для проходов - вверх на уровень */
if (!anyrun) {
int t;