数据结构实验报告(哈夫曼树)

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

2、;typedef struct LNodechar *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);此函数用于在HT1,i-1中选择parent为0且weight为最小的两个结点，其 下标分别为

3、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

4、&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:运行结果如下：按照提示输入任

5、意一个或多个哈弗曼编码，如输入11111110101：结果正确。若输入一个11111：结果正确。实验完成！实验体会和收获：本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上更加熟练，对数组的应用也有了提高。源代码：#include#include#include#includetypedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNodechar *elem;int stacksize;int top;SqStack;#define size 20void HuffTree

6、(HuffmanTree &HT,int n,int mun);void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);void HuffmanCoding(HuffmanTree HT,char *&HC,int n);void Coding(HuffmanTree HT,char *HC,int root,SqStack &S);void InitStack(SqStack &S);void Pop(SqStack &S,char e);void Push(SqStack &S,char e);int StackLength(SqS

7、tack S);int Find(char a,char s,int num);int Recover(HuffmanTree HT,char *HC,char string,char a,char b,int n);int main()int i=0,nsize=0,j=0,k=1,num=0;char stringsize=0,msize=0,asize=0,bsize=0;char* HC;HuffmanTree HT;printf(请输入电文串:n);scanf(%s,string);strcpy(m,string);while(stringj)if(stringj!=#) ak=st

8、ringj;i=j;while(stringi)if(stringi=ak)stringi=#;nk+;i+;if(nk!=0) printf(该电文中字符%c出现次数为%dn,ak,nk);num+;k+;j+; printf(哈弗曼树:n); HuffTree(HT,n,num);for(i=1;i=2*num-1;i+) printf(%dt%dt%dt%dn,HTi.weight,HTi.parent,HTi.lc,HTi.rc); printf(哈弗曼编码:n); HuffmanCoding(HT,HC,num);for(i=1;i=num;i+) printf(%c : %sn,a

9、i,HCi);printf(n该电文的哈弗曼编码为:n);i=0;while(stringi) printf(%s,HCFind(mi+,a,num);printf(n请输入哈弗曼编码：n);scanf(%s,string);if(Recover(HT,HC,string,a,b,num) printf(%sn,b);else printf(代码有误!n);system(pause);return 0;void HuffTree(HuffmanTree &HT,int n,int num)int i,m,s1,s2;m=2*num-1;HT=(HuffmanTree)malloc(m+1)*s

10、izeof(HTNode);for(i=1;i=m;i+)HTi.weight=i=num?ni:0;HTi.lc=HTi.rc=HTi.parent=0;for(i=num+1;i=m;i+)Select(HT,num,i,s1,s2);HTi.lc=s1;HTi.rc=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2)int k,t;s1=s2=-1;k=1;while(s1=-1)if(HTk.par

11、ent=0)s1=k;k+;k=1;while(s2=-1|s2=s1)if(HTk.parent=0)s2=k;k+;if(HTs2.weightHTs1.weight) t=s2;s2=s1;s1=t;for(k=1;ki;k+)if(HTk.parent=0)if(HTk.weightHTs1.weight&k!=s1&k!=s2) s2=s1;s1=k;else if(HTk.weight=HTs1.weight&k!=s1&k!=s2) s2=k;void HuffmanCoding(HuffmanTree HT,char *&HC,int n)SqStack S;InitStack

12、(S);HC=(char*)malloc(n+1)*sizeof(char*);Coding(HT,HC,2*n-1,S);void Coding(HuffmanTree HT,char *HC,int root,SqStack &S)if(root!=0)if(HTroot.lc=0)Push(S,0);HCroot=(char*)malloc(StackLength(S);strcpy(HCroot,S.elem);Pop(S,0);Push(S,0);Coding(HT,HC,HTroot.lc,S);Pop(S,0);Push(S,1);Coding(HT,HC,HTroot.rc,S

13、);Pop(S,0);void InitStack(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 Pop(SqStack &S,char e)if(S.top=-1) return;e=S.elemS.top-;return;int StackLength(SqStack S)if(S.top=-1) return(0);return(S.top);int Find(char a,char s

14、,int num)int i;for(i=1;i=num;i+)if(a=si) return i;return 0;int Recover(HuffmanTree HT,char *HC,char string,char a,char b,int n)int i=0,j=0,k,m=0,t=0,h=0;char ssize;k=2*n-1;while(stringi)if(!HTk.lc&!HTk.rc)if(stringi=0) sj=0;k=2*n-1;t=1;j=0;if(stringi=1) sj=0;k=2*n-1;t=1;j=0;for(h=1;h=n;h+)if(!strcmp(HCh,s) bm+=ah;elseif(stringi=0) k=HTk