《数据结构实验报告(哈夫曼树)（2020年7月整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告(哈夫曼树)（2020年7月整理）.pdf（9页珍藏版）》请在金锄头文库上搜索。
1、 1 数据结构实验报告数据结构实验报告 实验题目：实验题目： HuffmanHuffman 编码与解码编码与解码 姓名：姓名： 学号：学号： 院系：院系： 实验名称：实验名称： Huffman 编码与解码实验 问题描述：问题描述： 本实验需要以菜单形式完成以下功能： 1.输入电文串 2.统计电文串中各个字符及其出现的次数 3.构造哈弗曼树 4.进行哈弗曼编码 5.将电文翻译成比特流并打印出来 6.将比特流还原成电文 数据结构的描述：数据结构的描述： 逻辑结构：逻辑结构： 本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个 结点。在实验过程中我们也应用到了栈的概念。 存储结构：存
2、储结构： 使用结构体来对数据进行存储： typedef struct 2 int weight; int parent,lc,rc; HTNode,*HuffmanTree; typedef struct LNode char *elem; int stacksize; int top; SqStack; 在 main 函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述：程序结构的描述： 本次实验一共构造了 10 个函数： 1.void HuffTree(HuffmanTree 此函数根据给定的 mun 个权值构建哈弗曼树，n用于存放 num 个权值。 2.void Select(H
3、uffmanTree 此函数用于在 HT1,i-1中选择 parent 为 0 且 weight 为最小的两个结点，其 下标分别为 s1,s2. 3.void HuffmanCoding(HuffmanTree HT,char * 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char *HC,int root,SqStack 此函数用于初始化一个栈。 6.void Pop(SqStack 此函数为出栈操作。 7.void Push(SqStack 此函数为进栈操作。 8.int StackLength(SqS
4、tack 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:运行结果如下： 3 按照提示输入任意一个或多个哈弗曼编码，如输入 11111110101： 结果正确。 若输入一个 11111： 结果正确。 4 实验完成！ 实验体会
5、和收获：实验体会和收获： 本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上 更加熟练，对数组的应用也有了提高。 源代码：源代码： #include #include #include #include typedef struct int weight; int parent,lc,rc; HTNode,*HuffmanTree; typedef struct LNode char *elem; int stacksize; int top; SqStack; #define size 20 void HuffTree(HuffmanTree void Select(Hu
6、ffmanTree void HuffmanCoding(HuffmanTree HT,char * void Coding(HuffmanTree HT,char *HC,int root,SqStack void InitStack(SqStack void Pop(SqStack void Push(SqStack int StackLength(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 mai
7、n() 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) 5 if(stringj!=#) ak=stringj; i=j; while(stringi) if(stringi=ak) stringi=#; nk+; i+; if(nk!=0) printf(该电文中字符%c 出现次数为%dn,ak,nk);
8、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,ai,HCi); printf(n 该电文的哈弗曼编码为:n); i=0; while(stringi) printf(%s,HCFind(mi+,a,num); printf(n 请输
9、入哈弗曼编码：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 m=2*num-1; 6 HT=(HuffmanTree)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(
10、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 s1=s2=-1; k=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.pa
11、rent=0) if(HTk.weightHTs1.weight 7 s1=k; else if(HTk.weight=HTs1.weight void HuffmanCoding(HuffmanTree HT,char * 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 HCroot=(char*)malloc(StackLength(S); strcpy(HCroot,S.elem);
12、Pop(S,0); Push(S,0); Coding(HT,HC,HTroot.lc,S); Pop(S,0); Push(S,1); Coding(HT,HC,HTroot.rc,S); Pop(S,0); void InitStack(SqStack S.stacksize=size; S.top=-1; void Push(SqStack 8 void Pop(SqStack e=S.elemS.top-; return; int StackLength(SqStack S) if(S.top=-1) return(0); return(S.top); int Find(char a,
13、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.lck=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; else if(stringi=0) k=HTk.lc;sj+=0; if(stringi=1) 9 k=HTk.rc; sj=1; j+; t=0; if(!t) i+; if(!HTk.lck=2*n-1;j=0; if(stringi-1=1) sj=0; k=2*n-1; t=1; j=0; for(h=1;h=n;h+) if(!strcmp(HCh,s) bm+=ah; bm=0; if(k=2*n-1) return 1; else return 0;
