通过从堆中删除值并向堆中插入值来同步文件和堆中的数据

Question

你在这个文件的第一行写一个m数字，代表堆可以有的节点数，然后在下m 行，第 1 行或第 2 行，旁边是要在树中使用的指定编号。

您有 2 个操作（1 和 2）： 1 是添加一个元素，2 是删除最大的一个并显示它。

所以基本上，插入函数与堆函数绑定在一起，在末尾插入数字，然后将其放在前面。

另外，heapify的删除功能是将第一个和最后一个数字交换，然后删除最后一个数字（现在是第一个），但是你需要在另一个文件中打印。

在 pla.txt 文件中，你有这样的东西：

12代表节点数，那么如果我们读取1它会做插入，如果我们读取2它会做删除。我的问题是它不起作用，它只显示地址，而不是显示最大的数字。（数字2操作删除了堆中删除的最大数字，所以会在文件中输入"cur.txt"，18,15,12,8,19）怎么了？

#include <stdio.h>
void swap1(int c,int b)
{
    int aux=c;
    c=b;
    b=aux;
}FILE *g=fopen("cur.txt","w");
void heapify(int a[],int index,int m)
{
    int leftindex=2*index;
    int rightindex=2*index+1;
    int father=index;
    if(leftindex<m&&leftindex>0 && a[leftindex]>a[father])
    {
        father=leftindex;
    }
    if(rightindex<m && rightindex>0&& a[rightindex]>a[father])
    {
        father=rightindex;
    }
    if(father!=index)
    {
        swap1(a[index],a[father] );
        heapify(a,father,m-1);
    }   
}
void heap(int a[], int index)
{
    int parent=(index-1)/2;
    if(a[index]>a[parent] && a[parent]>0)
    {
        swap1(a[index],a[parent]);
        heap(a,parent);
    }
}   

void insertion(int a[],int x,int  m)
{   
        m++;
        a[m-1]=x;
        heap(a,m-1);
}
void deletetion(int a[],int m)
{
    a[1]=a[m-1];
    m=m-1;  
    heapify(a,1,m); 
    fprintf(g,"%d ",a[1]);

}
int main()
{   
    FILE *f=fopen("pla.txt","r");
    int m;
    fscanf(f,"%d",&m);
    int op,x;
    int a[m];
    int z=1;
    while(fscanf(f,"%d",&op)!=EOF)
    {
        if(op==1)
        {
            fscanf(f,"%d",&x);
            insertion(a,x,z);
        }
        else 
        {
            deletetion(a,z);
        }
    }

}

Answer 1

在删除函数中将fprintf(g,"%d ",&a[1]);更改为fprintf(g,"%d ",a[1]);。

还有一些潜在的错误。主要问题是您没有在函数中使用指针。因为 C 不支持传参。因此，您需要在 swap 函数中使用指针，并在 m 参数中使用指针 heapify, 插入和删除函数。

Answer 2

#include <stdio.h>
void swap1(int *c,int *b)
{
    int aux=*c;
    *c=*b;
    *b=aux;
}FILE *g=fopen("cur.txt","w");
void heapify(int a[],int index,int m)
{
    int leftindex=2*index; //=2
    int rightindex=2*index+1; //=3
    int father=index;
    if(leftindex<=m && leftindex>0 && a[leftindex]>a[father])
    {
        father=leftindex;
    }
    if(rightindex<=m && rightindex>0&& a[rightindex]>a[father])
    {
        father=rightindex;
    }
    if(father!=index)
    {
        swap1(&a[index],&a[father] );
        heapify(a,father,m);
    }   
}
void heap(int a[], int index)
{
    int parent=index/2;
    if(a[index]>a[parent] && a[parent]>0)
    {
        swap1(&a[index],&a[parent]);
        heap(a,parent);
    }
}   

void insertion(int a[],int x,int &m)
{   

        a[m]=x;
        heap(a,m);
        m++; 
}
void deletetion(int a[],int &m)
{
    //first time m=4;
    fprintf(g,"%d ",a[1]);
    a[1]=a[m-1];
    m=m-1;  
    heapify(a,1,m); 

}
int main()
{   
    FILE *f=fopen("pla.txt","r");
    int q;
    fscanf(f,"%d",&q);
    int op,x;
    int a[q];
    for(op=1;op<=q;op++)
    {
        a[op]=0;
    }
    int z=1;
    while(fscanf(f,"%d",&op)!=EOF)
    {
        if(op==1)
        {
            fscanf(f,"%d",&x);
            insertion(a,x,z);
        }
        else if(op==2)
        {
            deletetion(a,z);

        }
    }

}

通过从堆中删除值并向堆中插入值来同步文件和堆中的数据

Synchronizing data in a file and a heap by deleting values from a heap and inserting values into a heap

c

heap

tree

file

insertion