Форум программистов, компьютерный форум CyberForum.ru

Сортировка слиянием - C++

Восстановить пароль Регистрация
 
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 17:34     Сортировка слиянием #1
Даны два текстовых файла f1.txt и f2.txt, состоящие из целых чисел, которые упорядочены по неубыванию.
Числа лежат в диапозоне от 0 до 9. Например, f1.txt - 1 3 3 4 4 6
f2.txt - 2 2 3 4 4 7 7
Сформировать из элементов этих файлов третий текстовый файл f3.txt, в котором элементы будут упорядочены по неубыванию.
При этом учитывать исходную упорядоченность в файле, то есть каждый элемент сразу распологается на своём месте
f3.txt - 1 2 2 3 3 3 4 4 4 4 6 7 7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
 
int main()
{ 
    ifstream f1("f1.txt");
    ifstream f2("f2.txt");
    ofstream f3("f3.txt");
    int i, j;
    if(f1.peek()!= EOF)
    { 
        f1>>i;
    }
    if(f2.peek()!= EOF)
    {
        f2>>j;
    }
    while((f1.peek()!= EOF)||(f2.peek()!= EOF))
    {
        if((f1.peek()!= EOF)&&(f2.peek()!= EOF))
        {
            if(i<j)
            {
                f3<<i<<" ";
                f1>>i;
            }
            else
            {
                f3<<j<<" ";
                f2>>j;
            }
        }
        else if(f2.peek() == EOF)
        {
                f3<<i<<" ";
                f1>>i;
        }
        else if(f1.peek() == EOF)
        {
                f3<<j<<" ";
                f2>>j;
        }
    }
        
    f1.close();
    f2.close();
    f3.close();
 
    system("PAUSE");
    return 0;
}
Вот мой код, но он работает немного не правильно, у меня в f3 - 1 2 2 3 3 3 4 4 4 4 7
Помогите исправить ошибку

Добавлено через 2 часа 22 минуты
Ещё раз прошу о помощи)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2012, 17:34     Сортировка слиянием
Посмотрите здесь:

C++ сортировка слиянием
Сортировка слиянием C++
C++ сортировка слиянием
C++ Сортировка с слиянием
Сортировка слиянием c++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
28.10.2012, 18:44     Сортировка слиянием #2
Для начала считываем по одному числу с каждого файла пока не встретится EOF одного из них.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ifstream f1( "f1.txt", ios::in );
ifstream f2( "f2.txt", ios::in );
ofstream f3( "f3.txt", ios::out );
 
int num1;
int num2;
 
f1 >> num1;
f2 >> num2;
 
while ( f1.good() && f2.good()) {
   if ( num1 < num2 ) {
      f3 << num1 << ' ';
      f1 >> num1;
   } else {
      f3 << num2 << ' ';
      f2 >> num2;
   }
}
Как только встретится конец одного из файла, просто копируем оставшиеся числа из второго.
C++
1
2
3
4
5
6
7
8
9
while ( f1.good()) {
   f3 << num1 << ' ';
   f1 >> num1;
}
 
while ( f2.good()) {
   f3 << num2 << ' ';
   f2 >> num2;
}
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
28.10.2012, 18:44     Сортировка слиянием #3
Можно например вот так сделать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <fstream>
#include <algorithm> 
 
int main() 
{   
    int array1[6]; 
    int array2[7]; 
    int array[13]; 
    unsigned i = 0; 
    std::ifstream infile; 
    std::ofstream outfile("f3.txt");
    infile.open("f1.txt"); 
 
    if(!infile.is_open())  
        std::cout << "Error " << std::endl; 
    else  
        while(infile >> array1[i++]);   
    infile.close(); 
 
    i = 0;
    infile.open("f2.txt"); 
    if(!infile.is_open()) 
        std::cout << "Error " << std::endl; 
    else  
        while(infile >> array2[i++]); 
    infile.close(); 
 
    std::merge(array1, array1+6, array2, array2+7, array); 
 
    for ( i = 0; i < 13; i++) 
        outfile << array[i] << " "; 
    outfile.close();
 
}
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
28.10.2012, 18:50     Сортировка слиянием #4
все происходит в момент считывания 6, ваш файл заканчивается и начинается ввод с файла 2
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 19:09  [ТС]     Сортировка слиянием #5
David Sylva
Спасибо, но дополнительных массивов использовать нельзя

Добавлено через 1 минуту
Toshkarik
Вот что вы мне посоветовали сделать:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
 
