Huffman C Бесконечный цикл - PullRequest
Новая
       53

Huffman C Бесконечный цикл

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

У меня есть этот код Хаффмана, который предназначен для возврата кода Хаффмана для каждой буквы в массиве и печати их в алфавитном порядке.Проблема в том, что он не генерирует никаких выходных данных и вместо этого продолжает обработку, пока я не выйду из него вручную.Может кто-нибудь, пожалуйста, помогите мне определить ошибку?Я думаю, что мой код правильный, но я не знаю, откуда исходит бесконечный цикл.

void buildHuffmanTree(char arr[], int freq[]){
    int top = 0;
    for (int i=0;i<strlen(arr);i++){
        push(PQ,newNode(arr[i],freq[i]));
    }
    for (int i=0; i<qTop;i++){
        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);
    }
    struct node* root= pop(PQ);
    printCodes(root,arr2,top);
}

int main(){

    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
    int freq[] = { 5, 9, 12, 13, 16, 45 }; 

    buildHuffmanTree(arr,freq);

    return 0;
}

Вывод, который я ожидаю, таков.Но вместо этого он просто продолжает работать, не выводя ничего.Я уверен, что он правильно передает значения в PQ, поэтому я не знаю, где моя ошибка. 

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

Буду признателен за любые советы по этому поводу.Спасибо.

Ответы [ 2 ]

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

Просто быстрый бег.Похоже, ваша программа попала в бесконечный цикл, где слева никогда не будет NULL. 

#0  0x0000564d16bd086f in minHeapify (node=0x564d1739d340) at huffman.c:44
        right = 0x564d1739d300
        root = 21
        currentNode = 0x564d1739d320
        left = 0x564d1739d300
#1  0x0000564d16bd0a62 in pop (PQ=0x564d16e95540 <PQ>) at huffman.c:88
        node = 0x564d1739d2c0
#2  0x0000564d16bd0c2d in buildHuffmanTree (arr=0x7ffce3f795b2 "abcdef", freq=0x7ffce3f79590) at huffman.c:123
        node2 = 0x564d1739d360
        nodeL = 0x564d1739d2e0
        nodeR = 0x564d1739d320
        i = 2
        top = 0
        root = 0x0
#3  0x0000564d16bd0d3e in main () at huffman.c:139
        arr = "abcdef"
        freq = {5, 9, 12, 13, 16, 45}

Как отлаживать

Скомпилируйте ваш источник с помощью: 

gcc -Wall -ggdb huffman.c -o huffman

Теперь запустите его: 

./huffman

Он застрянет.

Откройте другую командную строку, запустите: 

ps aux | grep "PID\|huffman"

ЗапомнитеЗначение PID вашего процесса Хаффмана.

Теперь используйте gdb от имени root: 

sudo gdb

Присоедините к процессу Хаффмана: 

attach $your_huffman_pid

Выполните следующее, чтобы проверить стек вызовов: 

bt full

Для получения дополнительной информации: GDB cookbook

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

Вот большая проблема: 

for (int i=0;i<strlen(arr);i++){
//             ^^^^^^^^^^^

Функция strlen ожидает, что аргумент будет указателем на первый символ с нулевым символом в конце строка байтов .

Ваш массив символов не строка с нулевым символом в конце, что означает, что функция strlen выйдет за пределы, пытаясь найти терминатор.Выход за пределы приводит к неопределенному поведению .

Простым решением является использование литеральной строки в качестве инициализатора для массива: 

char arr[] = "abcdef";  // Make arr a null-terminated string

Другое и, возможно, более общее решение состоит в том, чтобы передать длину массива нужным функциям и использовать вместо этого этот аргумент.

...