您的位置：志宏网 >计算机 >数据结构(C语言) >哈夫曼编码
HuffmanTree
实验目的 树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.
问题描述 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.
基本要求 一个完整的系统应以下功能:
1. 初始化,从终端读入n个字符和n个权值,建立哈夫曼树,并将它存放在文件HuffmanTree中.
2. 编码.利用已建立好的哈夫曼树,对要传输的数据正文(存在文件StextFile中)进行编码,将结果代码存(传输)到文件CodeFile中.
3. 译码.利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件RtestFile中.
4. 打印和显示哈夫曼树,(可以树或凹入表的形式)
5. 打印文件.打印CodeFile,StestFile,RtestFile文件内容,以比较它们的不同.
测试数据 1. 利用教科书例6-2中的数据调试程序.
2. 用下面给出的字符集及频度的统计数据建立哈夫曼树:
字符:ABCDEFGHIJKLMN
频度:64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符:OPQRSTUVWXYZ 空
频度:63 15 1 48 51 80 23 8 18 1 16 1 186
并实现正文"THIS PROGEAM IS MY FAVORITE"的编码和译码.
实现提示 1. 文件可以使用数组表示.
2. 用户界面可以设计为菜单方式.
3. 第一次执行初始化程序后,哈夫曼树已建好,以后不一定需要再建立哈夫曼树.
选做内容 对你的"哈夫曼友的编码译码系统"的源程序代码(包括行尾符号)进行编码和译码.
--------------------------------------------------------------------------------
本源代码,版权所有,严禁复制,违者必究!
--------------------------------------------------------------------------------
测试通过, 仅供大家参考!!
#define MAX_INIT_TREE 100
#define OK 1
#define ERROR 0
#define SCREENWIDTH 40
#define SCREENHEIGHT 40
#define MAX_FILENAME 20
#include
typedef struct HTNode{
char character;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
HuffmanTree HT;
void FillTree(int n){
int i,weight,go,j;
char ch;
printf("There are %d TreeNodes requere!\nInput the 1 node!\n",n);
printf("ch\n");
scanf("%c",&ch);
getchar();
printf("weight\n");
scanf("%d",&weight);
getchar();
HT[1].character=ch;
HT[1].weight=weight;
for(i=2;i go=OK;
printf("There are %d TreeNodes requere!\nInput the %d node!\n",n,i);
printf("ch\n");
scanf("%c",&ch);
getchar();
printf("weight\n");
scanf("%d",&weight);
getchar();
for(j=1;j if(HT[j].character==ch){
printf("ERROR!\nHT[%d] is the same number!\nPlease reinput!\n",j);
go=ERROR;
break;
}
if(go){
HT[i].character=ch;
HT[i].weight=weight;
i++;
}
}
}
void Select(int num,int *s1,int *s2){
int i,num0,num1,num2;
for(i=1;i for(;i if(HT[num1].weight>HT[num2].weight){
num0=num1;num1=num2;num2=num0;
}
for(;i if(HT[i].weight if(HT[i].weight num2=num1;num1=i;
}else num2=i;
}
*s1=num1;*s2=num2;
}
int PrintFile(char *filename){
FILE *fp;
char ch;
int i;
printf("file:\t%s\n\n",filename);
if(!(fp=fopen(filename,"r"))){
printf("file %s is not exist!\n",filename);
return ERROR;
}
while(!feof(fp))putchar(fgetc(fp));
putchar('\n');
fclose(fp);
return OK;
}
int CreateHFTree(int *treenodes){
int n,i,m,s1,s2;
char ch;
m=treenodes;
printf("Tree has how many nodes?\n");
scanf("%d",&n);getchar();
if(nMAX_INIT_TREE){printf("Input ERROR!\n");return ERROR;}
m=2*n;
if(!(HT=(HuffmanTree)malloc(m*sizeof(HTNode))))printf("ERROR\n!");
for(i=0;i HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
FillTree(n);
for(i=n+1;i Select(i,&s1,&s2);
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[s1].parent=HT[s2].parent=i;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[i].character='\0';
}
*treenodes=n+1;
return OK;
}
void ClearScreen(){
int i;
for(i=0;i putchar('\n');
}
void HR(){
int i;
for(i=0;i putchar('\n');
}
int InCode(char *infile,int treenodes,char *outfile){
FILE *in,*out;
char ch,c[MAX_INIT_TREE];
int self,parent,start,i;
if(!(in=fopen(infile,"r"))){
printf("file %s is not exist!\n",infile);
return ERROR;
}
if(!(out=fopen(outfile,"w"))){
printf("open file %s ERROR!\n",outfile);
return ERROR;
}
while(!feof(in)){
ch=fgetc(in);
for(i=1;i if(ch==HT[i].character){
start=MAX_INIT_TREE;
c[--start]='\0';
self=i;parent=HT[self].parent;
while(parent){
c[--start]=(HT[parent].lchild==self)?'0':'1';
self=parent;
parent=HT[self].parent;
}
while(start break;
}
if(i>=treenodes)printf("%c is not found in HuffmanTree!\n",ch);
}
fclose(in);
fclose(out);
return OK;
}
int OutCode(char *infile,int treenodes,char *outfile){
FILE *in,*out;
int self,child;
char ch;
if(!(in=fopen(infile,"r"))){
printf("can not open file %s!\n",infile);
return ERROR;
}
if(!(out=fopen(outfile,"w"))){
printf("can not open file %s!\n",outfile);
return ERROR;
}
while(!feof(in)){
ch=fgetc(in);
self=2*treenodes-3;
if('0'==ch)child=HT[self].lchild;
else child=HT[self].rchild;
while(child){
self=child;
child=('0'==fgetc(in))?HT[self].lchild:HT[self].rchild;
}
fputc(HT[self].character,out);
}
return OK;
}
void PrintTree(int root,int n){
int i;
getch();
printf("[%c](%d)----",HT[root].character,HT[root].weight);
if(HT[root].rchild)PrintTree(HT[root].rchild,n+1);
else printf("NULL\n");
for(i=0;i printf("\n");
for(i=0;i if(HT[root].lchild)PrintTree(HT[root].lchild,n);
else printf("NULL\n");
}
main(){
char initfile[]={"D:\\stextfil.txt"},midfile[]={"D:\\codefile.txt"},lastfile[]={"D:\\textfile.txt"};
int treenodes;
ClearScreen();
CreateHFTree(&treenodes);
HR();getch();
printf("The following is the tree you just inputed!\n\n");
PrintTree(2*treenodes-3,0);HR();getch();
PrintFile(initfile);HR();getch();
InCode(initfile,treenodes,midfile);HR();
PrintFile(midfile);HR();getch();
OutCode(midfile,treenodes,lastfile);HR();getch();
PrintFile(lastfile);HR();getch();
printf("Now!OK!\n");
}
