主程序main.cpp
#include "stdafx.h" #include
#include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼樹 hlTable *codeTable = buildTable(codeTree);//建立編碼表 encode(codeTable,"I love FishC.com!");//對輸入的字元串進行編碼 decode(codeTree,"0011111000111");//解碼 system("pause"); return 0; }
兩個頭文件:
huffman.h:定義了哈夫曼樹和編碼表的結構
#pragma once
#ifndef _HUFFMAN_H
#define _HUFFMAN_H typedef struct _htNode{ char symbol; struct _htNode *left,*right; }htNode; typedef struct _htTree{ htNode *root; }htTree; typedef struct _hlNode{ char symbol; char *code; struct _hlNode *next; }hlNode; typedef struct _hlTable{ hlNode *first; hlNode *last; }hlTable; htTree *buildTree(char *str); hlTable *buildTable(htTree *huffmanTree); void encode(hlTable *table, char *stringToEncode); void decode(htTree *tree, char *stringToDecode);
#endif
queue.h：定義了有序隊列的結構，將字元按優先級排列，即頻率從小到大排列，val是樹節點，直接由隊列建立起哈夫曼樹
#pragma once #ifndef _PQUEUE_H #define _PQUEUE_H #include "huffman.h" #define MAX_SZ 256 #define TYPE htNode * typedef struct _pQueueNode{ TYPE val; unsigned int priority; struct _pQueueNode *next; }pQueueNode; typedef struct _pQueue{ unsigned int size; pQueueNode *first; }pQueue; void initPQueue(pQueue **queue); void addPQueue(pQueue **queue, TYPE val, unsigned int priority); TYPE getQueue(pQueue **queue);
#endif
兩個cpp文件實現兩個頭文件聲明的函數：
huffman.cpp
#include "stdafx.h" #include "queue.h"
#include "huffman.h"
#include
#include
#includehtTree *buildTree(char *str) { int *probability = (int *)malloc(sizeof(int) * 256);
//初始化
for (int i = 0; i < 256; i++) { probability[i] = 0; }
//統計待編碼的字元串各個字元出現的次數 for (int j = 0; str[j] != ''; j++) { probability[str[j]]++; }
//定義隊列的頭指針
pQueue *huffmanQueue; initPQueue(&huffmanQueue); //填充隊列 for (int k = 0; k < 256; k++) { if (probability[k] != 0) { htNode *aux = (htNode *)malloc(sizeof(htNode)); aux->left = NULL; aux->right = NULL; aux->symbol = (char)k; addPQueue(&huffmanQueue, aux, probability[k]); } } free(probability); //生成哈夫曼樹 while (huffmanQueue->size != 1) { unsigned int newPriority = huffmanQueue->first->priority + huffmanQueue->first->next->priority; htNode *aux = (htNode *)malloc(sizeof(htNode)); aux->left = getQueue(&huffmanQueue); aux->right = getQueue(&huffmanQueue); addPQueue(&huffmanQueue, aux, newPriority); } htTree *tree = (htTree *)malloc(sizeof(htTree)); tree->root = getQueue(&huffmanQueue); return tree; } void traverseTree(htNode *treeNode,hlTable **table,int k,char code[256]) { if (treeNode->left == NULL&&treeNode->right == NULL) { code[k] = ''; hlNode *aux = (hlNode *)malloc(sizeof(hlNode)); aux->code = (char *)malloc(sizeof(char)*(strlen(code) + 1)); strcpy(aux->code,code); aux->symbol = treeNode->symbol; aux->next = NULL; if ((*table)->first == NULL) { (*table)->first = aux; (*table)->last = aux; } else { (*table)->last->next = aux; (*table)->last = aux; } } if (treeNode->left != NULL) { code[k] = '0'; traverseTree(treeNode->left,table,k+1,code); } if (treeNode->right != NULL) { code[k] = '1'; traverseTree(treeNode->right, table, k + 1, code); } } hlTable *buildTable(htTree *huffmanTree) { hlTable *table = (hlTable *)malloc(sizeof(hlTable)); table->first = NULL; table->last = NULL; char code[256]; int k = 0; traverseTree(huffmanTree->root,&table,k,code); return table; } void encode(hlTable *table, char *stringToEncode) { hlNode *traversal; printf("Encoding......
Input string:
%s
Encoded string :
",stringToEncode); for (int i = 0; stringToEncode[i] != ''; i++) { traversal = table->first; while (traversal->symbol != stringToEncode[i]) traversal = traversal->next; printf("%s", traversal->code); } printf("
"); } void decode(htTree *tree,char *stringToDecode) { htNode *traversal = tree->root; printf("
Decoding......
Input string:
%s
Decoded string:
",stringToDecode); for (int i = 0; stringToDecode[i] != ''; i++) { if (traversal->left == NULL&&traversal->right == NULL) { printf("%c", traversal->symbol); traversal = tree->root; } if (stringToDecode[i] == '0') traversal = traversal->left; else if (stringToDecode[i] == '1') traversal = traversal->right; else { printf("The input string is not coded correctly!
"); return; } } printf(""); return; }
queue.cpp：
#include "stdafx.h" #include#include#include "queue.h" void initPQueue(pQueue **queue) { *queue = (pQueue *)malloc(sizeof(pQueue)); (*queue)->first = NULL; (*queue)->size = 0; return; } void addPQueue(pQueue **queue, TYPE val, unsigned int priority) { if ((*queue)->size == MAX_SZ) { printf("
Queue is full.
"); return; } pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode)); aux->priority = priority; aux->val = val; if ((*queue)->size == 0||(*queue)->first==NULL) { aux->next = NULL; (*queue)->first = aux; (*queue)->size = 1; return; } else { if (priority <= -="">first->priority) { aux->next = (*queue)->first; (*queue)->first = aux; (*queue)->size++; return; } else { pQueueNode *iterator = (*queue)->first; while (iterator->next!=NULL) { if (priority <= iterator-="">next->priority) { aux->next = iterator->next; iterator->next = aux; (*queue)->size++; return; } iterator = iterator->next; } if (iterator->next == NULL) { aux->next = NULL; iterator->next = aux; (*queue)->size++; return; } } } } TYPE getQueue(pQueue **queue) { TYPE returnValue; if ((*queue)->size > 0) { returnValue = (*queue)->first->val; (*queue)->first = (*queue)->first->next; (*queue)->size--; } else { returnValue = NULL; printf("
Queue is empty
"); } return returnValue; }
