• <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è)大寫(xiě)英文字母和一個(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;//輸入字符的種類(lèi)
            21         int i,j,num[lenth];//對(duì)應(yīng)每種字符的數(shù)目,無(wú)需關(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)過(guò)一次,才存在統(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è)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            亚洲AV无码久久精品狠狠爱浪潮 | 亚洲国产成人久久一区久久| 狠狠综合久久综合中文88| 激情综合色综合久久综合| 伊人久久成人成综合网222| 狠狠色噜噜色狠狠狠综合久久 | 久久无码AV中文出轨人妻| 亚洲精品无码专区久久久| 91久久九九无码成人网站| 久久久一本精品99久久精品88| 久久香综合精品久久伊人| 久久久黄片| 久久亚洲国产精品一区二区| 久久五月精品中文字幕| 久久99热精品| 久久久久人妻精品一区| 久久精品国产福利国产琪琪| 国产精品对白刺激久久久| 中文字幕亚洲综合久久菠萝蜜| 久久精品国产精品亚洲精品| 性做久久久久久久| 色综合久久夜色精品国产| 久久精品国产第一区二区| 精品一区二区久久| 久久亚洲AV成人无码国产 | A级毛片无码久久精品免费| 国内精品久久久久久久久电影网| 精品久久久无码中文字幕| 999久久久无码国产精品| 亚洲欧美伊人久久综合一区二区 | 久久精品aⅴ无码中文字字幕重口| 久久精品国产72国产精福利| 国产精品久久久久影视不卡| 国产亚洲色婷婷久久99精品| 午夜精品久久久久久久久| 国产精品久久久香蕉| 一本色道久久综合| 久久er99热精品一区二区| 丰满少妇人妻久久久久久4| 久久99精品久久久久久hb无码| 7777精品久久久大香线蕉|