VPF::Слияние множества отсортиртированных файлов

DigiLab

Дата 4.1.2013, 11:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 3.1.2013

Репутация: нет
Всего: нет

Имеется пронумерованные отсортированные текстовые файлы, помогите составить алгоритм их слияния, не нарушая сортировки.

А, вообще, задание такое:

Цитата

Сортировка текстового файла простым разделением (по длине строк).
Файл читается группами по n строк в динамический массив указателей на строки,
группа сортируется и записывается в промежуточный файл.
Имя промежуточного файла генерируется в виде Fnnnn. txt, где nnnn номер группы.
Затем файлы сливаются по “олимпийской” системе по два файла в один.

Половина уже готова, а вот слияние файлов не могу понять как сделать...

IValdemar

Дата 4.1.2013, 18:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 10.1.2012

Репутация: нет
Всего: нет

Цитата(DigiLab @ 4.1.2013, 11:31

)

Половина уже готова

Если я правильно понял то у тебя уже есть n-е количество файлов, отсортированных по длине строк.

Вот процедура слияния для 2х файлов. Расширить ее на несколько файлов будет не сложно.

Код


    ifstream file1("file1.txt"), file2("file2.txt"); //Два файла для обработки
    ofstream res("result.txt"); //Файл с результатом слияния
    string t1,t2; 
    /*Первое считывание*/
    getline(file1,t1); 
    getline(file2,t2);
    /*Пока что-то есть в обоих файлах*/
    while(!file1.eof()&&!file2.eof())
    {
        /*Сравниваем длину и записываем строку с наименьшей длиной*/
        if(t1.legth()<t2.length()) {res<<t1;  getline(file1,t1); }
        else {res<<t2; getline(file2,t2);}
    }
    /*Если в одном из файлов остались строки, то one будет указывать на него*/
    ofstream* one = NULL;
    if(!file1.eof()) one=&file1;
    else if(!file2.eof()) one=&file2;
    /*Дозаписываем файл*/
    if(one!=NULL)
        while(!one->eof()) 
        {
            getline(*one,t1);
            res<<t1;
        }

DigiLab

Дата 4.1.2013, 19:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 3.1.2013

Репутация: нет
Всего: нет

Цитата

Сравниваем длину и записываем строку с наименьшей длиной

Если я не ошибаюсь, в предложенной процедуре слияния, считывание идет по длине. Но нужно еще учитывать содержимое строк, т.к. они все отсортированы.. в каждом файле содержится строка длины не более размера буфера:
У нас в универе препода наше творчество на плагиат тестируют. Блин, если поисковик проиндексирует код, то мне баллы снимут))) Вот код, некоторые комментарии морально устарели)):

Код


#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <stdio.h>

#define MaxLgthBufRead 512 // Размер буфера
#define MaxLgthNameFile 10

using namespace std;

void sort(char *in, int l, int h); 
void swap(char *ArrIn, int i, int j);
void  MergeFiles(int Nfiles);

