浙江省住房和城乡建设厅 官方网站,域名免费注册地址,建设网站教程论坛,全国做网站的大公司有哪些(数据结构)哈夫曼编码实现#xff08;C语言#xff09; 哈夫曼的编码:从一堆数组当中取出来最小的两个值#xff0c;按照左下右大的进行绘制#xff0c;将两个权值之和#xff0c;放入队列当中#xff0c;然后再进行取出两个小的#xff0c;以此类推#xff0c;直到全部…(数据结构)哈夫曼编码实现C语言 哈夫曼的编码:从一堆数组当中取出来最小的两个值按照左下右大的进行绘制将两个权值之和放入队列当中然后再进行取出两个小的以此类推直到全部结束在根据图根节点到叶子节点每一个分支来得出编码向左0向右1即可得到一个结果。 #include stdio.h
#include stdlib.h// 定义哈夫曼树结点的结构
struct Node {int frequency;char data;struct Node* left;struct Node* right;
};// 创建一个新的哈夫曼树结点
struct Node* newNode(int frequency, char data) {struct Node* node (struct Node*)malloc(sizeof(struct Node));node-frequency frequency;node-data data;node-left NULL;node-right NULL;return node;
}struct MinHeap {int size;int capacity;struct Node** array;
};// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {struct MinHeap* minHeap (struct MinHeap*)malloc(sizeof(struct MinHeap));minHeap-size 0;minHeap-capacity capacity;minHeap-array (struct Node**)malloc(capacity * sizeof(struct Node*));return minHeap;
}// 交换两个结点的位置
void swapNode(struct Node** a, struct Node** b) {struct Node* temp *a;*a *b;*b temp;
}// 维护最小堆的性质
void minHeapify(struct MinHeap* minHeap, int idx) {int smallest idx;int left 2 * idx 1;int right 2 * idx 2;if (left minHeap-size minHeap-array[left]-frequency minHeap-array[smallest]-frequency) {smallest left;}if (right minHeap-size minHeap-array[right]-frequency minHeap-array[smallest]-frequency) {smallest right;}if (smallest ! idx) {swapNode(minHeap-array[smallest], minHeap-array[idx]);minHeapify(minHeap, smallest);}
}// 检查最小堆是否只有一个元素
int isSizeOne(struct MinHeap* minHeap) {return minHeap-size 1;
}// 检查结点是否是叶子结点
int isLeaf(struct Node* root) {return !(root-left) !(root-right);
}// 从最小堆中提取最小值即频率最小的结点
struct Node* extractMin(struct MinHeap* minHeap) {struct Node* temp minHeap-array[0];minHeap-array[0] minHeap-array[minHeap-size - 1];--minHeap-size;minHeapify(minHeap, 0);return temp;
}// 将结点插入最小堆
void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {minHeap-size;int i minHeap-size - 1;while (i node-frequency minHeap-array[(i - 1) / 2]-frequency) {minHeap-array[i] minHeap-array[(i - 1) / 2];i (i - 1) / 2;}minHeap-array[i] node;
}// 构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int frequency[], int size) {struct Node *left, *right, *top;// 创建一个最小堆并初始化struct MinHeap* minHeap createMinHeap(size);// 向最小堆中插入结点for (int i 0; i size; i) {insertMinHeap(minHeap, newNode(frequency[i], data[i]));}// 构建哈夫曼树while (!isSizeOne(minHeap)) {// 从最小堆中取出最小的两个结点作为左子树和右子树left extractMin(minHeap);right extractMin(minHeap);// 创建一个新的结点作为父结点top newNode(left-frequency right-frequency, -);top-left left;top-right right;// 将父结点插入最小堆中insertMinHeap(minHeap, top);}// 最后剩下的结点就是哈夫曼树的根结点return extractMin(minHeap);
}// 打印哈夫曼编码
void printHuffmanCodes(struct Node* root, int arr[], int top) {// 叶子结点是存有字符的结点if (root-left) {arr[top] 0;printHuffmanCodes(root-left, arr, top 1);}if (root-right) {arr[top] 1;printHuffmanCodes(root-right, arr, top 1);}// 如果是叶子结点没有左右子结点则打印编码if (!root-left !root-right) {printf(%c: , root-data);for (int i 0; i top; i) {printf(%d, arr[i]);}printf(\n);}
}int main() {char data[] { a, b, c, d, e };int frequency[] { 5, 9, 12, 13, 16 };int size sizeof(data) / sizeof(data[0]);struct Node* root buildHuffmanTree(data, frequency, size);int arr[100], top 0;printHuffmanCodes(root, arr, top);return 0;
}
