霍夫曼树
c语言实现霍夫曼树
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct {
char value;
int weight;
int parent,lchild,rchild;
char cd[20];
}HTNode;
HTNode SSS[26];
int sum=0;
void HTcd(char str[]){
int m;
char tempcd[20];
char voidone[20]="";
int t;
int sub;
int weights[26];
char values[26];
int i,j;
int flag=0;
int min1s1,min2s2;
int counter;
HTNode min1,min2;
for (i=0;str[i]!='\0';i++){
flag=0;
for (j=0;j<=i;j++){
if (str[i]==values[j]){
weights[j]++;
flag=1;
}
}
if (flag==0){
weights[sum]=1;
values[sum]=str[i];
sum++;
}
}
for(i=0;i<sum;i++){
printf("%c的权为%d\n",values[i],weights[i]);
}
m=(2*sum)-1;
for(i=0;i<sum;i++){
SSS[i].value=values[i];
SSS[i].weight=weights[i];
SSS[i].parent=0;
SSS[i].lchild=0;
SSS[i].rchild=0;
}
for(;i<=m;i++){
SSS[i].value=0;
SSS[i].weight=0;
SSS[i].parent=0;
SSS[i].lchild=0;
SSS[i].rchild=0;
}
for(i=0;i<m;i++){
sub+=SSS[i].weight;
}
counter=sum;
for(i=sum;i<m;i++){
min1s1=i-1;
min2s2=i-1;
min1.weight=sub+1;
min2.weight=sub+1;
for(j=0;j<counter;j++){
if(SSS[j].parent!=0) continue;
else if(min1.weight>=SSS[j].weight){
min1.weight=SSS[j].weight;
min1.value=SSS[j].value;
min1s1=j;
}
}
for(j=0;j<counter;j++){
if(SSS[j].parent!=0) continue;
else if (min2.weight>=SSS[j].weight&&SSS[j].value!=min1.value){
min2.weight=SSS[j].weight;
min2.value=SSS[j].value;
min2s2=j;
}
}
counter++;
SSS[min1s1].parent=i;
SSS[min2s2].parent=i;
SSS[i].lchild=min1s1;
SSS[i].rchild=min2s2;
SSS[i].weight=SSS[min1s1].weight+SSS[min2s2].weight;
}
printf("建好后的树为：\n");
for(j=0;j<sum;j++){
i=j;
t=0;
for(;SSS[i].parent!=0;) {
if(SSS[(SSS[i].parent)].lchild==i) tempcd[t]='0';
else if(SSS[(SSS[i].parent)].rchild==i) tempcd[t]='1';
i=SSS[i].parent;
t++;
}
strrev(tempcd);
strcpy(SSS[j].cd,tempcd);
strcpy(tempcd,voidone);
}
for(j=0;j<m;j++){
printf("第%d个字符%c的权为%d，父为%d，左子为%d，右子为%d，霍夫曼码为%s\n",j,SSS[j].value,SSS[j].weight,SSS[j].parent,SSS[j].lchild,SSS[j].rchild,SSS[j].cd);
}
printf("源码编码后为：");
for(i=0;str[i]!='\0';i++){
for(j=0;j<sum;j++){
if(SSS[j].value==str[i]) printf("%s ",SSS[j].cd);
}
}
printf("\n");
}
void HTtra(char str[]){
printf("密码翻译后为：");
int i,j=0;
i=(2*sum)-2;
while (str[j]!='2'){
if(str[j]=='0') i=SSS[i].lchild;
else if(str[j]=='1') i=SSS[i].rchild;
if(SSS[i].lchild==0&&SSS[i].rchild==0) {
printf("%c",SSS[i].value);i=(2*sum)-2;
}
j++;
}
}
int main(){
int process=0;
char str[200];
char decode[200];
FILE *fp;
int i,j;
char acc[20];
if((fp=fopen("D:\\SourceFile.txt","r"))==NULL) printf("打开文件失败,不能读取源码\n");
else{
fscanf(fp,"%s",&str);
rewind(fp);
fclose(fp);
HTcd(str);
process=1;
}
if((fp=fopen("D:\\Code.txt","w"))==NULL) printf("打开文件失败，不能输出编码字典\n");
else if(process==1){
printf("打开文件成功\n");
for(i=0;i<sum;i++) {
fprintf(fp,"%c的编码为",SSS[i].value);
fprintf(fp,"%s\n",SSS[i].cd);
}
rewind(fp);
fclose(fp);
}
if((fp=fopen("D:\\ResultFile.txt","w"))==NULL) printf("打开文件失败，不能输出编码\n");
else if(process==1){
fprintf(fp,"源字符串的编码为");
for(i=0;str[i]!='\0';i++){
for(j=0;j<sum;j++){
if(SSS[j].value==str[i])
fprintf(fp,"%s",SSS[j].cd);
}
}
fprintf(fp,"2");
rewind(fp);
fclose(fp);
printf("编码已写好\n");
}
printf("请输入要进行译码的文件的路径\n");
scanf("%s",&acc);
if((fp=fopen(acc,"r"))==NULL) printf("打开文件失败，不能读取译码");
else if(process==1){
fscanf(fp,"%s",&decode);
rewind(fp);
fclose(fp);
HTtra(decode);
}
}
文章最后发布于: 2018-11-20 20:15:23
相关阅读
消息队列的实现方式有很多种，比如有专业的rabbitmq,rocketmq,kafka等，这些mq提供了非常专业的功能实现异步发送，而且这些接入又比较
越来越多的企业注重自身的品牌形象，在实体店形象升级改造的同时，企业也不会放过网络这一块大蛋糕。那么，做网站便是企业的需求了。但
2011年10月17日从新浪微博上看到14日的一条微博:美国计算机科学家、C语言和Unix共同作者、图灵奖得主丹尼斯·里奇去世，享年70岁。
绩效管理是现代人力资源管理的重要组成部分，而绩效考核又是绩效管理中的重要一环。但目前，不少企业对于绩效管理的认知依旧存在偏差
使用padding-bottom和margin-bottom实现两栏等高布局
声明：以下均为个人见解，若有错误请指出。效果预览：<!DOCTYPE html> <html> <head> <title>demo</title> <style type="tex