二叉树的应用实验报告.docx
二叉树的应用实验报告实 验 报 告 课程名称 _数据结构上机实验_ 实验项目 _二叉树的应用 _ 实验仪器 _PC机_ 系 别_ 专 业_ 班级/学号_ 学生姓名 _ 实验日期 _ 成 绩 _ 指导教师 _ 实验三.二叉树的应用 1. 实验目的：掌握二叉树的链式存储结构和常用算法。利用哈夫曼树设计最优压缩编码。 2. 实验内容： 1) 编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。 2) 编写函数，实现生成哈夫曼编码的功能。 3) 编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码。 选做内容：修改程序，选择实现以下功能： 4) 编码：用哈夫曼编码对一段英文文本进行压缩编码，显示编码后的文本编码序列； 5) 统计：计算并显示文本的压缩比例； 6) 解码：将采用哈夫曼编码压缩的文本还原为英文文本。 3. 算法说明： 1) 二叉树和哈夫曼树的相关算法见讲义。 2) 编码的方法是：从头开始逐个读取文本字符串中的每个字符，查编码表得到它的编码并输出。重复处理直至文本结束。 3) 解码的方法是：将指针指向哈夫曼树的树根，从头开始逐个读取编码序列中的每位，若该位为1则向右子树走，为0则向左子树走。当走到叶子节点时，取出节点中的字符并输出。重新将指针放到树根，继续以上过程直至编码序列处理完毕。 4) 压缩比例的计算：编码后的文本长度为编码序列中的0和1,的个数，原文本长度为字符数*8。两者之比即为压缩比。 4. 实验步骤： 实现哈夫曼树的编码序列操作： int i=0,j=0; huffnode p; p=tree2*n-2;/序号2*n-2节点就是树根节点 while(hfmstri!='0')/从头开始扫描每个字符,直到结束 while(p.lchild!=-1&&p.rchild!=-1) if(hfmstri='0')/为0则向左子树走 p=treep.lchild;/取出叶子节点中的字符 else if(hfmstri='1')/为1则向右子树走 p=treep.rchild;/取出叶子节点中的字符 i+; decodestrj=p.data;j+;/对字符进行译码,结果放在decodestr字符串中 p=tree2*n-2;/返回根节点 程序修改后完整源代码如下： #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h>/专门用于检测整型数据数据类型的表达值范围 #define N 96 /ASCII字符集包含至多N个可见字符 typedef struct /Huffman树节点定义 char data; /字符值 int weight; /权重 int lchild; /左子结点 int rchild; /右子结点 huffnode; /huffman节点类型 struct charcode int count; /字符出现的次数(频率) char codeN; /字符的Huffman编码 codesetN; /编码表,长为N,每项对应一个ascii码字符,下标i的项对应ascii编码为i+32的字符 huffnode * CreateHufftree(char data, int weight, int n) /建立Huffman树的算法 int i,k; int min1,min2,min_i1,min_i2; huffnode *tree; tree=(huffnode *)malloc(2*n-1)*sizeof(huffnode); /为Huffman树分配2n-1个节点空间 for (i=0;i<2*n-1;i+) /初始化,将各字符和其频率填入Huffman树,作为叶子结点 treei.lchild=treei.rchild=-1; if (i<n) treei.data=datai; treei.weight=weighti; else treei.data=' ' for (i=n;i<2*n-1;i+) /合并两棵树,作n-1遍 min1=min2=INT_MAX; /INT_MAX为最大值 min_i1=min_i2=-1; for (k=0;k<i;k+) /查找定位两个最小权重节点 if (treek.weight>=0) /仅在根节点中找 if (treek.weight<min1) min2=min1; min_i2=min_i1; min1=treek.weight; min_i1=k; else if (treek.weight<min2) min2=treek.weight; min_i2=k; treei.weight=min1+min2; treemin_i1.weight *= -1; treemin_i2.weight *= -1; treei.lchild=min_i1; treei.rchild=min_i2; return tree; / 合并 void CreateHuffcode(huffnode tree, int i, char s)/已知treei节点的编码序列为s,求该节点下所有叶子节点的编码序列。 char s1N,c; if(i!=-1) if (treei.lchild=-1 && treei.rchild=-1) c=treei.data; strcpy(codesetc-32.code, s); else strcpy(s1, s); strcat(s1, "0"); CreateHuffcode(tree, treei.lchild, s1); strcpy(s1, s); strcat(s1, "1"); CreateHuffcode(tree, treei.rchild, s1); return; void PrintHufftree(huffnode tree, int n) Huffman树 int i; printf("Huffman tree :n"); /输出tree中的 printf("itValuetLchildtRchildtWeightn"); for(i=2*n-2;i>=0;i-) printf("%dt",i); printf("%ct",treei.data); printf("%dt",treei.lchild); printf("%dt",treei.rchild); printf("%dt",treei.weight); printf("n"); void EnCoding(char str, char hfmstr) /根据codeset编码表,逐个将str字符串中的字符转化为它的huffman编码,结果编码串放在hfmstr字符串中 int i, j; hfmstr0='0'/把hfmstr串赋空 i=0; while(stri!='0')/从第头开始扫描str的每个字符,一直到该字符的结束 j=stri-32;/执行字符到huffman的转换 strcat(hfmstr, codesetj.code);/把codest编码串添加到hfmstr结尾处 i+;/每次循环完i的值加1 void DeCoding(huffnode tree, int n, char hfmstr, char decodestr) /根据tree数组中的huffman树,逐个对hfmstr字符串中的字符进行译码,结果放在decodestr字符串中 int i=0,j=0; huffnode p; p=tree2*n-2;/序号2*n-2节点就是树根节点 while(hfmstri!='0')/从头开始扫描每个字符,直到结束 while(p.lchild!=-1&&p.rchild!=-1)/指针为空，儿子的值取完了 if(hfmstri='0')/为0则向左子树走 p=treep.lchild;/取出叶子节点中的字符 else if(hfmstri='1')/为1则向右子树走 p=treep.rchild;/取出叶子节点中的字符 i+; decodestrj=p.data;j+;/对字符进行译码,结果放在decodestr字符串中 p=tree2*n-2;/返回根节点 void main int i,j; huffnode * ht; /Huffman树 char dataN; /要编码的字符集合 int weightN; /字符集合中各字符的权重(频率) int n=0; /字符集合中字符的个数 char str1000; /需输入的原始字符串 char hfm_str1000="" /编码后的字符串 char decode_str1000=""/解码后的字符串 printf("请输入要转换的字符串n"); gets(str); for(i=0;i<N;i+) /初始化编码表,频率为0,编码串为空串 codeseti.count=0; codeseti.code0='0' i=0; while(stri!='0') /统计原始字符串中各字符出现的频率,存入编码表 j=stri-32; codesetj.count+; /codeset095对应ascii码32127的字符 i+; for(i=0;i<N;i+) /统计原始字符串中出现的字符个数 if(codeseti.count!=0) n+; printf("字符频率统计:n"); /显示统计结果 for(i=0;i<N;i+) if(codeseti.count!=0) codeseti.count); printf("n"); j=0; for(i=0;i<N;i+) /生成要编码的字符集合,以及权重 if (codeseti.count!=0) dataj=i+32; printf("%c:%d, ", i+32, weightj=codeseti.count; j+; ht=CreateHufftree(data,weight,n); /建立Huffman树,根节点是ht2*n-2 PrintHufftree(ht,n); /显示Huffman树的存储结果 CreateHuffcode(ht, 2*n-2, ""); /以ht2*n-2为根,以空字符串为起始编码字符串,求出各叶子节点的编码字符串 /显示codeset中的Huffman编码,参见"显示频率统计结果"的代码. printf("haffman编码为:n"); for(i=0;i<N;i+) if(codeseti.count!=0) printf("%c:%sn",i+32,codeseti.code ); EnCoding(str, hfm_str); /对str字符串进行编码,放在hfm_str字符串 printf("编码序列: %sn",hfm_str); DeCoding(ht, n, hfm_str, decode_str); /对hfm_str字符串进行译码,放在decode_str字符串中 printf("解码后的字符串: %sn",decode_str); free(ht); /释放Huffman树 实验总结：
