1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

二、设备与环境

微型计算机、Windows 系列操作系统 、Visual C++6.0软件

三、实验内容

根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

四、功能模块简介和系统结构图：

五、实验结果及分析

（1）系统的主要界面设计及运行说明

按屏幕提示进行文件压缩操作。

按屏幕提示进行文件解压缩操作。

（2）程序的主要代码

#include

#include

#include

#include

struct head

{

    unsigned char b;        //记录字符在数组中的位置

    long count;             //字符出现频率（权值）

    long parent,lch,rch;    //定义哈夫曼树指针变量

    char bits[256];         //定义存储哈夫曼编码的数组

}header[512],tmp;

void uncompress()  //文字解压函数

{

    char filename[255],outputfile[255],buf[255],bx[255];

    unsigned char c;

    long i,j,m,n,f,p,l;

    long flength;

    FILE *ifp,*ofp;

    printf("\请输入您要解压缩的文件名：");

    gets(filename);

    ifp=fopen(strcat(filename,".txt"),"rb");

    if(ifp==NULL)

    {

        printf("\\n\文件打开失败!\\n");

        return;

    }

    printf("\请输入您解压缩后的文件名：");

    gets(outputfile);

    ofp=fopen(outputfile,"wb");

    if(ofp==NULL)

    {

        printf("\\n\操作失败!\\n");

        return;

    }

    fread(&flength,sizeof(long),1,ifp);   //读取原文件长度，对文件进行定位

    fread(&f,sizeof(long),1,ifp);

    fseek(ifp,f,SEEK_SET);

    fread(&n,sizeof(long),1,ifp);

for(i=0;i    {

        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;

        else m=p/8;

for(j=0;j        {

            fread(&c,1,1,ifp);

            f=c;

            itoa(f,buf,2);   //将f转换为二进制表示的字符串

            f=strlen(buf);

for(l=8;l>f;l--)

            {

                strcat(header[i].bits,"0");

            }

            strcat(header[i].bits,buf);

        }

        header[i].bits[p]=0;

    }

    for(i=0;i    {

        for(j=i+1;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--) //在单字节内对相应位置补0

            {

                strcat(bx,"0");

            }

            strcat(bx,buf);

        }

        for(i=0;i        {

            if(memcmp(header[i].bits,bx,header[i].count)==0) break;

        }

        strcpy(bx,bx+header[i].count);  

        c=header[i].b;

        fwrite(&c,1,1,ofp);

        m++;   //统计解压缩后文件的长度

        if(m==flength) break;   //flength是原文件长度

    }

    fclose(ifp);

    fclose(ofp);

    printf("\\n\解压缩文件成功!\\n");

    if(m==flength)   //对解压缩后文件和原文件相同性比较进行判断（根据文件大小）

    printf("\解压缩文件与原文件相同!\\n\\n");

    else printf("\解压缩文件与原文件不同!\\n\\n");

    return;

}

void compress()       //文件压缩函数

{

    long i,j,m,n,f;

    unsigned char c;

    long min1,pt1,flength,length1,length2;

    double div;

    char filename[255],outputfile[255],buf[512];

    FILE *ifp,*ofp;

    printf("\请您输入需要压缩的文件名(格式如:*.txt)：");

    gets(filename);

    ifp=fopen(filename,"r");

    if(ifp==NULL)

    {

        printf("\\n\文件打开失败!\\n\\n");

        return;

    }

    printf("\请您输入压缩后的文件名(格式如:'*')：");

    gets(outputfile);

    ofp=fopen(strcat(outputfile,".txt"),"w");

    if(ofp==NULL)

    {

        printf("\\n\压缩文件失败!\\n\\n");

        return;

    }

    flength=0;

    while(!feof(ifp))

    {

        fread(&c,1,1,ifp);

        header[c].count++;    //字符重复出现频率+1

        flength++;            //字符出现原文件长度+1

    }       

    flength--;

    length1=flength;          //原文件长度用作求压缩率的分母

    header[c].count--;

for(i=0;i<512;i++)

    {

        if(header[i].count!=0) header[i].b=(unsigned char)i;

        else header[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            {

                tmp=header[i];

                header[i]=header[j];

                header[j]=tmp;

            }

        }

    }

for(i=0;i<256;i++) if(header[i].count==0) break;

    n=i;       //外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.

    m=2*n-1;

    for(i=n;i    {

        min1=999999999;   //预设的最大权值，即结点出现的最大次数

for(j=0;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;   //依据parent域值（结点层数）确定树中结点之间的关系

        header[i].lch=pt1;   //计算左分支权值大小

        min1=999999999;  

for(j=0;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    {

        f=i;

        header[i].bits[0]=0;   //根结点编码0  

        while(header[f].parent!=-1)

        {

            j=f;

            f=header[f].parent;

            if(header[f].lch==j)   //置左分支编码0

            {

                j=strlen(header[i].bits);

                memmove(header[i].bits+1,header[i].bits,j+1);

                //依次存储连接“0”“1”编码

                header[i].bits[0]='0';

            }

            else   //置右分支编码1

            {

                j=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);

    fseek(ofp,8,SEEK_SET);

    buf[0]=0;   //定义缓冲区,它的二进制表示00000000

    f=0;

    pt1=8;

    while(!feof(ifp))

    {

        c=fgetc(ifp);

        f++;

for(i=0;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;

else c=c<<1;

        }

            fwrite(&c,1,1,ofp);

            pt1++;   //统计压缩后文件的长度

            strcpy(buf,buf+8);   //一个字节一个字节拼接

            j=strlen(buf);

        }

        if(f==flength) break;

    }

    if(j>0)    //对哈夫曼编码位操作进行压缩存储

    {

        strcat(buf,"00000000");

for(i=0;i<8;i++)

        {

            if(buf[i]=='1') c=(c<<1)|1;

                else c=c<<1;

        }

        fwrite(&c,1,1,ofp);

        pt1++;

    }

    fseek(ofp,4,SEEK_SET);

    fwrite(&pt1,sizeof(long),1,ofp);

    fseek(ofp,pt1,SEEK_SET);

    fwrite(&n,sizeof(long),1,ofp);

for(i=0;i    {

        fwrite(&(header[i].b),1,1,ofp);

        c=strlen(header[i].bits);

        fwrite(&c,1,1,ofp);

        j=strlen(header[i].bits);

        if(j%8!=0)   //若存储的位数不是8的倍数，则补0  

        {

            for(f=j%8;f<8;f++)

            strcat(header[i].bits,"0");

        }

        while(header[i].bits[0]!=0)

        {

            c=0;

for(j=0;j<8;j++)

//字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接

            {

                if(header[i].bits[j]=='1') c=(c<<1)|1;  

 //|1不改变原位置上的“0”“1”值

else c=c<<1;

            }

            strcpy(header[i].bits,header[i].bits+8);  

 //把字符的编码按原先存储顺序连接

            fwrite(&c,1,1,ofp);

        }

    }

    length2=pt1--;

    div=((double)length1-(double)length2)/(double)length1;   //计算文件的压缩率

    fclose(ifp);

    fclose(ofp);

    printf("\\n\压缩文件成功!\\n");

    printf("\压缩率为 %f%%\\n\\n",div*100);

    return;

}

int main()

{

    int c;

    while(1)   //菜单工具栏

    {

        printf("\ ┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉\\n");

        printf("\┇            * 哈夫曼 压缩、解压缩 *           ┇ \\n");

        printf("\ ┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉┉\\n");   

        printf("\ _______________________________________________\\n");

        printf("\|                                               |\\n");  

        printf("\|                 1.压缩                        |\\n");  

        printf("\|                 2.解压缩                      |\\n");  

        printf("\|                 0.退出                        |\\n");

        printf("\|_______________________________________________|\\n");

        printf("\\n");

        printf("\                 说明：（1）采用哈夫曼编码\\n");

        printf("\                       （2）适用于字符型文本文件\\n");

        printf("\\n");

    do   //对用户输入进行容错处理

    {

        printf("\\n\*请选择相应功能(0-2):");    

        c=getch();

        printf("%c\\n",c);

        if(c!='0' && c!='1' && c!='2')

        {

            printf("\@_@请检查您输入的数字在0~2之间！\\n");

            printf("\请再输入一遍！\\n");

        }

   }while(c!='0' && c!='1' && c!='2');

   if(c=='1') compress();          //调用压缩子函数

        else if(c=='2') uncompress();   //调用解压缩子函数

   else

   {

        printf("\欢迎您再次使用该工具^_^\\n");

        exit(0);                    //退出该工具

   }

    system("pause");   //任意键继续

    system("cls");     //清屏

}

    return 0;

}

六、实验总结：

通过这次的综合性设计实践，我更深一步的了解了哈夫曼编码实现文件压缩及解压的原理和算法思想，能够构造简单的哈弗曼树并编写简单的哈夫曼编码。但由于只是浅层的了解相关知识，我的动手能力还很弱，没能自己完成编写代码。我能做到的只有努力去读懂现有代码，做到了解别人编程的思想，学到了一些书本上没有的东西，也对以后更深层的学习却有很大的帮助。所以在以后的学习中我会再接再厉，在用哈夫曼树实现文件的压缩及解压的掌握程度上更上一层。

评价教师签名：

年  月  日