信息论编码：霍夫曼编码、费诺编码、游程编码、算数编码的C++实现

#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #pragma warning(disable:4996) #define n 100 #define m 2*n-1 using namespace std; //码结点的存储结构 typedef struct { char ch; char bits[9];//起始位置start到结束位置存放01序列 int len;//码长 }CodeNode; typedef CodeNode HuffmanCode[n + 1]; typedef struct { int weight; int lchild, rchild, parent; }HTNode; typedef HTNode HuffmanTree[m + 1]; int num; //挑选权值最小的两个节点 void Hselect(HuffmanTree HT, int k, int& s1, int& s2) {//一共有k个节点 int i, j; int minl = 32767; for (i = 1; i <= k; i++){ if (HT[i].weight < minl && HT[i].parent == 0) { j = i; minl = HT[i].weight; } } s1 = j; minl = 32767; for (i = 1; i <= k; i++) { if (HT[i].weight < minl && HT[i].parent == 0 && i != s1) { j = i; minl = HT[i].weight; } } s2 = j; } //统计输入字符和串 int Hjsq(char* s, int cnt[], char str[]) { char* p; int i, j, k = 0; int temp[257]; for (i = 0; i < 257; i++) {//初始化temp数组 temp[i] = 0; } //s为字符串的首地址，把首地址赋给p //如果字符没有结束的话 for (p = s; *p != '\0'; p++) { temp[*p]++; } for (i = 0, j = 0; i <= 256; i++) { if (temp[i] != 0) { j++; str[j] = i; cnt[j] = temp[i]; } } num = j; return j; } //建立霍夫曼树 void chuffmanTree(HuffmanTree& HT, HuffmanCode& HC, int cnt[], char str[]) { int i, s1, s2; for (i = 1; i <= 2 * num - 1; i++) { HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0; HT[i].weight = 0; } for (i = 1; i <= num; i++) { HT[i].weight = cnt[i]; } for (i = num + 1; i <= 2 * num - 1; i++) { Hselect(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; } for (i = 1; i <= num; i++) { HC[i].ch = str[i]; } } //给霍夫曼树的每个叶子节点分配二进制码 void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC) { int c, p, i; char cd[n]; int start; cd[num] = '\0'; for (i = 1; i <= num; i++) {//1到num为叶子结点，每个结点都有一个二进制编码串 start = num; c = i; while ((p = HT[c].parent) > 0) { start--; cd[start] = (HT[p].lchild == c) ? '0' : '1'; c = p; } strcpy_s(HC[i].bits, &cd[start]); HC[i].len = num - start; } } //译码 void Hdecode(HuffmanCode HC, char receive[], char s[]) { char str[268]; char cd[9]; int i, j, k = 0, p = 0, cjs; while (receive[p] != '\0') {//如果字符串没有到头就一直循环 cjs = 0; for (i = 0; i < num && (cjs == 0) & (receive[p] != '\0'); i++) { //cd[i] =' ';//这里应该是初始化编码第i位 cd[i + 1] = '\0'; cd[i] = receive[p++]; for (j = 1; j <= num; j++) { if (strcmp(HC[j].bits, cd) == 0) { str[k] = HC[j].ch; k++; cjs = 1; break; } } } } str[k] = '\0'; strcpy(s, str); } //输出字符串的二进制代码 void Hcoding(HuffmanCode HC, char str[], char get[]) { int i, j = 0; while (str[j] != '\0') { for (i = 1; i <= num; i++) { if (HC[i].ch == str[j]) { strcat(get, HC[i].bits); break; } } j++; } strcat(get, "\0"); } //计算编码效率 double Hcode_ratio(char st[], int cn[], HuffmanCode HC) { double up = 0.0, down = 0.0, temp = 0.0; int i = 1, len = strlen(st); for (i; i <= num; i++) { temp = cn[i] / double(len);//每个码符号的概率；次数/总码长 up -= temp * (log(temp) / log(2));//H(s) down += temp * HC[i].len;//平均码长 } return (up / down) * 100; } void main() { char str[257]; char st[10000], s[10000];//st接受输入的字符串，s接受解压的字符串 int cn[257];//统计每个字符的频率 HuffmanTree HT; HuffmanCode HC; printf("输入要编码的字符串："); scanf("%s",&st); num = Hjsq(st, cn, str);//统计字符串中有几个不同的符号 str[num + 1] = '\0'; chuffmanTree(HT, HC, cn, str); HuffmanEncoding(HT, HC); printf("共有%d种符号\n", num); for (int i = 1; i <= num; i++) { printf("字符%c次数为%d,编码为%s\n" ,HC[i].ch ,cn[i] ,HC[i].bits ); } char get[10000]; get[0] = '\0'; Hcoding(HC, st, get); printf("上述字符串的霍夫曼码为%s\n", get); printf("编码效率为%f%%\n", Hcode_ratio(st, cn, HC)); printf("输入二进制码开始译码:"); char receive[10000]; scanf("%s", &receive); Hdecode(HC, receive, s); printf("译码得%s\n", s); }