C语言数据结构 堆的建立和维护

Question

Description
用已知的数据建立一个小顶堆，再对询问输出相应的结果。
Input
输入数据有多组
对于每组测试数据，第一行两个整数n和m ( n，m<= 10000)，表示要用n个整数要建立堆，有m个询问。第二行有n个整数。接下来m行，每行为“pop”或者“push x”表示取出堆顶元素和将x插入堆中
Output
对于“pop”询问输出一行，为堆顶元素
Sample Input
5 5
2 1 3 4 5
pop
push 3
pop
push 1
pop
Sample Output
1
2
1

Answer 1

主要函数功能：1、通过输入的数组，建立堆结构
                       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);
}

追问

这是个啥情况

追答

输入验证我没写，所以pish 1错误输入被当成两次询问了。你在main函数while那自己改下好了。

我这两天不在电脑旁，要不等两天后再给你添加验证，你先别输错误命令了。