c - 间隔堆的 printf 显示特定输入的意外结果

Question

对不起，如果我的英语不好，我会说韩语作为母语。

我刚刚了解了区间堆，并在 C 中实现了区间堆。

我的代码应该从输入文件接收整数，如果读取整数的值为正，则将该值插入区间堆，如果为负，则应执行最小删除操作。此外，我想在每次插入和删除时在标准输出上打印间隔堆的前序/中序遍历。

这是完整的代码：

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

typedef struct ipair_{
    int min;    //inserted first
    int max;
    int cnt;    //number of data in node
} interval;

typedef struct{
    interval * h;
    int size;
    int cnt;    //number of node
} *iheap;

typedef enum{
    NO_EMPTY=0,
    EMPTY_HEAP
} isEmpty;

void init_heap(iheap h, int n)
{   //initialize heap;
    n++;    // 1_based indices
    h->h = calloc(n, sizeof *h->h);
    h->size = n;
    h->cnt = 0;
}

//parent, child for 1_based_index
inline static int prt(int i)
{
    return i/2;
}

inline static int lch(int i)
{
    return i*2;
}

inline static int rch(int i)
{
    return i*2+1;
}

void insert_aux(iheap h, int cur, int data)
{   //insert to h->h[cur] in accordance with state of node;
    interval *current = h->h + cur;
    if((*current).cnt == 0)
    {
        (*current).min = data;
        (*current).cnt++;
    }
    //else if(h->h[h->cnt].cnt == 1)
    else if((*current).cnt == 1)
    {
        int prev = (*current).min;
        if(data < prev)
        {
            (*current).min = data;
            (*current).max = prev;
        }
        else
        {
            (*current).max = data;
        }
        (*current).cnt++;
    }
    else// if((*current).cnt >= 2)
    {
        current++;
        (*current).min = data;
        (*current).cnt++;
        h->cnt++;
    }
}

void insert(iheap h, int data)
{
    int cur = h->cnt + 1;
    int parent = prt(cur);
    if(data > h->h[parent].max)
    {
        while(data > h->h[parent].max)
        {
            if(cur == 1)
            {
                break;
            }
            //h->h[cur].max = h->h[parent].max;
            insert_aux(h, cur, h->h[parent].max);
            cur = parent;
            parent = prt(parent);
        }
        //h->h[cur].max = data;
        insert_aux(h, cur, data);
    }
    else if(data < h->h[parent].min)
    {
        while(data < h->h[parent].min)
        {
            if(cur == 1)
            {
                break;
            }
            //h->h[cur].min = h->h[parent].min;
            insert_aux(h, cur, h->h[parent].min);
            cur = parent;
            parent = prt(parent);
        }
        //h->h[cur].min = data;
        insert_aux(h, cur, data);

    }
    else
    {
        insert_aux(h, cur, data);
    }
    /*/
    interval *cur = h->h + h->cnt +1;   // +1 means 1_based indices
    interval *parent = h->h + (h->cnt+1)/2;
    if((*cur).cnt == 0)
    {
        (*cur).min = data;
        (*cur).cnt++;
    }
    //else if(h->h[h->cnt].cnt == 1)
    else if((*cur).cnt == 1)
    {
        int prev = (*cur).min;
        if(data < prev)
        {
            (*cur).min = data;
            (*cur).max = prev;
        }
        else
        {
            (*cur).max = data;
        }
        (*cur).cnt++;
    }
    else// if((*cur).cnt >= 2)
    {
        cur++;
        (*cur).min = data;
        (*cur).cnt++;
        h->cnt++;
    }
    /*/
}

void preorder(iheap h, int i)
{
    if(h->h[i].cnt)
    {
        if(h->h[i].cnt == 1)
        {
            printf(" (%d)", h->h[i].min);
        }
        else
        {
            printf(" (%d,%d)", h->h[i].min, h->h[i].max);
        }
        preorder(h, lch(i));
        preorder(h, rch(i));
    }
}

void printPreorder(iheap h)
{
    printf("preorder:");
    preorder(h, 1);
    putchar(10);
}

void inorder(iheap h, int i)
{
    if(h->h[i].cnt)
    {
        inorder(h, lch(i));
        if(h->h[i].cnt == 1)
        {
            printf(" (%d)", h->h[i].min);
        }
        else
        {
            printf(" (%d,%d)", h->h[i].min, h->h[i].max);
        }
        inorder(h, rch(i));
    }
}

void printInorder(iheap h)
{
    printf("inorder:");
    inorder(h, 1);
    putchar(10);
}

