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

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

2、ef 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 P

4、op(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:运行结果如下

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 20vo

6、id HuffTree(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 S

7、tackLength(SqStack 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(

8、stringj!=#) ak=stringj;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

9、+)printf(%c : %sn,ai,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=(H

10、uffmanTree)malloc(m+1)*sizeof(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=

11、1;while(s1=-1)if(HTk.parent=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;elseif(HTk.weight=HTs1.weight&k!=s1&k!=s2)s2=k;void HuffmanCoding(HuffmanTree HT,char *&HC,int n

12、)SqStack S;InitStack(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);Codi

13、ng(HT,HC,HTroot.rc,S);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);in

14、t Find(char a,char s,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=