Новичок
Профиль
Группа: Участник
Сообщений: 1
Регистрация: 14.6.2011
Репутация: нет
Всего: нет
|
Помогите исправить функцию реализующую сортировку текстового файла прямым слиянием Прямое слияние | Код |
Предположим, что имеется последовательный файл A, состоящий из записей a_ (1), a_2 .. a_n (для
простоты предположим, что n есть степень числа 2). Будем считать, что каждая запись состоит ровно
из одного элемента, представляющего собой ключ сортировки. Для сортировки используются два
вспомогательных файлов B и C (размер каждого из них будет n / 2).
Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение
файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения
последовательно читается файл A, и записи a_1, a_2 ..., a_ (n / 2) пишутся в файл B, а записи a_
(((n) / 2) +1), a_ (((n) / 2) +2), ..., a_n-в файл C (начальное распределение). Начальное слияние
выполняется над парами (a_1, a_ (((n) / 2) +1)), (a_2, a_ (((n) / 2) +2)), (a_ (((n) / 2) + 1),
a_n), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в
файл B записываются числа до середины файла А, а в файл C - остаток. При слиянии образуются и
пишутся в файл A упорядочены четверки записей. И т.д. Перед выполнением последнего шага файл A
будет содержать две упорядоченные подпоследовательности размером n / 2 каждая. При распределении
первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью
упорядоченную последовательность записей. В таблице показан пример внешнего сортировки простым
слиянием. |
Вот мой код Код | Код |
#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
int GetKey(char infoLine[30]) //получение ключа сортировки из строки
{
char temps[30];
strcpy(temps,infoLine); //сохранение исходной строки
return atoi(strtok(temps," ")); //возвращение первого числа из строки
}
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;
bool nl1=0,nl2=0;
if(feof(A)) nl1=1;
if(feof(B)) nl2=1;
bool once=1;
while((!feof(A) && !feof(B)) || once) //пока файлы не закончились
{
int iterA=0,iterB=0; //счетчики считаных чисел из каждого из файлов на
текущей итерации
bool iterCon=1; //необходимость продолжения слияния серий
while((iterCon && !feof(A) && !feof(B)) || (once && iterCon))
{
if(GetKey(temp1)<=GetKey(temp2)) //сравнить числа
{
fputs(temp1,FTS); //записать в изначальный файл
if(nl1) fputc('\n',FTS);
sh1=1;
if(fgets(temp1,30,A)!=NULL) sh1=0; else once=0;
iterA++; //увеличить количество чисел считаных их
первого файла
} else
{
fputs(temp2,FTS);
if(nl2) fputc('\n',FTS);
sh2=1;
if(fgets(temp2,30,B)!=NULL) sh2=0; else once=0;
iterB++;
}
if(iterA==iterator || iterB==iterator) iterCon=0; //если в
файле было считано количество чисел
} //которые необходимо считать на данной итерации
то закончить слияние серий
if(!iterCon) //если в одном из файлов еще не дозаписана серия то записать
ее
{
while(iterA<iterator)
{
fputs(temp1,FTS);
sh1=1;
if(fgets(temp1,30,A)!=NULL) sh1=0; else break;
iterA++;
}
while(iterB<iterator)
{
fputs(temp2,FTS);
sh2=1;
if(fgets(temp2,30,B)!=NULL) sh2=0; else break;
iterB++;
}
}
}
while(!feof(A)) //если один из файлов был больше другого то дозаписать его
концовку
{
fputs(temp1,FTS);
sh1=1;
if(fgets(temp1,30,A)!=NULL) sh1=0;
}
while(!feof(B))
{
fputs(temp2,FTS);
sh2=1;
if(fgets(temp2,30,B)!=NULL) sh2=0;
}
if(!sh1) fputs(temp1,FTS); //если данные были считаны но из-за концовки файла не
были переписаны в файл слияния
//в основном цикле то дозаписать
if(!sh2) fputs(temp2,FTS);
fclose(FTS); //закрыть файлы
fclose(A);
fclose(B);
iterator*=2; //увеличить длину серии
}
remove("a.txt");
remove("b.txt");
ShowFile(fileName);
}
int main()
{
char namer[20];
cin>>namer;
DirectMerge(namer);
} |
По сути это перевод Паскалевского кода (который работает) Код | Код |
var
s:string;
t:text;
Procedure MergeSort(name: string; var f: text);
Var a1,a2,s,i,j,kol,tmp: integer;
f1,f2: text;
b: boolean;
Begin
kol:=0;
Assign(f,name);
Reset(f);
While not EOF(f) do
begin
read(f,a1);
inc(kol);
End;
Close(f);
Assign(f1,'{имя 1-го вспомогательного файла}.txt');
Assign(f2,'{имя 2-го вспомогательного файла}.txt');
s:=1;
While (s<kol) do
begin
Reset(f); Rewrite(f1); Rewrite(f2);
For i:=1 to kol div 2 do
begin
Read(f,a1);
Write(f1,a1,' ');
End;
If (kol div 2) mod s<>0 then
begin
tmp:=kol div 2;
While tmp mod s<>0 do
begin
Read(f,a1);
Write(f1,a1,' ');
inc(tmp);
End;
End;
While not EOF(f) do
begin
Read(f,a2);
Write(f2,a2,' ');
End;
Close(f); Close(f1); Close(f2);
Rewrite(f); Reset(f1); Reset(f2);
Read(f1,a1);
Read(f2,a2);
While (not EOF(f1)) and (not EOF(f2)) do
begin
i:=0; j:=0;
b:=true;
While (b) and (not EOF(f1)) and (not EOF(f2)) do
begin
If (a1<a2) then
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End
else
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
If (i=s) or (j=s) then b:=false;
End;
If not b then
begin
While (i<s) and (not EOF(f1)) do
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End;
While (j<s) and (not EOF(f2)) do
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
End;
End;
While not EOF(f1) do
begin
tmp:=a1;
Read(f1,a1);
If not EOF(f1) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
While not EOF(f2) do
begin
tmp:=a2;
Read(f2,a2);
If not EOF(f2) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
Close(f); Close(f1); Close(f2);
s:=s*2;
readln;
End;
Erase(f1);
Erase(f2);
End;
Begin
MergeSort('input.txt',t);
end. |
но паскалевская прога сортирует числа в одной строке,а мне надо чтобы каждое число было с новой строки.Вся проблема в разнице между паскалевским EOF и сишным feof .Я наставил кучу проверок,но в результате что-то все равно не так. Например для файла 1 крутота 3 огог 2 зомби 5 ломби 7 йохохо 6 трулаа 1 1 3 2 11 27 200 токены 156 1 шмокены 24 56 лоло получается результат 1 крутота 1 1 шмокены 1 2 зомби 2 3 3 огог 5 ломби 6 трулаа 7 йохохо 11 24 27 27 56 лоло156 200 токены где 156 залазит в конец предпоследней строки,а число 27 встречается 2 раза.Где-то вконце строки 156 лоло не записался знак конца строки |
Помогите исправить функцию внешней сортировки 
Загрузка ...
