Huffman Tree.zip

#include <stdio.h> #include "HT.h" #include<string.h> #include <stdlib.h> #include "Common.h" void InitTree(HuffmanTree& T, int n) { T = (HuffmanNode*)malloc(sizeof(HuffmanNode) * (2 * n )); for (int i = 1; i < (2 * n - 1); ++i) { T[i].parent = T[i].lchild = T[i].rchild=0; } printf("请输入字符及其权值\n"); for (int i = 1; i <= n; ++i) { scanf("%c %d", &T[i].data, &T[i].weight); getchar(); } } void sort(HuffmanTree T, int& lchild, int& rchild, int m) { int mini = OTF; for (int i = 1; i < m; i++) { if (T[i].weight < mini && T[i].parent == 0) { mini = T[i].weight; lchild = i; } } mini = OTF; for (int i = 1; i < m; i++) { if (T[i].weight < mini && T[i].parent == 0 && T[i].weight != T[i].lchild) { mini = T[i].weight; rchild = i; } } } void CreateTree(HuffmanTree& T, int n) { InitTree(T, n); for (int i = n; i < 2 * n - 1; i++) { int lchild = 0; int rchild = 0; sort(T, lchild, rchild, i); T[lchild].parent = i; T[rchild].parent = i; T[i].lchild = lchild; T[i].rchild = rchild; T[i].weight = T[lchild].weight+ T[rchild].weight; } } void InitCode(HuffmanTree T, HuffmanCode& C, int n) { C = new HuffmanCodeNode[n]; for (int i = 0; i < n; i++) { C[i].data = T[i].data; } } void creatCode(HuffmanTree T, HuffmanCode& C, int n) { InitCode(T, C, n); for (int i = 0; i < n; i++) { char* cd; cd = new char[n]; cd[n - 1] = '\0'; int end = T[i].parent; int start = n - 1; int nowi = i; while (end != 0) { start--; if (T[end].lchild == nowi) cd[start] = '0'; else cd[start] = '1'; nowi = end; end = T[end].parent; } C[i].code = new char[n - start]; strcpy(C[i].code, &cd[start]); delete []cd; } }