Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.06.2011, 01:08   #1
Troilk
Новичок
Джуниор
 
Регистрация: 15.03.2011
Сообщений: 2
Печаль Внешняя сортировка методом прямого слияния

Помогите исправить код.
Необходимо выполнить сортировку чисел в текстовом файле методом прямого слияния.Предполагается что объем файла может быть больше чем количество оперативной памяти,поэтому нельзя просто загонять числа в массив.
Числа в файле записываются по одному числу в строчке
Приведенный ниже код не работает.Например при сортировке файла 1 3 2 5 4 получается 1 2 3 5 5.В частности получается что на последней итерации нет ни единого прохождения по циклу сравнений и поэтому из результата выпадает 4

void DirectMerge(char fileName[20]) //прямое слияние
{
FILE* FTS; //файл который будет сортироваться
FILE *A,*B; //временные файлы
long int numKeys=0; //количество ключей (чисел) в файле
char temp1[30],temp2[30]; //текущие числа из каждого из временных файлов
FTS=fopen(fileName,"rt");
while(!feof(FTS)) //получение количества чисел в исходном файле
{
fgets(temp1,30,FTS);
numKeys++;
}
fclose(FTS);
long int iterator=1; //количество чисел в одной серии
while(iterator<numKeys) //пока количество чисел в серии меньше количества чисел
{
FTS=fopen(fileName,"rt");
A=fopen("a.txt","wt");
B=fopen("b.txt","wt");
for(int i=0;i<numKeys/2;i++) //считывание половины чисел в первый временный файл
{
fgets(temp1,30,FTS);
fputs(temp1,A);
}
if((numKeys/2)%iterator!=0) //если в считаное количество чисел не "влазит" целое число серий
{
int tmp=numKeys/2;
while(tmp%iterator!=0) //пока не будет "влазить" целое число серий
{
fgets(temp1,30,FTS);
fputs(temp1,A);
tmp++;
}
}
while(!feof(FTS)) //все остальное записать во второй временный файл
{
fgets(temp2,30,FTS);
fputs(temp2,B);
}
fclose(FTS);
fclose(A);
fclose(B);
FTS=fopen(fileName,"wt"); //закрытие файлов и переоткрытие в другом режиме
A=fopen("a.txt","rt");
B=fopen("b.txt","rt");
fgets(temp1,30,A); //получение 1 числа из 1 врем. файла
fgets(temp2,30,B); //получение 1 числа из 2 врем. файла
bool sh1=1,sh2=1;
while(!feof(A) && !feof(B)) //пока файлы не закончились
{
int iterA=0,iterB=0; //счетчики считаных чисел из каждого из файлов на текущей итерации
bool iterCon=1; //необходимость продолжения слияния серий
while(iterCon && !feof(A) && !feof(B))
{
if(atoi(temp1)<=atoi(temp2)) //сравнить числа
{
fputs(temp1,FTS); //записать в изначальный файл
sh1=1;
if(fgets(temp1,30,A)!=NULL) sh1=0;
iterA++; //увеличить количество чисел считаных их первого файла
} else
{
fputs(temp2,FTS);
sh2=1;
if(fgets(temp2,30,B)!=NULL) sh2=0;
iterB++;
}
if(iterA==iterator || iterB==iterator) iterCon=0; //если в файле было считано количество чисел
} //которые необходимо считать на данной итерации то закончить слияние серий
if(!iterCon) //если в одном из файлов еще не дозаписана серия то записать ее
{
while(iterA<iterator && !feof(A))
{
fputs(temp1,FTS);
sh1=1;
if(fgets(temp1,30,A)!=NULL) sh1=0;
iterA++;
}
while(iterB<iterator && !feof(B))
{
fputs(temp2,FTS);
sh2=1;
if(fgets(temp2,30,B)!=NULL) sh2=0;
iterB++;
}
}
}
while(!feof(A)) //если один из файлов был больше другого то дозаписать его концовку
{
fputs(temp1,FTS);
fgets(temp1,30,A);
}
while(!feof(B))
{
fputs(temp2,FTS);
fgets(temp2,30,B);
}
if(!sh1) fputs(temp1,FTS); //если данные были считаны но из-за концовки файла не были переписаны в файл слияния
//в основном цикле то дозаписать
if(!sh2) fputs(temp2,FTS);
fclose(FTS); //закрыть файлы
fclose(A);
fclose(B);
iterator*=2; //увеличить длину серии
}
remove("a.txt");
remove("b.txt");
}
Troilk вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка методом прямого включения(паскаль) Cas01 Помощь студентам 1 17.03.2011 08:37
Сортировка методом слияния. Вера_М Помощь студентам 1 20.06.2010 11:33
сортировка методом прямого обмена sestrenka141989 Паскаль, Turbo Pascal, PascalABC.NET 1 27.05.2010 09:22
[pascal]Сортировка массива методом прямого выбора, работает неадекватно. fatoldsun Помощь студентам 7 22.04.2009 19:42
Сортировка массива методом прямого выбора(Дельфи) Onza Помощь студентам 20 25.01.2009 12:05