电报压缩_解压缩系统课程设计报告

1、. 课程设计报告( 2021- 2021年度第2学期)实验名称： 数据结构与算法 题 目： 电报压缩/解压缩系统 院 系： -班 级： - 学 号： - 学生姓名： - 指导教师： - 设计周数： 1周 成 绩： 日期：2021年7月11日.一、课程设计的目的与要求1 目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。2 要求: 用高级程序设计语言C编码，用VC+开发平台调试二、设计正文(一) 课程设计题目电报压缩/解压缩系统(二需求分析(1) 报文中含有中英文字符；(2) 原始报文、压缩报文和解压报文都

2、采用文件存储； (三) 概要设计本程序包含9个函数： 主函数main(); 菜单函数menu; 初始化链表函数initDLink(); 查找及插入新的数据函数search(); 数据处理及统计函数settle(); 求哈夫曼编码函数huf_code(); 创立哈夫曼树函数creatHufTree(); 压缩函数compress(); 解压函数uncompress();各函数间关系如下： maincompressuncompressmenucreatHufTreehuf_codeinitDLinksearchsettle(四) 详细设计 (1) 系统功能结构框图电报压缩/解压缩系统输入要压缩的文

3、档名字，对其压缩输入压缩后要保存的文档名字，将压缩后的文档保存在这。输入解压后要保存的文档名，解压后保存。(2) 数据类型定义1 typedef struct dataNode char c3; /用来存储每个汉字字符或英文字符 int weight; /用来存储出现的权值 struct dataNode *next; /指向下一个的指针DNode,*DLink; /结点类型和指针类型2typedef struct hufm char data3; /用来存储汉字字符或者英文字符 int weight; /用来存储字符出现的权值 int parent,lch,rch; /父亲节点及左孩子右孩子

4、NodeHufm,*HufTree; /哈夫曼树类型及其指针类型3typedef struct HCodeNode char bits26; /用来存储哈夫曼编码HCodeNode,*HufCode; /哈夫曼编码类型及其指针类型(3) 根本操作1int menu;功能：清空界面，显示选择操作界面；参数：无。2int initDLink(DLink &D);功能：初始化链表，采用带头结点的；参数：D:为带头结点的链表的头指针。3int search(char e,DLink &D,int &n);功能：查找是否存在传进来的字符串，假设果有权值加1如果没有创立并使权值初值

5、为1；参数：e:为要查找的字符串首地址，D:为链表的头指针; n:链表上节点的个数也就是字符的个数。统计n的大小是为以后算法实现打根底4int settle(FILE *ifp,DLink &D,int &flength,int &n);功能：从文件中读取数据，统计字符种类及其出现的权值并完成文本大小及字符个数的统计；参数：ifp:读入的文件指针；D:链表的头指针；flength:文件的大小；n:字符的个数。函数调用search函数统计出n,此函数中统计出flength,下面的算法需要n与flength，而在此函数中可以顺便得到它们。5void huf_code(Huf

6、Code &hcd,HufTree ht,int n);功能：根据传进来的哈夫曼树及字符个数求出对应的哈夫曼编码；参数：hcd:动态申请空间存储哈夫曼编码的数组名，每一个元素为字符串数据类型；ht:动态申请空间存储哈夫曼树的数组名，每个元素为一个结构体数据类型，元素包括数据，权值，父亲左孩子及右孩子；n:字符个数。根据是左孩子为0右孩子为1的规定得到哈夫曼编码。6void creatHufTree(HufTree &ht,FILE *ifp,int &n,int &flength);功能：通过从文件中读取信息创立哈夫曼树，并给调用它的函数统计出n与flength

7、；参数：ht:存储了哈夫曼树的信息。Ifp:为文件指针，从那里面得到数据进行统计来创立哈夫曼树。n为字符个数，flength为文件大小。7int compress(FILE *ifp,FILE *ofp)功能：传进来读取的文件指针以及压缩后保存文件的文件指针，对源文件进行压缩。参数：ifp:要压缩的文件指针；ofp:压缩后要保存的文件指针。8int uncompress(FILE *ifp,FILE *ofp);功能：将ifp所指向的文件进行解压，然后保存到ofp所指向的文件中。参数：ifp:要解压的文件指针；ofp:解压后后要保存的文件指针。(五) 测试结果1. 选择1，输入要压缩的文件名及

8、压缩后要保存的文件名进行压缩图 1：输入要压缩的文件名及压缩后要保存的文件名2.选择2，进行解压文件。输入要解压的文件名和解压后保存的文件名，进行解压图2：输入要解压的文件名和解压后保存的文件名三、课程设计总结或结论1 完成的工作：(1) 输入要压缩的文件名及压缩后要保存的文件名实现了压缩。(2) 输入要解压的文件名及解压后要保存的文件名实现了解压。(3) 压缩率介于百分之四十到五十之间，解压采用复原哈夫曼树的方法能够快速实现解压2 未完成的工作：无3 所需做的改良：寻找更好的压缩算法实现压缩进一步提升。四、参考文献五、代码 #include<stdio.h>#include<

9、;conio.h>#include<stdlib.h>#include<string.h>typedef struct dataNodechar c3;int weight;struct dataNode *next;DNode,*DLink;typedef struct hufmchar data3;int weight;int parent,lch,rch;NodeHufm,*HufTree;typedef struct HCodeNodechar bits26;HCodeNode,*HufCode;/*对初始文件进行统计，分析*/int initDLink(

10、DLink &D)DLink p=new DNode;if(p=NULL) return 0;p->next=NULL;D=p;return 1;int search(char e,DLink &D,int &n)DLink p=D->next;while(p)if(strcmp(p->c,e)=0)p->weight+;return 1;p=p->next;p=new DNode;if(p=NULL) return 0;n+;strcpy(p->c,e);p->weight=1;p->next=D->next;D-

