关于学校数据结构课程的一个大作业,我自己写了一段关于创建二叉树并插入50个随机数的代码,但是自己在调试的时候发现并不是每次都能产生50个随机数,请各位大神帮我看一下是哪一部分出了问题?
感激不尽~
#include <iostream>
#include <time.h>
#include <random>
using namespace std;
//Binary Heap; Max Heap;
class BinaryHeap
{
public:
BinaryHeap();
BinaryHeap(int capacity);
~BinaryHeap();
int insert(int value);
int getIndex(int value);
int remove(int value);
void print();
int deleteMin();
bool isEmpty();
private:
void sortUp(int start);
void sortDown(int start, int end);
int *heap;
int capacity;
int size ;
};
BinaryHeap::BinaryHeap()
{
this->size = 0;
this->capacity = 50;
heap = new int[this->capacity];
}
BinaryHeap::BinaryHeap(int capacity)
{
this->size = 0;
this->capacity = capacity;
heap = new int[this->capacity];
}
BinaryHeap::~BinaryHeap()
{
this->size = 0;
this->capacity = 0;
delete[] heap;
}
int BinaryHeap::insert(int value)
{
if (this->size==this->capacity) //The heap is full
{
return -1;
}
if (this->getIndex(value) >= 0)//There is a node which has the same value
{
return 1;
}
heap[this->size] = value;
this->sortUp(this->size);
this->size++;
return 0;
}
int BinaryHeap::getIndex(int value)
{
for (int i = 0; i < this->size; i++)
{
if (value==this->heap[i])
{
return i;
}
}
return -1;
}
int BinaryHeap::remove(int value)
{
int index;
if (this->size==0)
{
return 1;//The heap is empty
}
index = this->getIndex(value);
if (index==-1)
{
return -1;//The heap is not empty,but there is no node which has the value
}
this->heap[index] = this->heap[--this->size];
this->sortDown(index, this->size - 1);
return 0;
}
void BinaryHeap::print()
{
for (int i = 0; i < this->size; i++)
{
cout << "No." << i + 1 << " : " << heap[i] << " " << endl;;
}
}
int BinaryHeap::deleteMin()
{
int s = heap[0];
for (int i = 0; i < this->size; i++)
{
if (s>heap[i])
{
s = heap[i];
}
}
return remove(s);
}
bool BinaryHeap::isEmpty()
{
if (this->size == 0)
{
return true;
}
else
{
return false;
}
}
void BinaryHeap::sortUp(int start)
{
int c = start; //The location of current node
int p = (c - 1) / 2; //The location of parent node
int temp = heap[c]; //The value of current node
while (c>0)
{
if (heap[p] > temp)
{
break;
}
else
{
heap[c] = heap[p];
c = p;
p = (p - 1) / 2;
}
}
heap[c] = temp;
}
void BinaryHeap::sortDown(int start, int end)
{
int c=start; //the location of current node
int l = 2*c + 1; //The location of left child
int temp = heap[c]; //The value of current node
while (l <= end)
{
if (l<end && heap[l]<heap[l+1])
{
l++; //Choose the bigger one between left child and right child
}
if (temp>=heap[l])
{
break;
}
else
{
heap[c] = heap[l];
c = l;
l = 2 * l + 1;
}
}
heap[c] = temp;
}
int main()
{
BinaryHeap *b = new BinaryHeap(50);
default_random_engine random(time(NULL)); //C++ 11
uniform_int_distribution<int> num(0, 999);//C++ 11
cout << "Insert 50 randon number which between 0~999 " << endl ;
for (int i = 0; i <50; i++)
{
b->insert(num(random));
}
cout << "Print: " << endl;
b->print();
cout << endl << endl;
cout << "Is the heap empty? " << endl;
cout << boolalpha << b->isEmpty() << endl << endl;
cout << "Remove minimum" << endl;
switch (int n=b->deleteMin())
{
case 0:
cout << "Success! The min node has been removed!" << endl; break;
case 1:
cout << "Heap is empty! " << endl; break;
}
cout << endl;
cout << "Print: " << endl;
b->print();
system("pause");
return 0;
}