哈夫曼编译码器课程设计报告（完整版）

}

//建立赫夫曼树的算法

void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n) {

int m,i,x,y; HuffmanTree p; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)

{p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}

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

{p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;} for(i=n+1;i<=m;++i) {

select(HT,i-1,&x,&y);

HT[x].parent=i;HT[y].parent=i; HT[i].lchild=x;HT[i].rchild=y;

HT[i].weight=HT[x].weight+HT[y].weight; } }

//从HT[1]到HT[j]中选择parent为0，weight最小的两个结点，用x和y返回其序号

void select(HuffmanTree HT,int j,int *x,int *y)

9

{ int i;

//查找weight最小的结点 for (i=1;i<=j;i++) if (HT[i].parent==0) {*x=i;break;} for (;i<=j;i++)

if ((HT[i].parent==0)&&(HT[i].weight

HT[*x].parent=1; //查找weight次小的结点 for (i=1;i<=j;i++) if (HT[i].parent==0) {*y=i;break;} for (;i<=j;i++)

if ((HT[i].parent==0)&&(i!=*x)&&(HT[i].weight

//对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中 void Coding() {

FILE *fp,*fw; int i,f,c,start; char *cd; HuffmanCode HC; if(n==0)

10

n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

//求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中 {

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); 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)); strcpy(HC[i],&cd[start]); } free(cd); }

if((fp=fopen(\ printf(\if((fw=fopen(\ printf(\char temp;

fscanf(fp,\从文件读入第一个字符 while(!feof(fp))

11

{

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

if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置 for(int r=0;HC[i][r]!='\\0';r++) //将字符对应的编码存入文件 fputc(HC[i][r],fw);

fscanf(fp,\从文件读入下一个字符 }

fclose(fw); fclose(fp);

printf(\已将文件hfmtree.txt成功编码,并已存入codefile.txt中！\\n\\n\}

//将文件codefile中的代码进行译码，结果存入文件textfile中 void Decoding() {

FILE *fp,*fw; int m,i;

char *code,*text,*p;

if(n==0)

n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

if((fp=fopen(\ printf(\ if((fw=fopen(\

12