英文文件的压缩和解压缩v数据结构与算法课程设计报告Word格式.docx
《英文文件的压缩和解压缩v数据结构与算法课程设计报告Word格式.docx》由会员分享，可在线阅读，更多相关《英文文件的压缩和解压缩v数据结构与算法课程设计报告Word格式.docx（23页珍藏版）》请在冰点文库上搜索。
首先是统计英文文件中的字符种类数和每类字符的数目，定义一个数组s[128]，
For（i=0;
i<
128;
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;
=m;
i++）
{tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0;
}
=n;
{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]开始，以此类推，对所有叶子结点进行编码。
{
code[i].start=n-1;
j=i;
p=tree[i].parent;
while（p!
=0）
{if（tree[p].lchild==j）code[i].bits[code[i].start--]='
0'
;
elsecode[i].bits[code[i].start--]='
1'
j=p;
p=tree[p].parent;
图（3）
对英文文件进行压缩，打开一个英文文件，从中单个单个的读出字符，然后与tree[]的前n项中字符比较，找到相同的并记下下标i，接着项压缩文件中输入，如下：
for（j=code[i+1].start+1;
j<
n;
j++）
fputc（code[i+1].bits[j],fp_out）;
以此进行循环，直到文件中的字符全部编码。
接着就是对压缩文件的解压缩了，解压缩的过程其实与压缩的过程恰恰相反，首先打开一个压缩的文件，从中读出0和1代码，在读出这些代码的时候从哈夫曼树的根节点开始，一直向下，至于向左还是向右主要取决于读出的是0还是1，一直到叶子结点才结束读操作，将此编码对应的字符写入到另一个文件中，写完后又要继续的从刚才那个文件进行读操作，和上述一样，循环进行，直到所有编码都已读出。
为了查看解压缩文件和源文件是否相同，因此，在这里我对此进行了判断，判断函数如下：
voidJiancha（）
{
FILE*fp,*fp1;
charx,y;
intflag=0;
if（（fp=fopen（"
zxh.txt"
"
r"
））==NULL）
{
printf（"
打开文件失败!
\n"
）;
getch（）;
exit（0）;
}
if（（fp1=fopen（"
Uncode.txt"
while（（!
feof（fp））&
&
（!
feof（fp1）））
x=fgetc（fp）;
y=fgetc（fp1）;
if（x!
=y）{flag=1;
break;
}
if（!
flag）printf（"
\n源文件与解压后的文件保持一致!
elseprintf（"
\n源文件与解压后的文件不保持一致!
至此，这就解决了英文文件的压缩与解压缩的问题。
根据以上思想就可以写出源程序了。
四、上机调试
问题1：
一开始时就遇到了一个难题，如何从文件统计字符的种类数和每类字符的数目，想了好久也没有想出什么好办法。
经网上搜索，知道了一种简单的方法。
解决方案：
while（!
feof（fp））
{ch=fgetc（fp）;
s[ch]++;
｝此方法利用了ASCII码，一种字符对应了一种数值。
问题2：
在做好程序好，由于要压缩的文件只有2KB，因此增加了文件的大小，但是在增加到5KB之后，解压缩的时候就出错了，没有得到和源文件一样的英文文件。
开始以为是解码的函数写错了，但仔细研究，函数是对的，接着有一级一级的往上找，在找到哈夫曼编码的时候发现有的编码并不对，然后开始对建立哈夫曼树的函数进行了检查，终于找了错误，在找最小和次最小的结点的时候，定义的maxval的值小了。
#definemaxval10000
时间、空间性能分析：
本程序的空间复杂度不是很高，当中只需几个数组就可以满足本题的要求了。
而时间的复杂性主要体现在循环上了，因为要从文件中不断读出字符，还要写入字符，都需要循环来操作，而且在建立哈夫曼树的时候也利用了循环，最坏的情况也就是O（n2），n的范围也是有限的，因此时间复杂度也不是很高。
经验和体会：
开始拿到题目时，有点懵懵懂懂的，但是在做的过程中边查资料边上网搜索，有些问题就迎刃而解了。
通过这次实验，了解合理选择一种数据结构，有时候会使问题简单化，但是选择一种不合理但能解决问题的数据结构可能会使问题复杂化。
因此当我们拿到一个题目时应仔细考虑数据结构的选择，不要急于去写程序，先想好一切问题，这样会使我们办事更加有效率。
五、用户使用说明
本程序一开始时，需要用户按Enter键进入主菜单，然后会进行选择，用户需要了解什么，或是压缩文件，或是解压缩文件，只需按照提示选择相应的功能就可以了，没有什么特别复杂的操作，按照提示就可以轻松使用了
六、测试结果
统计英文文件的字符种类数和各类字符的数目：
哈夫曼树：
哈夫曼编码：
压缩英文文件：
本程序对zxh.txt的英文文件进行压缩，原本只有5KB的大小，经压缩后反而变大了为21KB，这是因为在压缩编码的过程中，每个字符都对应着一串编码，因此变大了，着应该属于正压缩，要想达到使文件变小的目的，必须对编码后的文件进行再操作，可以利用八位二进制代码对应一个字符，利用ASCII码，对其进行压缩，由于时间的问题，这个功能没有实现。
解压缩文件：
是否一致：
七、附录
#include"
stdio.h"
malloc.h"
stdlib.h"
conio.h"
typedefstruct{//叶子结点结构体
charsymbol;
intnum;
}Leaf;
typedefstruct{//哈夫曼树结点结构体
intparent;
intlchild;
intrchild;
intweight;
charc;
}Huffmantree;
typedefstruct{
charbits[128];
intstart;
}Codetype;
intn=0;
//全局变量表示文件中字符的种类数
voidMenu（）//菜单
printf（"
1、统计英文文件的字符种类数和各类字符的数目\n\n"
2、查看生成的哈夫曼树\n\n"
3、查看各类字符的哈夫曼编码\n\n"
4、英文文件的编码压缩\n\n"
5、编码压缩文件的解压\n\n"
6、检查源文件和解压后的文件的一致性\n\n"
0、结束本次操作\n\n"
Leaf*Getleafweight（）//从文件中获取字符的信息
charch;
Leaf*p;
FILE*fp;
ints[128],i,j=0;
for（i=0;
i++）//初始化个数开始为0
s[i]=0;
fp=fopen（"
if（fp==NULL）
打开文件发生错误!
while（!
ch=fgetc（fp）;
s[ch]++;
//字符按ASCII代码值统计各类字符的数目
p=（Leaf*）malloc（sizeof（Leaf））;
for（i=0;
if（s[i]!
{n++;
//统计字符种类
p[j].symbol=i;
//字符按ASCII代码值大小顺序存入数组
p[j].num=s[i];
j++;
}//存储叶子结点的字符和权值
fclose（fp）;
return（p）;
voidCount（Leaf*p）
inti;
\n\n总种类数:
%d种\n"
n）;
\n统计文件中各类字母的数目:
%c--%3d"
p[i].symbol,p[i].num）;
voidHuffman（Huffmantreetree[],Leaf*p）//生成哈夫曼树
inti,j,small1,small2,p1,p2,m;
m=2*n-1;
for（i=n+1;
i++）//循环查找最小权值和次最小权值
p1=p2=1;
small1=small2=maxval;
for（j=1;
=i-1;
j++）
if（tree[j].parent==0）//只在没有被选择的数当中寻找最小和次最小
if（tree[j].weight<
small1）
{small2=small1;
small1=tree[j].weight;
p2=p1;
p1=j;
elseif（tree[j].weight<
small2）
{small2=tree[j].weight;
p2=j;
tree[p1].parent=tree[p2].parent=i;
tree[i].weight=tree[p1].weight+tree[p2].weight;
//父节点的权值为左右孩子结点的权值之和
tree[i].lchild=p1;
tree[i].rchild=p2;
voidDisplayhuffmantree（Huffmantreetree[]）//查看生成哈夫曼树
inti,m=2*n-1;
哈夫曼树\n\n"
字符权值双亲左孩子右孩子\n"
%c%4d%4d%4d%4d\n"
tree[i].c,tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild）;
%4d%4d%4d%4d\n"
tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild）;
voidHuffmancode（Huffmantreetree[],Codetypecode[]）//对叶子结点进行编码左边为0右边为1
inti,j,p;
=0）//通过每个叶子一直向上找双亲直到双亲结点为0
//保留p并找到父节点赋给p
voidDisplayhuffmancode（Huffmantreetree[],Codetypecode[]）
inti,j;
哈夫曼编码:
{printf（"
%c--"
tree[i].c）;
for（j=code[i].start+1;
=n-1;
%c"
code[i].bits[j]）;
voidCoding（Huffmantreetree[],Leaf*p,Codetypecode[]）//对文本文件中进行Huffman编码
FILE*fp_in,*fp_out;
inti,j;
charch;
charfilename[20];
\n输入文件名:
"
scanf（"
%s"
filename）;
fp_in=fopen（filename,"
fp_out=fopen（"
code.txt"
w"
if（fp_in==NULL）
打开文件错误!
if（fp_out==NULL）
创建文件错误!
feof（fp_in））
ch=fgetc（fp_in）;
i++）
if（ch==p[i].symbol）//若读入字符和所存字符相同
{
for（j=code[i+1].start+1;
}//用字符Huffman编码对字符编码即是将其Huffman编码输出到文本文件
fclose（fp_in）;
fclose（fp_out）;
voidDecoding（Huffmantreetree[],Leaf*p）//对于一个已Huffman编码化的文件解码
inta=2*n-1;
//置起始位置
charx;
if（（fp_out=fopen（"
创建文件失败!
if（（fp_in=fopen（"
x=fgetc（fp_in）;
//读入已用Huffman编码编码过的文件中字符
if（（tree[a].lchild!
=0）&
（tree[a].rchild!
=0））//如果不是叶子结点执行后续操作
if（x=='
）
a=tree[a].lchild;
//原结点左子成为新结点
=0））
//读入新的字符
else
a=tree[a].rchild;
//原结点右子成为新结点
}
else//如果为叶子结点执行后续操作
fputc（p[a-1].symbol,fp_out）;
//将结点所存对应字符输出
a=2*n-1;
//置新的初始位置
//读入新字符
voidmain（）
inti=1;
Leafp1,*p=&
p1;
Huffmantreetree[256];
Codetypecode[128];
system（"
colorF"
\n\n\n\n\t\t\t\t欢迎使用\n\n"
\t\t\t英文文件的压缩与解压缩\n\n\n\n\n\n\n"
\t\t\t\t\t\t\t学校:
合肥学院\n\n"
\t\t\t\t\t\t\t专业:
计算机科学与技术\n\n"
\t\t\t\t\t\t\t姓名:
张小红\n\n"
\n按Enter键进入主菜单"
getch（）;
cls"
Menu（）;
\nPleasechoose:
"
scanf（"
%d"
&
i）;
p=Getleafweight（）;
Huffman（tree,p）;
Huffmancode（tree,code）;
while（i!
switch（i）
case1:
Count（p）;
break;
case2:
Displayhuffmantree（tree）;
case3:
Displayhuffmancode（tree,code）;
case4:
Coding（tree,p,code）;
\n压缩成功!
case5:
Decoding（tree,p）;
\n解压成功!
break;
case6:
Jiancha（）;
\n按Enter键返回主菜单"
\n\nPleasechoose:
八、参考书目与资料
[1]王昆仑，李红。
数据结构与算法。
北京：
铁道工业出版社，2007年5月第一版
[2]网上信息搜索。
升级会员 