数据结构大作业.pdf
-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-实实 验验 报报 告告学号姓名实验名称哈夫曼编码器设计指导老师班级实验日期实验报告具体内容一般应包括：一、实验目的和要求;二、实验原理;三、主要仪器设备(软件);四、实验内容及实验数据记录;五、实验数据处理与分析;六、问题与建议预习分操作分报告分总成绩-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-一、实验目的和要求：哈夫曼(Huffman)树与哈夫曼码1输入一个文本，统计各字符出现的频度，输出结果；2使用二叉链表或三叉链表作存储结构，构造哈夫曼(Huffman)树；3确定和输出各字符的哈夫曼码；4.输入一个由 0 和 1 组成的代码序列，翻译并输出与之对应的文本；要求：一个完整的系统应具有以下功能：（1）初始化：从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件；（2）编码：利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中；（3）解码：利用保存的赫夫曼编码，对任意输入的 0，1 序列能正确解码二、实验思路：对输入的一串字符串，用循环进行出现频率的统计，出现频率即为节点的权值。为了方便将叶子节点数定义成为全局变量。创建哈夫曼树时，先给哈夫曼树创建一个节点，依次对叶子节点和非叶子节点进行初始化。将全部的叶子节点中最小权值的两个节点的权值进行相加即为非叶子节点。进行哈夫曼编码时，从叶子节点到根节点进行编码。而进行解码时，是从根节点到叶子节点，向左为 0 向右为 1。由于书上有相关代码，一部分代码直接借用。三、实验代码：#define MAX 50typedef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char*HuffmanCode;int n;/叶子结点数char aMAX;/接受字符串的数组void select(HuffmanTree*ht,int i,int*s1,int*s2)int j=1;for(j=1;j=i;j+)if(*ht)j.parent=0)*s1=j;break;for(j=1;j=i;j+)if(j=*s1)continue;elseif(*ht)j.parent=0)*s2=j;break;for(j=1;j=i;j+)/选择两个最小权值的结点-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-if(*ht)j.weight(*ht)*s1.weight&(*ht)j.parent=0&(*ht)*s1.weight!=(*ht)*s2.weight)*s1=j;for(j=1;j=i;j+)if(j=*s1)continue;elseif(*ht)j.weight(*ht)*s2.weight&(*ht)j.parent=0)*s2=j;void Creattree(HuffmanTree*ht,HuffmanCode*hc,int*w)int m,i,s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);printf(Haffmantree:n);for(i=1;i=n;i+)/数组 Huffnode 初始化(*ht)i.weight=wi;(*ht)i.parent=0;(*ht)i.lchild=0;(*ht)i.rchild=0;for(i=n+1;i=m;i+)(*ht)i.weight=0;(*ht)i.parent=0;(*ht)i.lchild=0;(*ht)i.rchild=0;for(i=n+1;i=m;i+)/建立非叶子结点，Huffmantreeselect(ht,i-1,&s1,&s2);(*ht)s1.parent=i;(*ht)s2.parent=i;if(*ht)s1.weight(*ht)s2.weight)(*ht)i.lchild=s1;(*ht)i.rchild=s2;-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-else(*ht)i.lchild=s1;(*ht)i.rchild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight;printf(%d=n,(*ht)i.weight,(*ht)s1.weight,(*ht)s2.weight);void charge(int*w)printf(put in a stringn);scanf(%s,&a);int i,j,k=1;for(k=1;k=n;k+)wk=1;k=1;for(i=0;ai!=0;i+)if(ai=#)continue;for(j=i+1;aj!=0;j+)if(ai=aj)wk+;aj=#;printf(%c 的频数为:,ai);printf(%dn,wk);k+;void creatnode(HuffmanTree*ht,HuffmanCode*hc)char*cd;int i,start,c,p;*hc=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;printf(haffman编码:n);for(i=1;i=n;i+)start=n-1;-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-for(c=i,p=(*ht)i.parent;p!=0;c=p,p=(*ht)p.parent)if(*ht)p.lchild=c)cd-start=0;else cd-start=1;(*hc)i=(char*)malloc(n-start)*sizeof(char);strcpy(*hc)i,&cdstart);printf(w=%d,(*ht)i.weight);printf(%sn,(*hc)i);free(cd);void translate(HuffmanTree*ht,int*w)int p;char sMAX;int m,k,i;m=0;printf(请输入一串 01 代码:n);scanf(%s,s);p=2*n-1;printf(对应的字符为:n);for(i=0;si!=0;i+)if(si=0)p=(*ht)p.lchild;if(si=1)p=(*ht)p.rchild;if(*ht)p.lchild=0&(*ht)p.rchild=0)for(k=1;wk!=(*ht)p.weight;k+)m=m+wk;printf(%c,am);if(si!=0)p=2*n-1;m=0;printf(n);四、实验数据-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-五、实验小结：通过这次试验，我学会了如何进行哈夫曼树的创建，哈弗曼编码以及解码。实验中遇到的问题有：如何统计一个字符串中一个字符出现的次数以及如何将每个字符出现的次数保存；如何将一个数组传入到子函数中，在试验中常常出现数据无法传入子函数中的情况；如何在所有的节点中查找出最小的两个叶子节点；通过这次试验发现自己对子函数的参数的传入，指针的运用十分生疏。C 语言的一些内容也有些遗忘。-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-六、流程图Select 函数的 流程图：-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-Creattree 的函数流程图：-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-Charge 的函数流程图：-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-Creatnode 的函数流程图：-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-Translate 的函数流程图：-完整版学习资料分享-WORD-WORD 格式格式-可编辑可编辑-专业资料专业资料-数据结构实验题目：题目：哈夫曼哈夫曼(Huffman)(Huffman)树与哈夫曼码树与哈夫曼码学学院院:专专业业:学学号号:学生姓名学生姓名:指导教师指导教师:日日期期:-完整版学习资料分享-