int main()
{ 
    ifstream f1("f1.txt");
    ifstream f2("f2.txt");
    ofstream f3("f3.txt");
    int i, j;
    if(f1.peek()!= EOF)
    { 
        f1>>i;
    }
    if(f2.peek()!= EOF)
    {
        f2>>j;
    }
    while((f1.peek()!= EOF)&&(f2.peek()!= EOF))
    {
            if(i<j)
            {
                f3<<i<<" ";
                f1>>i;
            }
            else 
            {
                f3<<j<<" ";
                f2>>j;
            }
 
        }
    while(f1.peek() != EOF)
        {
                f3<<i<<" ";
                f1>>i;
        }
    while(f2.peek() != EOF)
        {
                f3<<j<<" ";
                f2>>j;
        }
        
    f1.close();
    f2.close();
    f3.close();
 
    system("PAUSE");
    return 0;
}
Данный код выдаёт мне f3 - 1 2 2 3 3 3 4 4 4 4 7 - то же самое
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
28.10.2012, 19:14     Сортировка слиянием #6
I_Masha_I, да, проверил, действительно. Это происходит потому что после считывания последнего числа сразу устанавливается флаг EOF. Можно добавить по конечному пробельному символу в каждый файл. Или придется делать еще несколько проверок.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
28.10.2012, 19:20     Сортировка слиянием #7
Цитата Сообщение от Toshkarik Посмотреть сообщение
Можно добавить по конечному пробельному символу в каждый файл
или так, сначала считываете, пишите, проверяете не конец ли файла, считываете, пишите, проверяете не конец ли файла и тд....
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 19:22  [ТС]     Сортировка слиянием #8
Toshkarik, спасибо за идею, так и сделаю, надеюсь, не придерутся))
И вот ещё один вопрос. Теперь надо сформировать файл f4, элементы которого будут те же что и в f3, но не будут повторяться.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
28.10.2012, 19:34     Сортировка слиянием #9
I_Masha_I, а в этом случае можно использовать массивы?
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 19:37  [ТС]     Сортировка слиянием #10
Нет, вообще нельзя использовать массивы
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
28.10.2012, 20:13     Сортировка слиянием #11
записывать из f3 в во временную ячейку и копировать на другую временую ячейку, записать в f4, далее считать с f3 в 1ю временную, проверить со 2й временной, если совпадают считать с f3 дальше если различаются записать во 2ю временную из 1й записать в f4
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
28.10.2012, 21:03     Сортировка слиянием #12
Ну по условию ведь все данные упорядоченны. Тогда делается так:
Создаете две переменные, для текущего значения и для предыдущего. Назовем их current и prev соответственно.

Считываете первое число, записываете его в файл.

Далее в цикле, пока не конец файла, записываете в переменную prev значение из current. Считываете следующее значение из файла f3 в переменную current.

Сравниваете current c prev. Если они не равны, то записываете значение current в файл.

Далее опять переменной prev присваиваете значение current и считываете следующее значение из f3 в переменную current.

И так пока не будет установлен флаг EOF.
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 21:04  [ТС]     Сортировка слиянием #13
А можете код написать, если не сложно
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
28.10.2012, 21:06     Сортировка слиянием #14
Цитата Сообщение от Toshkarik Посмотреть сообщение
Ну по условию ведь все данные упорядоченны. Тогда делается так:
Создаете две переменные, для текущего значения и для предыдущего. Назовем их current и prev соответственно.
Считываете первое число, записываете его в файл.
Далее в цикле, пока не конец файла, записываете в переменную prev значение из current. Считываете следующее значение из файла f3 в переменную current.
Сравниваете current c prev. Если они не равны, то записываете значение current в файл.
Далее опять переменной prev присваиваете значение current и считываете следующее значение из f3 в переменную current.
И так пока не будет установлен флаг EOF.
Цитата Сообщение от MrGrig Посмотреть сообщение
записывать из f3 в во временную ячейку и копировать на другую временую ячейку, записать в f4, далее считать с f3 в 1ю временную, проверить со 2й временной, если совпадают считать с f3 дальше если различаются записать во 2ю временную из 1й записать в f4
плагиат =Р
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
28.10.2012, 21:16     Сортировка слиянием #15
MrGrig, если честно, Ваше сообщение дальше 4 слова не читал, Вам нужно научится изъясняться яснее.
I_Masha_I,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   int current;
   int prev;
 
   f3 >> current;
 
   f4 << current << ' ';
 
   while ( f3.good()) {
      prev = current;
 
      file >> current;
 
      if ( current != prev )
         f4 << current << ' ';
   }
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
28.10.2012, 21:41  [ТС]     Сортировка слиянием #16
Toshkarik, большое спасибо, всё работает!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2012, 21:57     Сортировка слиянием
Еще ссылки по теме:

C++ Сортировка слиянием
Сортировка слиянием C++
Сортировка слиянием C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
28.10.2012, 21:57     Сортировка слиянием #17
Цитата Сообщение от Toshkarik Посмотреть сообщение
MrGrig, если честно, Ваше сообщение дальше 4 слова не читал, Вам нужно научится изъясняться яснее.
http://img1.joyreactor.cc/pics/comme...B2-186631.jpeg

Добавлено через 1 минуту
иногда мне проще написать код, того что хочу сказать, а писать бывает лень =)
Yandex
Объявления
28.10.2012, 21:57     Сортировка слиянием
Ответ Создать тему
Опции темы

Текущее время: 01:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru