c语言priorityqueue用pop

C语言中的priority_queue可以使用pop函数来弹出队列中的元素。具体操作如下所示：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> q;
    q.push(3);
    q.push(4);
    q.push(2);
    cout << "Top element: " << q.top() << endl; // 输出：4
    q.pop();
    cout << "Top element after pop: " << q.top() << endl; // 输出：3
    return 0;
}

在上述代码中，我们首先创建了一个priority_queue对象q，并向其中插入了三个元素3、4、2。然后我们使用q.top()函数获取队列中的最大元素，并使用cout输出。接着我们使用q.pop()函数弹出队列中的最大元素4，再次使用q.top()函数获取队列中的最大元素，并使用cout输出。最终输出结果为4和3。

相关问题

c语言实现哈夫曼编码压缩

哈夫曼编码是一种无损压缩算法，可以通过构建哈夫曼树来实现。

以下是使用C语言实现哈夫曼编码压缩的基本步骤：

1. 统计字符出现的频率，即计算每个字符出现的次数。
2. 将字符频率按照从小到大的顺序排序。
3. 构建哈夫曼树，将字符频率最小的两个节点合并成一个新节点，直到只剩下一个节点为止。
4. 根据哈夫曼树生成每个字符的编码，对于左子树的编码为0，右子树的编码为1。
5. 将每个字符的编码存储到文件中。
6. 将原始数据按照每个字符的编码进行压缩，并将压缩后的数据存储到文件中。

下面是一个简单的示例代码，实现了哈夫曼编码的压缩和解压缩功能：

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

typedef struct node {
    char data;
    int freq;
    struct node *left;
    struct node *right;
} Node;

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

typedef struct {
    char *code;
    char data;
} Code;

Node *createNode(char data, int freq) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->freq = freq;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

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

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

void push(PriorityQueue *queue, Node *node) {
    if (queue->size >= queue->capacity) {
        return;
    }
    queue->data[queue->size] = node;
    int curr = queue->size;
    while (curr > 0 && queue->data[curr]->freq < queue->data[(curr - 1) / 2]->freq) {
        swap(&queue->data[curr], &queue->data[(curr - 1) / 2]);
        curr = (curr - 1) / 2;
    }
    queue->size++;
}

Node *pop(PriorityQueue *queue) {
    if (queue->size <= 0) {
        return NULL;
    }
    Node *node = queue->data[0];
    queue->size--;
    queue->data[0] = queue->data[queue->size];
    int curr = 0;
    while (2 * curr + 1 < queue->size) {
        int child = 2 * curr + 1;
        if (child + 1 < queue->size && queue->data[child + 1]->freq < queue->data[child]->freq) {
            child++;
        }
        if (queue->data[curr]->freq > queue->data[child]->freq) {
            swap(&queue->data[curr], &queue->data[child]);
            curr = child;
        } else {
            break;
        }
    }
    return node;
}

void destroyPriorityQueue(PriorityQueue *queue) {
    free(queue->data);
    free(queue);
}

void destroyNode(Node *node) {
    if (node == NULL) {
        return;
    }
    destroyNode(node->left);
    destroyNode(node->right);
    free(node);
}

Node *buildHuffmanTree(char *data, int *freq, int size) {
    PriorityQueue *queue = createPriorityQueue(size);
    for (int i = 0; i < size; i++) {
        Node *node = createNode(data[i], freq[i]);
        push(queue, node);
    }
    while (queue->size > 1) {
        Node *left = pop(queue);
        Node *right = pop(queue);
        Node *parent = createNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        push(queue, parent);
    }
    Node *root = pop(queue);
    destroyPriorityQueue(queue);
    return root;
}

void generateCodes(Node *node, Code *codes, int top, char *buffer) {
    if (node->left != NULL) {
        buffer[top] = '0';
        generateCodes(node->left, codes, top + 1, buffer);
    }
    if (node->right != NULL) {
        buffer[top] = '1';
        generateCodes(node->right, codes, top + 1, buffer);
    }
    if (node->left == NULL && node->right == NULL) {
        Code code;
        code.data = node->data;
        code.code = (char *)malloc(sizeof(char) * (top + 1));
        memcpy(code.code, buffer, top);
        code.code[top] = '\0';
        codes[node->data] = code;
    }
}

void compressFile(char *inputFile, char *outputFile) {
    FILE *input = fopen(inputFile, "rb");
    if (input == NULL) {
        return;
    }
    FILE *output = fopen(outputFile, "wb");
    if (output == NULL) {
        fclose(input);
        return;
    }
    int freq[256] = {0};
    char buffer[1024];
    int size;
    while ((size = fread(buffer, sizeof(char), 1024, input)) > 0) {
        for (int i = 0; i < size; i++) {
            freq[buffer[i]]++;
        }
    }
    fseek(input, 0, SEEK_SET);
    Node *root = buildHuffmanTree((char *)freq, freq, 256);
    Code codes[256];
    char codeBuffer[256];
    generateCodes(root, codes, 0, codeBuffer);
    fwrite(freq, sizeof(int), 256, output);
    int bitCount = 0;
    char bitBuffer = 0;
    while ((size = fread(buffer, sizeof(char), 1024, input)) > 0) {
        for (int i = 0; i < size; i++) {
            Code code = codes[buffer[i]];
            for (int j = 0; j < strlen(code.code); j++) {
                if (code.code[j] == '1') {
                    bitBuffer |= 1 << (7 - bitCount);
                }
                bitCount++;
                if (bitCount == 8) {
                    fwrite(&bitBuffer, sizeof(char), 1, output);
                    bitBuffer = 0;
                    bitCount = 0;
                }
            }
        }
    }
    if (bitCount > 0) {
        fwrite(&bitBuffer, sizeof(char), 1, output);
    }
    fclose(input);
    fclose(output);
    destroyNode(root);
}

void decompressFile(char *inputFile, char *outputFile) {
    FILE *input = fopen(inputFile, "rb");
    if (input == NULL) {
        return;
    }
    FILE *output = fopen(outputFile, "wb");
    if (output == NULL) {
        fclose(input);
        return;
    }
    int freq[256] = {0};
    fread(freq, sizeof(int), 256, input);
    Node *root = buildHuffmanTree((char *)freq, freq, 256);
    int bitCount = 0;
    char bitBuffer = 0;
    Node *curr = root;
    while (fread(&bitBuffer, sizeof(char), 1, input) > 0) {
        for (int i = 0; i < 8; i++) {
            if (bitBuffer & (1 << (7 - i))) {
                curr = curr->right;
            } else {
                curr = curr->left;
            }
            if (curr->left == NULL && curr->right == NULL) {
                fwrite(&curr->data, sizeof(char), 1, output);
                curr = root;
            }
        }
    }
    fclose(input);
    fclose(output);
    destroyNode(root);
}

int main() {
    compressFile("input.txt", "output.bin");
    decompressFile("output.bin", "output.txt");
    return 0;
}

该示例代码中使用了优先队列来构建哈夫曼树，同时还实现了文件压缩和解压缩的功能。

用C语言写出哈夫曼树的代码和注释

以下是用C语言实现哈夫曼树的代码和注释：

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

// 定义哈夫曼树节点结构体
typedef struct huffman_node {
    int value; // 节点权值
    struct huffman_node *left; // 左子节点指针
    struct huffman_node *right; // 右子节点指针
} HuffmanNode;

// 定义优先队列（小根堆）结构体
typedef struct priority_queue {
    HuffmanNode **nodes; // 节点数组指针
    int size; // 当前队列大小
    int capacity; // 队列容量
} PriorityQueue;

// 创建一个新的哈夫曼树节点
HuffmanNode *new_huffman_node(int value) {
    HuffmanNode *node = (HuffmanNode *) malloc(sizeof(HuffmanNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 交换两个哈夫曼树节点的位置
void swap_nodes(HuffmanNode **a, HuffmanNode **b) {
    HuffmanNode *tmp = *a;
    *a = *b;
    *b = tmp;
}

// 初始化优先队列
PriorityQueue *init_priority_queue(int capacity) {
    PriorityQueue *queue = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    queue->nodes = (HuffmanNode **) malloc(sizeof(HuffmanNode *) * capacity);
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

// 向优先队列插入一个节点
void insert_node(PriorityQueue *queue, HuffmanNode *node) {
    // 如果队列已满则返回
    if (queue->size == queue->capacity) {
        return;
    }
    // 将新节点插入队列末尾
    queue->nodes[queue->size++] = node;
    int index = queue->size - 1;
    // 将新节点上浮到正确的位置
    while (index > 0 && queue->nodes[index]->value < queue->nodes[(index - 1) / 2]->value) {
        swap_nodes(&queue->nodes[index], &queue->nodes[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

// 从优先队列中取出最小的节点
HuffmanNode *pop_min_node(PriorityQueue *queue) {
    // 如果队列为空则返回 NULL
    if (queue->size == 0) {
        return NULL;
    }
    // 取出队列头部节点
    HuffmanNode *min_node = queue->nodes[0];
    // 将队列尾部节点移到头部
    queue->nodes[0] = queue->nodes[--queue->size];
    int index = 0;
    // 将头部节点下沉到正确的位置
    while (index * 2 + 1 < queue->size) {
        int left_child_index = index * 2 + 1;
        int right_child_index = index * 2 + 2;
        int min_child_index = left_child_index;
        if (right_child_index < queue->size && queue->nodes[right_child_index]->value < queue->nodes[left_child_index]->value) {
            min_child_index = right_child_index;
        }
        if (queue->nodes[min_child_index]->value >= queue->nodes[index]->value) {
            break;
        }
        swap_nodes(&queue->nodes[index], &queue->nodes[min_child_index]);
        index = min_child_index;
    }
    return min_node;
}

// 构建哈夫曼树
HuffmanNode *build_huffman_tree(int *weights, int size) {
    PriorityQueue *queue = init_priority_queue(size);
    // 将所有树叶节点插入优先队列
    for (int i = 0; i < size; i++) {
        insert_node(queue, new_huffman_node(weights[i]));
    }
    // 不断取出两个最小的节点合并成一个新节点，直到队列中只有一个节点为止
    while (queue->size > 1) {
        HuffmanNode *left_child = pop_min_node(queue);
        HuffmanNode *right_child = pop_min_node(queue);
        HuffmanNode *new_node = new_huffman_node(left_child->value + right_child->value);
        new_node->left = left_child;
        new_node->right = right_child;
        insert_node(queue, new_node);
    }
    HuffmanNode *root = pop_min_node(queue);
    free(queue->nodes);
    free(queue);
    return root;
}

// 打印哈夫曼树的结构
void print_huffman_tree(HuffmanNode *root, int depth) {
    if (root == NULL) {
        return;
    }
    for (int i = 0; i < depth; i++) {
        printf(" ");
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%d\n", root->value);
    } else {
        printf("+-\n");
        print_huffman_tree(root->left, depth + 1);
        print_huffman_tree(root->right, depth + 1);
    }
}

int main() {
    int weights[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int size = sizeof(weights) / sizeof(weights[0]);
    HuffmanNode *root = build_huffman_tree(weights, size);
    print_huffman_tree(root, 0);
    return 0;
}

以上代码实现了哈夫曼树的构建和打印结构功能。可以通过修改 `weights` 数组中的元素来构建不同的哈夫曼树。