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

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

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

Найти ошибку в реализации алгоритма n - путевого слияния - C++

21.06.2013, 10:16. Просмотров 359. Ответов 0
Метки нет (Все метки)

Доброе утро.
Нужно реализовать алгоритм n - путевого слияния (n - аргумент функции). Некоторые операции проходят неверно, причём вычислить ошибку никак не удаётся (подробности ниже). Вот код:
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
namespace MultiMerge {
 
const int empty=0x80000000;
 
struct Buffer {
    //буфер для работы с ключами
    Buffer():prev(empty),curr(empty) { };
 
    int prev;
    int curr;
};
 
void create_files(vector<string>& fnames, int n)
{
    //создание списка имён вспомогательных файлов
    string templ="_File_for_MultiMerge";
    for (int i=0; i<2*n; ++i)
        fnames.push_back(templ+to_string(i));
 
    //создание самих файлов
    ofstream ofs;
    for (int i=0; i<2*n; ++i) {
        ofs.open(fnames[i]);
        ofs.close();
    }
}   
 
int split(const string& source, vector<string>& workfiles, int n)
{
    //распределение элементов из исходного файла, 
    //возвращается кол-во возрастающих серий в source
 
    ifstream ifs(source);   
    if (!ifs) throw runtime_error("split: can't open source file");
 
    vector<ofstream> vofs(n);       
    for (int i=0; i<n; ++i) {
        vofs[i].open(workfiles[i]);
        if (!vofs[i]) throw runtime_error("split: can't open one of auxiliary file");
    }
 
    int series(0);                          
    int write_num(0);                       //номер вспомогательного файла, в который идёт запись
    int buffer1(empty), buffer2(empty);     //буферы для чтения ключей и определения границ серий
    while (true) {
        if (buffer2==empty && !(ifs>>buffer2)) {
            ++series;
            break;
        }
        if (buffer2>=buffer1) {
            vofs[write_num]<<buffer2<<" ";
            buffer1=buffer2;
            buffer2=empty;
        }
        else {                              //конец очередной серии
            ++series;
            write_num=(write_num+1)%n;
            buffer1=empty;                  //начало новой серии, условие (buffer2>=buffer1)==true
        }
    }
 
    return series;
}
 
void sort(const string& source, int n)
{
    //source - исходный файл, n - путевое слияние
    if (n<2) throw runtime_error("sort: not enough auxiliary files for sorting");
 
    vector<string> fnames;
    create_files(fnames,n);
    int series=split(source,fnames,n);  //кол-во серий на каждом очередном этапе
 
    vector<int> table_dir(2*n);         //таблица, первые n значений - индексы сливаемых файлов
    for (int i=0; i<2*n; ++i)
        table_dir[i]=i;
 
    vector<int> table_from(n);          //таблица для отслеживания окончания серий и окончания данных в сливаемых файлах
    vector<Buffer> v_buf(2*n);          //вектор буферов для каждого файла, из которого на данном этапе сливаются ключи
    while (series>1) {
 
        int cnt1(n), cnt2(n);           //число непустых файлов; число файлов, в которых текущая серия ещё не закончилась
        if (series<n) 
            cnt1=cnt2=series;
 
        int file_for_write=n;               //table_dir[file_for_write] - индекс файла, в который идёт запись
        series=0;
 
        for (int i=0; i<n; ++i) {
            table_from[i]=table_dir[i];         //подготовка таблицы
            v_buf[table_from[i]].prev=empty;    //подготовка буферов (1)
        }
        
        vector<fstream> v_fs(2*n);              //подготовка файлов
        for (int i=0; i<2*n; ++i) {
            v_fs[i].open(fnames[table_dir[i]]); 
            if (!v_fs[i]) throw runtime_error("sort: can't open one of auxiliary files during merge stage");
        }
        
        for (int i=0; i<cnt1; ++i)
            v_fs[table_from[i]]>>v_buf[table_from[i]].curr; //подготовка буферов (2)
 
        cout<<"Buffers before merge: ";
        for (int i=0; i<table_from.size(); ++i)
            cout<<v_buf[table_from[i]].curr<<", ";
        cout<<endl;
        while (cnt1) {
    
            //поиск минимума
            int nmin(0);
            for (int i=0; i<cnt2; ++i) {
                if (v_buf[table_from[i]].curr<v_buf[table_from[nmin]].curr) nmin=i;
            }
            cout<<"min="<<v_buf[table_from[nmin]].curr<<endl;
 
            //запись минимума
            v_fs[table_dir[file_for_write]]<<v_buf[table_from[nmin]].curr<<" ";
            v_buf[table_from[nmin]].prev=v_buf[table_from[nmin]].curr;
 
            //работа с буфером, проверки на конец серии и конец файла
            if (!(v_fs[table_from[nmin]]>>v_buf[table_from[nmin]].curr)) {
                --cnt1;
                --cnt2;
                swap(table_from[nmin],table_from[cnt1]);
                swap(table_from[nmin],table_from[cnt2]);
            } else if (v_buf[table_from[nmin]].curr < v_buf[table_from[nmin]].prev) {
                --cnt2;
                swap(table_from[nmin],table_from[cnt2]);
            }
            cout<<"cnt1 == "<<cnt1<<", cnt2 == "<<cnt2<<endl;
            cout<<"Buffers: ";
            for (int i=0; i<table_from.size(); ++i)
                cout<<v_buf[table_from[i]].curr<<", ";
            cout<<endl<<endl;
 
            //проверка на конец серий в каждом файле
            if (cnt2==0) {
                ++series; //неправльная работа с сериями (условие!)
                cnt2=cnt1;
                if (file_for_write<2*n-1)   //меняем файл для записи
                    ++file_for_write;
                else
                    file_for_write=n;
            }
 
        }
        cout<<"series=="<<series<<endl;
        cout<<"-------------------------------------------------"<<endl;
        
        //подготовка к следующему слиянию: блоки из n файлов меняются ролями
        for (int i=0; i<n; ++i)
            swap(table_dir[i],table_dir[i+n]);
        system("pause");
    }
 
    //результат должен  в v_fs[table_dir[0]]
    //перенос результата в исходный файл
    /*ifstream ifs(fnames[table_dir[0]]);
    ofstream ofs(source);
    if (!ifs || !ofs) throw runtime_error("sort: can't return result in source file");
    int buffer;
    while (ifs>>buffer)
        ofs<<buffer<<" ";*/
 
    /*удаление вспомогательных файлов*/
    /*for (int i=0; i<fnames.size(); ++i)
        remove(fnames[i].c_str());*/
}
 
}
Функции split и create_files отлажены. Тестировал на последовательности 10, 9, 8, 7, 6, 5, 4, 3, 2 (сортировать нужно по возрастанию), первый этап проходит верно: series == 3, получаем последовательности 8,9,10 | 5,6,7 | 2, 3, 4. Однако на следующем шаге перед началом слияния в буферы снова попадают 10,9,8 вместо 8,5,2 => зацикливание.
Подскажите:
1) В чём же проблема?
2) Можно ли как-то упростить код, нет ли в моё варианте слишком большого кол-ва ненужных операций?
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 10:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти ошибку в реализации алгоритма n - путевого слияния (C++):

