C语言基于结构体实现最大最小堆排序功能异常问题咨询

背景说明 #

我编写了C语言代码，通过自定义结构体element实现最大堆、最小堆，二者最大容量均为1000000，支持读取输入文件中的INSERT、ASCEND、DESCEND命令，通过memcpy拷贝堆后输出排序结果，预期ASCEND输出升序序列、DESCEND输出降序序列。

存在异常 #

• insertmaxheap函数中执行temp=++(*maxn)赋值后，temp与++(*maxn)值不一致
• 插入5个测试元素后执行deleteminheap仅输出3个元素，剩余2个未输出

完整代码 #

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h> 

#define maxelements 1000001

typedef struct {
    int key; 
} element;

int maxn=0; 
int minn=0 ;

element maxheap[maxelements];
element minheap[maxelements]; 
element copyheap[maxelements]; 

void insertmaxheap(element item, int *maxn); 
void insertminheap(element item , int *minn); 
element deletemaxheap(int *maxn); 
element deleteminheap(int *minn); 

int main(int argc, char* argv[]){
    double start,end; 
    start= (double)clock()/CLOCKS_PER_SEC; 
//////////////////////////////////////////////////////////////
    int get,num,j ;
    int maxtemp,mintemp;
    element newitem,item;//element to print 
    char arr[8]; 
    char insert[] = "INSERT"; 
    char ascend[] = "ASCEND"; 
    char descend[] = "DESCEND"; 

    if(argc !=2) 
    {
        printf("usage: ./hw2 input_filename"); 
    }   

    FILE *fp = fopen(argv[1],"r"); 
    // FILE *result = fopen("hw2_result.txt", "w"); 
    if(fp == NULL){
        printf("The input file does not exist.\n");
    }
     
    while(!feof(fp)) {
        get = fscanf(fp,"%s %d",arr,&num); 
        if (!strcmp(arr,insert)) { //putting num into maxheap and minheap 
            printf("%d is number to insert\n", num);  
            newitem.key = num ;
            insertmaxheap(newitem, &maxn); 
            insertminheap(newitem, &minn); 
        }
        if (!strcmp(arr,ascend)) {
            //copy minheap to copyheap and then use  
            memcpy(&copyheap, &minheap,sizeof(minheap)); 
            mintemp = minn;
            printf("%d is total number and i will ascend\n", minn); 

            for(j = 0; j < minn; j++) {
                item = deleteminheap(&minn); 
                printf("%d ",item.key);  
            }
            minn = mintemp; 
        }
        printf("\n"); 

        if (!strcmp(arr,descend)) {
            //copy maxheap to copyheap and then use
            memcpy(&copyheap,&maxheap,sizeof(maxheap)); 
            maxtemp = maxn;
            printf("%d is total number and i will descend\n", maxn); 
            for(j = 0; j < maxn; j++) {
                item = deletemaxheap(&maxn); 
                printf("%d ",item.key );
            }

            maxn = maxtemp; 
        }
        printf("\n"); 
    }
    fclose(fp);
    end = (((double)clock()) / CLOCKS_PER_SEC);
    printf("output written to hw2_result.txt.\n"); 
    printf("running time: %1f\n", (end-start)); 
}

void insertmaxheap(element item, int *maxn) {
    int temp; 
    temp = ++(*maxn); 
    while((temp != 1) && (item.key > maxheap[temp/2].key)) {
        maxheap[temp] = maxheap[temp/2]; 
        temp /= 2; 
    }
    maxheap[temp] = item; 
    printf("i put %d in %d and %d \n",item.key, temp,*maxn);  
}

void insertminheap(element item , int *minn) {
    int i; 
    i = ++(*minn);
    while((i != 1) && (item.key < minheap[i/2].key)) {
        minheap[i] = minheap[i/2]; 
        i /= 2;
    }
    minheap[i] = item;
    printf("i put %d in %d\n", item.key,i);
}

element deletemaxheap(int *maxn) {
    //copy it to copyheap first
    int parent, child; 
    element item,temp;  
    item = copyheap[1]; 
    temp = copyheap[(*maxn)--]; 
    parent = 1;
    child = 2;  
    while(child <= *maxn) {
        if((child < *maxn) && (copyheap[child].key < copyheap[child+1].key)) child++;
        if(temp.key >= copyheap[child].key) break;
        copyheap[parent] = copyheap[child]; 
        parent = child;
        child *= 2;  
    }
    copyheap[parent] = temp; 
    return item; 
}
element deleteminheap(int *minn){
     //copy it to copyheap first
     int parent,child; 
     parent = 1;
     child = 2 ;
     element item, temp;
     item = copyheap[1]; 
     temp = copyheap[(*minn)--]; 
     while(child <= *minn){
         if((child < *minn)&&(copyheap[child].key > copyheap[child+1].key)) child++; 
         if(temp.key <= copyheap[child].key) break;
        copyheap[parent] = copyheap[child]; 
        parent = child; 
        child *= 2 ;
    }
    copyheap[parent] = temp;
    return item;
} 

样本输入 #

INSERT 1
INSERT 2
INSERT 3
INSERT 4
INSERT 5
ASCEND
DESCEND

问题定位及修复方案 #

核心错误1：输出元素不全 #

ASCEND和DESCEND分支的循环条件错误。你已经将执行排序前的堆大小存储在mintemp、maxtemp变量中，但循环时仍用实时变化的minn、maxn作为终止条件：每次调用删除堆顶函数时都会将minn/maxn减1，导致循环提前终止。以5个元素为例：
初始minn=5，j从0开始循环：

• j=0：0<5成立，执行删除后minn=4
• j=1：1<4成立，执行删除后minn=3
• j=2：2<3成立，执行删除后minn=2
• j=3：3<2不成立，循环结束，仅输出3个元素
  修复方式：将循环条件改为j < mintemp、j < maxtemp即可

问题2：insertmaxheap中temp与*maxn值不一致 #

这个问题是参数命名冲突导致的：函数insertmaxheap的形参名为maxn，和全局变量maxn同名，编译时函数内优先使用形参，虽然你传入的是全局变量的地址逻辑上没问题，但如果打印时混淆了全局变量和形参的取值，就会出现数值不一致的错觉。
修复方式：将函数形参改名为p_maxn、p_minn等和全局变量不冲突的名称即可

其他优化建议 #

• memcpy的参数不需要对数组取地址，数组名本身就是首元素地址，改为memcpy(copyheap, minheap, sizeof(minheap))更符合C语言规范
• 读取文件时判断fscanf的返回值，避免读取失败时逻辑异常

内容的提问来源于stack exchange，提问作者chae yeon