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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
I_Masha_I
2 / 2 / 0
Регистрация: 14.10.2012
Сообщений: 53
#1

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

28.10.2012, 17:34. Просмотров 1028. Ответов 16
Метки нет (Все метки)

Даны два текстовых файла 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++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

Шейкерная сортировка + сортировка слиянием - C++
вот часть когда,которая выполняет шейкерную сортировку : для символьного и целочисленого массива . // ConsoleApplication15.cpp:...

Сортировка слиянием в С++ - C++
Вот такое задание: Составить программу реализации указанного метода сортировки и иллюстрации его выполнения. В программе предусмотреть...

сортировка слиянием - C++
программа должна выполнять сортировку строк слиянием с использованием указателей. #include&lt;iostream&gt; #include&lt;string.h&gt; ...

Сортировка слиянием - C++
Требуется отсортировать слиянием массив структур. По одному из элемерту структуры. Вторая ночь без сна, не могу понять даже реализацию...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 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
1285 / 947 / 51
Регистрация: 17.05.2012
Сообщений: 2,687
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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 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 << ' ';
   }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2012, 21:16
Привет! Вот еще темы с ответами:

сортировка слиянием - C++
Доброго времени суток, помогите пожалуйста с сортировкой слиянием... дело в том что нужно сделать её через вектор.. помогите кто чем...

Сортировка слиянием - C++
void merg1(int* mas, int p, int q, int r) { int size1 = p + q; int size2 = r - q + 1; int *mas1 = new int; int *mas2 = new...

Сортировка слиянием - C++
Добрый вечер. C си начал совсем недавно работать, до этого был паскаль, делфи. Есть рабочий код на паскале, прошу помочь разобраться в чем...

Сортировка слиянием - C++
Нужен алгоритм сортировки массива слиянием. Массив из 1000 чисел, введенных рандомно. На visual c++ заранее большое спасибо.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.10.2012, 21:16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru