Проблема реализации минимальных куч в переполнении стека

^

^

 heapify(a,i);

^

 ^

#include <iostream>
using namespace std;
#define HEAPSIZE 10

class Heap
{

int a[HEAPSIZE+1];

Heap()
{
for (j=1;j<(HEAPISZE+1);j++)
{
cin>>a[j];
cout<<"\n";
}
}

int heapify(int i) //i is the parent index, a[] is the heap array
{
int l,r,smallest,temp;
l=2i;
r=2i+1;
if (l<11 && a[l]<a[i])
smallest=l;
else
smallest=i;
if (r<11 && a[r]<a[smallest])
smallest=r;
if (smallest != i)
{
temp = a[smallest];
a[smallest] = a[i];
a[i]=temp;
heapify(smallest);
}
}

int main()
{
int i;

for (i=1;i<=HEAPSIZE;i++)
{
heapify(a,i);
}
}
}

В конечном счете, проблема с этим кодом заключается в том, что он был написан кем-то, кто пропустил главы 1, 2 и 3 «C ++ для начинающих». Давайте начнем с некоторых основ.

#include <iostream>
using namespace std;
#define HEAPSIZE 10

Здесь мы включили заголовок C ++ для ввода-вывода (ввода-вывода). Прекрасное начало. Затем мы выпустили директиву, которая говорит: «Поместите все, что находится в пространстве имен std в глобальное пространство имен «. Это экономит время при наборе текста, но означает, что все тысячи вещей, которые были тщательно разделены на std:: теперь может конфликтовать с именами, которые вы хотите использовать в своем коде. Это плохая вещь (ТМ). Старайтесь избегать этого.

Тогда мы пошли дальше и использовали C-ism, #define. Есть моменты, когда вам все еще нужно делать это в C ++, но лучше этого избегать. Мы вернемся к этому.

Следующая проблема, по крайней мере в опубликованном вами коде, — это неправильное понимание C ++. class,

Язык C, на котором основан C ++, имеет концепцию struct для описания коллекции элементов данных.

struct
{
int id;
char name[64];
double wage;
};

Важно отметить синтаксис — завершающий ‘;’. Это потому, что вы можете одновременно описывать структуру и объявлять переменные ее типа.

struct { int id; char name[64]; } earner, manager, ceo;

Это объявляет структуру, которая не имеет имени типа и переменных earner, manager а также ceo этого типа. Точка с запятой сообщает компилятору, когда мы закончим с этим оператором. Изучение, когда вам нужна точка с запятой после ‘}’, занимает немного времени; обычно вы этого не делаете, но в определении структуры / класса вы это делаете.

C ++ добавил много вещей в C, но одно общее недоразумение заключается в том, что struct а также class как-то радикально отличаются.

C ++ изначально расширил struct концепция, позволяющая вам описывать функции в контексте структуры и позволяющая вам описывать элементы / функции как private, protected или же publicи разрешая наследование.

