📄 hafuman.cpp
字号:
void select(HuffmanTree t, int i, int &s1, int &s2)
{ //此函数被调用一次则就用堆排序选择两个最小的赋给s1和s2
SqList L;
RedType rc;
int j, k, n = 1;
L.length = 0;
for (j = 1 ; j <= i ; j++)
{
if (t[j].parent!=0)
continue;
L.r[n].key = t[j].weight; //赋值好,用堆排序
L.r[n].otherinfo = j; //存放序号,j是一直在加一的，循环一次加1，但是n不是的只有在符合条件的情况下才加1
n++;
L.length++; //这样写很巧妙的
}
for (k = L.length/2 ; k > 0 ; --k)
HeapAdjust(L,k,L.length);
s1 = L.r[1].otherinfo; //最小的选出来了！
/***把最小的换到最下面***/
rc = L.r[1];
L.r[1] = L.r[L.length]; //此次的select函数，进行堆排序的只有L.length 个（parent！=0的没有在里面），所以这里是L.length而不是i
L.r[L.length] = rc;
HeapAdjust(L,1,L.length-1);
s2 = L.r[1].otherinfo; //次小的选出来了(这里当输入1 4 2 8四个数时，第一次选出的s1=1,s2=3是对的，但第二次选出的s1=5，但s2是随机数)
}
/**************************************赫夫曼编码***************************************************/
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) // 算法6.12
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m, i, s1, s2, start, k;
unsigned c, f;
HuffmanTree p;
char *cd;
if (n <= 1)
return;
m = 2 * n - 1;
w = (float *)malloc(30*sizeof(float));
for (i = 0 ; i < 30 ; i++)
*(w+i) = b[i];
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for (p = HT + 1, i = 1 ; i <= n ; ++i, ++p, ++w)
{
(*p).weight = *w;
(*p).parent = 0;
(*p).lchild = 0;
(*p).rchild = 0;
}
for (i = n + 1 ; i <= m ; ++i, ++p)
(*p).parent=0;
for (i = n + 1 ; i <= m ; ++i) // 建赫夫曼树
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT, i-1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i; //最小的和次小的双亲已经不为0了，下次就不在它两中间找最小的和次小的了。
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
} //建立赫夫曼树也容易，关键是select这个子函数!!!
printf("赫夫曼树如下表:\n") ;
printf("__________________________________________________________________\n") ;
printf("|_number__|__name__|___weight___|__parent__|__lchild__|__rchild__|\n");
for(k = 1 ; k <= m ; k++)
{
if (k < 27)
printf("|___%2d____|__%c和%c__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,k+64,k+96,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
if (k == 27)
printf("|___%2d____|___,____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
if (k == 28)
printf("|___%2d____|___.____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
if (k == 29)
printf("|___%2d____|__空格__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
if (k == 30)
printf("|___%2d____|__换行__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
if (k > 30)
printf("|___%2d____|________|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
}
printf("\n") ;
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; //这里f=HT[f].parent是很巧妙的!!!
for (c = i, f = HT[i].parent ; f!=0 ; c = f, f = HT[f].parent)//f=HT[i].parent f!=0是结束条件，所有的编码最后都要回到HT[m],而只有HT[m]的parent是0!!!
// 从叶子到根逆向求编码
if (HT[f].lchild==c) //c是左孩子则码值是0
cd[--start] = '0'; //这样逆着输，当我们正序输出的时候就恰好是想要的编码了!!!
else
cd[--start] = '1';
HC[i] = (char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC，这里的&cd[start]是一个地址
}
free(cd); // 释放工作空间
printf("经赫夫曼编码后码值如下:\n");
for (i = 1 ; i <= 26 ; i++)
{
printf("%c和%c---->%f---->", i+64, i+96, HT[i].weight);
puts(HC[i]);
}
printf(" , ---->%f---->%s\n", HT[27].weight, HC[27]);
printf(" . ---->%f---->%s\n", HT[28].weight, HC[28]);
printf("空格---->%f---->%s\n", HT[29].weight, HC[29]);
printf("换行---->%f---->%s\n", HT[30].weight, HC[30]);
}
/*************************************输出各个字符的次数，比例****************************************/
void showdetail()
{
int i;
printf("此英文文章中各个字母,个数，比例如下表:\n");
printf("____________________________________________\n");
printf("|__字母__|_____个数_____|_______比例_______|\n");
for (i = 0 ; i < 26 ; i++)
printf("|__%c和%c__|_____%3d______|_____%f_____|\n", i+97, i+65, a[i], b[i]);
printf("|___,____|_____%3d______|_____%f_____|\n", a[26], b[26]);
printf("|___.____|_____%3d______|_____%f_____|\n", a[27], b[27]);
printf("|__空格__|_____%3d______|_____%f_____|\n", a[28], b[28]);
printf("|__换行__|_____%3d______|_____%f_____|\n", a[29], b[29]);
printf("\n");
}
/***************************************输出原英文文章，并做统计**************************************/
void showpassage()
{
float count = 0;
int i;
char ch;
fp = fopen("Huffman.txt","r");
if (!fp)
{
printf("can not open Huffman.txt !\n");
exit(0);
}
printf("要编码的文章如下:\n");
ch = fgetc(fp);
while (ch!=EOF)
{
putchar(ch); //把要编码的文章输入到屏幕中
if (ch >= 'a' && ch <= 'z')
{
a[ch-'a']++;
count+=1;
}
if (ch >= 'A' && ch <= 'Z')
{
a[ch-'A']++;
count+=1;
}
if (ch == ',')
a[26]++; //逗号放在27号单元
if (ch == '.')
a[27]++; //句号放在28号单元
if (ch == ' ')
a[28]++; //空格符放在29号单元
if (ch == '\n')
a[29]++; //换行符放在30号单元
ch = fgetc(fp); //a[]的零号单元放a
}
printf("\n\n");
for (i = 0 ; i < 30 ; i++)
b[i] = a[i]/count;
fclose(fp); //文件用完就关闭
}
/**************************************************主函数******************************************************/
void main()
{
char c;
char s[200]=" 1.查看原文.\n 2.字符统计.\n 3.赫夫曼编码并输出内容.\n 4.输出整篇文章的码字.\n 5.求最小权值.\n 6.对码子进行解码.\n 7.测试解码.\n 8.退出.\n";
printf("\n\n");
printf(" ********************************************************\n");
printf(" ** **\n");
printf(" ** 说明:本程序只对英文文章的52个大小写字母，逗号，句 **\n");
printf(" ** 号，空格符，换行符进行赫夫曼编码，并且大小写字母不 **\n");
printf(" ** 区分，其它字符因为出现的概率太低，故本程序没有考虑 **\n");
printf(" ** ，各个字符出现的频率对应他们的权值，解码时可能与原 **\n");
printf(" ** 文有少量的失真，希望用户理解和支持，谢谢! **\n");
printf(" ** **\n");
printf(" ********************************************************\n");
printf("\n\n");
printf(" ******************************************************\n");
printf(" * 注意:必须按顺序先进行1，2，3项的操作,否则会有错误! *\n");
printf(" * 当1,2,3项顺次进行完后可以任意选择这8种操作. *\n");
printf(" ******************************************************\n");
printf("请认真阅读以上注意的内容，如果已经读完请按任意键开始操作:\n");
c=getch();
system("cls");
do
{
printf("\n请选择你要的操作:\n\n");
puts(s);
c=getch();
switch (c)
{
case '1' : showpassage(); //这里必须先按顺序进行1，2，3的操作，否则有问题
break; //1，2，3先按顺序操作完后，则可以任意选择这8项操作
case '2' : showdetail();
break;
case '3' : HuffmanCoding(HT, HC, w, 30);
break;
case '4' : printcode();
break;
case '5' : minweight();
break;
case '6' : decode();
break;
case '7' : testdecode();
break;
case '8' : break;
default : putch(7);
printf("请输入正确的选项!\n");
}
}while(c!='8');
printf("\n\nBye Bye ^_^ .!\n\n");
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -