英文文件的压缩和解压缩v数据结构与算法课程设计报告Word格式.docx
- 文档编号:904355
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:23
- 大小:183.21KB
英文文件的压缩和解压缩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]网上信息搜索。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 英文 文件 压缩 和解 数据结构 算法 课程设计 报告