数据结构试验报告哈夫曼树

1、数据结构实验报告实验题目：Huffman编码与解码姓名:学号:院系:实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完成以下功能：1 输入电文串2. 统计电文串中各个字符及其出现的次数3. 构造哈弗曼树4. 进行哈弗曼编码5. 将电文翻译成比特流并打印出来6. 将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个 结点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：typedef StrllCtint weight;int Pare nt,lc,rc;HTNode,*Huffma nTre

2、e;typedef StrllCt LNodeChar *elem;int stacksize;int top;JSqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。程序结构的描述：本次实验一共构造了 10个函数：1. void HUffTree(HUffma nTree &H T,i nt n ,i nt mun);此函数根据给定的mun个权值构建哈弗曼树，叩用于存放num个权值。2. void SeleCt(HUffma nTree &H T,i nt n,i nt i,i nt & s1,i nt &s2);此函数用于在HT1中选择Parent为0且Weight为最小的

3、两个结点，其 下标分别为s1,s2.3. void Huffma nCodi ng(Huffma nTree HT.char &HC,i nt n);此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC中C4. void Codi ng(Huffma nTree HT.char *HC,i nt root.SqStack &S)此函数用于哈弗曼编码，先序遍历哈弗曼树HT,求得每个叶子结点的编码字 符串，存入数组HC, S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT 中根结点的位置下标。5. void In itStack(SqStack & S);此函数用于初始化一个栈

4、。6. void POP(SqStaCk & S.char e);此函数为出栈操作。7. void PUSh(SqStaCk & S.char e);此函数为进栈操作。8.1 nt StaCkLe ngth(SqStack S);此函数用于求栈长，返回一个int型的值。9.1 nt Fin d(char a.char s,i nt nu m);此函数用于查找字符a在电文串中的位置。1O.int ReCOVer(HUffmanTree HT.char *HC,char String,char a,char b,int n)；此函数用于将比特流还原成电文。调试分析：输入任意一个字符串如输入Welc

5、ometoustc:运行结果如下：5冷冷冷冷冷冷 7 洱 UUUUUU UUU 4J - “ JH-比比比tttttttttt 扫泊曲曲曲曲 -FH CI4164541671051?1112B1弗曼编码，P: 1110 e = Hll1 :I111C: 100D:Ieln:OQOt: 110U:001s : 018该电文的哈弗曼编码为；11100111111100101600011110101601010110100 请输入哈弗曼编码 I按照提示输入任意一个或多个哈弗曼编码，如输入 11111110101：请输入哈弗曼编码;III111I0101 Ivo结果正确。若输

6、入-11111 :请输入哈弗員编码=I111I代码有误!结果正确。实验完成！实验体会和收获:本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，更在栈的运用上 加熟练 对数组的应用也有了提高。源代码:#i nclude#i nclude#i nclude#i nclude typedef StrUCtint weight;int Pare nt,lc,rc; HTNode,*Huffma nTree;typedef StrUCt LNode Char *elem; int stacksize; int top;JSqStack;#defi ne SiZe 20VOid HUffTree(

