C语言数据结构 堆的建立和维护
发布网友
发布时间：2022-04-23 18:19
共1个回答
热心网友
时间：2023-10-12 16:50
2、将堆结构按小顶堆排列
3、输入POP命令提取一个顶元素，存放在数组中。
（删除顶节点，重新初始化堆结构，重新按小顶堆排列）
4、输入PUSH命令将一个数值插入到堆末尾。
（新数值插入数组末尾，用新数组重建堆，重新按小顶堆排列）
5、打印所有POP提取的顶元素#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct node
{
int *data;
struct node *left;
struct node *right;
struct node *brother;
struct node *father;
}NODE;
typedef struct heapTree
{
int size;
int *nums;//节点数值对应的数组
NODE **nodes;//所有的节点指针，用于释放堆
struct node *rootNode;//根节点
struct node *lastNode;//从上往下，从左往右数最后一个节点
}HEAP;
HEAP *initHeap(int *nums,int size);//初始化堆
void recom(NODE *lastNode,int b);//重组堆，按小顶堆排列。先和子女比较，再兄弟和子女比较，再父亲和子女比较。
//参数：lastNode最后一个节点; b避免兄弟间无限循环，b=2跳出兄弟，进行父亲与子女比较,首次调用b传值1
void printfHeap(NODE *rootNode);//测试调试使用：遍历并打印堆数值
void freeHeap(HEAP *heap);//释放堆内存
int getRootNode(HEAP *heap);//取出顶元素
void addRootNode(HEAP *heap,int num);//插入节点元素
int main()
{
int i,m,n,*nums=NULL,*rootNums=NULL,rNumSize=0,xwNum;//xwNum询问数值
char xwStr[5];//询问字符串POP或PUSH
HEAP *heap=NULL;
printf("输入n,m的值：\n");
scanf("%d%d",&n,&m);
nums=(int *)malloc(sizeof(int)*n);
printf("输入%d个数字：\n",n);
for(i=0;i<n;i++)
scanf("%d",&nums[i]);
heap=initHeap(nums,n);
recom(heap->lastNode,1);
//printfHeap(heap->rootNode);//测试：顺序打印节点
printf("等待%d次询问，请输入POP或PUSH命令:\n",m);
while(1)
{
scanf("%s",xwStr);
if(strcmp(xwStr,"POP")==0)
{
rNumSize++;
if(rootNums==NULL)
rootNums=(int *)malloc(sizeof(int)*rNumSize);
else
rootNums=(int *)realloc(rootNums,sizeof(int)*rNumSize);//扩展原取值的存储内存
rootNums[rNumSize-1]=getRootNode(heap);//取出顶元素
//printfHeap(heap->rootNode);//测试：顺序打印节点
}
else if(strcmp(xwStr,"PUSH")==0)
{
scanf("%d",&xwNum);
addRootNode(heap,xwNum);//插入新元素
//printfHeap(heap->rootNode);//测试：顺序打印节点// 插入后重新排序有问题
}
m--;
if(m==0)
break;
}
printf("所有取出的顶端数值为：\n");
for(i=0;i<rNumSize;i++)
printf("%d ",rootNums[i]);
printf("\n");
return 0;
}
void addRootNode(HEAP *heap,int num)//插入节点元素
{
int i,*numsSave=NULL,*nums=heap->nums,size=heap->size;
numsSave=(int *)malloc(sizeof(int)*(size+1));
for(i=0;i<size;i++)
numsSave[i]=nums[i];
nums=NULL;
numsSave[i]=num;//将新元素添加在数组末尾
freeHeap(heap);//释放堆内存
heap=initHeap(numsSave,size+1);//重新初始新的堆
recom(heap->lastNode,1);//重新小顶堆排列
}
int getRootNode(HEAP *heap)//取出顶元素
{
int i,*numsSave=NULL,*nums=heap->nums,size=heap->size,rootNum;
rootNum=*heap->rootNode->data;
*heap->rootNode->data=nums[size-1];//根节点对应值换成数组最后一位地址值
numsSave=(int *)malloc(sizeof(int)*(size-1));
for(i=0;i<size-1;i++)
numsSave[i]=nums[i];
nums=NULL;//原数组空间将在freeHeap函数中一并释放
freeHeap(heap);//释放堆内存
heap=initHeap(numsSave,size-1);//重新初始新的堆
recom(heap->lastNode,1);//重新小顶堆排列
return rootNum;
}
void freeHeap(HEAP *heap)//释放堆内存
{
int i;
for(i=0;i<heap->size;i++)//释放所有节点空间
{
heap->nodes[i]->data=NULL;
heap->nodes[i]->brother=NULL;
heap->nodes[i]->father=NULL;
heap->nodes[i]->left=NULL;
heap->nodes[i]->right=NULL;
free(heap->nodes[i]);
}
free(heap->nums);
heap->nums=NULL;
heap->nodes=NULL;
heap->lastNode=NULL;
heap->rootNode=NULL;
heap->size=0;
free(heap);
}
void printfHeap(NODE *rootNode)//遍历并打印堆数值
{
printf("%d ",*rootNode->data);
if(rootNode->father==NULL && rootNode->left!=NULL)//根节点
printfHeap(rootNode->left);
else if(rootNode->father->left==rootNode && rootNode->father->right!=NULL)//如果第左，那么找右
printfHeap(rootNode->father->right);
else if(rootNode->father->right==rootNode && rootNode->brother->left!=NULL)//如果第右，那么找左的左儿子
printfHeap(rootNode->brother->left);
else
printf("\n");
}
HEAP *initHeap(int *nums,int size)
{
int i;
NODE *newNode=NULL;
HEAP *heap=(HEAP *)malloc(sizeof(HEAP));
heap->rootNode=NULL;
heap->lastNode=NULL;
heap->nodes=(NODE **)malloc(sizeof(NODE *)*size);
heap->nums=nums;
for(i=0;i<size;i++)
{
newNode=(NODE *)malloc(sizeof(NODE));
heap->nodes[i]=newNode;
newNode->data=&nums[i];
newNode->left=NULL;
newNode->right=NULL;
newNode->brother=NULL;
newNode->father=NULL;
if(heap->rootNode==NULL)
heap->rootNode=newNode;
else if(heap->lastNode->father==NULL)//上一个节点为根节点没有兄弟，新节点放在左位置
{
heap->lastNode->left=newNode;
newNode->father=heap->lastNode;
}
else if(heap->lastNode->father->left==heap->lastNode)//上一个非根左节点，新节点放兄弟位置
{
heap->lastNode->brother=newNode;
newNode->brother=heap->lastNode;
newNode->father=heap->lastNode->father;
newNode->father->right=newNode;
}
else if(heap->lastNode->father->right==heap->lastNode)//上一个非根右节点，新节点放兄弟左儿子位置
{
heap->lastNode->brother->left=newNode;
newNode->father=heap->lastNode->brother;
}
heap->lastNode=newNode;
}
heap->size=size;
return heap;
}
void recom(NODE *lastNode,int b)//重组堆，按小顶堆排列。先和子女比较，再兄弟和子女比较，再父亲和子女比较。
//参数：lastNode最后一个节点; b避免兄弟间无限循环，b=2跳出兄弟，进行父亲与子女比较
{
int numSave;
NODE *minNode=NULL,*fNode=lastNode->father,*bNode=lastNode->brother,*lNode=lastNode->left,*rNode=lastNode->right;
if(lNode!=NULL)
{
minNode=lastNode;
if(*minNode->data>*lNode->data)
{
numSave=*minNode->data;
*minNode->data=*lNode->data;
*lNode->data=numSave;
}
}
if(rNode!=NULL)
{
if(*minNode->data>*rNode->data)
{
numSave=*minNode->data;
*minNode->data=*rNode->data;
*rNode->data=numSave;
}
}
if(b==2)
recom(fNode,1);
else if(bNode!=NULL)
recom(bNode,2);
}
