huffman编码.rar

  • frameking
    了解作者
  • C/C++
    开发工具
  • 325KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 1
    下载次数
  • 2021-01-03 13:05
    上传日期
功能实现 (函数定义内部有对函数功能的简介) 1.编码 2.转码 3.简单菜单 4.字符集及权值可自定义
huffman编码.rar
  • final
  • bin
  • Debug
  • final.exe
    1.5MB
  • obj
  • Debug
  • main.o
    24.1KB
  • main.cpp
    7.5KB
  • final.layout
    358B
  • final.depend
    220B
  • main.cpp.save
    7.3KB
  • final.cbp
    1KB
内容介绍
/** 程序名称: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"); }
评论
    相关推荐
    • Huffman 编码
      实现了Huffman编码算法: 1、使用链表结构。 2、使用《数据结构》(严蔚敏,C语言版)中给出的算法; 3、增加预先排序的功能的算法
    • huffman编码
      huffman编码合集,里面收录了各种数据结构的Huffman编码
    • huffman 编码
      对一个灰度图像进行huffman编码,C++
    • 实现Huffman编码
      HUFFMAN编码又称哈夫曼编码,是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,...
    • huffman编码
      在MFC框架下实现huffman编码,同时计算平均码长,信息熵,编码效率
    • Huffman编码
      1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码
    • Huffman 编码
      VC++完全版 能够直接在VC6.0上运行
    • huffman编码
      huffman编码(编码加解码三个),这个编码是信息论以及各种数据结构的实验,都有用的东西
    • Huffman编码
      数据结构 C++ Huffman编码 对文件进行压缩,生成一个huf文件,还可以解压缩。
    • Huffman 编码
      哈夫曼压缩算法,刚开始学习的可以下载下来参考参考,代码注释比较完整