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条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥100 Jenkins自动化部署—悬赏100元
    • ¥15 关于#python#的问题:求帮写python代码
    • ¥20 MATLAB画图图形出现上下震荡的线条
    • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
    • ¥15 perl MISA分析p3_in脚本出错
    • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
    • ¥15 ubuntu虚拟机打包apk错误
    • ¥199 rust编程架构设计的方案 有偿
    • ¥15 回答4f系统的像差计算
    • ¥15 java如何提取出pdf里的文字?