(完整word版)实验七哈夫曼编码实验(word文档良心出品)

树和二叉树实验七哈夫曼编码哈夫曼编码1. 问题描述设某编码系统共有 n 个字符， 使用频率分别为 w1, w2, , wn ，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2. 基本要求 设计数据结构； 设计编码算法； 分析时间复杂度和空间复杂度。3. 编码#include#includeusing namespace std;const int Size=10,Size1=50;struct elementint weight;int lchild,rchild,parent;char sSize;int wSize,w1Size;int getW(char T1)/统计字母频率，获得权值char TSize1;strcpy(T,T1);char c;int count,k=0;for(int i=0;Ti!=0;i+)count=0;if(Ti=a&T1hi4.weight)c=i3;i3=i4;i4=c;for(i;hi.weight0;i+)if(hi.parent=-1)树和二叉树if(hi.weighthi3.weight)i4=i3,i3=i;else if(hi.weighthi4.weight)i4=i;void HuffmanTree(element *huffTree,int n)/哈夫曼树int i1,i2;for(int i=0;i2*n-1;i+)huffTreei.parent=-1;huffTreei.lchild=-1;huffTreei.rchild=-1;for(i=0;in;i+)huffTreei.weight=wi;for(int k=n;k=a&sj=z;j+)if(hm.weight=wj)strcpy(codei.bits,b);codei+.ch=sj;wj=-1;break;s1+top=m;m=hm.lchild;if(top!=-1)m=s1top-;m=hm.rchild;void jm(element huffT,int n,char t1)树和二叉树char b1Size;b10=0;int k=2*n-2,g=0;for(int i=0;t1i!=0;i+)if(t1i=0)k=huffTk.lchild;b1g+=0;b1g=0;elsek=huffTk.rchild;b1g+=1;b1g=0;if(huffTk.lchild=-1 & huffTk.rchild=-1)for(int j=0;jn;j+)if(strcmp(b1,codej.bits)=0)coutcodej.ch;break;k=2*n-2;g=0;coutendl;void main()char TSize1,tSize1;int n;cout 输入字符串：;gets(T);n=getW(T);element huffTreeSize1;树和二叉树HuffmanTree(huffTree,n);cout 编码： endl;bm(huffTree,2*n-2);for(int i=0;in;i+) coutcodei.ch:codei.bitsendl;for(i=0;Ti!=0;i+)for(int j=0;jn;j+)if(Ti=codej.ch)coutcodej.bits;coutendl;cout 输入编码 :;gets(t);cout 解码： endl;jm(huffTree,n,t);4.实验结果5.实验小结本次实验主要是通过实验过程掌握哈夫曼编码的逻辑结构，掌握哈夫曼编码和解码的树和二叉树基本算法， bm 函数中通过对树的遍历寻找叶子结点，进行编码。