哈夫曼编码与解码C语言知识讲解Word文档下载推荐.docx
- 文档编号:8169663
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:10
- 大小:17.13KB
哈夫曼编码与解码C语言知识讲解Word文档下载推荐.docx
《哈夫曼编码与解码C语言知识讲解Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《哈夫曼编码与解码C语言知识讲解Word文档下载推荐.docx(10页珍藏版)》请在冰点文库上搜索。
HafuTreeht;
/*声明一个指向树结点到指针*/
typedefstruct
/*叶子结点字符*/
charcodestr[20];
/*字符编码*/
}HafuCode;
HafuCodecode[27];
/*用于存放对应字符到哈夫曼编码*/
voidInitHafuArry()
{/*导入文件计算权值,生成只含有叶子结点的HafuNode数组*/
intj,i,k;
HafuNodetmpht;
FILE*fp;
/*定义一指向打开文件的指针*/
/*用于存储一个字母*/
charlocation[30]="
D:
\\"
ht=(HafuTree)malloc(53*sizeof(HafuNode));
/*为哈夫曼数分配内存空间*/
if(ht==NULL)return;
for(i=0;
i<
53;
i++)/*初始化所以的数据单元,每个单元自成一棵树*/
{
ht[i].w=0;
/*权值初始化为0*/
ht[i].lchild=ht[i].rchild=-1;
/*左右子为空*/
}
num=0;
printf("
Filename:
);
scanf("
%s"
filename);
strcat(location,filename);
fp=fopen(location,"
r"
if(!
fp)/*返回1时即存在文件*/
OpenError"
return;
while(!
feof(fp))/*没到结尾时返回0*/
ch=fgetc(fp);
if(ch=='
'
||ch<
='
z'
&
ch>
a'
Z'
A'
)
%c"
ch);
)ch='
#'
for(j=0;
j<
num;
j++)
if(ht[j].ch==ch)
break;
if(j==num)/*找到新字符*/
ht[num].ch=ch;
/*将新字符存入并将权值加1*/
ht[num].w++;
num++;
else
ht[j].w++;
/*将已有字符权值加1*/
}fclose(fp);
\n"
i++)/*对叶子结点按权值进行升序排序*/
k=i;
for(j=i+1;
if(ht[j].w<
ht[k].w)/*如果后面发现权值比i小的则将其下标记录下来,循环完之后找到最小的*/
k=j;
if(k!
=i)/*如果权值最小的不是第i个元素则交换位置,将小的放到前面*/
tmpht=ht[i];
ht[i]=ht[k];
ht[k]=tmpht;
}
intCreateHafuman(HafuTreeht)
{/*在数组ht中生成哈夫曼数,返回根节点下标*/
inti,k,j,root;
HafuNodehfnode;
codenum=0;
num-1;
i++)
{/*需生成num-1个结点*/
k=2*i+1;
/*每次取最前面两个结点,其权值必定最小*/
hfnode.w=ht[k].w+ht[k-1].w;
hfnode.lchild=k-1;
hfnode.rchild=k;
for(j=num+i;
j>
k;
j--)/*将新结点插入有序数组中*/
if(ht[j].w>
hfnode.w)
ht[j+1]=ht[j];
elsebreak;
ht[j]=hfnode;
root=j;
/*一直跟随新生成的结点,最后新生成的结点为根结点*/
returnroot;
voidGetHafuCode(HafuTreeht,introot,char*codestr)
{/*ht是哈夫曼树,root是根结点下标,codestr是来暂时存放叶子结点编码的,一开始为空*/
FILE*out;
intlen,i;
if(ht[root].lchild==-1)
{/*遇到递归终点是叶子结点记录叶子结点的哈夫曼编码*/
code[codenum].ch=ht[root].ch;
strcpy(code[codenum].codestr,codestr);
codenum++;
else/*不是终点则继续递归*/
len=strlen(codestr);
codestr[len]='
0'
/*左分支编码是0*/
codestr[len+1]=0;
/*向左孩子递归之前调整编码序列末尾加0,相当于加了个‘\0’(null)其十进制值是0,以便下次循环时添加字符,否则会被覆盖掉*/
GetHafuCode(ht,ht[root].lchild,codestr);
/*向左递归*/
codestr[len-1]='
1'
/*右分支编码为1,想右递归之前末尾编码0改为1*/
GetHafuCode(ht,ht[root].rchild,codestr);
/*向右递归*/
codestr[len-1]=0;
/*左右孩子递归返回后,删除编码标记末尾*/
out=fopen("
\\code.txt"
"
w+"
);
out)
/*printf("
WriteError"
*/
/*再打开源文件,对照哈夫曼编码译成编码*/
{if(ch=='
/*如果是空格就用#号代替*/
codenum;
{/*找到字符所对应到哈夫曼编码*/
if(ch==code[i].ch)
{/*将所得哈夫曼编码输出到文件中*/
fputs(code[i].codestr,out);
fclose(fp);
/*关闭打开到两个文件*/
fclose(out);
voiddecodeHafuCode(HafuTreeht,introot)/*将哈夫曼编码翻译为明文*/
FILE*fp2;
intcurr=root;
/*当前结点到下标*/
charfilename2[20]="
/*获得文件名*/
fp2=fopen(location,"
fp2)/*返回1时即存在文件*/
OpenError2"
Code:
feof(fp2))/*没到结尾时返回0*/
ch=fgetc(fp2);
if(ch>
ch<
)/*将编码过滤出来*/
/*将密文输出显示*/
rewind(fp2);
/*将文件指针位置定位在开头*/
)/*如果为0则当前结点向左走*/
if(ht[curr].lchild!
=-1)
curr=ht[curr].lchild;
/*若有左子则去左子*/
curr=root;
/*没有则返回根结点*/
)/*如果为1则当前结点向右走*/
if(ht[curr].rchild!
curr=ht[curr].rchild;
/*若有右子则去右子*/
if(ht[curr].lchild==-1&
ht[curr].rchild==-1)/*若为叶子结点则打印输出*/
ht[curr].ch=='
?
'
:
ht[curr].ch);
/*回到根结点继续索引*/
fclose(fp2);
voidmain()
{introot;
inti;
charcodestr[20]="
intcontrol;
/*显示菜单可选择编码、译码还是退出*/
================Menu==============\n"
chose1:
encode\n"
chose2:
decode\n"
chose3:
exit\n"
%d"
&
control);
while(control!
=3)/*只有没有选择退出就一直循环*/
if(control==1)/*选择编码选项*/
FILE*output;
InitHafuArry();
/*初始化结点*/
root=CreateHafuman(ht);
/*造一棵哈夫曼树*/
GetHafuCode(ht,root,codestr);
/*根据哈夫曼树将明文译成密码*/
output=fopen("
\\CODE.TXT"
output)/*返回1时即存在文件*/
OpenError3"
continue;
feof(output))/*没到结尾时返回0*/
ch=fgetc(output);
fclose(output);
/*将打开文件关闭*/
if(control==2)/*如果选择译码,则调用译码函数*/
decodeHafuCode(ht,root);
if(control==3)/*如果选择3则退出程序*/
exit(0);
/*若没有退出则继续打印菜单提示供选择*/
\n\n================Menu==============\n"
getch();
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码 解码 语言 知识 讲解