Доступ к памяти вне массива, дерева двоичной кучи - PullRequest
Новая
       28

Доступ к памяти вне массива, дерева двоичной кучи

0 голосов
/ 03 декабря 2011

Для класса я давал задание взять данные из командной строки и создать дерево кучи с вводом. Числа считываются из командной строки.

Например:

Пример ввода:

. / Heapify 2 9 7 6 5 8

Пример вывода:

9 6 8 2 5 7

Я так много работаю, и кажется, что каждый ввод с 6 числами или меньше работает нормально. Если на входе 7 или более чисел, подобных этому:

Пример ввода:

. / Heapify 3 10 8 7 5 9 6

Мой вывод:

32767 10 9 6 8 7 5

что-то идет не так. Очевидно, что я либо использую много памяти в моей программе и получаю число «дерьмо», либо я обращаюсь к памяти вне моего массива, что приводит к другому числу «дерьмо». Я думал о том, что может быть не так, но я просто не уверен. Любая помощь будет оценена.

Если у вас есть вопросы или вам нужна ясность, не стесняйтесь их задавать. 

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

void heap(int *array, int n);

int main(int argc, char* argv[]){

    int array[argc+1];
    int length = argc+1;

    for(int i = 1; i < length-1; i++){
        array[i]=atoi(argv[i]);
    }

    array[0]= -1;
    cout << "unheapified array: ";
    for(int k = 1; k < length-1; k++){
        cout << array[k] << " ";
    }
    cout << endl;
    heap(array, length);

    cout << "heapified array: ";
    for(int k = 1; k < length-1; k++){
        cout << array[k] << " ";
    }
    cout << endl;
return 0;
}

void heap(int *array, int n){
    int i, v, j,k;
    bool heap;

    for(int i=(n/2); i>0; --i){
        k = i;
        v = array[k];
        heap = false;

        while(heap == false && (2*k) <= n-1){
            j = 2*k;
            if(j<n){
                if(array[j] < array[j+1])
                    j += 1;
            }
            if (v >= array[j])
                heap = true;
            else{
                array[k] = array[j];
                k = j;
            }
        }       
        array[k] = v;   
    }
}

1 Ответ

1 голос
/ 03 декабря 2011

Измените вашу heap функцию следующим образом: 

    while(heap == false && (2*k) <= n-1){
        j = 2*k;
        if(j<n){
            assert((j+1)<n); // ADDED THIS
            if(array[j] < array[j+1])
                j += 1;
        }

Вы увидите, что assert сработает. Так что array[j+1] не в конце.

...