Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/39: Рейтинг темы: голосов - 39, средняя оценка - 4.69
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
1

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

19.12.2010, 13:39. Показов 8134. Ответов 9
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Всем доброго время суток, дана задача:
Требуется упорядочить элементы некоторого массива целых чисел, который следует упорядочить по возрастанию:

Файл 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 не определена как переменная
0
Лучшие ответы (1)
Сообщение: #3202941
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 19.12.2010, 13:39
Ответы с готовыми решениями:

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким...

Сортировка Слиянием vs Быстрая Сортировка - что лучше
Народ, помогите разобраться какой из методов сортировки лучше &quot;Сортировка Слиянием&quot; или &quot;Быстрая...

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

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

9
4773 / 2582 / 894
Регистрация: 29.11.2010
Сообщений: 5,590
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;
}
0
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
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

Подскажите пожалуйста товарищи программисты, что надо сделать?????
Ничего умного в голову не приходит. Заранее огромное спасибо.
0
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
20.12.2010, 21:42  [ТС] 4
Что никто не может подсказать в чем ошибка?
0
652 / 462 / 80
Регистрация: 26.10.2010
Сообщений: 1,263
Записей в блоге: 4
06.06.2012, 22:26 5
isaak, в Main.cpp у вас N = 10, а в MergeSort.h N = NULL.
0
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
09.06.2012, 18:24  [ТС] 6
Если я в в MergeSort.h N = 10 все равно ошибка? Как правильно????
0
gencurrent
23.06.2012, 17:00 7
N должна стать глабальной.

Добавлено через 23 минуты
Этот код работает у меня.
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
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

Заранее огромное спасибо.
0
gencurrent
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 неинициализирована. Это одна из проблем.
171 / 104 / 25
Регистрация: 17.10.2010
Сообщений: 1,146
24.06.2012, 15:42  [ТС] 10
gencurrent спасибо огромное ваш код на много проще все работает как надо!!!!!
0
24.06.2012, 15:42
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 24.06.2012, 15:42
Помогаю со студенческими работами здесь

Сортировка слиянием
Нужен самый примитивный рабочий код желательно с комментарием. Спасибо

Сортировка слиянием
Требуется отсортировать слиянием массив структур. По одному из элемерту структуры. Вторая ночь без...

Сортировка с слиянием
Добрый вечер! Помогите с подсчетом перестановок и сравнений при сортировке с слиянием. Вот нашел...

Сортировка слиянием
Сортировка слияние, есть???


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru