寻找一种没有STM32动态分配的C语言数据压缩实现

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

typedef struct {
    unsigned char character;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct {
    Node** nodes;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createPriorityQueue(int capacity) {
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->nodes = (Node**)malloc(capacity * sizeof(Node*));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void swap(Node** a, Node** b) {
    Node* temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(PriorityQueue* pq, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (pq->nodes[parent]->frequency <= pq->nodes[index]->frequency) {
            break;
        }
        swap(&pq->nodes[parent], &pq->nodes[index]);
        index = parent;
    }
}

void heapifyDown(PriorityQueue* pq, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < pq->size && pq->nodes[left]->frequency < pq->nodes[smallest]->frequency) {
        smallest = left;
    }
    if (right < pq->size && pq->nodes[right]->frequency < pq->nodes[smallest]->frequency) {
        smallest = right;
    }
    if (smallest != index) {
        swap(&pq->nodes[index], &pq->nodes[smallest]);
        heapifyDown(pq, smallest);
    }
}

void insertPriorityQueue(PriorityQueue* pq, Node* node) {
    if (pq->size == pq->capacity) {
        pq->capacity *= 2;
        pq->nodes = (Node**)realloc(pq->nodes, pq->capacity * sizeof(Node*));
    }
    pq->nodes[pq->size] = node;
    pq->size++;
    heapifyUp(pq, pq->size - 1);
}

Node* extractMin(PriorityQueue* pq) {
    if (pq->size <= 0) {
        return NULL;
    }
    if (pq->size == 1) {
        pq->size--;
        return pq->nodes[0];
    }

    Node* root = pq->nodes[0];
    pq->nodes[0] = pq->nodes[pq->size - 1];
    pq->size--;
    heapifyDown(pq, 0);

    return root;
}

Node* createNode(unsigned char character, int frequency) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->character = character;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

Node* buildHuffmanTree(unsigned char* data, int size) {
    PriorityQueue* pq = createPriorityQueue(size);

    for (int i = 0; i < size; i++) {
        int frequency = 0;
        for (int j = 0; j < size; j++) {
            if (data[j] == data[i]) {
                frequency++;
            }
        }
        insertPriorityQueue(pq, createNode(data[i], frequency));
    }

    while (pq->size > 1) {
        Node* left = extractMin(pq);
        Node* right = extractMin(pq);

        Node* newNode = createNode('$', left->frequency + right->frequency);
        newNode->left = left;
        newNode->right = right;

        insertPriorityQueue(pq, newNode);
    }

    Node* root = extractMin(pq);
    free(pq->nodes);
    free(pq);

    return root;
}

void generateHuffmanCodes(Node* root, unsigned char* code, int top, unsigned char** huffmanCodes) {
    if (root->left) {
        code[top] = '0';
        generateHuffmanCodes(root->left, code, top + 1, huffmanCodes);
    }

    if (root->right) {
        code[top] = '1';
        generateHuffmanCodes(root->right, code, top + 1, huffmanCodes);
    }

    if (!root->left && !root->right) {
        huffmanCodes[(unsigned char)root->character] = (unsigned char*)malloc((top + 1) * sizeof(unsigned char));
        memcpy(huffmanCodes[(unsigned char)root->character], code, top);
        huffmanCodes[(unsigned char)root->character][top] = '\0';
    }
}

void compressData(unsigned char* data, int size, unsigned char** compressedData, int* compressedSize) {
    Node* root = buildHuffmanTree(data, size);

    unsigned char* code = (unsigned char*)malloc(256 * sizeof(unsigned char));
    unsigned char** huffmanCodes = (unsigned char**)malloc(256 * sizeof(unsigned char*));
    memset(huffmanCodes, 0, 256 * sizeof(unsigned char*));

    generateHuffmanCodes(root, code, 0, huffmanCodes);

    int index = 0;
    *compressedSize = 0;
    for (int i = 0; i < size; i++) {
        unsigned char* code = huffmanCodes[data[i]];
        while (*code) {
            (*compressedData)[index++] = *code++;
            (*compressedSize)++;
        }
    }

    free(code);
    free(huffmanCodes);
    free(root);
}

int main() {
    unsigned char data[] = "this is an example for huffman encoding";
    int size = strlen((char*)data);

    unsigned char* compressedData = (unsigned char*)malloc(size * sizeof(unsigned char));
    int compressedSize;

    compressData(data, size, &compressedData, &compressedSize);

    printf("Compressed Data: ");
    for (int i = 0; i < compressedSize; i++) {
        printf("%d ", compressedData[i]);
    }
    printf("\n");

    free(compressedData);
    return 0;
}