• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            no_rain

            huffman 編碼學(xué)習(xí)

            該程序?qū)崿F(xiàn)的功能是將一段字符串進(jìn)行統(tǒng)計(jì)之后再進(jìn)行huffman編碼(二進(jìn)制);
            注意的地方:
            1,huffman編碼要用到貪心算法,所以用priority_queue可以在常量時(shí)間內(nèi)取出和插入值。
            2,靜態(tài)建樹:huffman樹的節(jié)點(diǎn)表示方法采用了最多的變量,即父親節(jié)點(diǎn),左右子節(jié)點(diǎn)(因?yàn)槌绦蛑写_實(shí)有這種需要,這里不同與二叉堆,無法通過在靜態(tài)樹(鏈表)的位置來確定其父親節(jié)點(diǎn)和子節(jié)點(diǎn)); 

              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 閱讀(409) 評(píng)論(0)  編輯 收藏 引用


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            導(dǎo)航

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

            統(tǒng)計(jì)

            常用鏈接

            留言簿

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            成人午夜精品久久久久久久小说| 久久久久久国产精品无码下载| 久久精品中文字幕第23页| 久久av免费天堂小草播放| 久久久久久久综合综合狠狠| 2021国产精品久久精品| 亚洲精品乱码久久久久久久久久久久 | 久久精品国产亚洲综合色| 国产AⅤ精品一区二区三区久久| 久久影院午夜理论片无码| 区久久AAA片69亚洲| 久久无码av三级| 狠狠色丁香久久婷婷综合_中 | 精品99久久aaa一级毛片| 久久久久久久免费视频| 91久久精品视频| 国内精品久久人妻互换| 国产精品久久新婚兰兰| 久久免费高清视频| 热re99久久6国产精品免费| 久久一区二区三区免费| 青青草国产精品久久| 亚洲精品白浆高清久久久久久 | 狠狠色伊人久久精品综合网 | 蜜臀av性久久久久蜜臀aⅴ麻豆| 欧美与黑人午夜性猛交久久久| WWW婷婷AV久久久影片| 性欧美丰满熟妇XXXX性久久久| 亚洲欧美日韩精品久久亚洲区 | 久久久久99精品成人片试看| 香蕉久久AⅤ一区二区三区| 久久电影网一区| 久久亚洲国产午夜精品理论片| 久久精品国产第一区二区三区| 亚洲愉拍99热成人精品热久久| 97久久国产综合精品女不卡| 久久无码AV一区二区三区| 久久久国产视频| 亚洲国产视频久久| 亚洲精品无码专区久久久| 欧美午夜精品久久久久免费视|