Timmy's Blog

Heap.h

struct Heap{
ElemType *heap;
int len;
int MaxSize;
};

void InitHeap(Heap &HBT)
{
HBT.MaxSize=10;
HBT.heap=new ElemType[HBT.MaxSize];
if(!HBT.heap){
cout<<"memory is full , exit !"< exit(1);
}
HBT.len=0;
}

void ClearHeap(Heap &HBT)
{
if(HBT.heap!=NULL){
delete[] HBT.heap;
HBT.heap=NULL;
HBT.len=0;
HBT.MaxSize=0;
}
}

bool EmptyHeap(Heap &HBT)
{
return HBT.len==0;
}

void InsertHeap(Heap &HBT,ElemType item)
{
if(HBT.len==HBT.MaxSize){
int k=sizeof(ElemType);
HBT.heap=(ElemType*)realloc(HBT.heap,2*HBT.MaxSize*k);
if(HBT.heap==NULL){
cout<<"memory is full ,exit !"< exit(1);
}
HBT.MaxSize=2*HBT.MaxSize;
}
int i=HBT.len;
while(i!=0){
int j=(i-1)/2;
if(item>=HBT.heap[j])
break;
HBT.heap[i]=HBT.heap[j];
i=j;
}
HBT.heap[i]=item;
HBT.len++;
}

ElemType DeleteHeap(Heap &HBT)
{
if(HBT.len==0){
cerr<<"heap is empty, exit!"< exit(1);
}
ElemType temp=HBT.heap[0];
HBT.len–;
if(HBT.len==0)
return temp;
ElemType x=HBT.heap[HBT.len];
int i=0;
int j=1;
while(j<=HBT.len-1){
if(jHBT.heap[j+1])
j++;
if(x<=HBT.heap[j])
break;
HBT.heap[i]=HBT.heap[j];
i=j;
j=2*i+1;
}
HBT.heap[i]=x;
return temp;
}

Test6.cpp

#include
#include
typedef int ElemType;
#include”Heap.h”
void main()
{
int a[8];
Heap b;
InitHeap(b);
int item,i,x;
cerr<<"input 8 elements: ";
for(i=0;i<8;i++){
cin>>a[i];
InsertHeap(b,a[i]);
}
for(i=0;i<7;i++)
cout< cout< while(!EmptyHeap(b)){
x=DeleteHeap(b);
cout< if(!EmptyHeap(b))
cout<<',';
}
cout< ClearHeap(b);
}

不妨再看看这些相关的日志:

1. 实验七 栈的基本操作
2. 实验四 线性表的顺序表示和实现
3. 实验十  二叉树的基本操作
4. 实验十三  排序算法的应用
5. 实验4 栈的应用-算术表达式计算