北邮数据结构上机实验-哈夫曼树.doc

北邮数据结构上机实验- 哈夫曼树/* 题目 2 ——应用实验利用二叉树结构实现哈夫曼编/ 解码器。基本要求: 1 、初始化(Init) :能够对输入的任意长度的字符串 s 进行统计,统计每个字符的频度,并建立哈夫曼树 2 、建立编码表(CreateTable) :利用已经建好的哈夫曼树进行编码, 并将每个字符的编码输出。 3 、编码(Encoding) :根据编码表对输入的字符串进行编码,并将编码后的字符串输出。 4 、译码(Decoding) :利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果。 5 、打印(Print) :以直观的方式打印哈夫曼树(选作) 6 、计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。 7 、可采用二进制编码方式(选作) 测试数据: I love data Structure, I puter 。I will try my best to study data Structure. 提示: 1 、用户界面可以设计为“菜单”方式:能够进行交互。 2 、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的字符一律不用编码。 3 代码要求 1 、必须要有异常处理,比如删除空链表时需要抛出异常; 2 、保持良好的编程的风格: ? 代码段与段之间要有空行和缩近? 标识符名称应该与其代表的意义一致? 函数名之前应该添加注释说明该函数的功能? 关键代码应说明其功能 3 、递归程序注意调用的过程,防止栈溢? */ #include<iostream> #include<string> #include<iomanip> using namespace std; // 静态三叉链表,用于存储哈夫曼树 struct hnode { char ss;// 结点代表的字符 int weight;// 结点的权重 int parent;// 双亲指针 int lchild;// 左孩子指针 int rchild;// 右孩子指针}; // 哈夫曼编码表 struct hcode { char data;// 存储字符 char code[100];// 存储字符编码}; //huffman 类 class huffman { private: hnode *htree;// 哈夫曼树动态数组的指针, huffman 树 hcode *hcodetable;// 哈夫曼树的编码数组指针,huffma n 编码表 int hn; // 存储哈夫曼数组的大小 public: void Init(char *s);// 初始化哈夫曼树 void createhuffman();// 创建哈夫曼树 void selectmin(int &x,int &y,int i);// 寻找权重最小的两个数 void createcodetable();// 创建哈夫曼编码表 void reverse(char m[]);// 逆置编码字符,颠倒 void encode(char *s,string *d);// 编码 void decode(char *s,char *d);// 解码 void printtable();// 打印哈夫曼树~huffman(){ delete[]htree; delete[]hcodetable; }// 析构函数}; // 初始化 void huffman::Init(char *s) { int n=0; while(*(s+n)!='\0')// 统计字符串字符数{ n++; } char *m=new char[n];// 动态字符数组存储字符串 for(int i=0;i<n;i++) { m[i]=*(s+i); } char temp; for(int i=0;i<n-1;i++)// 冒泡排序法排序{ for(int j=0;j<n-1-i;j++) { if(m[j]>m[j+1]) { temp=m[j]; m[j]=m[j+1]; m[j+1]=temp; }}} int k=1; for(int i=1;i<n;i++)// 统计不同的字符数的个数{ if(m[i]!=m[i-1]) { k++; }} htree=new hnode[2*k-1]; hn=2*k-1; int l=0;// 统计不同字符出现的频度 k=0;// 哈夫曼数组下标 temp=m[0];// 标记? for(int i=0;i<n;i++) { if(m[i]==temp) { l++;// 统计出现次数 if(i==n-1) htree[k].weight=l; } else { htree[k].weight=l; htree[k].ss=temp;