7、HUffma nTree &H T,i nt n Q,i nt mun);void SeleCt(HUffma nTree &H T,i nt n,i nt i,i nt & s1,i nt &s2);void HUffma nCodi ng(Huffma nTree HT,char *&HC,i nt n);void Codi ng(Huffma nTree HT,char *HC,i nt root,SqStack & S);void In itStack(SqStack & S);void POP(SqStaCk & S,char e);void PUSh(SqStaCk & S.cha

8、r e);int StaCkLe ngth(SqStack S);int Fin d(char a,char s,i nt nu m);int ReCOVer(HUffma nTree HT.char *HC,char Stri ng,char a,char b,i nt n); int main()int i=O,n size=0,j=0,k=1, num=0;Char Stri ngsize=0,msize=0,asize=0,bsize=0;char* HC;HUffma nTree HT;PrintfCm输入电文串： n-);SCa nf(%s,stri ng);StrCPy(m,st

9、ri ng);While(Stri ngj)if(stri ngO!-#) ak=stri ngO； 鬥；While(Stri ngi)if(stri ngi=ak)Stri ngi=#;n k+;i+；if(n k!=0)Printff1该电文中字符c出现次数为d nu,ak,nk); nu m+;k+;j+;Printf(”哈弗曼树： n);HuffTree(HT ,n,n um);for(i=1;i=2* num-1 ;i+)Prin tf(%d t%d t%d t%d nH,HTi.weight,HTi.pare nt,HTi.lc,HTi.rc);Printf(”哈弗曼编码: n);

10、HUffma nCodi ng(HT,HC ,n um);for(j=1;i二nu m;i+)Prin tf(%c : %s n,ai,HCi);PrintfC* n该电文的哈弗曼编码为: n);i=0;While(Stri ngi)Prin tf(%sH,HCFi nd(mi+,a, num);Printf(H n请输入哈弗曼编码: n);SCa nf(%s,stri ng);if(Recover(HT,HC,stri ng,a,b, nu m) pri ntf(%s n,b); else Printf(代码有 误! rT);SyStem(pause);return 0;void HUffT

11、ree(HUffma nTree &HT,i nt n ,i nt num)int i,m,s1,s2;m=2* nu m-1;HT=(HUffma nTree)malloc(m+1 )*sizeof(HTNode); for(i=1;i=m;i+)HTi.weight=i=num?n i:0;HTi.lc=HTi.rc=HTi.pare nt=O;for(j=nu m+1;iv二m;i+)SeleCt(HT ,n um,i,s1,s2);HTi.lc=s1;HTi.rc=s2;HTi.weight=HTs1.weight+HTs2.weight; HTs1.pare nt=HTs2.pare

12、 nt=i;void SeleCt(HUffma nTree &H T,i nt n,i nt i,i nt & s1,i nt & s2)int k,t;S 仁 s2=-1;k=1;While(S 仁二 1)if(HTk.pare nt=O)s仁k;k+;k=1;While(S2=-1 I I s2=s1)if(HTk.pare nt=O)s2=k;k+; if(HTs2.weightHTs1.weight) t=s2;s2=s1;S 仁 t;for(k=1;ki;k+)if(HTk.pare nt=O) if(HTk.weightHTs1.weight&k!=s1 &k!=s2)s2=s1

13、;S仁k;elseif(HTk.weight=HTs1.weight&k!=s1 &k!=s2) s2=k;void HUffma nCodi ng(Huffma nTree HT,char *&HC,i nt n) SqStaCk S;Ini tStack(S);HC=(Char*)malloc( n+1)*sizeof(char*);Codi ng(HT,HC,2* n-1,S);VOid COdi ng(Huffma nTree HT,char *HC,i nt root,SqStack &S) if(root!=0)if(HTroot.lc=O)PuSh(S； O);HCroot=(c

14、har*)malloc(StackLe ngth(S);StrCPy(HCroot,S.elem);Pop(S； O);PUSh(S,O);Codi ng(HT,HC,HTroot.lc,S);Pop(S； 0*);PUSh(S；1);Codi ng(HT,HC,HTroot.rc,S);Pop(S； 0*);void In itStack(SqStack &S)S.elem=(char *)malloc(size*sizeof(char);S.stacksize=size;S.top=-1;void PUSh(SqStaCk & S,char e)S.elem+S.top=e;void PO

15、P(SqStaCk & S,char e)if(S.top=-1) return; e=S.elemS.top-; return;int StaCkLe ngth(SqStack S)if(S.top=-1) return(O); return(S.top);int Fin d(char a,char s,i nt num)int i;for(i=1;i二nu m;i+)if(a=si) return i;return 0;int ReCOVer(Huffma nTree HT,char *HC,char Stri ng,char a,char b,i nt n) int i=O,j=O,k,m=O,t=O,h=O;Char ssize;k=2* n-1;While(Stri ngi)if(!HTk.lc&!HTk.rc)if(stri ngi=O,) sO=0,;k=2* n-1;t=1;j=0;if(stri ngi=*r)sO= O;k=2* n-1;t=1;j=0; for(h=1;h二n ;h+)if(!strcmp(HCh,s) bm+=ah;elseif(stri ngi=