c - 我的数组的值正在以意想不到的方式发生变化

Question

#define HEAP_MAX_SIZE 100
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

int size;
int heap[HEAP_MAX_SIZE];
int printcounter=0;

void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;  
}
/*
*max_heap() performs creates a max heap. (the printf in comments were used for debugging)
*/
void max_heap(int key)
{
    int leftkey = (2*key) +1;
    int rigtkey = (2*key) +2;
    //printf("key is: %d left child index is: %d right child index is: %d \n", key, leftkey, rigtkey);  
    //printf("value at key is: %d left child is: %d right child is: %d \n", heap[key], heap[leftkey], heap[rigtkey]);
    if (key >= 0){
        if (leftkey < size && leftkey != size){
            if (heap[leftkey] > heap[key]){ printf("If %d > %d\n", heap[leftkey], heap[key]);

                    printf("Swap %d and %d\n", heap[leftkey], heap[key]); 
                    swap(&heap[leftkey], &heap[key]);
                    max_heap(key+1);
            }
        }
        if (rigtkey < size && rigtkey != size){ 
            if (heap[rigtkey] > heap[key]){ printf("If %d > %d\n", heap[rigtkey], heap[key]);       

                    printf("Swap %d and %d\n", heap[rigtkey], heap[key]);                   
                    swap(&heap[rigtkey], &heap[key]);
                    max_heap(key+1);
            }
        }
        if (heap[leftkey] < heap[key] && heap[rigtkey] < heap[key]){
            max_heap(key-1);
        }

    }
}

/**
 * heapDelete() removes the biggest integer in the heap and returns it.
 *
 */
int heapDelete()
{
    int largest;    
    int i;  

    max_heap(size/2);
    largest = heap[0];

    ///Shifting the array so the first value is gone. (Should have used a link list instead of an array)
    for (i=0;i<size;i++){
        heap[i] = heap[i+1];
    }       
    size--; 
    printf("Just deleted: %d\n", largest);
    return largest;
}


/**
 *  addHeap(thing2add) adds the "thing2add" to the Heap.
 *
 */
void addHeap(int thing2add)
{   
    if (size == HEAP_MAX_SIZE)
    {
        fprintf(stderr, "Inputing too many values, increase HEAP_MAX_SIZE in intHeap.ca\n");
    }
    else
    {  
        heap[size] = thing2add;
        size++; 
    }
}

堆数组为 {1 5 68 56 2 13 8 5 4 6 3 58 4 3 21 5}

Just deleted: 1

If 21 > 5

Swap 21 and 5

If 58 > 13

Swap 58 and 13

If 4 > 2

Swap 4 and 2

.... (you get the idea)....

Just deleted: 4

Just deleted: 4

Just deleted: 3

Just deleted: 3

Just deleted: 2

交换很好，删除也很好。然而 1 被忽略。另外，程序应该在执行第一个“deleted:”printf 之前完成 max_heap()。为什么它先执行 printf ？和stdder有关系吗？

但这并不总是发生。如果我输入一个小集合，例如:1 5 89 23 4 或 100 5 9 4 56 8 程序将按预期工作。

主要内容如下:

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

extern int pop();
extern void push(int);
extern void addHeap(int);
extern int heapDelete();
extern void printHeap();

int main(int argc, char * argv[])
{
    int value;
    int size=0;
    int i=0;
    while (scanf("%d\n", &value) != EOF) {
        fprintf(stderr, "READING INPUT: %d\n", value);
        size++;
        addHeap(value); 
    }
    /*to print the heap in XML format*/

    printHeap();

    /*Print ends here*/

    /*print the heap in descending order, followed by ascending order (by pushing and popping from a stack)*/
    for (i=0;i<size;i++){
        push(heapDelete());
    }
    for (i=0;i<size;i++){
        printf("%d ", pop());
    }

    exit(0);
    /*Decsending and Ascending order ends here*/
}

Answer 1

我已经玩过你的代码，需要注意的一件事是父级，左子级和右子级必须是连续工作:

parent      at position  i
left child  at position  i + 1
right child at position  i + 2

此外，在您的示例中 {1 2 3} 输出也必须排序 {3 2 1} 而不是 {3 1 2} 。

所以，如果你改变

int leftkey = (2 * key) + 1;
int rigtkey = (2 * key) + 2;

至

int leftkey = key +1; 
int rigtkey = key +2;

它按预期工作

瓦尔特