数据结构综合性实验报告格式.doc

《数据结构综合性实验报告格式.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构A实验学期2015至2016学年第二学期学生所在系部管理学院年级2014专业班级电商B142学生姓名梁祺学号8成绩评定：1、工作量：A（），B（），C（），D（）,F()2、难易度：A（），B（），C（），D（）,F()3、答辩情况：基本操作：A（），B（），C（），D（）,F()代码理解：A（），B（），C（），D（）,F()4、报告规范度：A（），B（），C（），D（）,F()5、学习态度：A（），B（），C（），D（）,F()总评成绩:_________________________________指导教师:兰芸

2、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows7操作系统、VisualC++6.0软件四、实验内容：根据Ascii码文件中各Ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、系统设计：树中从根到每个叶子都有一条路径，对路径上的个分支约定：指向左子树的分支表示“0”码

3、，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符编码，这就是赫夫曼编码。实验前，先统计数据出现的频率，得出权值；然后开始实验，先通过for循环结构获得所有结点中权值最小的根结点序号，再通过Select方法选择权值最小的树的根结点的序号构建赫夫曼树，之后调用HuffmanTreeCoding方法，先初始化节点，之后再利用for循环结构建赫夫曼树，待生成赫夫曼树之后，从叶子到根逆向求每个字符的赫夫曼编码，最后设计主函数，实现实验中的大概步骤。以下是实验流程图：开始定义变量得出权值最小的根节点序号初始化节点输入需要编码的字符构建赫夫曼树

4、输出赫夫曼树构建过程表生成赫夫曼树从叶子到根逆向求每个字符的赫夫曼编码输出结果结束六、系统实现及测试结果：实验源代码：#include#include#include#includetypedefintElementType;typedefstructhuffmantree{unsignedintweight;//权值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCod

5、e;//动态分配数组存储赫夫曼编码表intMin(HuffmanTreet,inttotalNodes){//获得totalNodes个结点中权值最小的根结点序号intminIndex=0;unsignedintunWeight=UINT_MAX;//无符号整型最大值for(inti=1;i<=totalNodes;i++){if(t[i].weight

6、查找改点returnminIndex;}voidSelect(HuffmanTreet,intminIndex,int&minIndex1,int&minIndex2){//选择权值最小的树的根结点的序号minIndex1=Min(t,minIndex);minIndex2=Min(t,minIndex);inttempIndex;if(minIndex1>minIndex2){tempIndex=minIndex1;minIndex1=minIndex2;minIndex2=tempIndex;}return;}voidHuffmanTreeCoding(Huffman

7、Tree&HT,HuffmanCode&HC,int*w,intn){//存放n个字符的权值,构造赫夫曼树，求出n个字符的赫夫曼编码HCif(n<=1)return;intm=2*n-1;//总结点和inti;//根结点序号ints1,s2,j;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}f