c - 插入部分有序树

Question

我试图在部分有序树中插入一个元素，但是当我试图显示作为数组实现的树时，它不会显示元素。

这是堆结构。我只是暂时让它变得简单。

typedef struct{
    int Elem[SIZE];
    int last;
}Heap;

这是我为插入所做的。

void insertHeap(Heap *HH, int given)
{
    int parent, child, temp;

    if(HH->last < SIZE){
        HH->Elem[HH->last] = given;
        parent = (HH->last - 1) / 2;
        for(child = HH->last ; child >= 0 && HH->Elem[child] <= HH->Elem[parent] ;  child = parent, parent = parent - 1 / 2 ){
            temp = HH->Elem[parent];
            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;
        }
        HH->last++;
    }
}

Answer 1

您的代码进入无限循环。你应该解决两件事:

• 在for循环控件的更新部分计算新的父级时，(parent - 1)应该有括号；
• 您的条件 parent >= 0 将始终为真，因为即使对于 parent == 0，(parent - 1)/2将产生 0，因为根据 C 的整数除法规则，-1/2 为零。

所以:

void insertHeap(Heap *HH, int given)
{
    int parent, child, temp;

    if(HH->last < SIZE){
        HH->Elem[HH->last] = given;
        parent = (HH->last - 1) / 2;
        for (child = HH->last; 
             child > 0 && HH->Elem[child] <= HH->Elem[parent];
             child = parent, parent = (parent - 1) / 2)
        {
            temp = HH->Elem[parent];
            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;
        }
        HH->last++;
    }
}

包含三个长部分的 for 循环看起来有点笨拙。您还可以将变量声明移到更靠近需要变量的地方并立即初始化它们。下面的代码做同样的事情，但在我看来更具可读性，但这当然是个人风格的问题。

void insertHeap(Heap *HH, int given)
{    
    if(HH->last < SIZE){        
        int parent = (HH->last - 1) / 2;
        int child = HH->last;

        HH->Elem[HH->last] = given;

        while (child > 0 && HH->Elem[child] <= HH->Elem[parent]) {
            int temp = HH->Elem[parent];

            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;

            child = parent;
            parent = (parent - 1) / 2;
        }

        HH->last++;
    }
}