no_rain

huffman 编码学习

该程序实现的功能是将一段字符串进行统计之后再进行huffman编码(二进制);
注意的地方:
1,huffman编码要用到贪心算法,所以用priority_queue可以在常量时间内取出和插入值。
2,静态建树:huffman树的节点表示方法采用了最多的变量,即父亲节点,左右子节点(因为程序中确实有这种需要,这里不同与二叉堆,无法通过在静态树(链表)的位置来确定其父亲节点和子节点); 

  1 #include<iostream>
  2 #include<cstring>
  3 #include<queue>
  4 #include<cstdlib>
  5 using namespace std;
  6 const int MAXSIZE = 27;
  7 class huffNode{
  8 public:
  9   int pr;
 10   int lc , rc;
 11   char s;
 12   int pow;
 13   bool operator < (const huffNode& b)const{
 14     return pow > b.pow;
 15   }
 16 };
 17 huffNode huff[MAXSIZE * 2];
 18 string buf;
 19 int count[26];
 20 priority_queue<huffNode> greed;
 21 //for the sake of convenience , assume that the
 22 //standard input is from 'a' to 'z'.
 23 int  input(){
 24   cout << "input the text!"<<endl;
 25   cin >> buf;
 26   for(int i = 0; i < 26 ; i++) count[i] = 0;
 27   memset(huff , 0, sizeof(huff));
 28   for(int i = 0; i < buf.length();i++)count[buf[i]-'a']++;
 29   int len = 0;
 30   for(int i = 0 ,j = 0; i < 26; i++)
 31     if(count[i]){
 32       huff[j].s = i + 'a';
 33       huff[j].pow = count[i];
 34       huff[j].pr = j;
 35       cout << "the" << ' '<<'\''<< char(i+'a') <<'\''
 36        <<' '<<"have arisen for " <<count[i]<<" time(s)"
 37        <<endl;
 38       greed.push(huff[j]);
 39       len = j;
 40       j++;
 41     }
 42   return len;
 43 }
 44 
 45 int createTree(int len){
 46   if(len == 0) {
 47     cout << " Only one kind of alf !"<<endl;
 48     exit(1);
 49   }
 50   huffNode temp1 ,temp2,temp;
 51   while(!greed.empty()){
 52     temp1 = greed.top();
 53     greed.pop();
 54     temp2 = greed.top();
 55     greed.pop();
 56     len ++;
 57     temp.lc = temp1.pr;
 58     temp.rc = temp2.pr;
 59     huff[temp1.pr].pr = huff[temp2.pr].pr = len;
 60     temp.pr = len;
 61     temp.pow = temp1.pow + temp2.pow;
 62     huff[len] = temp;
 63     if(!greed.empty()) greed.push(temp);
 64   }
 65   return len;
 66 }
 67 
 68 void reserve(char * a){
 69   int len = strlen(a);
 70   for(int i = 0 ; i <= len/2 ;i ++)
 71     swap(a[i],a[len-i-1]);
 72 }
 73 struct code{
 74   char s;
 75   char co[50];
 76 };
 77 
 78 void coding(int len1,int len2){
 79   code* mycode = new code[len1+1];
 80   memset(mycode ,0 ,sizeof(mycode));
 81   for(int i = 0; i <= len1 ; i++){
 82     int j = i;
 83     int t = 0;
 84     mycode[i].s = huff[i].s;
 85     while(j < len2){
 86       if(huff[huff[j].pr].lc == j)
 87     mycode[i].co[t++] = '0';
 88       else mycode[i].co[t++] = '1';
 89       j = huff[j].pr ;
 90     }
 91     reserve(mycode[i].co);
 92     cout << "the code of " << mycode[i].s
 93      << " is " << mycode[i].co <<endl;
 94   }
 95   delete[] mycode;
 96 }
 97 
 98 int main(){
 99   int len1 = input();
100   int len2 = createTree(len1);
101   coding(len1,len2); 
102 }
103   
104   
105       
106 

posted on 2011-12-06 14:46 is-programmer 阅读(375) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2011年12月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