int _tmain(int argc, _TCHAR* argv[])
{    
    setlocale(LC_ALL, "Russian");

    FILE *Fin, *Fcur;
    int NStrings, i=0;
    char *InNameFile = new char[MaxLgthNameFile];

    cout << "Введите имя файла -> ";
    cin >> InNameFile;
    cout << "Введите количество строк -> ";
    cin >> NStrings;

    char *Buf1 = new char[MaxLgthBufRead], // Массив буфера чтения
    *NameMedFile = new char[MaxLgthNameFile], // Массив имен промежуточных файлов
    **Arr = new char*[NStrings]; // Динамический массив указателей на строки

    if((Fin=fopen(InNameFile,"r"))==NULL) cout << "Ошибка открытия файла " << '\"' << InNameFile << '\"';
    else
    {
        while(!feof(Fin))
        {
            for(i; i<NStrings; i++)
            {
                sprintf(NameMedFile,"F%d.txt",i);
                if((Fcur=fopen(NameMedFile,"w"))==NULL) // Создаем промежуточный файл, проверяем открылся ли он?!
                {
                    cout << "Ошибка создания файла " << '\"' << NameMedFile << '\"'; 
                    break; 
                }
                else
                {
                    if(fgets(Buf1, MaxLgthBufRead, Fin)==NULL) break; // Заполняем буфер
                    Arr[i] = new char[strlen(Buf1)+1]; // Выделили память для строки
                    strcpy(Arr[i],Buf1); // Скопировали из буфера в массив
                    cout << Arr[i]; // Вывели что скопировали
                    sort(Arr[i],0,strlen(Arr[i])-1); // Отсортировали
                    fputs(Arr[i], Fcur); // Записали в файл
                    delete []Arr[i]; // Освободили память
                    Arr[i]=NULL; // Присвоили нуль-указатель
                }
                fclose(Fcur); // Закрываем промежуточный файл
            }
        }
    }
    // Освобождаем память, возвращаем все обратно в кучу:
    delete [] Arr;
    Arr=NULL;
    delete [] Buf1;
    Buf1=NULL;
    delete [] NameMedFile;
    NameMedFile = NULL;
    
    fclose(Fin); // Закрываем файл
    cout << '\n'; 
    system("PAUSE");
}
void sort(char *in, int l, int h) // Функция сортировки разделением (входной массив, нижний предел, верхний предел)
{
    int i=l, j=h; // Переменным циклов, присваиваем верхний и нижний предел соответственно
    int rel=in[(l+h)/2]; // Находим средний элемент массива, берем его в качестве опорного. Так как индекс целочисленный, остаток отбрасывается
    do {
        while(in[i] < rel) ++i; // Индекс i увеличивается, пока i-ый элемент не превысит опорный
        while(in[j] > rel) --j; // Индекс j уменьшается, пока j-ый элемент не станет меньше опорного
        if(i <= j) // Если мы нашли середину, или i стало меньше j, тогда меняем элементы местами. 
        // Это делается для того чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него:
        {
            swap(in, i, j);
            i++; j--; // Инкрементируем и декрементируем i, j соответственно. Подсчитываем количество перестановок
        }
    } while(i<j); 
// Продолжаем сортировку с тех индекcов, которые были достигнуты:
    if(l<j) sort(in, l, j);
    if(i<h) sort(in, i, h);
}
// Функция обмена значений двух элементов в массиве:
void swap(char *ArrIn, int i, int j)
{
    int temp = ArrIn[i];
    ArrIn[i] = ArrIn[j];
    ArrIn[j] = temp;
}
void  MergeFiles(int Nfiles)
{
    char *Buf1 = new char[MaxLgthBufRead], // Массив буфера чтения
    *Buf2 = new char[MaxLgthBufRead], // Массив буфера чтения
    *NameMedFile = new char[MaxLgthNameFile], // Массив имен промежуточных файлов
    *NameMedFile1 = new char[MaxLgthNameFile]; // Массив имен промежуточных файлов

    for(int k=0; k<Nfiles; k+=2)
    {
        sprintf(NameMedFile,"F%d_%d.txt", k, k+1);
        ofstream Fcur(NameMedFile);
        Fcur.unsetf(ios_base::skipws);
        if(!Fcur.is_open()) // Создаем промежуточный файл, проверяем открылся ли он?!
        {
            cout << "Ошибка создания файла " << '\"' << NameMedFile << '\"'; 
            break; 
        }
        else
        {
            sprintf(NameMedFile,"F%d.txt",k);
            sprintf(NameMedFile1,"F%d.txt",k+1);
            ifstream Fin1(NameMedFile);
            ifstream Fin2(NameMedFile1);
            Fin1.unsetf(ios_base::skipws); // "Включаем" чтение пробелов
            Fin2.unsetf(ios_base::skipws); 
            if((Fin1.is_open())&&(Fin2.is_open()))
            {
                for(int i=0;(!Fin1.eof())&&(!Fin2.eof())||i<MaxLgthBufRead; i++)
                {
                        Fin1 >> Buf1[i];
                        Fin2 >> Buf2[i];
                        // как их слить?! чтобы внутри сортировку не нарушить.
                }
                remove(NameMedFile); // удалим файл
                remove(NameMedFile1); // удалим файл
            }
            Fin1.close();
            Fin2.close();
        }
        Fcur.close(); // Закрываем промежуточный файл
    }
}

NoviceF

Дата 4.1.2013, 20:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 13.3.2012
Где: Ростов-на-Дону

Репутация: 2
Всего: 2

Цитата(DigiLab @ 4.1.2013, 20:05

)

Но нужно еще учитывать содержимое строк, т.к. они все отсортированы..

Какова структура файлов? Есть ли там вообще переводы строки, или всё содержимое записано одной строкой? Если строка одна, или же, если наличие строк не указано в условиях, может просто использовать merge? http://cplusplus.com/reference/algorithm/merge/

И что значит "не нарушая сортировки"? Файлы должны быть "склеены" начало одного к концу другого, или объединены с помощью сортировки слиянием?

DigiLab

Дата 4.1.2013, 20:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 3.1.2013

Репутация: нет
Всего: нет

Цитата

Поступает текстовый файл, с любым текстом в т.ч. и с 'переводами'. Кол-во строк задается пользователем. Строки в нашем случае - массив символов кол-во которых, задается размером буфера. Затем каждая строка сортируется и пишется по файлам Fnnn.txt. а затем файлы объединяют, по два, в новые файлы не нарушая сортировки. Это так нам препод сказал, хотя я по другому понимаю задание.

IValdemar

Дата 4.1.2013, 22:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 10.1.2012

Репутация: нет
Всего: нет

Цитата(DigiLab @ 4.1.2013, 19:05

)

Если я не ошибаюсь, в предложенной процедуре слияния, считывание идет по длине. Но нужно еще учитывать содержимое строк

У тебя же указано:

Цитата(DigiLab @ 4.1.2013, 11:31

)

Сортировка текстового файла простым разделением (по длине строк).

Так сливать их надо по длине строк или еще и лексикографически? Если нужно еще и лексикографическое сравнение достаточно расширить сравнение строк: если они одной длины записываем ту что лексикографически меньше.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »