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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.92
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
19.12.2010, 13:39     Сортировка слиянием #1
Всем доброго время суток, дана задача:
Требуется упорядочить элементы некоторого массива целых чисел, который следует упорядочить по возрастанию:

Файл MergeSort.h
C++
1
2
3
4
5
6
7
8
9
10
#ifndef __MERGE_SORT_H__
#define __MERGE_SORT_H__
 
// Включить печать отладочных сообщений.
#define DEBUG_ECHO 1
 
// Сортировка слиянием
void MergeSort(int array[], int N);
 
#endif
Файл MergeSort.cpp
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
#include <assert.h>
 
#include "MergeSort.h"
 
#ifdef DEBUG_ECHO
#include <iostream>
using namespace std;
#endif
 
void Merge(int array[], int first, int middle, int last, int temp[]) {
    int idx = first;            // Куда будем делать слияние
    int begin1 = first, end1 = middle;  // Первый из двух сливаемых массивов array[begin1]..array[end1]
    int begin2 = middle+1, end2 = last; // Второй из двух сливаемых массивов array[begin2]..array[end2]
 
    for(; begin1 <= end1 && begin2 <= end2; ) {
        if (array[begin1] < array[begin2]) 
            temp[idx] = array[begin1++];
        else
            temp[idx] = array[begin2++];
        idx++;
    }
 
    for(; begin1 <= end1; )
        temp[idx++] = array[begin1++];
 
    for(; begin2 <= end2; )
        temp[idx++] = array[begin2++];
 
    #ifdef DEBUG_ECHO           // Печать отладочной информации (если разрешено)
    int _z;
    cout << "***merge process begin" << endl;
    for(_z = first; _z <= last; _z++) cout << array[_z] << (_z==middle ? " - " : "  ");
    cout << endl;
    for(_z = first; _z <= last; _z++) cout << temp[_z] << "  ";
    cout << endl << "***merge process end" << endl;
    #endif
 
    for(idx = first; idx <= last; idx++) 
        array[idx] = temp[idx];
}
 
void InternalMergeSort(int array[], int first, int last, int buffer[]) {
    #ifdef DEBUG_ECHO           // Печать отладочной информации (если разрешено)
    cout << "MergeSort: " << first << "  " << last << endl;
    #endif
 
    if (first < last) {
        int m = (first + last)/2;
        InternalMergeSort(array, first, m, buffer);
        InternalMergeSort(array, m+1, last, buffer);
        Merge(array, first, m, last, buffer);
    }
}
 
void MergeSort(int array[], int first, int last) {
    // Временный массив выделяется только один раз
    // (не тратим время на бесполезное перераспределение памяти)
    int *buffer = new int[N];
    InternalMergeSort(array, 0, N-1, buffer);
    delete[] buffer;
}
Файл Main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include "MergeSort.h"
 
void main(void) {
    int const N = 10;
    int i, *a = new int[N];
 
    srand(unsigned(time(NULL)));
    for(i=0; i<N; i++) std::cout << (a[i] = int((double(rand()) / RAND_MAX) * 100)) << "\t";
    std::cout << std::endl;
 
    MergeSort(a, N);
 
    for(i=0; i<N; i++) std::cout << a[i] << "\t";
    std::cout << std::endl;
    delete[] a;
}
При компиляции выскакивает ошибка:
Error 1 error C2065: 'N' : undeclared identifier c:\users\администратор\documents\visual studio 2008\projects\c++\console\p1068\p1068\mergesort.cpp 56 p1068
Error 2 error C2065: 'N' : undeclared identifier c:\users\администратор\documents\visual studio 2008\projects\c++\console\p1068\p1068\mergesort.cpp 57 p1068
Не понимаю почему ведь, N уже определена как переменная:
C++
1
2
int const N = 10;
int i, *a = new int[N];
Почему же тогда выскакивает сообщение, N не определена как переменная
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2010, 13:39     Сортировка слиянием
Посмотрите здесь:

C++ Сортировка слиянием
Сортировка слиянием C++
C++ сортировка слиянием
C++ Сортировка слиянием
шейкерная сортировка + сортировка слиянием C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.12.2010, 13:54     Сортировка слиянием #2
Вот сюда он ругается.
C++
1
2
3
4
5
6
7
void MergeSort(int array[], int first, int last) {
        // Временный массив выделяется только один раз
        // (не тратим время на бесполезное перераспределение памяти)
        int *buffer = new int[N]; <--- кто такой N?
        InternalMergeSort(array, 0, N-1, buffer);
        delete[] buffer;
}
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
19.12.2010, 14:58  [ТС]     Сортировка слиянием #3
Как сделать, чтобы он перестал ругаться, я все перепробовал добавил в MergeSort.cpp:
C++
1
2
3
4
5
6
7
8
void MergeSort(int array[], int first, int last) {
    // Временный массив выделяется только один раз
    // (не тратим время на бесполезное перераспределение памяти)
    int N;
    int *buffer = new int[N];
    InternalMergeSort(array, 0, N-1, buffer);
    delete[] buffer;
}
непомогло:
Warning 1 warning C4700: uninitialized local variable 'N' used c:\users\администратор\documents\visual studio 2008\projects\c++\console\p1068\p1068\mergesort.cpp 57 p1068
Error 2 error LNK2019: unresolved external symbol "void __cdecl MergeSort(int * const,int)" (?MergeSort@@YAXQAHH@Z) referenced in function _main Main.obj p1068
Error 3 fatal error LNK1120: 1 unresolved externals C:\Users\Администратор\Documents\Visual Studio 2008\Projects\C++\Console\p1068\Debug\p1068.exe p1068
Добавил в начало файла MergeSort.cpp
C++
1
#include "Main.cpp"
"включение" (если не правильно выразился, то прошу меня простить, я пока в этом полное ламо) файла Main.cpp, так там это переменная описана:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include "MergeSort.h"
 
void main(void) {
    int const N = 10;
    int i, *a = new int[N];
 
    srand(unsigned(time(NULL)));
    for(i=0; i<N; i++) std::cout << (a[i] = int((double(rand()) / RAND_MAX) * 100)) << "\t";
    std::cout << std::endl;
 
    MergeSort(a, N);
 
    for(i=0; i<N; i++) std::cout << a[i] << "\t";
    std::cout << std::endl;
    delete[] a;
}
Ничего не помогло, результат тот же:
Error 1 error C2065: 'N' : undeclared identifier c:\users\администратор\documents\visual studio 2008\projects\c++\console\p1068\p1068\mergesort.cpp 58 p1068
Error 2 error C2065: 'N' : undeclared identifier c:\users\администратор\documents\visual studio 2008\projects\c++\console\p1068\p1068\mergesort.cpp 59 p1068

Подскажите пожалуйста товарищи программисты, что надо сделать?????
Ничего умного в голову не приходит. Заранее огромное спасибо.
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
20.12.2010, 21:42  [ТС]     Сортировка слиянием #4
Что никто не может подсказать в чем ошибка?
QVO
 Аватар для QVO
636 / 447 / 32
Регистрация: 26.10.2010
Сообщений: 1,261
Записей в блоге: 4
Завершенные тесты: 2
06.06.2012, 22:26     Сортировка слиянием #5
isaak, в Main.cpp у вас N = 10, а в MergeSort.h N = NULL.
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
09.06.2012, 18:24  [ТС]     Сортировка слиянием #6
Если я в в MergeSort.h N = 10 все равно ошибка? Как правильно????
gencurrent
Сообщений: n/a
23.06.2012, 17:00     Сортировка слиянием #7
N должна стать глабальной.

Добавлено через 23 минуты
Этот код работает у меня.
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
24.06.2012, 14:54  [ТС]     Сортировка слиянием #8
Подскажите пожалуйста как правильно описать глобальную переменную, подскажите пожалуйста, где ошибка:
Main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include "MergeSort.h"
extern int N;
void main(void) {
    int const N = 10;
    int i, *a = new int[N];
 
    srand(unsigned(time(NULL)));
    for(i=0; i<N; i++) std::cout << (a[i] = int((double(rand()) / RAND_MAX) * 100)) << "\t";
    std::cout << std::endl;
 
    MergeSort(a, N);
 
    for(i=0; i<N; i++) std::cout << a[i] << "\t";
    std::cout << std::endl;
    delete[] a;
}
MergeSort.cpp:
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
#include <assert.h>
 
#include "MergeSort.h"
 
#ifdef DEBUG_ECHO
#include <iostream>
using namespace std;
 
 
#endif
extern int N;
 
void Merge(int array[], int first, int middle, int last, int temp[]) {
    int idx = first;            // Куда будем делать слияние
    int begin1 = first, end1 = middle;  // Первый из двух сливаемых массивов array[begin1]..array[end1]
    int begin2 = middle+1, end2 = last; // Второй из двух сливаемых массивов array[begin2]..array[end2]
 
    for(; begin1 <= end1 && begin2 <= end2; ) {
        if (array[begin1] < array[begin2]) 
            temp[idx] = array[begin1++];
        else
            temp[idx] = array[begin2++];
        idx++;
    }
 
    for(; begin1 <= end1; )
        temp[idx++] = array[begin1++];
 
    for(; begin2 <= end2; )
        temp[idx++] = array[begin2++];
 
    #ifdef DEBUG_ECHO           // Печать отладочной информации (если разрешено)
    int _z;
    cout << "***merge process begin" << endl;
    for(_z = first; _z <= last; _z++) cout << array[_z] << (_z==middle ? " - " : "  ");
    cout << endl;
    for(_z = first; _z <= last; _z++) cout << temp[_z] << "  ";
    cout << endl << "***merge process end" << endl;
    #endif
 
    for(idx = first; idx <= last; idx++) 
        array[idx] = temp[idx];
}
 
void InternalMergeSort(int array[], int first, int last, int buffer[]) {
    #ifdef DEBUG_ECHO           // Печать отладочной информации (если разрешено)
    cout << "MergeSort: " << first << "  " << last << endl;
    #endif
 
    if (first < last) {
        int m = (first + last)/2;
        InternalMergeSort(array, first, m, buffer);
        InternalMergeSort(array, m+1, last, buffer);
        Merge(array, first, m, last, buffer);
    }
}
 
void MergeSort(int array[], int first, int last) {
    // Временный массив выделяется только один раз
    // (не тратим время на бесполезное перераспределение памяти)
    int *buffer = new int[N];
    InternalMergeSort(array, 0, N-1, buffer);
    delete[] buffer;
}
MergeSort.h:
C++
1
2
3
4
5
6
7
8
9
10
11
#ifndef __MERGE_SORT_H__
#define __MERGE_SORT_H__
 
// Включить печать отладочных сообщений.
#define DEBUG_ECHO 1
 
extern int N;
// Сортировка слиянием
void MergeSort(int array[], int  N);
 
#endif
Все равно выдает ошибки:

Error 3 error LNK1120: 2 unresolved externals C:\Users\Администратор\Documents\Visual Studio 2010\Projects\C++\Console\p1783\Collating sort\Debug\Collating sort.exe 1 1 Collating sort
Error 2 error LNK2001: unresolved external symbol "int N" (?N@@3HA) C:\Users\Администратор\Documents\Visual Studio 2010\Projects\C++\Console\p1783\Collating sort\Collating sort\MergeSort.obj Collating sort
Error 1 error LNK2019: unresolved external symbol "void __cdecl MergeSort(int * const,int)" (?MergeSort@@YAXQAHH@Z) referenced in function _main C:\Users\Администратор\Documents\Visual Studio 2010\Projects\C++\Console\p1783\Collating sort\Collating sort\Main.obj Collating sort

Заранее огромное спасибо.
gencurrent
Сообщений: n/a
24.06.2012, 15:39     Сортировка слиянием #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Попробуйте сначала упрощенную версию кода без препроцессорной обработки условий и макросов.
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
#include <iostream> 
#include <iomanip>
#include <time.h> 
using namespace std; 
 
int const N = 16;
 
void MergeSort(int[], int, int);
 
int main() 
{
    system("color 0a");
    int i, *a = new int[N];
 
    srand(unsigned(time(NULL)));
    for(i=0; i<N; i++) cout << setw(4) << (a[i] = int((double(rand()) / RAND_MAX) * 100));
    cout << endl;
 
    MergeSort(a, 0, N);
 
    for(i=0; i<N; i++) cout << setw(4) << a[i];
    cout << endl;
    delete[] a;
 
    system("PAUSE");
}
 
void Merge(int array[], int first, int middle, int last, int temp[]) 
{
    int idx = first;            
    int begin1 = first, end1 = middle;  
    int begin2 = middle+1, end2 = last; 
 
    for(; begin1 <= end1 && begin2 <= end2; ) 
    {
        if (array[begin1] < array[begin2]) 
            temp[idx++] = array[begin1++];
        else
            temp[idx++] = array[begin2++];
    }
 
    for(; begin1 <= end1; )
        temp[idx++] = array[begin1++];
 
    for(; begin2 <= end2; )
        temp[idx++] = array[begin2++];
 
 
    for(idx = first; idx <= last; idx++) 
        array[idx] = temp[idx];
}
 
void InternalMergeSort(int array[], int first, int last, int buffer[]) 
{
     if (first < last) 
     {
        int m = (first + last)/2;
        InternalMergeSort(array, first, m, buffer);
        InternalMergeSort(array, m+1, last, buffer);
        Merge(array, first, m, last, buffer);
    }
}
 
void MergeSort(int array[], int first, int last) 
{
    int *buffer = new int[N];
    InternalMergeSort(array, 0, N-1, buffer);
    delete[] buffer;
}
Потом разделите ее на файлы, если это необходимо.

У меня на Visual C++2010 все работает.

В конце концов, можно будет передать N как аргумент.

Добавлено через 4 минуты
Кстати, Ваша external N неинициализирована. Это одна из проблем.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2012, 15:42     Сортировка слиянием
Еще ссылки по теме:

2 сортировки: пирамидальная сортировка и сортировка слиянием C++
C++ Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Сортировка слиянием C++

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

Или воспользуйтесь поиском по форуму:
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
24.06.2012, 15:42  [ТС]     Сортировка слиянием #10
gencurrent спасибо огромное ваш код на много проще все работает как надо!!!!!
Yandex
Объявления
24.06.2012, 15:42     Сортировка слиянием
Ответ Создать тему
Опции темы

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