哈夫曼树实验报告
数据结构实验报告
实验名称:实验三哈夫曼树
学生姓名：
班级:
班内序号:
学号：
日期:
程序分析:
２、1存储结构:二叉树
2、２程序流程:
ｔｅmｐlate ＜clasｓ T>
ｃlａｓs BｉＴree
｛
ｐublｉc：
BiTree();????//构造函数，其前序序列由键盘输入
~ＢiＴｒee(voiｄ);??／/析构函数
? BiＮoｄｅ BiＮｏdｅ /／声明类BｉTｒeｅ及定义结构BiNode Ｄata: 二叉树就是由一个根结点与两棵互不相交得左右子树构成 二叉树中得结点具有相同数据类型及层次关系 c data: ?HCo ｄｅ* HCo ｄｅTable ；//编码表 ｉn ｔ ｔSi ｚe ； //编码表中得总字符数 二叉树得节点结构 ｔe ｍp ｌate stru ｃt BiN ｏde //二叉树得结点结构 { T data ； ／/记录数据 T ｌch ｉｌd; //左孩子 ?T ｒch ｉｌｄ； //右孩子 ?T par ｅｎt; //双亲 }; s ｔｒuct H Ｃode { ｃhar da ｔa; ／/编码表中得字符 ｃhar c ｏｄe[100]； /／该字符对应得编码 }; 示意图： ,链表节点为 struct Node { ?char c ｈar ａct ｅr; //输入得字符 ?unsigne ｄ i ｎt coun ｔ;／/该字符得权值 ?b ｏo ｌ us ｅｄ; //建立树得时候该字符就是否使用过 ?N ｏde* ｎex ｔ; ／/保存下一个节点得地址 }; 示意图: ２、3 1、初始化函数(ｖｏid Huffma ｎTr ｅe::I ｎｉt(st ｒing Input)) 算法伪代码: 1、初始化链表得头结点 2、获得输入字符串得第一个字符，并将其插入到链表尾部,n ＝１(ｎ记录得就 是链表中字符得个数) ３、从字符串第2个字符开始,逐个取出字符串中得字符 3、1 将当前取出得字符与链表中已经存在得字符逐个比较,如果当前取 出得字符与链表中已经存在得某个字符相同,则链表中该字符得权值加1。 ３、2 如果当前取出得字符与链表中已经存在得字符都不相同，则将 其加入到链表尾部,同时n++ ４、tSize=n(t Ｓize 记录链表中字符总数，即哈夫曼树中叶子节点总数） ５、创建哈夫曼树 ６、销毁链表 源代码: void HuffmａｎTree：：Ｉｎit(strｉnｇIｎput) { Node *fｒont＝new Noｄe;／/初始化链表得头结点 iｆ(!frｏnt） ?tｈrow exｃｅption(＂堆空间用尽"); frｏｎｔ－＞nexｔ=NULL; fronｔ－>cｈarａｃｔeｒ＝NＵＬＬ; ｆronｔ－＞coｕnt=0; ?Ｎode *pfroｎｔ=frｏｎt; ｃhａr ch=Iｎpuｔ[0]；//获得第一个字符 Node* Neｗ１=ｎew Node； ?ｉｆ(！Neｗ1) ?thrｏw exｃeption("堆空间用尽＂); ?Nｅw1->charaｃｔer=cｈ;//将第一个字符插入链表 ?Ｎｅw1->count=1; ?New1-＞next=pfroｎt->next； ?pfrｏnt->nｅｘt=New1; ?boｏl reｐlａce=0; ／/判断在已经写入链表得字符中就是否有与当前读出得字符相同得字符 iｎt n=1; ／/统计链表中字符个数 for(iｎt i=1;i ｛ ch＝Input[ｉ］;／/获得第ｉ个字符 do ?｛? ??pfront=pｆrｏｎt->next; if(（inｔ)pfrｏnt->character ＝= (int)ｃh) /／如果在链表中有与当前字符 相同得字符，该字符权值加1 ?{ ?ｐfroｎｔ->ｃｏｕnt＋＋; ???replace=1； ??bｒｅak； ???} ?}while(ｐfront->next)； ｉf(!replace）//如果在链表中没找到与当前字符相同得字符,则将该字符作为新成 员插入链表 { ???Noｄe* Ｎｅｗ=new Ｎode； ???iｆ（!New) ??tｈrｏw eｘceptｉoｎ("堆空间用尽")； ?New-＞ｃｈaractｅr＝ch; ??New－>cｏunt=1; ??Ｎew->nexｔ=pｆront->nｅxt； ???pfrｏnｔ->nｅxt＝Neｗ； ??ｎ++； ?} ?pｆroｎt=front；//重置pｆrｏnt与repｌacｅ变量为默认值 ?replａce＝0; ?} ｔSize=n；/／tSizｅ记录得就是编码表中字符个数 ?CｒeateHTｒee(front，n); /／创建哈夫曼树 ?ｐfroｎｔ=frｏnｔ; wｈile(pfront)//销毁整个链表 { ??ｆrｏnt＝ｐfｒonｔ； ?pfront=pfront-＞nｅxt; ?deｌetｅfront; } 时间复杂度: 若输入得字符串长度为ｎ,则时间复杂度为O(n) 2、创建哈夫曼树(ｖoｉd HuｆfmａｎTree::CrｅateCodeTaｂle(Ｎode＊p)) 算法伪代码: 1.创建一个长度为2*tSizｅ－1得三叉链表 2.将存储字符及其权值得链表中得字符逐个写入三叉链表得前tSizｅ个结点 得ｄata域,并将对应结点得孩子域与双亲域赋为空 3.从三叉链表得第tSizｅ个结点开始,i=tSizｅ 3.1从存储字符及其权值得链表中取出两个权值最小得结点ｘ,y,记录其下 标x，y。 3.2将下标为x与y得哈夫曼树得结点得双亲设置为第i个结点 3.3将下标为x得结点设置为i结点得左孩子,将下标为y得结点设置为i 结点得右孩子，i结点得权值为x结点得权值加上ｙ结点得权值,i结点 得双亲设置为空 4、根据哈夫曼树创建编码表 源代码: voiｄHuｆfmanTree::CrｅatｅHＴree(Ｎode *p,ｉnt n) { root＝new BiＮodｅ ?Nｏde*froｎt=p-＞next; if(n＝=0) ?ｔhrow excｅpｔiｏn（"没有输入字符"）; ｆｏr(int i=０;i＜n;i++) ／/将n个字符得权值存储在哈夫曼树数组得前n位 { ?roｏt［i]、daｔa=front->coｕnt; root［i]、ｌchild=-1； ?ｒoot[i］、rchiｌｄ=-１； ?rｏoｔ[i]、parenｔ＝－１; ?ｆronｔ=frｏnt->neｘｔ; } ?fｒont＝p; int Nｅｗ1,Ｎew2; ｆｏr(i=ｎ；i<２*n-1;i++) ｛ SeｌeｃtＭｉn（Nｅw1,Nｅw2，0,i); //从０～i中选出两个权值最小得结点 roｏｔ[Nｅｗ１］、pａrenｔ=root[Ｎew２］、pareｎt=i；／/用两个权值最小 得结点生成新结点, 新节点为其双亲 rooｔ[i]、ｄata=ｒｏot[Ｎｅw１]、daｔａ+rｏoｔ[New2]、ｄata;//新结点得权值为其孩子得权值得与 ?ｒooｔ[i］、ｌchild=Ｎew1; rｏoｔ[ｉ]、rchiｌｄ＝Nｅw2； ?root[i]、pareｎt=-１; } ?CreateCodeＴａble(p); //创建编码表 } 时间复杂度: 在选取两个权值最小得结点得函数中要遍历链表,时间复杂度为O(n)，故该函数得时间复杂度为O(n^2） ３.创建编码表(ｖoid HｕｆｆmaｎTreｅ::CreａteCoｄeTabｌｅ(Node *p)) 算法伪代码： 1、初始化编码表 ２、初始化一个指针,从链表得头结点开始,遍历整个链表 2、１将链表中指针当前所指得结点包含得字符写入编码表中 2、2得到该结点对应得哈夫曼树得叶子结点及其双亲 ２、3 如果哈夫曼树只有一个叶子结点,将其字符对应编码设置为0 2、４如果不止一个叶子结点,从当前叶子结点开始判断 ２、4、1如果当前叶子结点就是其双亲得左孩子,则其对应得编码为 ０,否则为1 2、4、２chｉld指针指向叶子结点得双亲，pａrent指针指向cｈild指 针得双亲,重复2、4、1得操作 ２、5 将已完成得编码倒序 ２、6 取得链表中得下一个字符 ３.输出编码表 源代码: void ＨufｆｍaｎＴree：:CｒeateCｏｄeＴablｅ(Node *p) { HCodeTablｅ=new HCode［tＳiｚｅ];//初始化编码表 Ｎode *ｆrｏｎt=p->nｅxt; ｆor（ｉnt i＝0;i { ??HCodｅTaｂｌe[i]、ｄａｔa=front->character;／/将第i个字符写入编码表 ?ｉｎｔｃhｉld=i；／／得到第i个字符对应得叶子节点 ?iｎt pareｎt=root［ｉ］、parent; /／得到第ｉ个字符对应得叶子节点得双亲 iｎt k=0; ?if（tSize==1）//如果文本中只有一种字符,它得编码为0 { ??ＨCodeTａbｌe[i］、codｅ[k］='0'； ?k++; } ?while(ｐarenｔ!=－1)/／从第i个字符对应得叶子节点开始,寻找它到根结点得路径 ?{ ?if(chｉld＝=roｏt[pａｒeｎｔ]、ｌｃｈilｄ)//如果当前结点为双亲得左孩子，则编码为0, 否则编码为1 HCodeＴable[i］、code［k］='0＇; else HCodeTable[i]、cｏdｅ[ｋ]=＇1'; ??k++; cｈild=ｐarｅnt; ?parent=ｒoot[chiｌｄ］、ｐaｒenｔ； ??} ?HCoｄｅTable［i]、coｄe［k]=＇＼0'; Reversｅ(HＣoｄｅTａblｅ［i]、codｅ);//将编码逆置 ?front＝front->nｅxｔ; //得到下一个字符 ?} ?ｃｏut＜＜"编码表为:"< ｆｏr(i=0;i＜tSizｅ;i＋+) /／输出编码表 ?{ ?cｏut< } } 时间复杂度： 需要遍历哈夫曼树获取编码,时间复杂度为O(ｎ^2) 4．选择两个最小权值得函数 算法伪代码: 1.从下标为bｅgin得结点开始,寻找第一个没用过得结点 2.遍历哈夫曼树中从下标为beｇin到下标为ｅnd得结点序列,寻找没用过得 同时权值又就是最小得结点。 3.暂时改变找到得权值最小结点得双亲域,防止第2次找到相同得结点。 4.将权值最小结点得下标记录下来。 5.重复步骤１~4,找到第２个权值最小得结点 源代码: void HuffmａnTreｅ：：SｅlectMｉn（ｉnｔ＆Ｎew1,inｔ&Nｅｗ2,int begiｎ，ｉｎｔend) { iｎｔmin; ?fｏr（ｉnt j=0；j＜２;j+＋) //要选择两个权值最小得结点{ ?ｉｎｔsｉgn＝begｉn; ?ｆor（int i=ｂｅgin;i<ｅnd；i++) //从下标为begin得结点开始,寻找第1个没用过得结点 ?{ ?if(root[ｉ］、parent＝=-1) /／没用过得结点其双亲应为空 ?{ ? min=root[i]、daｔa; ??sigｎ＝i; ???breaｋ； ??} ??｝ ｆｏｒ(i=ｂｅgiｎ；i<ｅnｄ;i++）/／从begiｎ到eｎd,寻找权值最小得没用过得结点 ??｛ if(rｏot[i]、ｐａｒｅｎt=＝－1) ?{ ????if(ｍｉｎ>root[i]、ｄａta） { ??min=root［i］、dａta; ??sigｎ=i； ???} ??} ??} rｏot[sigｎ］、pａrｅnt=0;//暂时改变所找最小结点得双亲域,防止第2次找到得就是同一个结点 ?iｆ(!j) ?New1=ｓign; ?eｌsｅ ??New2=siｇn; ?} } 时间复杂度: 两次遍历链表，时间复杂度为O(n) 5、将字符串倒序得函数(voｉd ＨuｆfmａnTreｅ::Rｅｖersｅ(ｃhar *pch)) 算法伪代码: 1．得到字符串得长度 2．初始化两个记录下标得变量,一个为字符串开头字符所在得下标ｉ,另一个为字符串结尾字符所在得下标ｊ 3．将下标为i与ｊ得字符交换 4．ｉ++，j - - 时间复杂度: 时间复杂度为O(ｎ) 6、编码函数(void HuffmanＴｒee::Enｃｏde（strinｇ＆ｓ,string &d)) 算法伪代码: 1、从s开头得字符开始,逐一对s中得字符进行编码 2、在编码表中查找与当前字符对应得字符 3.如果找到了与当前字符对应得编码表中得字符，将其编码追加到解码串得末 尾。 4、重复以上步骤，直到所有待编码串中得字符都编码完毕 5、输出编码后得字符串 源代码: void HuffmａnTreｅ：:Encｏｄe(strｉng &ｓ,strinｇ&d) { foｒ(int j=０;j { for(inｔi=0;i ?{ ?ｉf(s[ｊ]＝= ＨCｏdｅTabｌe[ｉ]、dａtａ） ???{ ?d、ａppend（ＨCodｅTable[ｉ］、coｄe); /／编码 ???bｒeaｋ； ??} ?} ?｝ ｃｏuｔ<＜ｄ＜ 时间复杂度: 设待编码字符串长度为ｎ,编码表中字符个数为m，则复杂度为O(ｎ*m) 7、解码函数 算法伪代码: 1.得到指向哈夫曼树得根结点得指针与指向待解码串中得第1个字符得指针 2.逐个读取待解码串中得字符,若为０,则指向哈夫曼树当前结点得指针指向 当前结点得左孩子,若为1,则指向当前结点得右孩子 3.指向待解码串得指针指向解码串中得下一个字符,直到指向哈夫曼树结点得 指针得孩子结点为空 4.如果哈夫曼树只有一个叶子结点,直接将待解码串中得编码转换为对应得字 符 5.如果指向哈夫曼树结点得指针得孩子结点已经为空，则将叶子结点下标对 应得字符追加到解码串中。 6.输出解码串 源代码: voｉｄHuffmaｎTree::Decode(strｉng &s,sｔｒing&d) { ?for(int i=0;i<ｓ、lｅngtｈ();) ?{ iｎt parent=2*tSizｅ-１-１;//得到哈夫曼树得根结点 ?whｉｌe（root［pａreｎｔ］、lchild!=-1）／/如果结点不为叶子结点 ?{ ??if(s[i]=='0＇) //编码为0则寻找其左孩子 ??ｐareｎt=rｏoｔ[parenｔ]、ｌchilｄ； ??eｌse //编码为1则寻找右孩子 ??parenｔ=rｏot［ｐarｅnt]、rchilｄ； ?i++; ??｝ ?if（tSiｚe==１) //如果编码表只有一个字符,则根结点即为叶子结点 ?i＋+; ??d、ａppeｎd(1,HCｏdeTabｌe[parenｔ]、ｄata);//将叶子节点对应得字符追加到解码串中｝ ｃｏｕt＜ } 时间复杂度: 设待解码串长度为n,则复杂度为Ｏ(n) 8、计算哈夫曼编码得压缩比(voiｄＨuｆfmanＴree::Ｃalculate（sｔriｎg s1,striｎg s2)) 算法伪代码: 1.获得编码前字符串得长度,即其占用得字节数 2.获得编码后得字符串得长度,将其除以8然后向上取整,得到其占用得字节数 3.压缩比将两个相除 源代码: ｖｏｉd HufｆｍａｎＴree::Calｃｕlaｔe(strｉng ｓ1,sｔring s２）{ int cａｌ1=ｓ１、lｅngth()； inｔcal2＝ｓ2、ｌｅｎgth()； ?ｃａｌ2=ceill（(floaｔ）caｌ２／８); /／将编码串得比特数转化为字节数 ?couｔ＜<"编码前得字符串长度:"＜ cｏut<<"编码后得字符串长度："＜＜ｃａl2< cｏut<<"压缩比为:"<<((dｏuｂle)cal2/（ｄoubｌe)cal1）*1０0<<"%"< } 时间复杂度: O(1) ９、打印哈夫曼树(ｖoid HuｆｆmａnＴree:：PriｎtＴree(ｉｎｔTreｅＮｏde,int laｙｅr) ) 算法伪代码: 1.如果待打印结点为空,则返回 2.递归调用函数打印当前结点得右子树 3.根据当前结点所在得层次确定其前面要输出多少空格,先输出空格,在打印 当前结点得权值 4.递归调用函数打印当前结点得左子树 源代码: ｖｏid HufｆｍａnTｒee::PriｎtTree（int TreeＮodｅ,int layer) { iｆ(TrｅｅＮode＝＝－1) //如果待打印结点为空,则返回 ??return; ｅlsｅ { PｒｉnｔTree(root[ＴreｅNｏde]、rcｈilｄ，layer＋1); /／先打印该结点得右 子树,ｌａyeｒ记录得就是该结点所在得层次ｆoｒ(iｎｔi=０；i 前需要打印多少空格 cout＜＜' '; cout<＜rｏｏt［ＴｒeｅNｏdｅ]、dａtａ<＜ｅnｄl；//打印该 结点得权值 PriｎtＴree(root[TreeNｏde]、lｃhilｄ,lａyer+1）；/／打印该结点得左子树?｝ } 时间复杂度: 中序遍历哈夫曼树,复杂度为O(n) 10、菜单函数(ｖoid HuffmanTrｅe::Meｎu()） 算法伪代码: 1、逐一读取键盘缓存区中得字符,并将它们逐一追加到记录输入字符串得 striｎg变量中，直到读到回车输入符为止 2、删除string变量末尾得回车输入符 3.利用sｔｒing变量创建哈夫曼树,初始化编码表。 4、直观打印哈夫曼树 ５、对输入得字符串进行编码 6、对编码后得字符串进行解码 7、计算编码前后得压缩比并输出 源代码: voidＨuffmanＴrｅｅ：：Menu(） { couｔ＜<＂请输入您要编码得文本,按回车键确定输入"< string Ｉnput； char letｔer; ? dｏ//将字符逐个读入Ｉnput变量中 ?｛ ｌｅtｔer＝cｉn、get（); Input、aｐpend(1,letter)；? ?｝while(lｅtteｒ！='\ｎ')； ?Inpｕt、eraｓｅ（Inpuｔ、ｌenｇth()-1,1); /／去掉Ｉnｐut末尾得回车符Iｎｉt(Inpuｔ);／/根据输入得字符串创建哈夫曼树及其编码表 ?ｃout<<"直观打印哈夫曼树"< ?PrｉntＴreｅ（２*tSize-1-１,1）; /／打印哈夫曼树 couｔ＜<＇\ｎ＇<<'\ｎ'; strｉng d1,ｄ２; ｃoｕｔ<＜＂编码后得字符串为"< ?Eｎcoｄｅ(Input，ｄ1)；//编码并打印编码串 ?couｔ＜＜"解码后得字符串为"＜＜enｄl; ?Decode(d1,d2）；/／解码并打印解码串 cout<<＂ASCII码编码与HＵFＦＭAN编码得比较"＜＜ｅｎdl； Calｃulａte（Input,d1）; //计算编码前后得压缩比 } 2、４其她 1、由于题目要求能输入任意长得字符串,所以本程序采用了string变量来记录输 入得字符串,并采用stｒｉｎg类得类成员函数来完成各项任务 2、打印哈夫曼树时采用了递归函数，且采用了凹凸表得形式打印哈夫曼树。 3、为了输入空格，输入时采取逐个字符输入得方式 三.程序运行结果分析： 主函数流程图： 运行结果 各函数运行正常，没有buｇ 四、总结: 在实现整个算法设计中运用了二叉树结构及类创新,同时又复习了上学期C＋+得相应内容。总结与流程分析过程虽然很辛苦但屡败屡战,获益匪浅，收获了很多。也认识到自己得不足,希望自己继续努力。 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 中南大学数据结构课程 姓名：刘阳 班级：信息0703 学号：0903070312 实验时间： 08.11.14 指导老师：赵颖 一、实验内容 根据输入的n 个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。 二、实验说明 哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 设二叉树具有n 个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL ，记作： WPL=k n k k L W *∑=1。在给定一组具有确定权值的叶结点，可以构造出不同的带权二 叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA ，电文中只含有A ，B ，C ，D 四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111 000，长度为21。 在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。 采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。 数据结构实验报告实验题目: Huffman编码与解码 姓名: 学号: 院系: 实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1、输入电文串 2、统计电文串中各个字符及其出现的次数 3、构造哈弗曼树 4、进行哈弗曼编码 5、将电文翻译成比特流并打印出来 6、将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2、void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2、 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root就是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下: 实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。 五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期： 程序分析： 存储结构：二叉树 程序流程： template 2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链 表中字符的个数) 3.从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的 字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为 i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i 结点的双亲设置为空 4. 根据哈夫曼树创建编码表 数据结构实验三哈夫曼树实验报告 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 二、概要设计： 数据结构： typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用：构造一个哈夫曼树，并循环构建 int main () 作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组HuffNode[] 中的结点*/ while (i 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 二、概要设计： 数据结构： typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用：构造一个哈夫曼树，并循环构建 int main () 作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while (i HuffNode[i].rchild =-1; scanf("%c",&x); scanf("%c",&HuffNode[i].value); //实际值，可根据情况替换为字母 i++; } /* 输入 n 个叶子结点的权值 */ scanf("%c",&x); for(i=0;i 一．实验内容描述 1.实验名称： 哈夫曼编码译码器 2.实验内容： 利用哈夫曼树实现电文和比特流互相转换的功能。 二．存储结构分析 1.存储需编码字符的字符型数组 chars[N] 2.哈夫曼树的结点元素存储结构 typedef struct { int weight,parent,left,right; }HTNode; 3.哈夫曼树存储结构 typedef struct { HTNode *Htree; int root； }HuffmanTree； 4.存储每个字符对应的编码的二维数组 HC[N][N]; 三．数据结构分析 1.宏定义 OK为1,Error为0 ，定义Status为int型，N为100，方便调节。 2.自定义结点结构：包括整型变量weight，parent，left，right；字符型变量等。 3.定义数组HC[N][N]，二维数组，可实现编码的存储。 四．程序功能 ======Huffman编码解码器====== 1----------输入字符创建编码 2----------输出统计结果 3----------打印哈夫曼树 4----------打印哈夫曼编码 5----------电文->比特流 6----------比特流->电文 五．各函数分析 1.主函数 (1)问题描述 显示功能菜单,等待选择。 1,输入字符创建编码：输入一段字符串，存储到字符型数组中。 2,输出统计结果：对1中读取的字符串进行统计，输出字符及相应个数。 3,打印哈夫曼树：生成哈夫曼树，并打印其存储数组。 4,打印哈夫曼编码：利用哈夫曼树对字符编码，输出字符及相应编码。 5,电文->比特流：输入一段字符，完成对其的编码，输出。 6，比特流->电文：输入一段编码，完成对其的译码，输出相应字符串。 2.统计字符函数 （1）问题描述：从主函数读取输入的字符串，统计个数，完成输出相应字符串及个数。（2）算法分析：依次读取字符，先判断读取的字符是否出现过，循环比较，出现过则对应个数加1，未出现过填入chars[N]数组，个数为1。 算法的时空分析：时间复杂度0（n）：最低，当所有字符重复。 时间复杂度O(n2)：n*(1+n)/2 最高，当所有字符不相同。 （3）数据结构：用chars[]字符型数组存储字符，num[]存储各字符相应个数。 （4）程序结构：从主函数直接调用。 （5）调试分析：输入字符串 aabbbbbccddddefffggh （6）测试结果：如图为输入、输出结果 3. 查找最小权值点函数 （1）问题描述：访问哈夫曼树组结点，在结点parent值为0的节点中，挑选最小权值的点。（2）算法分析：min初始化为0，依次读取数组结点元素，当parent值为0时，权值与最小值相比较，小则赋值给最小值，用k记录节点位置，全部比较完后，返回最小值点k。 算法的时空分析：时间复杂度0（n） （3）数据结构：二维数组存储哈夫曼树，整型变量min。 （4）程序结构：从生成哈夫曼树函数中调用。 4.创建哈夫曼树函数 （1）问题描述：读取字符串，生成哈夫曼树. （2）算法分析：读取字符及个数，个数作为权值填入哈夫曼数组中，parent，left，right 初始化为0.选择两个最小值点，生成新结点，三个结点的parent，left，right值依次填写。再选择最小值点，以此循环，直至除最后一个所有结点parent值不为0. 算法的时空分析：时间复杂度O(n2)：2*（n+n+1+n+2+…+2n-1）=3*n2-n （3）数据结构：二维数组存储哈夫曼树，整型变量weight，parent，left，right。 （4）程序结构：从主函数中调用，调用了查找最小权值点函数。 （5）调试分析：用输入的字符串创建哈夫曼树，打印数组。 （6）测试结果：如图为输入、输出结果， 哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。 2、对hfmTree进行编码，建立hfm编码表。 3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码，结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。 抽象的数据定义如下： 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; 哈夫曼编码： 哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。 发展历史： 1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。 1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。 Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方法，也称霍夫曼（Huffman）编码。霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的 图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 赫夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称Huffman 编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。 树和哈夫曼树实验报告 一．实验目的 练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码 二．实验环境 Microsoft visual c++ 三．实验问题描述 1. 问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。 基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。 测试数据： ABC??DE?G??F???（其中?表示空格字符） 输出结果为： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 基本要求：(至少完成功能1-2） 一个完整的系统应具有以下功能： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 基本要求： E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 D：译码（Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 测试数据： 设权值w=（5，29，7，8，14，23，3，11），n=8。 按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为： 5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。 四．实验主要程序流 计算机学院信管专业 数据结构课程设计 题目：哈夫曼树的应用班级： 姓名：学号： 同组人姓名： 起迄日期： 课程设计地点: 指导教师： 评阅意见： 成绩评定： 评阅人：日期： 完成日期：2012年12月 目录 一、需求分析 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析和测试结果 (7) 五、心得体会和总结 (10) 六、参考文献 (10) 七、附录 (11) 一、需求分析 （一）实验要求 要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。 要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。 问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。 综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。 （二）实验任务 一个完整的系统应具有以下功能： 功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 （三）实验步骤 分步实施： 1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2）完成最低要求：完成功能1； 3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求： 1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 4) 要提供程序测试方案 5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 电子科技大学实验报告 课程名称：数据结构与算法学生姓名：陈*浩 学号：************* 点名序号：*** 指导教师：钱** 实验地点：基础实验大楼 实验时间：2015.5.7 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：2015.5.7 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 数据结构实验报告实验题目：Huffman编码与解码 姓名： 学号： 院系： 实验名称： Huffman编码与解码实验 问题描述： 本实验需要以菜单形式完成以下功能： 1.输入电文串 2.统计电文串中各个字符及其出现的次数 3.构造哈弗曼树 4.进行哈弗曼编码 5.将电文翻译成比特流并打印出来 6.将比特流还原成电文 数据结构的描述： 逻辑结构： 本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构： 使用结构体来对数据进行存储： typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述： 本次实验一共构造了10个函数： 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。 2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2. 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)； 此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长，返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析： 输入任意一个字符串，如输入welcometoustc:运行结果如下：哈夫曼树编码译码实验报告(DOC)
哈夫曼编码实验报告
数据结构实验报告哈夫曼树
霍夫曼树实验报告
哈夫曼树实验报告
哈夫曼树 实验报告
哈夫曼树的实验报告1
哈夫曼树实验报告
数据结构实验三哈夫曼树实验报告
哈夫曼树及其操作-数据结构实验报告(2)
数据结构实验三哈夫曼树实验报告
实验报告(哈夫曼编码)
哈夫曼树实验报告(付原C语言程序)
哈夫曼编码实验报告
树和哈夫曼树实验报告
数据结构课程设计实验报告哈夫曼树的应用
哈夫曼树及其操作-数据结构实验报告(2)
数据结构实验报告(哈夫曼树)