Huffman数组越界,求问原因 40C
 #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;
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!