isEmpty deleteMin(iheap h, int * buf)
{
    int p, last, cur, temp;
    _Bool rch_lower;
    if(!h->cnt)
    {
        if(h->h[0].cnt == 0)
        {
            return EMPTY_HEAP;
        }
        else if(h->h[0].cnt == 1)
        {
            *buf = h->h[0].min;
            h->h[0].cnt--;
            return NO_EMPTY;
        }
    }
    *buf = h->h[0].min;
    last = h->cnt + 1;
    p = h->h[last].min;
    h->h[last].cnt--;
    if(h->h[last].cnt == 0)
    {
        h->cnt--;
    }
    cur = 1;
    while(1)
    {
        if(!h->h[lch(cur)].cnt)
        {
            break;
        }
        int minch;
        rch_lower = 0;
        if(h->h[rch(cur)].cnt == 0)
        {
            minch = h->h[lch(cur)].min;
        }
        else
        {
            if(h->h[lch(cur)].min > h->h[rch(cur)].min)
            {
                rch_lower = 1;
                minch = h->h[rch(cur)].min;
            }
            else
            {
                minch = h->h[lch(cur)].min;
            }
        }
        if(!(p>minch))
        {
            break;
        }
        h->h[cur].min = minch;
        if(rch_lower)
        {
            cur = rch(cur);
        }
        else
        {
            cur = lch(cur);
        }
        if(p > h->h[cur].max)
        {
            temp = p;
            p = h->h[cur].max;
            h->h[cur].max = temp;
        }
    }
    h->h[cur].min = p;
    return NO_EMPTY;
}

int main(int argc, char * * argv)
{
    int * buf;
    int cnt;
    int temp;

    iheap h = malloc(sizeof *h);

    if(argc != 2)
    {
        printf("usage: %s <filename>", argv[0]);
        exit(EXIT_FAILURE);
    }

    FILE *fp = NULL;
    if((fp = fopen(argv[1], "r")) == NULL)
    {
        //file open failed
        fprintf(stderr, "file open error\n");
        exit(EXIT_FAILURE);
    }

    //file open succeeded

    for(cnt=0; ; cnt++)
    {
        if((fscanf(fp, "%i", &temp)) == EOF)
        {
            break;
        }
    }
    rewind(fp);
    buf = calloc(cnt, sizeof *buf);
    for(int i=0; i<cnt; i++)
    {
        fscanf(fp, "%i", buf+i);
    }

    init_heap(h, cnt);

/*/
    for(int i=0; i<cnt; i++)
    {
        printf("%d ", buf[i]);
    }
    putchar(10);
/*/

    for(int i=0; i<cnt; i++)
    {
        if(buf[i] < 0)
        {
            if(deleteMin(h, &temp))
            {
                puts("공백 트리");
            }
            else
            {
                printPreorder(h);
                printInorder(h);
            }
        }
        else
        {
            insert(h, buf[i]);
            printPreorder(h);
            printInorder(h);
        }
    }

/*/
    for(int i=1; i<cnt+1; i++)
    {
        printf("%d-%d ", h->h[i].min, h->h[i].max);
    }
    putchar(10);
/*/


    return 0;
}

它似乎适用于短输入，但长输入
2 40 3 17 4 32 4 12 3 11 5 10 6 30 4 10 5 11 5 9 4 7 8 8 7 9 15 15 -1 会导致奇怪的输出：

...
(skipped)
...
preorder: (2,40) (3,17) (4,12) (4,10) (5,11) (3,11) (5,9) (4,7) (4,32) (5,10) (8,8) (7,9) (15,30) (10)
inorder: (4,10) (4,12) (5,11) (3,17) (5,9) (3,11) (4,7) (2,40) (8,8) (5,10) (7,9) (4,32) (10) (15,30)
preorder: (2,40) (3,17) (4,12) (4,10) (5,11) (3,11) (5,9) (4,7) (4,32) (5,10) (8,8) (7,9) (15,30) (10) (15) (1041,0) (1919247474,841490490)
inorder: (4,10) (4,12) (5,11) (3,17) (5,9) (3,11) (4,7) (2,40) (8,8) (5,10) (7,9) (4,32) (10) (15,30) (1041,0) (15) (980575588,741615648)
preorder: (3,40) (3,17) (4,12) (4,10) (5,11) (4,15) (5,9) (7,11) (4,32) (5,10) (8,8) (7,9) (15,30) (10)
inorder: (4,10) (4,12) (5,11) (3,17) (5,9) (4,15) (7,11) (3,40) (8,8) (5,10) (7,9) (4,32) (10) (15,30)

我无法弄清楚我写的逻辑是错误的。这是错误的行为，但没有检测到编译错误/分段错误。

标签： cbinary-treeheappriority-queuetree-traversal