почему узлы моего кода Хаффмана не отсортированы должным образом?С - PullRequest
Новая
       65

почему узлы моего кода Хаффмана не отсортированы должным образом?С

0 голосов
/ 20 октября 2018

Я пытаюсь отладить мой код Хаффмана и выяснил, когда я вызываю свое buildHuffmanTree и печатаю узлы моего minHeap с помощью функции печати, которую я закомментировал ниже, я получаю Сегментационную ошибку: 11, потому что у меня только 5узлы в моем дереве Хаффмана, когда я ожидаю, что будет 11 из первоначальных 6 букв, плюс 5 внутренних узлов, которые являются суммой их частот.Может кто-нибудь помочь мне разобраться, как это исправить? 

    #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;
}

Когда я запускаю функцию закомментированной печати, я получаю: 

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

, и в результате мойкодировка неверна, и моя программа выводит: 

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

вместо: 

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

Пожалуйста, помогите мне понять, почему все мои узлы перемешиваются, когда я вставляю их в свой minHeap.Спасибо.

1 Ответ

0 голосов
/ 20 октября 2018

PQ - это массив указателей.Когда push вызывается впервые, ни один из этих указателей не был назначен.push выполняет: 

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

В этот момент i больше нуля, но PQ[j] не было присвоено значение.С этого момента поведение программы не определено.

...