VPF::Сортировка слиянием - Форум программистов

MaXL

Дата 24.1.2008, 07:10 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

Всем привет. Вот пытаюсь написать алгоритм сортировки слиянием, но чо-то у меня никак не выходит.
В процедуре Merge, которая "сливает" подмассивы я динамически создаю два массива, а потом пытаюсь их удалить на вылетает ошибка, и не понятно на что они там ругаются =(
Вот блок кода, из-за которого это происходит:

Код


    delete left;
    delete right;

Вот сообщение об ошибки:
Windows has triggered a breakpoint in sort.exe.
This may be due to a corruption of the heap, which indicates a bug in sort.exe or any of the DLLs it has loaded.
This may also be due to the user pressing F12 while sort.exe has focus.
The output window may have more diagnostic information.
Я так понимаю что тут произошло что-то с кучей, а вот как от этого избавиться ?
Ну и когда размер массивы велик(ну хотябы 500 элементов) и при этом отсуствует блок кода, который я привёл выше, то программа вылетает с другой ошибкой:
Run-Time Check Failure #2 - Stack around the variable 'arr' was corrupted.(это в дебаг режиме такое даёт).
Ну а вот собственно привожу полностью код(в процедуре merge я использую числа 99999, пока только для наглядности):

Код


#include "stdafx.h"

#define maxN  5

void Merge(int *arr, int p, int q, int r){
    int n1, n2;
    int i, j, k;
    int *left;
    int *right;    
    
    n1 = q - p + 1;
    n2 = r - q;
    left = new int[n1];
    right = new int[n2];    
    for(i = 1; i <= n1; i++)
        left[i] = arr[p + i - 1];
    for(j = 1; j <= n2; j++)
        right[j] = arr[q + j];        
    left[n1 + 1] = 99999; //не ругайте потом этого не будет, это поко только для наглядности ;-)
    right[n2 + 1] = 99999;
    i = 1; j = 1;
    for(k = p; k <= r; k++)
        if(left[i] <= right[j])
            arr[k] = left[i++];                                
        else
            arr[k] = right[j++];        
    /*delete left; //если этот участок кода оставить то вылетает ошибка
    delete right*/
}

void MergeSort(int *arr, int p, int r){
    int q;

    if(p < r){
        q = (p + r) / 2;
        MergeSort(arr, p, q);
        MergeSort(arr, q + 1, r);
        Merge(arr, p, q, r);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{    
    int arr[maxN];
    int i;

    for(i = 1; i <= maxN; i++){
        arr[i] = maxN - i;
        printf("%d ", arr[i]);
    }
    MergeSort(arr, 1, maxN);    
    printf("\n");
    for(i = 1; i <= maxN; i++)
        printf("%d ", arr[i]);
    scanf("_");
    return 0;
}

Это сообщение отредактировал(а) MaXL - 24.1.2008, 07:13

--------------------

MaXL

archimed7592

Дата 24.1.2008, 07:24 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Начнём с того, что в твоём случае нужно писать delete [] XXX; smile

--------------------

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

MaXL

Дата 24.1.2008, 09:04 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

archimed7592, я пробовал писать и так но оно всё равно ничего не дало(относительно этой ошибки), ошибка как появлялась, так и осталась появляться.

--------------------

MaXL

ptr

Дата 24.1.2008, 09:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 661
Регистрация: 31.5.2006
Где: Новосибирск

Репутация: 1
Всего: 14

MaXL, индексация в массивах начинается с 0.

--------------------

Единственный способ определить границы возможного - это выйти за эти границы, в невозможное.
Артур Кларк.

_stranger_

Дата 24.1.2008, 11:28 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 52
Регистрация: 3.10.2006
Где: город-герой Киев

Репутация: 2
Всего: 2

Цитата(ptr @ 24.1.2008, 09:30

)

MaXL, индексация в массивах начинается с 0.

т.о. неоднократный выход за пределы массивов и конечно

Код


delete []left;
delete []right;

MaXL

Дата 24.1.2008, 11:43 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

ptr, пасиб, но это я знаю.
Просто у меня не получилось реализовать эту сортировку с массивами где индексация идёт с нуля =( (привык к Паскалю).
Знал о том что индексация с нуля начинается, а вот даже и не задумывался =( вот сделал, вроде бы не ругается.
Вот изменённые куски процедуры Merge:

Код


        //.....
        left = new int[n1 + 2];
        right = new int[n2 + 2];
       //......
       delete []left;
       delete []right;

Ну и ошибка с массивом arr решилась также:

Код


   int arr[maxN + 1];

Всем спасибо. Вопрос решён!

Это сообщение отредактировал(а) MaXL - 24.1.2008, 11:45

--------------------

MaXL

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »