huffman编码.rar

/** 程序名称：huffman编码 * 编写环境：Code::Blocks 17.12 * author：王威 * 学院：计电学院 * 专业：计科19101 * 学号：201914040128 */ /**功能实现 * （函数定义内部有对函数功能的简介） * 1.译码 * 2.转码 * 3.简单菜单 * 4.字符集及权值可自定义 */ #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <windows.h> #include <iomanip> #define MAXSIZE 1000 //权值上限 #define NUM 31 using namespace std; typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } htnode, * huffmantree; typedef char** huffmancode; void huffmancoding(huffmantree &ht, huffmancode &hc, unsigned int* w, int n); void select(huffmantree& ht, int n, int &s1, int &s2); void huffmaninput(unsigned int* w, char* str); void huffmanoutput(huffmantree ht, huffmancode hc); void huffmantranstr(huffmancode hc); void decode(huffmantree &ht, huffmancode &hc); void show(); void out(); huffmantree ht; huffmancode hc; unsigned int w[NUM]; //权值 char str_extern[NUM]; //字符集 int n; //字符集个数 char str[MAXSIZE]; int main() { show(); huffmaninput(w, str_extern); huffmancoding(ht, hc, w, n); while (1) { system("cls"); show(); out(); } } void huffmancoding(huffmantree &ht, huffmancode &hc, unsigned int* w, int n) { /** function: * 1.建haffman树 * 2.huffman编码 * 3.声明：书中源码 */ if (n <= 1) return; //可表示字符数量小于等于1 int m; m = 2 * n - 1; //哈夫曼树结点总数 ht = (huffmantree)malloc((m + 1) * sizeof(htnode)); if (ht) { int i, s1, s2; huffmantree p = ht; p++; for (i = 1; i <= n; ++i, ++p, ++w) { (*p).weight = *w; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; } for (; i <= m; ++i, ++p) //对除叶子结点外的结点初始化为0 { (*p).weight = 0; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; } //建树 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; } //编码 char* cd = NULL; hc = (huffmancode)malloc((n + 1) * sizeof(char*)); if(hc) { cd = (char*)malloc(n * sizeof(char)); if (cd) { cd[n - 1] = '\0'; //字符对应的前缀编码 unsigned int start, c, f; 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)); if(hc) { strcpy(hc[i], &cd[start]); } } } free(cd); } } } void select(huffmantree& ht, int n, int &s1, int &s2) { //待改进 /** function: * 权值最大不超过MAXSIZE * 筛选左子树和右子树使权值最小 */ int myhash[MAXSIZE] = { 0 }; int i; int tmp; int flag; //权值被正常存入数组 for (i = 1; i <= n; i++) { flag = 0; if (ht[i].weight != 0 && ht[i].parent == 0) { tmp = ht[i].weight; //处理权值相等的情况 while (!flag) { if(myhash[tmp] == 0) { myhash[tmp] = i; flag = 1; } else tmp++; } } } i = 1; int selector = 1; while (selector <= 2) { if (myhash[i] != 0) { if (selector == 1) s1 = myhash[i]; else s2 = myhash[i]; selector++; } i++; } } void huffmaninput(unsigned int* w, char* str) { /** function * 输入： * 1.字符集个数 * 2.输入字符 * 2.权值 */ cout << "请输入字符集个数(不超过31个):" << endl; cin >> n; for(int i=0; i<n; i++) { cout << "输入第" << i+1 << "个字符:"; cin >> str[i]; cout << "权值(互不相同且大于0):"; cin >> w[i]; } } void huffmanoutput(huffmantree ht, huffmancode hc) { /** function * 1.输出huffman树 * 2.输出huffman编码 * 声明：输出格式出于借鉴 */ cout << setw(5) << "n" << setw(12) << "weight" << setw(12) << "parent" << setw(12) << "lchild" << setw(12) << "rchild" << setw(12) << "char" << setw(12) << "code" << endl; int i; for(i=1; i<=n; i++) { cout << setw(5) << i << setw(12) << ht[i].weight << setw(12) << ht[i].parent << setw(12) << ht[i].lchild << setw(12) << ht[i].rchild << setw(12) << str_extern[i-1] << setw(12) << hc[i] << endl; } for(; i<=2*n-1; i++) { cout << setw(5) << i << setw(12) << ht[i].weight << setw(12) << ht[i].parent << setw(12) << ht[i].lchild << setw(12) << ht[i].rchild << setw(12) << '\0' << setw(12) << '\0' << endl; } } void huffmantranstr(huffmancode hc) { /** function * 转码 */ cout << "请输入待转码字符序列" << endl; cin >> str; int i=0, j; while (str[i] != '\0') { for(j=0; j<n; j++) if(str[i] == str_extern[j]) cout << hc[j+1]; i++; } cout << endl; } void decode(huffmantree &ht, huffmancode &hc) { /** function * 译码 */ cout << "请输入待译码字符序列" << endl; cin >> str; int i=0; int pos = 2*n-1; while (str[i] != '\0') { if(str[i] == '0') pos = ht[pos].lchild; else pos = ht[pos].rchild; if(ht[pos].lchild==0 && ht[pos].rchild==0) { for(int j=0; j<n; j++) if(w[j] == ht[pos].weight) cout << str_extern[j]; pos = 2*n-1; } i++; } cout << endl; } void show() { cout << "\t\t\t\t\t\t******huffman编码******\t" << endl; //cout << "输入下方序号，选择相应功能" << endl; cout << "1.转码" << endl; cout << "2.译码" << endl; cout << "3.输出树和编码" << endl; cout << "4.退出" << endl; cout << "请选择功能：" << endl; } void out() { int option; scanf(" %d", &option); switch (option) { case 1: huffmantranstr(hc); break; case 2: decode(ht, hc); break; case 3: huffmanoutput(ht, hc); break; case 4: exit(0); break; default: cout << "error!"; break; } cout << endl; system("pause"); }