数据结构-哈弗曼

《数据结构-哈弗曼》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、AU瑯遂上舅实验报告（2014/2015学年第一学期）课程名称数据结构实验名称二叉树的基本操作及哈夫曼编码系统的实现实验时间2015年10月30口指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院（系）专业问题陈述1.在二叉链表上实现二叉树运算2.实现哈夫曼编码和译码系统二.概要设计1.创建一个全局变量string,使川string來保存需要编码的字符。2.创建一个全局变量数组weightcode来保存每个字符所占的权重3.创建一个全局变量数组string*codeArray来保存每个字符的哈夫曼编码template<

2、classT>classHfmTree:publicBinaryTree十public:operatorT()const{returnweight;}TgetW(){returnweight;}voidputW(constT&x)3{weight=x;-}voidSetNull(){this->zoot=NULL;}voidcode(string&c)3{code(this->rootfc);-}voiddecode(strings);private:Tweight;voidcode(BTNode*Z,string

3、&c);templatevoidHfmTree::code(BTNode*z,string&c)3E]voidInpuc(HfmTree&q)m二.详细设计生成编码函数：voidHfmTree::code(BTNode*t,string&c){if(t){if(t->IChild==NULL&&t->rChild==NULL){for(inti=0;ielement==weightArray[iJ)

4、{codeArrayfi]=c;cout«“字符”«s[i]«”的权重是“《weightArray[i]«”，哈弗曼编码是"«codeArray[i]«endl;break;}}}if(t->IChild!=NULL){stringIs;ls.assign(c);ls.append(nOn);codc(t->IChild,Is);}if(t->rChild!=NULL){stringrs;rs.assign(c);rs.append("l");code(t->rChild,rs);对相丿、V的字符串进行编码的函数voidenc

5、ode(){讦(codcArray==NULL){cout

6、译码函数：templatevoidHfmTree::decode(stringdecodeString){if(codeArray==NULL){cout«”尚未编码!n«endl;return;}BTNode*searchNode=this->root;for(inti二0;ivdecodeString」ength();i++){if(decodeString[i]!='O'&&decodeString[i]!=T){cout«”所给码榕式不正确！”vvcndl;return;}if(search

7、Node->IChild==NULL&&searchNode->rChild==NULL){Tvalue=searchNode・>element;for(intj=0;jroot;}if(decodeString[iJ=='0')searchNode=searchNode->IChild;if(decodeStringli]==T)searchNode=searchNode

8、->rChild;}if(searchNode->IChild==NULL&&searchNode->rChild==NULL){Tvalue=searchNode・>element;for(intj=0;j