Подскажите ошибку в реализации алгоритма Хаффмана - C++
при архивации txt файла проблем не возникает, но со всеми остальными (например: png,doc,exe,docx и т.д.) он не работает, подскажите что не...

Найти и исправить ошибки в реализации алгоритма Дейкстры - C++
Алгоритм Дейкстры (построение путей с минимальными цепями) #include&lt;iostream.h&gt; #include&lt;string.h&gt; #include&lt;stdio.h&gt; ...

Найти ошибку в реализации метода Гаусса - C++
Нужно решить матрицу методом гауза вот код: #include &quot;iostream&quot; #include &quot;math.h&quot; #include &quot;stdlib.h&quot; #include...

Нужно найти ошибку в коде реализации метода половинного деления - C++
Программа должна решать методом половинного деления уравнение: #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; float...

Задача на построение циклического алгоритма,выбивает ошибку.Вводятся N чисел,найти сумму кратных 5-ти - C++
Задача: Вводятся N чисел,найти сумму кратных 5-ти. при вызове отладчика возникает бесконечно повторяющиеся фразы(фото) ...

Вопросы по реализации алгоритма DES - C++
Всем добрый вечер! Понадобилось написать алгоритм DES по учебе, в связи с этим возникли кое-какие вопросы: а именно - сначала мы считываем...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2013, 10:16
Привет! Вот еще темы с ответами:

Нужне совет по реализации алгоритма - C++
a1, (a1+a2), (a1+a2+a3), ... , (a1+a2+...aN)

Не найден заголовочный файл в реализации алгоритма Дейкстры - C++
запускаю программу и выдает ошибку &quot;fatal error C1083: Не удается открыть файл включение: stdafx.h: No such file or directory&quot; код...

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

Написал вариант реализации алгоритма for_each. Не понимаю, как он работает с функциями - C++
template&lt;typename Container, typename Func&gt; Func for_each(typename Container::iterator begin, typename Container::iterator end, Func op) ...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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