porterlu 2018-09-04 16:59 采纳率: 100%
浏览 289
已结题

Huffman数组越界,求问原因

 #include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
struct node
{
    char content;
    int value;
    bool visit;
    node* left;
    node* right;
    friend bool operator > (const node& a,const node& b)
    {
        return a.value > b.value;
    }
}tree[27],origin[27];
priority_queue <node,vector<node>,greater <node> > q;
string str;
int ch[27],len[27],sign1,sign2;
void huffman()
{
    while(q.size()!=1)
    {
        node n1=q.top();
        q.pop();
        node n2=q.top();
        q.pop();
        tree[sign1].content=' ';
        tree[sign1].value=n1.value+n2.value;
        tree[sign1].left=&n1;
        tree[sign1].right=&n2;
        tree[sign1].visit=false;
        q.push(tree[sign1]);
        sign1++;
    }
}
void depth_search(node* u,int depth)
{
    char c=u->content;
    if(c!=' ')
    {
        if(c=='_')
            len[26]=depth;
        else if(c>='A'&&c<='Z')
            len[c-'A']=depth;
    }
    u->visit=true;
    if(u->left!=NULL&&u->left->visit==false) {depth_search((u->left),depth+1); }
    if(u->right!=NULL&&u->right->visit==false) {depth_search((u->right),depth+1);}
}
int main(void)
{
   int i;
   while(cin>>str&&str!="END")
   {
       sign1=0; sign2=0;
       memset(ch,0,sizeof(ch));
       memset(len,0,sizeof(len));
       for(i=0;i<str.length();i++)
       {
           if(str[i]=='_')
                ch[26]++;
            else
                ch[str[i]-'A']++;
       }
       for(i=0;i<27;i++)
       {
           if(ch[i]==0) continue;
           if(i==26)
                origin[sign2].content='_';
            else
                origin[sign2].content=i+'A';
            origin[sign2].value=ch[i];
            origin[sign2].visit=false;
            origin[sign2].left=NULL; origin[sign2].right=NULL;
            q.push(origin[sign2]);
            sign2++;
       }
       node head;//=q.top();
       huffman();
       head=q.top();
       node k=*(head.left);
       node m=*(head.right);
       node j=*(k.right);
       cout<<head.value<<" "<<head.visit<<" "<<head.content<<endl;
       cout<<k.value<<" "<<k.visit<<" "<<k.content<<endl;
       cout<<m.value<<" "<<m.visit<<" "<<m.content<<endl;
       cout<<j.value<<" "<<j.visit<<" "<<j.content<<endl;
       depth_search(&head,0);
       int sum=0;
       for(i=0;i<27;i++)
       {
            sum+=ch[i]*len[i];
       }
        cout<<sum<<endl;
   }
   return 0;
}

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
    • ¥20 有关区间dp的问题求解
    • ¥15 多电路系统共用电源的串扰问题
    • ¥15 slam rangenet++配置
    • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
    • ¥15 ubuntu子系统密码忘记
    • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
    • ¥15 保护模式-系统加载-段寄存器
    • ¥15 电脑桌面设定一个区域禁止鼠标操作
    • ¥15 求NPF226060磁芯的详细资料