HuffmanCode_霍夫曼编码.docVIP

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define NULL 0 typedef int Status; #include stdio.h #include stdlib.h #include iostream.h /*-------------------*/ /***以下是霍夫曼编码相关定义***/ #include string.h typedef unsigned Frequence; #define MAXWEIGHT 65535u //定义频度的存储方式及该存储方式可能的最大值 typedef struct HTNode {Frequence weight; //频度 struct HTNode *parent,*child0,*child1;} HTNode; //霍夫曼树结点 #define CHAR_SET_SIZE 27 //程序支持的字符集大小 Frequence FQTab[CHAR_SET_SIZE]= {186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; //空格及 a ~ z 各字符使用频度的实际统计数据 (单位:千分之) //Total=1000; //程序支持的字符集频度列表 HTNode TreeAry[2*CHAR_SET_SIZE]; //开辟霍夫曼树存储区域 char* Index[CHAR_SET_SIZE]; //程序字符集中所有字符所对应霍夫曼编码的索引表 Status InitTreeAry(HTNode* TreeAry,Frequence* FQTab); //利用频度表初始化霍夫曼树的叶子 void Select(HTNode* TreeAry,HTNode* s1,HTNode* s2); //从正在生长的霍夫曼树中选取最小的两个根结点 Status MakeHuffmanTree(HTNode* TreeAry,unsigned leaves); //从有leaves个带权叶子结点的树生成一棵霍夫曼树 //并且核对权重总和是否前后一致 void MakeCodeIndex(HTNode* TreeAry,char** Index); //由霍夫曼树生成各字符的代码及其索引 void ShowAllCode(char** Index); //显示所有字符的霍夫曼编码 int FormatString(char* p); //格式化字符串,返回经过格式化的字符总数 void Char2Code(char* chr,char* code,char** index); //将字符串chr 译成霍夫曼编码code void Code2Char(char* chr,char* code,HTNode* HTree); //将霍夫曼编码code 译成字符串chr /***以下是霍夫曼编码子程序***/ Status InitTreeAry(HTNode* TreeAry,Frequence* FQTab) //利用频度表FQTab初始化霍夫曼树的叶子 {unsigned change=0; for(++TreeAry; changeCHAR_SET_SIZE; change++,TreeAry++,FQTab++) //数组 0 位禁用 {TreeAry-weight =*FQTab; //填入各结点权重 TreeAry-parent =TreeAry-child0 =TreeAry-child1 =NULL; } //for 生成带权重的叶子结点 for(change=1; changeCHAR_SET_SIZE; change++,TreeAry++) {TreeAry-weight =0; TreeAry-parent =TreeAry-child0 =TreeAry-child1 =NULL; } //for 将剩余的待生长结点全部清零 return OK;} //InitTreeAry static HTNode boot1={MAXWEIGHT,NULL,NULL,NULL}; static HTNode boot2={MAXWEIGHT,NULL,NULL,NULL}; //两个必定是最大的附加结点,用于初始化 void Select(HTNode* TreeAry,HTNode* s1,HTNode* s2) //从正在生长的霍