Huffman with C，分段默认（核心转储）

Question

我尝试使用二叉树和 2 个队列用 C 实现哈夫曼算法:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define L 71/*Letters in the alphabet*/

typedef struct Node Node;

struct Node {

    int frequency;
    char letter;
    Node *left, *right;
};

typedef struct Queue Queue;

struct Queue {

    int front, rear;
    int size;
    int capacity;
    Node **array;
};

void readFile(char letterArray[L], int letterCount[L], const char* filename);
void fill(int *letterCount);
void findLowest(Node* leafNode, char letterArray[L], int letterCount[L]);
char findFrequency(int letterCount[L]);
Queue* newQueue(int capacity);
Node* newInternalNode(char letter, int f);
void addHeapNode(Queue* Q, Node* HeapNode);
void removeHeapNode(Queue* Heap, int indxToDel);
void buildTree(char letterArray[L], int letterCount[L]);
void printCodes(Node* root, int arr[100], int top);
int isLeaf(Node* root);
int cmpfunc (const void * item1, const void * item2);
int isSizeOne(Queue* queue);
int isEmpty(Queue* queue);
int isFull(Queue* queue);
void addLeaves(Queue *Q1, char letterArray[L], int letterCount[L]);
void enQueue(Queue* Q, Node* item);
Node* deQueue(Queue *Q);
Node* findMin(Queue *Q1, Queue *Q2);
Node* getFront(Queue *Q);

void printArr(int arr[], int n, int frequency);

int main(int argc, char const* argv[]) {

    if (argc != 2) {
        printf("Enter a file");
        return 1;
    }
    char letterArray[L] = {'"', '\'', '(', ')', ',', '-', '.', '/', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                       ':', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
                       'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
                       'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    int letterCount[L];
    fill(letterCount);
    readFile(letterArray, letterCount, argv[1]);
    buildTree(letterArray, letterCount);
    return 0;
}

Queue* newQueue(int capacity) {

    Queue* newQueue = malloc(sizeof(Queue));
    newQueue->front = newQueue->rear = -1;
    newQueue->capacity = capacity;
    newQueue->size = 0;
    newQueue->array = (Node**) malloc(newQueue->capacity * sizeof(Node*));
    return newQueue;
}

Node* newInternalNode(char letter, int f) {

    Node* LeafNode = malloc(sizeof(Node));
    LeafNode->frequency = f;
    LeafNode->letter = letter;
    LeafNode->left = LeafNode->right = NULL;
    return LeafNode;
}

void fill(int *letterCount) {

    int i;

    for (i = 0; i < L; i++) {
        *letterCount = 0;
        letterCount++;
    }
}

void readFile(char letterArray[L], int letterCount[L], const char* filename) {

    FILE *fp;
    int c = 0;
    int i;

    fp = fopen(filename, "r");

    if (fp == NULL) {
        fprintf(stderr, "failure\n");
        exit(1);
    }
    for (;;) {
        c = fgetc(fp);
        if (feof(fp)) {
            break;
        }
        for (i = 0; i < L; i++) {
            if (letterArray[i] == c) {
                letterCount[i] += 1;
            }
        }
    }
    fclose(fp);
}

void addLeaves(Queue *Q1, char letterArray[L], int letterCount[L]) {

    int i = 0;

    for (i = 0; i < L; i++) {
        if (letterCount[i] > 0) {
            Node* LeafNode = malloc(sizeof(Node));
            LeafNode->frequency = letterCount[i];
            LeafNode->letter = letterArray[i];
            LeafNode->left = LeafNode->right = NULL;
            enQueue(Q1, LeafNode);
        }
    }
}

void buildTree(char letterArray[L], int letterCount[L]) {

    int array[100];
    int t = 0;
    Node *left, *right, *top;
    Queue *Q1, *Q2;
    int size = 0;
    Q1 = newQueue(L);
    Q2 = newQueue(L);

    addLeaves(Q1, letterArray, letterCount);
    qsort(Q1->array, Q1->size, sizeof(int), cmpfunc);

    // Run while Queues contain more than one node. Finally, first queue will
    // be empty and second queue will contain only one node
    while (!(isEmpty(Q1) && isSizeOne(Q2))) {
        // Step 3: Dequeue two nodes with the minimum frequency by examining
        // the front of both queues
        left = findMin(Q1, Q2);
        right = findMin(Q1, Q2);
        // Step 4: Create a new internal node with frequency equal to the sum
        // of the two nodes frequencies. Enqueue this node to second queue.
        top = newInternalNode('$', left->frequency+ right->frequency);
        top->left = left;
        top->right = right;
        enQueue(Q2, top);
        }
        Node* root = (Node*)malloc(sizeof(Node));
        root = deQueue(Q2);
        printCodes(root, array, t);
}

// A utility function to check if size of given queue is 1
int isSizeOne(Queue* queue)
{
    return queue->front == queue->rear && queue->front != -1;
}

// A utility function to check if given queue is empty
int isEmpty(Queue* queue)
{
    return queue->front == -1;
}

// A utility function to check if given queue is full
int isFull(Queue* queue)
{
    return queue->rear == queue->capacity - 1;
}

// A utility function to add an item to queue
void enQueue(Queue* Q, Node* item) {

    if (isFull(Q)) return;
    Q->array[++Q->rear] = item;
    Q->size++;
    if (Q->front == -1)
        ++Q->front;
}

// A utility function to remove an item from queue
Node* deQueue(Queue *Q) {
    if (isEmpty(Q)) return NULL;
    Node* temp = Q->array[Q->front];
    if (Q->front == Q->rear)  // If there is only one item in queue
        Q->front = Q->rear = -1;
    else
        ++Q->front;
    return temp;
}

// A utility function to get from of queue
Node* getFront(Queue *Q) {
    if (isEmpty(Q)) return NULL;
    return Q->array[Q->front];
}

/* A function to get minimum item from two queues */
Node* findMin(Queue *Q1, Queue *Q2) {
    // Step 3.a: If second queue is empty, dequeue from first queue
    if (isEmpty(Q1)) {
        return deQueue(Q2);
    }

    // Step 3.b: If first queue is empty, dequeue from second queue
    if (isEmpty(Q2)) {
        return deQueue(Q1);
    }

    // Step 3.c:  Else, compare the front of two queues and dequeue minimum
    if (getFront(Q1)->frequency < getFront(Q2)->frequency) {
        return deQueue(Q1);
    }

    return deQueue(Q2);
}

int cmpfunc (const void * item1, const void * item2) {

    struct Node *a = *(struct Node **)item1; // first dereference gets the pointer to the struct
    struct Node *b = *(struct Node **)item2;
    return( a->frequency - b->frequency ); // second dereference using -> notation gets the id
}

void printCodes(Node* root, int arr[100], int top) {

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

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

    if (isLeaf(root)) {
        printf("'%c' : ", root->letter);
        printArr(arr, top, root->frequency);
        printf("\n");
    }
}

int isLeaf(Node* root) {
    return !(root->left) && !(root->right);
}

void printArr(int arr[], int n, int frequency) {

    int i;
    for (i = 0; i < n; ++i) {
        printf("%1d", arr[i]);
    }
    printf(" (%d * %d)", n, frequency);
}

当我编译并执行这段代码时，我得到了这个错误：

Segmentation fault (core dumped)

segmentation fault line 237 return( a->frequency - b->frequency ); // >second dereference using -> >notation gets the id

任何帮助将不胜感激^^

Answer 1

它在 qsort 内部爆炸了，所以调试起来有点棘手。在调用 qsort 之前尝试在 buildTree 中停止。

初学者：

qsort(Q1->array, Q1->size, sizeof(int), cmpfunc);

应该是：

qsort(Q1->array, Q1->size, sizeof(Node *), cmpfunc);

在 Linux x86_64 上，sizeof(int) 为 4，但指针为 8。这停止了崩溃，之后我得到了某种输出。

我建议使用 printf 或 gdb 一次一步仔细检查，以确保每一步都正确。

Huffman with C，分段默认（核心转储）

Huffman with C , segmentation default (core dumped)

c

segmentation-fault

binary-tree

huffman-code