英文文件的压缩和解压缩v-数据结构与算法课程设计报告.docVIP

题目： 名称：英文文件的压缩和解压缩 内容：采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。要求：（1）压缩原文件的规模应不小于5K。 （2）提供解压缩后文件与原文件的相同性比较功能。 一、问题分析何任务定义 通过阅读并理解这个题目，要求实现对一个大小不小于5KB的英文文件的压缩和解压缩功能。为了完成这个功能，可以采用哈夫曼编码具体实现。 实现本程序需要解决一下几个问题： 如何统计英文文件的字符种类数和各类字符的数目，并将各类字符作为哈夫曼树的叶子，数目作为它的权值。 如何利用上述的字符数目作为叶子权值建立哈夫曼树。 如何对于步骤2建立的哈夫曼树的叶子（字符）进行编码。 如何将已知的字符编码应用到英文文件。 如何对应经压缩的文件进行解压缩。 首先，给定一个英文文件，如图（1）： 图（1） 解压后的文件： 然后再进行字符统计，可以利用ASCII码表的字符与数字一一对应的知识计算出每类字符的数目，把计算出的每类字符放到另一个数组中顺序存储。 利用上述统计出的每类字符及字符数目作为哈夫曼树（数组存储）的叶子结点，把上述数组顺序存储的字符及数目赋给哈夫曼数组前n位，每次选用权值最小和次最小的两个结点构建哈夫曼树，已经选用的就不再此操作了。 建立好哈夫曼树后就是对其叶子进行编码，因为哈夫曼树的结点的度数不是2就是0（叶子），此叶子就是要进行编码的对象，令其左边为0，右边为1，如图（2） 图（2） 从每个叶子结点开始一直沿着哈夫曼树向上，直到根结点，循环此操作，将每个字符进行编码。 对每个字符编码后，就要对英文文件进行压缩了，再次从英文文件单个单个读出字符，将每个字符对应的编码向另一个文件中写入，此时是利用循环来将字符对应的编码一个个的写入到文件中。直到文件结束，此时压缩成功。并可以查看压缩的文件code.txt。 对于一个压缩的文件进行译码，译码的方法就是从压缩文件连续读出0或1，将连续读出的0或1从哈夫曼树的根结点开始一直向下，直到某个叶子结点，将此编码所对应的字符写入另一个文件中，然后在继续读入0或1，利用上述的办法循环写入字符，直到文件结束。为了确定译码后的文件内容和源文件的内容相同，再添加一个功能判别源文件和译码后的文件是否保持一致性。这样就可以解决本题目了。 二、概要设计和数据结构选择 本题对英文文件进行哈夫曼编码，利用是哈夫曼树的知识，即二叉树的知识，因此所选用的数据结构是二叉树。因为哈夫曼树的建立很特别，可以用数组来存储这个哈夫曼树。 流程图如图（3） 三、详细设计 首先是统计英文文件中的字符种类数和每类字符的数目，定义一个数组s[128]， For(i=0;i128;i++) s[i]=0; 利用ASCII表的字符与数字一一对应的关系来对英文文件进行统计，从文件读取字符赋给ch，令s[ch]++；定义一个变量n表示种类数，循环进行此操作直到文件结束，再定义一个指针p，将数组s[128]中表示的字符及数目赋给以p为首地址的连续空间中（p[n]）。 建立哈夫曼树，定义一个数组tree[2*n]，将p[n]的值赋给tree[2*n]的前n项，并且另 for(i=1;i=m;i++) {tree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;tree[i].weight=0;} for(i=1;i=n;i++) {tree[i].weight=p[i-1].num; tree[i].c=p[i-1].symbol;} 然后开始寻找前n项中最小p1和次最小p2的的结点，建立一颗二叉树，将它们相加的和放到tree[n+1]项中，另p1和p2结点的父节点为n+1，且另tree[n+1]的左孩子为p1，右孩子为 p2，然后继续寻找最小p1和次最小p2的的结点，注意此时只能在parent为0的结点当中寻 找，在前面建立的二叉树基础上继续添加结点，以此循环，知道建立哈夫曼树。 对叶子进行哈夫曼编码，建立好哈夫曼树后，另其左边为0，右边为1，从tree[1]（前n为叶子结点即需要编码的结点）开始一直向上寻找parent，直到parent为0结束，在此经过的路径的0和1组合就是此叶子结点的编码，即从根节点开始到此叶子结点上的0和1组合，然后从tree[2]开始，以此类推，对所有叶子结点进行编码。 for(i=1;i=n;i++) { code[i].start=n-1; j=i; p=tree[i].parent; while(p!=0) {if(tree[p].lchild==j) code