《数据结构》课程设计报告设计题目压缩软件专业计算机科学与技术班级12计算机科学与技术姓名张双林学号121114039完成日期2014年5月25目录(空两行)1. 问题描述 (2)2. 系统设计 (2)3. 数据结构与算法描述 (4)4. 测试结果与分析 (4)5. 总结 (6)6. 参考文献 (6)附录程序源代码 (7)(要求：给出一级目录，宋体加粗，四号字,1.5倍行距。

)（报告正文部分）：课程设计题目(要求：正文部分一律用小四号字，宋体，1.5倍行距。

一级标题靠左，四号加粗。

二级、三级标题靠左，小四加粗。

)1.问题描述准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

2. 系统设计2.1 设计目利用哈弗曼编码，将文件压缩和解压2.2 设计思想根据ascii码文件中各ascii字符出现的频率情况创建哈夫曼树，再将各字符对应的哈夫曼编码相连，每八位作为一个字符，写入文件中，同时Huffman树也要压缩后写入压缩文件，以实现文件压缩。

2.3 系统模块划分（要给出流程图）2.3.1压缩部分1.构造哈夫曼树，对其进行前缀编码（1）扫描待压缩文件，得出各字符出现频率。

（2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。

（3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。

（4）在F中删除这两棵树。

同时将新得到的二叉树加入F中。

重置（2）和（3），直到F只含一棵树为止。

这棵树便是哈夫曼树。

2.由Huffman树得到各字符前缀编码。

3.根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。

4.处理剩余不到八位部分，写入压缩文件。

5.将前缀编码及相关信息写入压缩文件。

6.关闭指针，完成压缩。

计算压缩率。

2.3.2 解压部分1.读入压缩文件长度和源文件长度。

读入前缀编码。

2.对文件中各字符解码，写入解压文件。

3.判断解压文件是否完好（对比压缩前文件长度），关闭指针，完成解压。

3. 数据结构与算法描述5. 总结通过本次实验，我熟练的掌握了利用哈弗曼编码压缩和解压文件，刚开始看到这个题目的时候我一点头绪都没有，通过上网查找资料和翻看一些书籍，我知道了如何将问价进行压缩，最后在老师的指导下完成了这一项艰巨的任务。

6. 参考文献（包括书籍、论文、网络资料等）参考书籍《c++语言程序设计》第四版严蔚敏编写，清华出版社出版附录程序源代码#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct head {unsigned char b; //记录字符在数组中的位置long count; //字符出现频率（权值）long parent,lch,rch; //定义哈夫曼树指针变量char bits[256]; //定义存储哈夫曼编码的数组}header[512],tmp;void compress(){char filename[255],outputfile[255],buf[512];unsigned char c;long n,m,i,j,f; //作计数或暂时存储数据用long min1,pt1,flength=0,length1,length2; //记录最小结点、文件长度double div; //计算压缩比用FILE *ifp,*ofp; //分别为输入、输出文件指针printf("\t请您输入需要压缩的文件（需要路径）：");gets(filename);ifp=fopen(filename,"rb");if(ifp==NULL){printf("\n\t文件打开失败!\n ");system("pause");return;}printf("\t请您输入压缩后的文件名（如无路径则默认为桌面文件）：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp==NULL){printf("\n\t压缩文件失败!\n ");system("pause");return;}flength=0;while(!feof(ifp)){fread(&c,1,1,ifp);header[c].count++; //字符重复出现频率+1flength++; //字符出现原文件长度+1}flength--;length1=flength; //原文件长度用作求压缩率的分母header[c].count--;for(i=0;i<512;i++){if(header[i].count!=0)header[i].b=(unsigned char)i;/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，且编码表中的下标和ASCII码满足顺序存放关系*/elseheader[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1;//对结点进行初始化}for(i=0;i<256;i++){ //按出现权值从大到小排序for(j=i+1;j<256;j++){if(header[i].count<header[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i<256;i++) //找到第一个空的header结点if(header[i].count==0)break;n=i;m=2*n-1;for(i=n;i<m;i++){min1=999999999; //预设的最大权值，即结点出现的最大次数for(j=0;j<i;j++){if(header[j].parent!=-1)continue; /*parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count; header[pt1].parent=i;header[i].lch=pt1;min1=999999999;for(j=0;j<i;j++){if(header[j].parent!=-1)continue;if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1;header[pt1].parent=i; //哈夫曼无重复前缀编码}for(i=0;i<n;i++){f=i;header[i].bits[0]=0; //根结点编码0while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j){ //置左分支编码0j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);//依次存储连接"0""1"编码，此处语句为网络借鉴header[i].bits[0]='0';}else{ //置右分支编码1j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}}fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp); /*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int 数目*/fseek(ofp,8,SEEK_SET);buf[0]=0; //定义缓冲区,它的二进制表示00000000f=0;pt1=8; /*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识别编码第一个'0'，那么将其左移一位，看起来没什么变化。

