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

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


            亚洲国产成人精品91久久久| 精品一区二区久久| 国产精品成人无码久久久久久 | 久久97久久97精品免视看秋霞| 国产一区二区三精品久久久无广告| 国产999精品久久久久久| 粉嫩小泬无遮挡久久久久久| 久久久久亚洲精品天堂久久久久久| 国产精品99久久不卡| 日韩十八禁一区二区久久| 久久人人爽人人澡人人高潮AV| 香蕉99久久国产综合精品宅男自 | 久久久WWW成人免费毛片| 天天综合久久一二三区| 狠狠久久亚洲欧美专区| 欧美精品福利视频一区二区三区久久久精品 | 久久久国产视频| 日本精品久久久久中文字幕| 狠狠综合久久AV一区二区三区| 久久国产精品-久久精品| 一级做a爰片久久毛片免费陪| 久久精品国产只有精品2020| 亚洲国产精品久久电影欧美| 久久久这里有精品中文字幕| 久久最近最新中文字幕大全| 综合人妻久久一区二区精品| 亚洲成av人片不卡无码久久| 99久久免费国产精品| 久久香蕉国产线看观看乱码| 久久ZYZ资源站无码中文动漫| 久久精品中文字幕一区| 无码人妻久久一区二区三区蜜桃| 国产精品九九久久免费视频| 2022年国产精品久久久久| 色88久久久久高潮综合影院| 无遮挡粉嫩小泬久久久久久久| 久久夜色精品国产噜噜亚洲a | 亚洲AV日韩AV永久无码久久| 亚洲午夜无码AV毛片久久| 欧美日韩精品久久久久| 日本加勒比久久精品|