📄 final - 032223.cpp
字号:
//*********************032223 Chen Chao*********************//
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 30
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
void Select(HuffmanTree HT,int n,int &s1,int &s2){ //选择2最小数
int i;
unsigned int min=65535; //min可改，如
s1=1; //min=HT[i].weight
s2=1; //此时要注意HT[i].parent
for(i=1;i<=n;i++){ //且不能s1和s2的min不能重复
if(HT[i].parent==0)
if(HT[i].weight<min){
s1=i;min=HT[i].weight;
}
}
for(i=1,min=65535;i<=n;i++){
if(i!=s1)
if(HT[i].parent==0)
if(HT[i].weight<min){
s2=i;min=HT[i].weight;
}
}
return;
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){//求哈夫曼数和编码
HuffmanTree p; //书上有原程序，不再详细注释
int m,i,s1,s2,start; //需要注意，w[0] && HT[0]没有使用
unsigned int c,f;
char *cd;
if(n<=1)return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //初始化
for(p=HT,i=0;i<=n;++i,++p,++w){
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p){
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//printf("Now:\n");
//printf("\tstr\tweight\tparent\tlchild\trchild\n");
//for(i=1;i<=m;i++)
//printf("%d\t\t%d\t%d\t%d\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
for(i=n+1;i<=m;++i){
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//printf("Now2:\n");
//printf("\tweight\tparent\tlchild\trchild\n");
//for(i=1;i<=m;i++)
//printf("%d\t%d\t%d\t%d\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
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);
}
void input(char *str,int *w,int &n){ //输入函数
FILE *fp; //可键盘输入，也可调用文件
char filename[10];
int i;
printf("File Input or Keyboard Input?(F) or (K):");
switch(getchar()){
case 'f' :
case 'F' : printf("Please input filename:(Load)");
scanf("%s",filename);
if((fp=fopen(filename,"rb+"))==NULL){
printf("cannot open file\n");
exit(0);
}
for(i=0;!feof(fp);i++){
fread(&str[i],sizeof(char),1,fp);
fread(&w[i+1],sizeof(int),1,fp);
}
fclose(fp);
str[i-1]='\0';
n=strlen(str);
break;
case 'K' :
case 'k' : printf("Please input string:");
scanf("%s",str);
n=strlen(str);
printf("Please input weight:\n");
for(i=0;i<n;i++){
printf("%c:",str[i]);
scanf("%d",&w[i+1]);
}
printf("Please input filename(Save):");
scanf("%s",filename);
if((fp=fopen(filename,"wb+"))==NULL){
printf("cannot open file\n");
exit(0);
}
for(i=0;i<n;i++){
fwrite(&str[i],sizeof(char),1,fp);
fwrite(&w[i+1],sizeof(int),1,fp);
}
fclose(fp);
break;
default : printf("ERROR!\n");
exit(0);
break;
}
}
int Decoding(HuffmanTree HT,char *code,int *Dcode,int n){ //译码程序
int i,j=0,root,temp;
for(i=1;i<=2*n-1;i++) //寻找根节点
if(HT[i].parent==0){
root=temp=i;
break;
}
for(i=0;i<=(int)strlen(code)+1;i++){ //为0则左孩子，1为右孩子
if(code[i]=='0')
if(temp<=n){Dcode[j]=temp;temp=root;i--;j++;}
else if(HT[temp].lchild!=0)temp=HT[temp].lchild;
else {printf("ERROR!\n");exit(0);}
else //if(code[i]=='1'&&code[i]=='\0') //判断语句
if(temp<=n){Dcode[j]=temp;temp=root;i--;j++;}
else if(HT[temp].rchild!=0)temp=HT[temp].rchild;
else {printf("ERROR!\n");exit(0);}
}
return j;
}
void Encoding(HuffmanCode HC,char *str,char *code,char Ecode[MAX][MAX]){
for(int i=0;code[i]!='\0';i++)
for(int j=0;str[j]!='\0';j++){
if(code[i]==str[j])//printf("%c:%s\t",str[j],HC[j+1]);
strcpy(Ecode[i],HC[j+1]);
}
}
void main(){
HuffmanTree HT;
HuffmanCode HC;
int i,j,n,w[MAX]={0},Dcode[MAX];
char str[MAX],code[MAX+30],Ecode[MAX][MAX];
FILE *fp;
char filename[10];
input(str,w,n);
printf("String:%s\n",str);
printf("Weight:");
for(i=1;i<=n;i++)
printf("%d ",w[i]);
putchar('\n');
HuffmanCoding(HT,HC,w,n);
printf("\tweight\tparent\tlchild\trchild\n");
for(i=1;i<=2*n-1;i++)
printf("%d\t%d\t%d\t%d\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
if((fp=fopen("HuffmanCode.txt","wb+"))==NULL){
printf("cannot open file\n");
exit(0);
}
for(i=1;i<=n;i++){
if(i%6==0)putchar('\n');
printf("%c:%s\t",str[i-1],HC[i]);
fwrite(&str[i-1],sizeof(char),1,fp);
fwrite(HC[i],sizeof(HC[i]),1,fp);
}
printf("\nEncoding:\nplease input code:");
scanf("%s",code);
Encoding(HC,str,code,Ecode);
for(i=0;i<(int)strlen(code);i++){
if(i%6==0)putchar('\n');
printf("%c:%s\t",code[i],Ecode[i]);
}
puts("\nHuffmancode is:\n");
for(i=0;i<(int)strlen(code);i++)
printf("%s",Ecode[i]);
// puts(Ecode);
/* for(i=0;code[i]!='\0';i++){
if(i%6==0)putchar('\n');
printf("%c:%s\t",code[i],HC[i+1]);
}
*/
printf("\nDecoding:\nplease input code:");
scanf("%s",code);
j=Decoding(HT,code,Dcode,n);
printf("You Code is:");
for(i=0;i<j;i++){
fwrite(&code[i],sizeof(char),1,fp);
printf("%c",str[Dcode[i]-1]);
}
putchar('\n');
/* for(i=0;i<n;i++)
fwrite(&str[Dcode[i]-1],sizeof(int),1,fp);
fclose(fp);
*/
}
/*
File Input or Keyboard Input?(F) or (K):K
Please input string:.ABCDEFGHIJKLMNOPQRSTUVWXYZ
Please input weight:
.:186
A:64
B:13
C:22
D:32
E:103
F:21
G:15
H:47
I:57
J:1
K:5
L:32
M:20
N:57
O:63
P:15
Q:1
R:48
S:51
T:80
U:23
V:8
W:18
X:1
Y:16
Z:1
Please input filename(Save):2
String:.ABCDEFGHIJKLMNOPQRSTUVWXYZ
Weight:186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 1
6 1
weight parent lchild rchild
1 186 50 0 0
2 64 45 0 0
3 13 33 0 0
4 22 37 0 0
5 32 39 0 0
6 103 48 0 0
7 21 36 0 0
8 15 33 0 0
9 47 41 0 0
10 57 43 0 0
11 1 28 0 0
12 5 31 0 0
13 32 39 0 0
14 20 36 0 0
15 57 43 0 0
16 63 44 0 0
17 15 34 0 0
18 1 28 0 0
19 48 42 0 0
20 51 42 0 0
21 80 46 0 0
22 23 37 0 0
23 8 32 0 0
24 18 35 0 0
25 1 29 0 0
26 16 34 0 0
27 1 29 0 0
28 2 30 11 18
29 2 30 25 27
30 4 31 28 29
31 9 32 30 12
32 17 35 23 31
33 28 38 3 8
34 31 38 17 26
35 35 40 32 24
36 41 40 14 7
37 45 41 4 22
38 59 44 33 34
39 64 45 5 13
40 76 46 35 36
41 92 47 37 9
42 99 47 19 20
43 114 48 10 15
44 122 49 38 16
45 128 49 2 39
46 156 50 40 21
47 191 51 41 42
48 217 51 6 43
49 250 52 44 45
50 342 52 46 1
51 408 53 47 48
52 592 53 49 50
53 1000 0 51 52
.:111 A:1010 B:100000 C:00000 D:10110
E:010 F:110011 G:100001 H:0001 I:0110 J:1100001000
K:11000011 L:10111 M:110010 N:0111 O:1001 P:100010
Q:1100001001 R:0010 S:0011 T:1101 U:00001 V:1100000
W:110001 X:1100001010 Y:100011 Z:1100001011
Encoding:
please input code:THIS.PROGRAM.IS.MY.FAVORITE
T:1101 H:0001 I:0110 S:0011 .:111 P:100010
R:0010 O:1001 G:100001 R:0010 A:1010 M:110010
.:111 I:0110 S:0011 .:111 M:110010 Y:100011
.:111 F:110011 A:1010 V:1100000 O:1001 R:0010
I:0110 T:1101 E:010
Huffmancode is:
11010001011000111111000100010100110000100101010110010111011000111111100101000111
11110011101011000001001001001101101010
Decoding:
please input code:0001010101111011110011110000000000
You Code is:HELLO.CC
File Input or Keyboard Input?(F) or (K):f
Please input filename:(Load)2
String:.ABCDEFGHIJKLMNOPQRSTUVWXYZ
Weight:186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 1
Encoding:
please input code:HI.CC
H:0001 I:0110 .:111 C:00000 C:00000
Huffmancode is:
000101101110000000000
Decoding:
please input code:00010110
You Code is:HI
*/⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -