设计与实现(求助攻)

唐柏tang

哈夫曼编/译码系统的设计与实现(求助攻)

2．一个完整的系统应具有以下功能：

1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；

2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；

3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；

4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；

要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data和CodeFile.data三个文件，以保证系统的通用性。

一、 实验目的：

理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对二叉树的构建、遍历等以及哈夫曼编码的应用有更深层次的理解。

实验步骤：实验分2次完成

第1次：完成程序的主框架设计，进行调试，验证其正确性；（2学时）

第2次：详细设计，进行调试，对运行结果进行分析，完成实验报告。（2学时）

二、 参考程序

（一）基本实验的参考程序

1．文件HuffermanDef.h 是赫夫曼树和赫夫曼编码的存储表示

typedef struct

{

        char ch;

        unsigned int weight;

        unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树*/typedef char **HuffmanCode； /* 动态分配数组存储赫夫曼编码表*/

2． 文件HuffermanUse.c 是求赫夫曼编码

#include"HuffermanDef.h"

int Min(HuffmanTree t,int i)

{ /* 函数void select()调用*/

        int j,flag;

        unsigned int k=UINT_MAX; /* 取k 为不小于可能的值*/

        for(j=1;j<=i;j++)

                if(t[j].weight<k&&t[j].parent==0)

                        k=t[j].weight,flag=j;

                t[flag].parent=1;

                return flag;

}

void Select(HuffmanTree t,int i,int *s1,int *s2)

{ /* s1 为最小的两个值中序号小的那个*/

        int j;

        *s1=Min(t,i);

        *s2=Min(t,i);

        if(*s1>*s2)

        {

                j=*s1;

                *s1=*s2;

                *s2=j;

        }

}

HuffmanCode HuffmanCoding(HuffmanTree *HT,char *ch,int *w,int n)

{ /* w 存放n 个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC */

        HuffmanCode HC;

        int m,i,s1,s2,start;

        unsigned c,f;

        HuffmanTree p;

        char *cd;

        if(n<=1)

                return NULL;

        m=2*n-1; //哈夫曼树的结点数

        *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0 号单元未用*/

        for(p=(*HT)+1,i=1;i<=n;++i,++p,++w,++ch)

        {

                (*p).ch=*ch;

                (*p).weight=*w;

                (*p).parent=0;

                (*p).lchild=0;

                (*p).rchild=0;

        }

        for(;i<=m;++i,++p)

                (*p).parent=0;

        for(i=n+1;i<=m;++i) /* 建赫夫曼树*/

        { /* 在HT[1~i-1]中选择parent 为0 且weight 最小的两个结点,其序号分别为s1 和s2 */

                Select(*HT,i-1,&s1,&s2);

                (*HT)[s1].parent=(*HT)[s2].parent=i;

                (*HT)[i].lchild=s1;

                (*HT)[i].rchild=s2;

                (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;

        }

        /* 从叶子到根逆向求每个字符的赫夫曼编码*/

        HC=(HuffmanCode)malloc((n+1)*sizeof(char*));

        /* 分配n 个字符编码的头指针向量([0]不用) */

        cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间*/

        cd[n-1]='\0'; /* 编码结束符*/

        for(i=1;i<=n;i++)

        { /* 逐个字符求赫夫曼编码*/

                start=n-1; /* 编码结束符位置*/

                for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)

                        /* 从叶子到根逆向求编码*/

                        if((*HT)[f].lchild==c)

                                cd[--start]='0';

                        else

                                cd[--start]='1';

                        HC[i]=(char*)malloc((n-start)*sizeof(char));

                        /* 为第i 个字符编码分配空间*/

                        strcpy(HC[i],&cd[start]); /* 从cd 复制编码(串)到HC */

        }

        free(cd); /* 释放工作空间*/

        return HC;

}

3.FileOper.c 是C语言文件操作

void ReadDataFile(char *fileName)//读初始化文件内容

{

        FILE *fp;

        char ch;int w;

        if((fp=fopen(fileName,"r"))==NULL)

        {

                printf("\nerror on open %s!",fileName);

                exit(1);

        }

        printf("\n文件内容：\n");

        while(!feof(fp))

        {

                fscanf(fp,"%c",&ch);

                if(ch=='\n') continue; //读到换行符，跳过，读下一行

                printf("ch=%c ",ch);

                fscanf(fp,"%5d",&w); // fscanf中的格式化要加\n,文件指针才会指向下一行

                printf("weight= %5d \n",w);

        }

        fclose(fp);

}

void WriteDataFile(char *fileName)//将初始化信息写入文件中

{

        FILE *fp;

        char c;int weight;

        if((fp=fopen(fileName,"w"))==NULL)

        {

                printf("\nerror on open %s!",fileName);

                exit(1);

        }

        printf("请输入相关字符及字符的权值,#结束:\n");

        while((c=getche())!='#')

        {               

                fprintf(fp,"%c",c);//将字符写入文件

                scanf("%d",&weight);

                fprintf(fp,"%5d\n",weight);//将字符的权值写入文件，采用fprintf格式化写入

        }

        fclose(fp);       

}

三、 实验步骤及结果测试

[测试数据] 用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：

字符	A	B	C	D	E	F	G	H	I	J	K	L	M	N
频度	64	13	22	32	103	21	15	47	57	1	5	32	20	57
字符	O	P	Q	R	S	T	U	V	W	X	Y	Z	空格
频度	63	15	1	48	51	80	23	8	18	1	16	1	168

并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”

求助攻，小弟写不来，求大侠