Когда вы объявляете structпо умолчанию public, class не более чем struct который начинается `частный

struct
{
int id;
char name[64];
double wage;
};

class
{
public:
int id;
char name[64];
double wage;
};

Полученные определения оба идентичны.

Ваш код не имеет спецификатора доступа, поэтому все в вашем классе Heap является приватным. Первая и наиболее проблемная проблема, которую это вызывает: никто не может вызывать ЛЮБЫЕ из ваших функций, потому что они являются закрытыми, их можно вызывать только от других членов класса. Это включает в себя конструктор.

class Foo { Foo () {} };

int main()
{
Foo f;
return 0;
}

Приведенный выше код не удастся скомпилировать, потому что main не является членом Foo и поэтому не может ничего назвать private,

Это подводит нас к другой проблеме. В вашем коде, как опубликовано, main это член Foo. Точка входа в программу C ++ mainне Foo::main или же std::main или же Foo::bar::herp::main, Просто старый добрый int main(int argc, const char* argv[]) или же int main(),

В C с структурами, поскольку C не имеет функций-членов, вы никогда бы не оказались в случае, когда вы использовали непосредственно struct-members, не ставя префикс с указателем или ссылкой на член, например, foo.id или же ptr->wage, В C ++ в функции-члене на переменные-члены можно ссылаться точно так же, как на локальные переменные функции или параметры. Это может привести к некоторой путанице:

class Foo
{
int a, b;

public:
void Set(int a, int b)
{
a = a;  // Erh,
b = b;  // wat???
}
};

Есть много способов обойти это, но одним из наиболее распространенных является префикс переменных-членов с m_,

Ваш код идет вразрез с этим, по-видимому, оригинал в C передал массив в heapify, а массив находился в локальной переменной a, Когда вы сделали a в член, оставляя имя переменной точно таким же, что позволило вам не упустить тот факт, что вам больше не нужно передавать его объекту (и действительно, ваша функция-член heapify больше не принимает массив в качестве указателя, что приводит к одна из ваших ошибок компиляции).

Следующая проблема, с которой мы сталкиваемся, но не являющаяся непосредственно вашей проблемой, это ваша функция Heap(), Во-первых, это личное — вы использовали class и не сказал public еще. Но во-вторых, вы упустили значение этой функции.

В C ++ каждая структура / класс имеет подразумеваемую функцию с тем же именем, что и определение. За class Heap это было бы Heap(), Это конструктор по умолчанию. Эта функция будет выполняться каждый раз, когда кто-либо создает экземпляр Heap без каких-либо параметров.

Это означает, что он будет вызван, когда компилятор создаст кратковременную временную кучу, или когда вы создадите вектор из Heap () и выделите новый временный.

Эти функции имеют одну цель: подготовить хранилище, которое объект занимает для использования. Вы должны стараться избегать как можно большего количества другой работы до позднего времени. С помощью std::cin заполнение членов в конструкторе — одна из самых ужасных вещей, которые вы можете сделать.

Теперь у нас есть основание, чтобы начать писать внешнюю оболочку кода таким образом, чтобы он работал.

Последнее изменение — замена «HEAPSIZE» на перечисление класса. Это часть инкапсуляции. Вы могли бы уйти HEAPSIZE как #define но вы должны показать его в своем классе, чтобы внешний код не полагался на него, а вместо этого мог сказать что-то вроде Heap::Size или же heapInstance.size() и т.п.

#include <iostream>
#include <cstdint> // for size_t etc
#include <array> // C++11 encapsulation for arrays.

struct Heap // Because we want to start 'public' not 'private'.
{
enum { Size = 10 };

private:
std::array<int, Size> m_array; // meaningful names ftw.

public:
Heap() // default constructor, do as little as possible.
: m_array() // says 'call m_array()s default ctor'
{}

// Function to load values from an istream into this heap.
void read(std::istream& in)
{
for (size_t i = 0; i < Size; ++i)
{
in >> m_array[i];
}
return in;
}

void write(std::ostream& out)
{
for (size_t i = 0; i < Size; ++i)
{
if (i > 0)
out << ','; // separator
out << m_array[i];
}
}

int heapify(size_t index)
{
// implement your code here.
}
}; // <-- important.

int main(int argc, const char* argv[])
{
Heap myHeap; // << constructed but not populated.
myHeap.load(std::cin); // read from cin
for (size_t i = 1; i < myHeap.Size; ++i)
{
myHeap.heapify(i);
}
myHead.write(std::cout);

return 0;
}

Наконец, мы столкнулись с простой, фундаментальной проблемой с вашим кодом. C ++ не имеет неявного умножения. 2i это число 2 с суффиксом. Это не то же самое, что 2 * i,

int l = 2 * i;

В вашем коде есть также особенность, которая предполагает, что вы смешиваете реализацию на основе 0 и 1. Выберите один и придерживайтесь его.

— РЕДАКТИРОВАТЬ —

Технически это:

    myHeap.load(std::cin); // read from cin
for (size_t i = 1; i < myHeap.Size; ++i)
{
myHeap.heapify(i);
}

плохая инкапсуляция. Я написал это таким образом, чтобы нарисовать исходную компоновку кода, но хочу отметить, что одна из причин разделения конструкции и инициализации состоит в том, что она позволяет инициализации быть уверенной, что все готово к работе.

Поэтому было бы правильнее переместить вызовы heapify в функцию load. В конце концов, что может быть лучше, если мы добавим новые значения, чтобы сохранить список в порядке все время.

for (size_t i = 0; i < Size; ++i)
{
in >> m_array[i];
heapify(i);
}

Теперь вы упростили API классов, и пользователям не нужно знать о внутреннем механизме.

Heap myHeap;
myHeap.load(std::cin);
myHeap.write(std::cout);