• <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>

            pku1223 DEHUFF 哈夫曼樹確定,PKU1261簡化版

            題目描述:
            一個哈夫曼樹,給出一個字符串以及編碼,要求確定哈夫曼樹
            如果無解或者多解,輸出MULTIPLE TABLES

            解法:
            同pku1261,那題我寫了詳細的報告,http://www.shnenglu.com/yzhw/archive/2011/01/11/138368.aspx

            代碼:
              1# include <cstdio>
              2# include <cstring>
              3# include <stack>
              4using namespace std;
              5struct node
              6{
              7    int count;
              8    node *c[2];
              9    node *pre;
             10    char end;
             11    node()
             12    {
             13        count=0;
             14        c[0]=c[1]=pre=NULL;
             15        end=0;
             16    }

             17}
            ;
             18node *head=NULL,*ans[27],*res[27];
             19char str[1024],code[1024];
             20int count,total;
             21bool used[27],hasfind;
             22void clear(node *p=head)
             23{
             24    if(!p) return;
             25    clear(p->c[0]);
             26    clear(p->c[1]);
             27    delete p;
             28}

             29void init()
             30{
             31    clear();
             32    head=new node();
             33    head->count=1;
             34    memset(used,0,sizeof(used));
             35    memset(ans,0,sizeof(ans));
             36    count=2;
             37    hasfind=false;
             38}

             39bool solve(int p1,int p2,node *p=head)
             40{
             41    if(count>total||p->end) return 0;
             42    else if(str[p1]=='\0'&&code[p2]=='\0'
             43    {
             44        if(!hasfind)
             45        {
             46            hasfind=true;
             47            memcpy(res,ans,sizeof(ans));
             48            return 0;
             49        }

             50        else return 1;
             51    }

             52    else if(str[p1]=='\0'return 0;
             53    else if(str[p1]==' '&&ans[26]||str[p1]!=' '&&ans[str[p1]-'A'])
             54    {
             55        stack<int> s;
             56        node *t=ans[str[p1]==' '?26:str[p1]-'A'];
             57        while(t->pre)
             58        {
             59            s.push(t->pre->c[0]==t?0:1);
             60            t=t->pre;
             61        }

             62        for(;code[p2]!='\0'&&!s.empty();p2++)
             63            if(code[p2]==s.top()+48)
             64                s.pop();
             65            else return 0;
             66        if(!s.empty()) return 0;
             67        else return solve(p1+1,p2);
             68    }

             69    else
             70    {
             71        p->count++;
             72        if(p->count==1)
             73        {
             74            p->end=str[p1];
             75            ans[str[p1]==' '?26:str[p1]-'A']=p;
             76            if(solve(p1+1,p2)) return 1;
             77            p->end=0;
             78            ans[str[p1]==' '?26:str[p1]-'A']=NULL;
             79        }

             80        if(code[p2]=='\0')
             81        {
             82            p->count--;
             83            return 0;
             84        }

             85        if(p->count==1)
             86            count++;
             87        if(p->c[code[p2]-'0']==NULL)
             88        {
             89            p->c[code[p2]-'0']=new node();
             90            p->c[code[p2]-'0']->pre=p;
             91        }

             92        if(solve(p1,p2+1,p->c[code[p2]-'0'])) return 1;
             93        if(p->count==1)
             94            count--;
             95        p->count--;
             96        return 0;
             97        
             98    }

             99}

            100int main()
            101{
            102    //freopen("ans.txt","w",stdout);
            103    int test;
            104    scanf("%d",&test);
            105    getchar();
            106    for(int t=1;t<=test;t++)
            107    {
            108        init();
            109        gets(str);
            110        gets(code);
            111        total=0;
            112        for(int i=0;str[i]!='\0';i++)
            113            used[str[i]==' '?26:str[i]-'A']=true;
            114        for(int i=0;i<27;i++)
            115            total+=used[i];
            116        printf("DATASET #%d\n",t);
            117       if(solve(0,0)||!hasfind) printf("MULTIPLE TABLES\n");
            118       else if(hasfind)
            119       {
            120           if(used[26])
            121           {
            122               printf("  = ");
            123               stack<int> s;
            124               while(res[26]->pre)
            125               {
            126                   s.push(res[26]==res[26]->pre->c[0]?0:1);
            127                   res[26]=res[26]->pre;
            128               }

            129               while(!s.empty())
            130               {
            131                   printf("%d",s.top());
            132                   s.pop();
            133               }

            134               printf("\n");
            135           }

            136           
            137               for(int i=0;i<26;i++)
            138                   if(used[i])
            139                   {
            140                       printf("%c = ",i+65);
            141                       stack<int> s;
            142                       while(res[i]->pre)
            143                       {
            144                           s.push(res[i]==res[i]->pre->c[0]?0:1);
            145                           res[i]=res[i]->pre;
            146                       }

            147                       while(!s.empty())
            148                       {
            149                           printf("%d",s.top());
            150                           s.pop();
            151                       }

            152                       printf("\n");
            153                   }

            154       }

            155
            156    }

            157    return 0;
            158}

            posted on 2011-01-16 14:01 yzhw 閱讀(238) 評論(0)  編輯 收藏 引用 所屬分類: search 、data struct

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久青青草原综合伊人| 久久久久亚洲av成人网人人软件 | 久久99久久99精品免视看动漫| 777午夜精品久久av蜜臀| 日韩乱码人妻无码中文字幕久久 | 久久综合九色综合欧美狠狠| 91精品国产91久久久久久蜜臀| 久久一区二区免费播放| 狠狠色婷婷久久一区二区| 色综合久久最新中文字幕| 亚洲国产视频久久| www.久久热| 精品国产青草久久久久福利| 久久精品国产91久久综合麻豆自制| 久久无码AV中文出轨人妻| 国产亚洲欧美精品久久久| 亚洲国产成人久久精品99| 国产美女久久久| 7777久久久国产精品消防器材| 久久久久无码中| 伊人久久综在合线亚洲2019 | 久久精品国产亚洲av麻豆图片| aaa级精品久久久国产片| 中文字幕乱码久久午夜| 久久人人爽人人精品视频| 久久er国产精品免费观看2| 狠狠色丁香婷婷久久综合| 久久免费观看视频| 久久久久国产精品嫩草影院 | 亚洲欧美一区二区三区久久| 久久精品国产只有精品2020| 无码久久精品国产亚洲Av影片 | 无码国内精品久久人妻蜜桃| 亚洲精品国产综合久久一线| 久久久亚洲精品蜜桃臀| 久久国产福利免费| 久久伊人五月天论坛| 久久无码精品一区二区三区| 欧美久久综合九色综合| 亚洲欧美成人久久综合中文网| 亚洲综合久久久|