C语言实现Huffman的编码和解码( 二 ) _字符编码

< size; ++index) {if (nodelist[index] == NULL) {/*从表中找到空位放入新节点*/nodelist[index] = node;break;}}}/*从森林列表弹出权重最低的Huffman树节点*/pNode popMinNodeFromList(pNode nodelist[], int size) {int min = -1;int index;for (index = 0; index < size; ++index) {if (nodelist[index]) {if (min == -1) {min = index;} else {if (nodelist[min]->weight > nodelist[index]->weight) {/*当发现存在更小权重节点时候更新记录*/min = index;}}}}if (min != -1) {pNode node = nodelist[min];nodelist[min] = NULL;return node;}return NULL;}/*通过递归遍历方式为Huffman树中的的所有节点产生Huffman编码*/void generateHuffmanCode(pNode root) {if (root) {if (root->left) {strcpy(root->left->code, root->code);strcat(root->left->code, "0");generateHuffmanCode(root->left);}if (root->right) {strcpy(root->right->code, root->code);strcat(root->right->code, "1");generateHuffmanCode(root->right);}}}/*传入权重表构建Huffman树*/pNode buildHuffmanTree(int times[]) {pNode nodelist[FOREST_SIZE] = { NULL };pNode root = NULL;struct timeval startstamp = startTimestamp();int index;/*创建森林表*/for (index = 0; index < LIST_SIZE; ++index) {if (times[index] > 0) {/*将所有节点逐个放入森林表*/addNodeToList(nodelist, FOREST_SIZE, createDataNode(index, times[index]));}}/*构建Huffman树*/while (1) {pNode left = popMinNodeFromList(nodelist, FOREST_SIZE);pNode right = popMinNodeFromList(nodelist, FOREST_SIZE);if (right == NULL) {/*当森林中只剩下一颗树节点的时候表示整个Huffman树构建完成*/root = left;break;} else {pNode node = createBlankNode(left->weight + right->weight);node->left = left;node->right = right;/*每次从森林表中取出两个最小的节点，并创建新节点重新放入森林表*/addNodeToList(nodelist, FOREST_SIZE, node);}}generateHuffmanCode(root);printf("bulid huffman tree : %lf msc\n", endTimestamp(startstamp));return root;}/*在Huffman树中前进一步*/pNode setpHuffmanTree(pNode root, int flag) {switch (flag) {case NODE_FLAG_LEFT:return root->left;case NODE_FLAG_RIGHT:return root->right;}return NULL;}/*通过后序遍历的方式销毁Huffman树*/void destroyHuffmanTree(pNode root) {if (root) {destroyHuffmanTree(root->left);destroyHuffmanTree(root->right);free(root);}}/*从文件构建Huffman树*/pNode buildHuffmanTreeFromFile(FILE* input) {int times[LIST_SIZE] = { 0 };Byte byte;while (fread(&byte, sizeof(byte), 1, input) == 1) {++times[byte];}return buildHuffmanTree(times);}/*计算Huffman树的权重总值*/int countHuffmanTreeWeightTotal(pNode root) {int total = 0;if (root) {/*只获取有效字符节点*/if (root->type == NODE_TYPE_DATA) {total = root->weight;}total += countHuffmanTreeWeightTotal(root->left);total += countHuffmanTreeWeightTotal(root->right);}return total;}/*通过递归遍历将Huffman树转换成Huffman表*/void convertTreeToList(pNode root, pNode nodelist[]) {if (root) {/*只获取有效字符节点*/if (root->type == NODE_TYPE_DATA) {nodelist[root->data] = root;}convertTreeToList(root->left, nodelist);convertTreeToList(root->right, nodelist);}}/*清理Huffman表中的空指针，并返回实际的表元素数量*/int trimNodeList(pNode nodelist[], int size) {int count = 0;int index;for (index = 0; index < size; ++index) {pNode node = nodelist[index];if (node) {nodelist[count++] = node;}}return count;}/*对文件数据进行Huffman编码*/int encodeFileData(pNode root, FILE* input, FILE* output) {int total = 0;int count = 0;if (root) {Byte byte;int buffer = 0;pNode nodelist[LIST_SIZE] = { NULL };/*将Huffman树转换成Huffman表*/convertTreeToList(root, nodelist);while (fread(&byte, sizeof(byte), 1, input) == 1) {char* cursor = nodelist[byte]->code;while (*cursor) {buffer <<= 1;if (*cursor == '0') {buffer |= 0;} else {buffer |= 1;}++count;if (count == 8) {Byte byte = (Byte)buffer;fwrite(&byte, sizeof(byte), 1, output);count = 0;buffer = 0;++total;}++cursor;}}if (count > 0) {buffer <<= (8 - count);char byte = (char)buffer;fwrite(&byte, 1, 1, output);++total;}}return total;}/*对文件数据进行Huffman解码*/void decodeFileData(pNode root, FILE* input, FILE* output, int count) {if (root) {Byte byte;pNode cursor = root;while (fread(&byte, sizeof(byte), 1, input) == 1) {int buffer = byte;int index;for (index = 0; index