![]() |
Как реализовать многофазную сортировку на С++ ?
|
Для 3-х ыайлов и чисел Фибоначи первого порядка:
#include <stdio.h> #include <stdlib.h> void sl (FILE *fn1, FILE *fn2, FILE *fn3, char *max) { // функция слияния int ch1,ch2,tmp,tml,m,n; // используемые переменные FILE *temp; #define read_a if (!feof(fn1)) fscanf(fn1,"%d",&ch1); else ch1=-1; #define read_b if (!feof(fn2)) fscanf(fn2,"%d",&ch2); else ch2=-1; while (!feof(fn1)) { // пока не достигнем конца файла read_a; if(!feof(fn1)) read_b; // считываем первые элементы серий while (ch1>=0 && ch2>=0) { // пока серия не кончилась if (ch1<ch2) { fprintf(fn3,"%5d",ch1); read_a;} // записываем текущий элемент изфайлф fn1 и считываем следующий else { fprintf(fn3,"%5d",ch2); read_b;} // записываем текущий элемент изфайлф fn2 и считываем следующий } if (ch1<0 && !feof(fn1)) while (ch2>=0) { fprintf(fn3,"%5d",ch2); read_b; } // если серия файла fn2 еще не кончилась, дописываем оставшиеся элементы if (ch2<0) { while (ch1>=0) { fprintf(fn3,"%5d",ch1); read_a; } // если серия файла fn1 еще не кончилась, дописываем оставшиеся элементы if (!feof(fn1)) fprintf(fn3,"%5d\n",-1); } } fclose(fn1); fclose(fn3); temp=fopen("temp.txt","w"); while (fscanf(fn2,"%d",&tml)!=EOF) fprintf(temp,"%5d",tml); fclose(fn2);fclose(temp); fn2=fopen(max,"w"); temp=fopen("temp.txt","r"); while (fscanf(temp,"%d",&tmp)!=EOF) { fprintf(fn2,"%5d",tmp); if(tmp==-1) fprintf(fn2,"\n"); } fclose(fn2);fclose(temp); remove("temp.txt"); } void sort (char *fname) { // функция сортировки int i,j,k,a1,a2,a,b,l,h,h1,h2,h3; // используемые переменные FILE *file,*f1,*f2,*f3; // испоьзуемые файлы file=fopen(fname,"r"); // открывафем исходный файл f1=fopen("tmp1.txt","w"); // создаем временный файл j=0; k=0; // минимальный элемент и кол-во серий while (fscanf(file,"%d",&i)!=EOF) { // перебираем все элементы файла if (i<j) {fprintf(f1,"%5d\n",-1); // если серия закончилась k++; } // число серий fprintf(f1,"%5d",j=i); } // записываем число во временный файл fcloseall(); // закрываем все файлы a1=0; a2=1; // первые числа Фибоначи a=a1+a2; // след. число while (a<k) { // превышает число серий a1=a2; a2=a; a=a1+a2; } // вычисление послед. чисел b=a-k; // кол-во пустых серий f1=fopen("tmp1.txt","a+"); // for (l=1; l<=b; l++) // fprintf(f1,"%5d\n",-1); // добавляем фиктивные серии fclose(f1); l=0; // закрываем все файлы f1=fopen("tmp1.txt","r"); // f2=fopen("tmp2.txt","w"); // открываем файлы f3=fopen("tmp3.txt","w"); // while (l<a1) { // записываем во 2-ой файл fscanf(f1,"%d",&i); // кол-во серий if (i==-1) { // удовлетв. первому l++; // из чисел Фибоначи fprintf (f2,"%5d\n",i); } // (меньшему) else fprintf (f2,"%5d",i); } // while (l<a) { // записываем в 3-ий файл fscanf(f1,"%d",&i); // кол-во серий if (i==-1) { // удовлетв. второму из l++; // чисел Фибоначи fprintf (f3,"%5d\n",i); } // (большему) else fprintf (f3,"%5d",i); } // fcloseall(); // закрываем все файлы while ((!feof(f1) && !feof(f2)) || (!feof(f1) && !feof(f3)) || (!feof(f2) && !feof(f3))) { fseek(f1,-5,1);fseek(f2,-5,1);fseek(f3,-5,1); fcloseall(); f1=fopen("tmp1.txt","w"); // для 1-го, 4-го, 7-го и т.д. прохода f2=fopen("tmp2.txt","r"); f3=fopen("tmp3.txt","r"); sl(f2,f3,f1,"tmp3.txt"); fcloseall(); f1=fopen("tmp1.txt","r"); // для 2-го, 5-го, 8-го и т.д. прохода f2=fopen("tmp2.txt","w"); f3=fopen("tmp3.txt","r"); sl(f3,f1,f2,"tmp1.txt"); fcloseall(); f1=fopen("tmp1.txt","r"); fscanf(f1,"%5d",&h); if (feof(f1)) { f3=fopen("tmp3.txt","w"); fclose(f3); fclose(f1); } else { fseek(f1,-5,1); // для 3-го, 6-го, 9-го и т.д. прохода f2=fopen("tmp2.txt","r"); f3=fopen("tmp3.txt","w"); sl(f1,f2,f3,"tmp2.txt"); fcloseall(); } fcloseall(); f1=fopen("tmp1.txt","r"); f2=fopen("tmp2.txt","r"); f3=fopen("tmp3.txt","r"); fscanf(f1,"%5d",&h1); fscanf(f2,"%5d",&h2); fscanf(f3,"%5d",&h3); } if (!feof(f1)){ // если последняя серия в первом файле f1=fopen("tmp1.txt","r"); // file=fopen(fname,"w"); // while(fscanf(f1,"%d",&i)!=EOF) // fprintf(file,"%5d\n",i); } // записываем серию в исходный файл if (!feof(f2)){ // если последняя серия во втором файле f2=fopen("tmp2.txt","r"); // file=fopen(fname,"w"); // while(fscanf(f2,"%d",&i)!=EOF) // fprintf(file,"%5d\n",i); } // записываем серию в исходный файл if (!feof(f3)){ // если последняя серия в третьем файле f1=fopen("tmp3.txt","r"); // file=fopen(fname,"w"); // while(fscanf(f3,"%d",&i)!=EOF) // fprintf(file,"%5d\n",i); } // записываем серию в исходный файл fcloseall(); // закрываем все файлы remove("tmp1.txt");remove("tmp2.txt");remove("tmp3.txt"); // удаляем временные файлы } void main () { // основная программа int i; // используемые переменные FILE *f; // используемые файлы randomize(); // инициализируем генератор случайных чисел // ***** Заполняем файл случайными перестановками ***** f=fopen("file.txt","w"); // создаем новый файл for (i=0; i<100; i++) fprintf(f,"%5d",random(100)); // заполняем его случайными числами fclose(f); // закрываем созданный файл sort("file.txt"); // сортируем файл } |
Время: 09:12. |
Время: 09:12.
© OSzone.net 2001-