¿por qué son los nodos de mi código de Huffman no clasificada apropiadamente? do

votos
1

Estoy tratando de depurar mi código de Huffman y descubrí la que estoy llamando a mi buildHuffmanTree e impresión de los nodos de mi minHeap utilizando la función de impresión que os comento a continuación, me sale un fallo de segmentación: 11 porque sólo tengo 5 nodos en mi árbol de Huffman cuando estoy esperando que haya hecho 11 de los originales 6 letras, además de los 5 nodos internos que son la suma de sus frecuencias. Podría alguien ayudarme a averiguar cómo solucionar este problema?

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

    #define SIZE 100000

    char arr[SIZE];
    int  freq[SIZE]; 
    int  arr2[SIZE]; 

    int qTop = 0;
    int size=0;

    struct node{

        char data;
        int frequency;
        struct node* left;
        struct node* right;
    };

    struct node* PQ[SIZE];

    struct node* newNode(char data, int frequency){

        struct node* t = (struct node*)malloc(sizeof(struct node)); 
        t->data = data;
        t->frequency= frequency; 
        t->left = NULL; 
        t->right = NULL; 
        return (t); 
    }



void minHeapify(struct node* PQ[], int x){

    int frequency = PQ[x]->frequency;
    char data = PQ[x]->data;
    int i=x;  //the current node
    int j= 2*i; //the left node
    while(j<=qTop){
        if (j<qTop && (PQ[j+1]->frequency < PQ[j]->frequency)){
            j=j+1; //the right node
        }
        if (PQ[j]->frequency < frequency){
            PQ[i]->frequency = PQ[j]->frequency;
            PQ[i]->data = PQ[j]->data;
            i=j;
            j=2*i;
        } else{
            break;
        }
    }

}

void push(struct node* PQ[], struct node* node){

    if (qTop==SIZE){
        printf(PQ OVERFLOW \n);
    } else{
        qTop=qTop+1;
        int i = qTop;
        int j = (int)(i/2);
        while (i > 1 && PQ[j]->frequency > node->frequency){
            PQ[i] = PQ[j];
            i = j;
            j = (int)(i/2);
        }
        PQ[i] = node;
    }
}

struct node* pop(struct node* PQ[]){

    if (qTop==0){
        printf(PQ UNDERFLOW \n);
        return NULL;
    } else{
        struct node* node = PQ[1];
        PQ[1] = PQ[qTop];
        qTop = qTop - 1;
        minHeapify(PQ,1);
        return node;
    }

}

void printCodes(struct node* root, int arr2[], int top) {  

    if (root->left) { 
        arr2[top] = 0; 
        printCodes(root->left, arr2, top + 1); 
    } 

    if (root->right) { 
        arr2[top] = 1; 
        printCodes(root->right, arr2, top + 1); 
    } 

    if (root->left == NULL && root->right == NULL) { 
        printf(%c: , root->data); 
        for (int i = 0; i < top; i++){
            printf(%d, arr2[i]); 
        } 
        printf(\n); 

    } 
}

void buildHuffmanTree(char arr[], int freq[]){

    for (int i=0;i<strlen(arr);i++){
        struct node* node = newNode(arr[i],freq[i]);
        push(PQ,node);
        size++;
    }
    int PQsize=0;
    for (int i=1; i<size;i++){
        PQsize++;
        struct node* node2 = newNode('!',0);
        node2->left = pop(PQ);
        node2->right = pop(PQ);
        struct node* nodeL=node2->left;
        struct node* nodeR=node2->right;
        node2->frequency = nodeL->frequency + nodeR->frequency;
        push(PQ,node2);
    }

    /*
    for (int i=1;i<PQsize,i++){
        printf(%c:%d \n,PQ[i]->data,PQ[i]->frequency);
    }
    */
    struct node* root= pop(PQ);
    int top=0;
    printCodes(root,arr2,top);
}

int main(){

    char arr[] = abcdef; 
    int freq[] = { 5, 9, 12, 13, 16, 45 }; 

    buildHuffmanTree(arr,freq);

    return 0;
}

Cuando ejecuto la impresión que se comenta a cabo la función, me sale:

!:100 
!:55 
!:30 
e:16 
d:13 
b:9 
Segmentation fault: 11

y como resultado, mi codificación está mal y mis productos de los programas:

c: 00
a: 010
b: 011
!: 10
!: 110
e: 111

en lugar de:

a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

Por favor, ayuda a entender por qué todo mi nodo de conseguir involucró una vez que insertarlos en mi minHeap. Gracias.

Publicado el 20/10/2018 a las 10:50
fuente por usuario
En otros idiomas...                            


1 respuestas

votos
1

PQes una matriz de punteros. Cuando pushse llama por primera vez, nada se ha asignado a cualquiera de estos punteros. pushejecuta:

    qTop=qTop+1;
    int i = qTop;
    int j = (int)(i/2);
    while (i > 0 && PQ[j]->frequency > node->frequency){

En este punto, ies mayor que cero, pero PQ[j]no se le ha asignado un valor. El comportamiento del programa es indefinido a partir de este momento.

Respondida el 20/10/2018 a las 11:37
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more