下一个是'1'，应该|1，结果00000001同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，继续读下一个字符，根据编码表继续拼完剩下4位，如果字符的编码不足4位，还要继续读一个字符，如果字符编码超过4位，那么把剩下的位信息拼接到一个新的字节里*/while(!feof(ifp)){c=fgetc(ifp);f++;for(i=0;i<n;i++){ //找到对应的header[i]if(c==header[i].b)break;}strcat(buf,header[i].bits);j=strlen(buf);c=0;while(j>=8){for(i=0;i<8;i++){if(buf[i]=='1')c=(c<<1)|1; //添加最后一位为1 elsec=c<<1; //添加最后一位为0 }fwrite(&c,1,1,ofp);pt1++;strcpy(buf,buf+8);j=strlen(buf);}if(f==flength)break;}if(j>0){ //最后不满八位的buf 处理strcat(buf,"00000000"); //buf后加八位0for(i=0;i<8;i++){ //逐位输入八位前的二进制符if(buf[i]=='1')c=(c<<1)|1;elsec=c<<1;}fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET); //指针回到输出文件头部后面四位fwrite(&pt1,sizeof(long),1,ofp); //pt1统计了输出文件中的字符个数，包括了最后的'/0'fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp); //n统计了权值不为0的header[]数量for(i=0;i<n;i++){fwrite(&(header[i].b),1,1,ofp); //依次写入每个叶子结点的b、长度和内容c=strlen(header[i].bits);fwrite(&c,1,1,ofp);j=strlen(header[i].bits);if(j%8!=0){ //若存储的位数不是8的倍数，则补0for(f=j%8;f<8;f++)strcat(header[i].bits,"0");}while(header[i].bits[0]!=0){ /*字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接，可理解为前缀编码也被压缩过*/c=0;for(j=0;j<8;j++){if(header[i].bits[j]=='1')c=(c<<1)|1;elsec=c<<1;}strcpy(header[i].bits,header[i].bits+8);fwrite(&c,1,1,ofp); //以上与上面连接字符一段可相同理解}}length2=pt1--;div=((double)length1-(double)length2)/(double)leng th1; //计算文件的压缩率fclose(ifp);fclose(ofp);printf("\n\t压缩文件成功!\n");printf("\t压缩率为 %f%%\n\n",div*100);return;}void uncompress(){charfilename[255],outputfile[255],buf[255],bx[255];unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("\t请您输入需要解压缩的文件（如无路径则默认为桌面文件）：");gets(filename);ifp=fopen(filename,"rb");if(ifp==NULL){printf("\n\t文件打开失败!\n ");system("pause");return;}printf("\t请您输入解压缩后的文件名：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp==NULL){printf("\n\t解压缩文件失败!\n ");system("pause");return;}fread(&flength,sizeof(long),1,ifp); //读入文件长度flengthfread(&f,sizeof(long),1,ifp); //读入header数组的存储地址fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp); //读入header数组中元素的个数for(i=0;i<n;i++){ //读入header数组fread(&header[i].b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c;header[i].count=p;header[i].bits[0]=0;if(p%8>0)m=p/8+1;elsem=p/8;for(j=0;j<m;j++){fread(&c,1,1,ifp);f=c;itoa(f,buf,2); /*此处借鉴网络程序，包括itoa()函数itoa()函数的作用为，把int型的f化为二进制数，再变成char型存入buf*/f=strlen(buf);for(l=8;l>f;l--){ //在单字节内对相应位置补0strcat(header[i].bits,"0");}strcat(header[i].bits,buf);}header[i].bits[p]=0;}for(i=0;i<n;i++){ //按Huffman编码从小到大排序for(j=i+1;j<n;j++){if(strlen(header[i].bits)>strlen(header[j].bits)){ tmp=header[i];header[i]=header[j];header[j]=tmp;}}}p=strlen(header[n-1].bits);fseek(ifp,8,SEEK_SET);m=0;bx[0]=0;while(1){ //对文件其余部分，即真正的文件部分解压缩while(strlen(bx)<(unsigned int)p){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l--){strcat(bx,"0");}strcat(bx,buf);}for(i=0;i<n;i++){ //依次比对Huffman前缀编码if(memcmp(header[i].bits,bx,header[i].count)==0)/*此函数也为网络借鉴，memcmp函数此处的作用是比较bx的相应位是否与header[i].bits相同，若前header[i].count均相同，则返回0 */break;}strcpy(bx,bx+header[i].count);c=header[i].b;fwrite(&c,1,1,ofp);m++; //m用来统计解压缩后文件的长度if(m==flength) //检验是否与源文件长度匹配break;}fclose(ifp);fclose(ofp);printf("\n\t解压缩文件成功!\n");if(m==flength)printf("\t解压缩文件与原文件相同!\n\n");elseprintf("\t解压缩文件与原文件不同!\n\n");return;}int main(){int c;while(1){printf("\ 12计算机科学与技术压缩＆解压缩121114039 张双林\n");printf("\t1.压缩 2.解压缩 0.退出\n");do{ //对用户输入进行容错处理printf("\n\t*请选择相应功能编号(0-2):");c=getch();printf("%c\n",c);if(c!='0' && c!='1' && c!='2'){printf("\t请检查您的输入在0~2之间！请再输入一遍！\n");}}while(c!='0' && c!='1' && c!='2');if(c=='1') //调用压缩子函数compress();else if(c=='2')uncompress(); //调用解压缩子函数else{exit(0);}system("pause");system("cls");}return 0;}。