• <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>
            隨筆-65  評(píng)論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:對(duì)輸入字符串【長(zhǎng)度不知,僅含26個(gè)大寫英文字母和一個(gè)空格表示符‘_’,共27種字符】,
             4             統(tǒng)計(jì)每種字符出現(xiàn)頻度,按哈夫曼編碼原理給出最小的編碼位數(shù)之和,得出與8位固定字長(zhǎng)
             5             編碼的比率【保留一位小數(shù)】。
             6 How to Do:    哈夫曼編碼原理的理解及優(yōu)先隊(duì)列的運(yùn)用<priority_queue>,引用頭文件<queue>
             7   */
             8 #include <iostream>
             9 #include <string.h>
            10 #include <queue>
            11 #include <algorithm>
            12 using namespace std;
            13 #define lenth 300
            14 int main(){
            15     //freopen("in.txt","r",stdin);
            16     char str[1000];//輸入字符串
            17     while(scanf("%s",str),strcmp(str,"END")!=0){
            18         int lenStr=strlen(str);
            19         int worse=lenStr<<3;//固定字長(zhǎng)編碼所需的總位數(shù)
            20         char ch[lenth];int lenCh=0;//輸入字符的種類
            21         int i,j,num[lenth];//對(duì)應(yīng)每種字符的數(shù)目,無需關(guān)注具體對(duì)應(yīng)的是哪個(gè)字符,只需記錄數(shù)目即可。【為什么呢?】
            22         memset(num,0,lenth);//字符數(shù)目數(shù)組初始置零
            23         //對(duì)字符串逐個(gè)統(tǒng)計(jì)出現(xiàn)次數(shù)
            24         for(i=0;i<lenStr;i++){
            25             for(j=0;j<lenCh;j++){
            26                 if(str[i]==ch[j]){
            27                     num[j]++;break;
            28                 }
            29             }
            30             if(j==lenCh){
            31                 ch[j]=str[i];num[j]++;lenCh++;
            32             }
            33         }
            34         sort(num,num+lenCh);//對(duì)得到的字符數(shù)目【大于零,即至少出現(xiàn)過一次,才存在統(tǒng)計(jì)必要】序列進(jìn)行升序快排
            35         priority_queue<int,vector<int>,greater<int> >    que;//對(duì)于int整型數(shù)據(jù),進(jìn)行自小至大的優(yōu)先級(jí)排列
            36         for(i=0;i<lenCh;i++)    que.push(num[i]);
            37         int sum=0;
            38         while(true){
            39             int aa=que.top();    que.pop();
            40             if(que.empty())    {
            41                 if(lenCh==1)    sum=aa;
            42                 break;
            43             }
            44             int bb=que.top();    que.pop();
            45             sum+=aa+bb;        que.push(aa+bb);
            46         }
            47         printf("%d %d %.1lf\n",worse,sum,worse*1.0/sum);
            48     }
            49     return 0;
            50 }
            posted on 2012-03-02 14:48 Leo.W 閱讀(850) 評(píng)論(0)  編輯 收藏 引用

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


            国产精品欧美久久久久天天影视 | 性做久久久久久久久老女人 | 性欧美大战久久久久久久| 亚洲国产成人精品无码久久久久久综合| 99久久伊人精品综合观看| 天堂无码久久综合东京热| 无码人妻精品一区二区三区久久| 国内精品久久九九国产精品| 中文精品99久久国产| 精品综合久久久久久97超人| 中文字幕无码久久精品青草| 国产美女久久精品香蕉69| 日本精品久久久久久久久免费| 久久人妻少妇嫩草AV无码专区| 国产精品美女久久久久av爽| 久久精品国产亚洲av影院| 欧美大战日韩91综合一区婷婷久久青草 | 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 伊人久久大香线蕉av不变影院| 狠色狠色狠狠色综合久久 | 亚洲国产成人精品无码久久久久久综合 | 久久人人爽人爽人人爽av| 精品综合久久久久久888蜜芽| 偷偷做久久久久网站| 国产精品丝袜久久久久久不卡| 久久久精品2019免费观看| 国产精品久久久久久久app| 久久噜噜久久久精品66| 欧美久久精品一级c片片| 久久精品国产亚洲AV嫖农村妇女| 亚洲?V乱码久久精品蜜桃 | 亚洲中文字幕久久精品无码喷水 | 无码日韩人妻精品久久蜜桃 | 国产亚洲精久久久久久无码AV| 国产三级久久久精品麻豆三级 | 国产精品青草久久久久婷婷| 久久天天躁狠狠躁夜夜躁2O2O | 色综合久久久久网| 久久美女人爽女人爽| 日本三级久久网| 久久精品国产欧美日韩|