11、>next=p;return 1;int settle(FILE *ifp,DLink &D,int &flength,int &n)DLink p;int e;unsigned char c;char data3;data2=0;/赋予结束标志flength=0;initDLink(D);fread(&c,1,1,ifp);/读取文件时注意，先读取一个，完成后再读取一个，防止eof假出，从而不会多读flength+;while(!feof(ifp)e=(int)c;if(e>127)data0=c;fread(&c,1,1,ifp);dat

12、a1=c;flength+;elsedata0=c;data1=0;search(data,D,n);fread(&c,1,1,ifp);flength+; flength-;/计算文件的字节长度/*flength-原因是因为到最后时，文件不能读取返回-1，此时flength又+*/return 1;void huf_code(HufCode &hcd,HufTree ht,int n)/n是用来控制循环次数，求出每个节点编码int i;int index,t;char *code=new char26;int c_parent;for(i=0;i<n;i+)code25

13、='0'index=24;t=i;c_parent=hti.parent;while(c_parent!=-1)if(htc_parent.lch=t)codeindex='0'elsecodeindex='1'index-;t=c_parent;c_parent=htc_parent.parent;strcpy(hcdi.bits,&codeindex+1);void creatHufTree(HufTree &ht,FILE *ifp,int &n,int &flength)/此处n为节点数DLink D,p;

14、int i,j,s;int s1,s2;long MIN1,MIN2;/*创立之前，进行文件数据的整理*/settle(ifp,D,flength,n);/*有了n之后对哈夫曼树进行申请空间*/ht=new NodeHufm2*n-1;/*对哈夫曼树进行初始数据*/for(i=0;i<2*n-1;i+)hti.lch=hti.rch=hti.parent=-1;hti.weight=0;p=D->next;i=0;while(p)strcpy(hti.data,p->c);hti.weight=p->weight;p=p->next;i+;/找两个最小的for(i

15、=n;i<2*n-1;i+)MIN1=10000000; MIN2=10000000;s1=s2=1000000;for(j=0;j<i;j+)/htj.parent=-1 找最小的if(htj.parent!=-1) continue;/选完后的点parent 不为-1if(MIN2>htj.weight)MIN1=MIN2;s1=s2;MIN2=htj.weight;s2=j; continue;elseif(htj.weight<MIN1)MIN1=htj.weight; s1=j;/建立新的节点，从n下标开始hti.weight=hts1.weight+hts2

16、.weight;hti.lch=s1; hti.rch=s2;hts1.parent=i;hts2.parent=i;int compress(FILE *ifp,FILE *ofp)HufTree ht;HufCode hcd;int n=0;/总字节数int flength=0;/文件大小long f_count,h_read;unsigned char c;char data3;data2=0;/用来保存节点字符char code100;/用来暂时存放编码int i,j;/*将n,flength传进去，是为了将获得它，为以后压缩解压做准备*/creatHufTree(ht,ifp,n,f

17、length);/*此处对哈弗曼编码动态申请空间*/hcd=new HCodeNoden;huf_code(hcd,ht,n);code0=0;h_read=0;f_count=8;/用来记录压缩后文件的大小 /*进行压缩*/fseek(ifp,0,SEEK_SET);/将文件指针移到距离文件开始出0个字节出fseek(ofp,8,SEEK_SET);/将文件指针移到距离文件开始出8个字节出c=fgetc(ifp);while(!feof(ifp)h_read+;/计算已经读取的字节数if(c>127)data0=c;fread(&c,1,1,ifp);h_read+;/计算已经

18、读取的字节数data1=c;elsedata0=c;data1=0;for(i=0;i<n;i+)if(strcmp(hti.data,data)=0) break;/找到其下标strcat(code,hcdi.bits);/将编码存到code中j=strlen(code);/计算编码的位数c=0;/*-*/while(j>=8)/如果j大于8 那么进行安位存取进去 剩下小于8的读下一个补到后面for(i=0;i<8;i+)if(codei='1') c=(c<<1)|1;/一位一位的进行写入else c=c<<1; fwrite(&a

19、mp;c,1,1,ofp);f_count+;/写入一个字节，进行加1strcpy(code,code+8);/将code+8后的字符串放到code中j=strlen(code);if(h_read=flength) break;c=fgetc(ifp);/*处理最后一个不满8位的*/if(j>0)/j大于0，说明有剩余的strcat(code,"00000000");/不够补0for(i=0;i<8;i+)if(codei='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp

20、);f_count+;fseek(ofp,0,SEEK_SET);/将文件指针移到 文件开始出fwrite(&flength,sizeof(long),1,ofp);/将原文件的大小放到文件中fwrite(&f_count,sizeof(long),1,ofp);/将压缩后文件的大小放到文件中fseek(ofp,f_count,SEEK_SET);/将文件指针移到末尾fwrite(&n,sizeof(long),1,ofp);/将出现的文件的中 共有多少个字节数放到文件末尾/*接下来将文件中节点信息，及出现频率放到文件中*/for(i=0;i<n;i+)/*将每一

21、个节点及其权值放到文件末尾*/c=hti.data0;if(c>127)fwrite(&hti.data0,1,1,ofp);fwrite(&hti.data1,1,1,ofp);elsefwrite(&hti.data0,1,1,ofp);fwrite(&(hti.weight),4,1,ofp);/将节点的权值放进去fclose(ifp);fclose(ofp);printf("文件压缩成功!n");return 1;void uncompress(FILE *ifp,FILE *ofp)HufTree ht;char data3;

22、data2=0;char ex;int count;unsigned char c,t,z;long i,j,m,n,p,l;int e;/用于转换用long f,flength;int index;fread(&flength,sizeof(long),1,ifp);/读原文件大小fread(&f,sizeof(long),1,ifp);/读压缩后文件大小fseek(ifp,f,SEEK_SET);/将文件指针移到文件压缩后的大小出，读其下一数据fread(&n,sizeof(long),1,ifp);/将文件字节数读出来/*将字节数读出来后进行对哈夫曼树存储空间动态

23、申请*/ht=new NodeHufm2*n-1;/*初始化哈夫曼树*/for(i=0;i<2*n-1;i+)hti.lch=hti.rch=hti.parent=-1;hti.weight=0;/*读出每个字节的数据*/for(i=0;i<n;i+)fread(&c,1,1,ifp);if(c>127)hti.data0=c;fread(&c,1,1,ifp);hti.data1=c;hti.data2=0;elsehti.data0=c;hti.data1=0;fread(&(hti.weight),4,1,ifp);/读出编码长度/*恢复哈夫曼树

24、*/int MIN1,MIN2,s1,s2;for(i=n;i<2*n-1;i+)MIN1=10000000; MIN2=10000000;s1=s2=1000000;for(j=0;j<i;j+)/htj.parent=-1 找最小的if(htj.parent!=-1) continue;/选完后的点parent 不为-1if(MIN2>htj.weight)MIN1=MIN2;s1=s2;MIN2=htj.weight;s2=j; continue;elseif(htj.weight<MIN1)MIN1=htj.weight; s1=j;hti.weight=hts

25、1.weight+hts2.weight;hti.lch=s1; hti.rch=s2;hts1.parent=i;hts2.parent=i;/*开始解压文件*/ fseek(ifp,8,SEEK_SET);/将文件指针移到开始字节8出 m=0;/用来计数，表示到原文件大小时结束count=0;/计数表示压缩后的文件大小index=2*n-2;/就是最后一个，根节点while(1)fread(&c,1,1,ifp);/读一个字节count+;for(i=0;i<8;i+)if(htindex.lch=-1)t=(unsigned char)htindex.data0;if(12

26、7>=t)z=htindex.data0;fwrite(&z,1,1,ofp);m+;elsem=m+2;z=htindex.data0;fwrite(&z,1,1,ofp);z=htindex.data1;fwrite(&z,1,1,ofp);index=2*n-2;if(m=flength) break;/m记录翻译的数据个数，如果等于最开始文件大小便说明已经翻译完了if(c>127)index=htindex.rch;elseindex=htindex.lch;c=c<<1;if(count=f-8) break;/m记录翻译的数据个数，如果等于最开始文件大小便说明已经翻译完了fclose(ifp);fclose(ofp);printf("文件解压成功!n");int menu()int n,yn;while(1)system("cls");printf