数据结构-哈弗曼.docx

数据结构-哈弗曼.docxAU瑯遂上舅实验报告(2014/2015学年第一学期)课程名称 数据结构实验名称二叉树的基本操作及哈夫曼编码系统的实现实验时间 2015年10月30口指导单位 计算机科学与技术系指导教师 骆健学生姓名 班级学号学院(系) ,使川string來保存需要编码的字符。创建一个全局变量数组weightcode来保存每个字符所占的权重创建一个全局变量数组string*codeArray来保存每个字符的哈夫曼编码template<classT>classHfmTree:publicBinaryTree<T>十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<T>*Z,string&c);template<classT>voidHfmTree<T>::code(BTNode<T>*z,string&c)3< template<classT>E] voidInpuc(HfmTree<int>&q) m 详细设计生成编码函数:voidHfmTree<T>::code(BTNode<T>*t,string&c){if(t){if(t->IChild==NULL&&t->rChild==NULL){for(inti=0;i<();i++){if(t->element==weightArray[iJ){codeArrayfi]=c;cout«“字符”«s[i]«”的权重是“《weightArray[i]«”,哈弗曼编码是"«codeArray[i]«endl;break;}}}if(t->IChild!=NULL){stringIs;(c);(nOn);codc(t->IChild,Is);}if(t->rChild!=NULL){stringrs;(c);("l");code(t->rChild,rs);对相丿、V的字符串进行编码的函数voidencode(){讦(codcArray==NULL){cout<v”尚未编码!”«endl;return;stringencodeString;cout«”请输入需要编码的字符串:”;cin»encodeString;cout«"\n经过编码的码值为:";for(inti=0;i<();i++){for(intj=0;j<s」ength();j++){if(s[j]==encodeString[i]){cout«codeArrayljJ;break;}}}cout«endl;}对给定字符串进行译码函数:template<classT>voidHfmTree<T>::decode(stringdecodeString){if(codeArray==NULL){cout«”尚未编码!n«endl;return;}BTNode<T>*searchNode=this->root;for(inti二0;ivdecodeString」ength();i++){if(decodeString[i]!='O'&&decodeString[i]!=T){cout«”所给码榕式不正确!”dl;return;}if(searchNode->IChild==NULL&&searchNode->rChild==NULL){Tvalue=searchNode・>element;for(intj=0;j<();j++){if(value==wcightArraylj]){cout«s[j];break;}}searchNode=this->root;}if(decodeString[iJ=='0')searchNode=searchNode->IChild;if(decodeStringli]==T)searchNode=searchNode->rChild;}if(searchNode->IChild==NULL&&searchNode->rChild==NULL){Tvalue=searchNode・>element;for(intj=0;j<gth();j++){if(value==weightArray[