设计与实现(求助攻)
哈夫曼编/译码系统的设计与实现(求助攻)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.weight<k&&t.parent==0) k=t.weight,flag=j; t.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中选择parent 为0 且weight 最小的两个结点,其序号分别为s1 和s2 */ Select(*HT,i-1,&s1,&s2); (*HT).parent=(*HT).parent=i; (*HT).lchild=s1; (*HT).rchild=s2; (*HT).weight=(*HT).weight+(*HT).weight; } /* 从叶子到根逆向求每个字符的赫夫曼编码*/ HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); /* 分配n 个字符编码的头指针向量(不用) */ cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间*/ cd='\0'; /* 编码结束符*/ for(i=1;i<=n;i++) { /* 逐个字符求赫夫曼编码*/ start=n-1; /* 编码结束符位置*/ for(c=i,f=(*HT).parent;f!=0;c=f,f=(*HT).parent) /* 从叶子到根逆向求编码*/ if((*HT).lchild==c) cd[--start]='0'; else cd[--start]='1'; HC=(char*)malloc((n-start)*sizeof(char)); /* 为第i 个字符编码分配空间*/ strcpy(HC,&cd); /* 从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); }三、 实验步骤及结果测试[测试数据] 用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：字符ABCDEFGHIJKLMN
频度641322321032115475715322057
字符OPQRSTUVWXYZ空格
频度63151485180238181161168
并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”
求助攻，小弟写不来，求大侠
页:
[1]