dz_1997
dz_1997
2017-11-18 14:18

数据结构huffman编码树问题

  • 数据结构

以下是用于将树节点按权值插入forest数组的函数(权值小的在前),在调试中发现插入函数有问题,但编译器未报错。求大神指点,谢谢。
void insert(huffnode* temp)
{
curr=0;
if(size==0)
{
nodearray[curr]=temp;
size++;
}
else
{
while(temp->getweight()>=nodearray[curr]->getweight())
{
curr++;
}

        for(int i=size;i>curr;i--)
        {
            nodearray[i]=nodearray[i-1];
        }
        nodearray[curr]=temp;
        delete temp;
        size++;
    }
}

以下为调试时的代码

#include
#include
using namespace std;

class huffnode
{
private:
int weight;
char it='#';
huffnode* lc;
huffnode* rc;
public:
huffnode(char _it,int _weight)
{
it=_it;weight=_weight;lc=NULL;rc=NULL;
}
huffnode(huffnode* _lc,huffnode* _rc)
{
lc=_lc;rc=_rc;
weight=lc->getweight()+rc->getweight();
}
int getweight(){return weight;}
bool isleaf()
{
if(it=='#')
return false;
else
return true;
}
huffnode* getlc(){return lc;}
huffnode* getrc(){return rc;}
char getit(){return it;}
};

class hufftree
{
private:
huffnode* root;
public:
hufftree(huffnode* rt)
{
root=rt;
}
huffnode* getroot(){return root;}

};

void inorder(huffnode* rt)
{
if(rt!=NULL)
{
inorder(rt->getlc());
cout<getit();
inorder(rt->getrc());

}

}

class forest
{
private:
int size;
int curr;
int maxsize;
huffnode** nodearray;
public:
forest(int m)
{
size=0;curr=0;maxsize=m;nodearray=new huffnode*[maxsize];
}
void insert(huffnode* temp)
{
curr=0;
if(size==0)
{
nodearray[curr]=temp;
size++;
}
else
{
while(temp->getweight()>=nodearray[curr]->getweight())
{
curr++;
}

        for(int i=size;i>curr;i--)
        {
            nodearray[i]=nodearray[i-1];
        }
        nodearray[curr]=temp;
        delete temp;
        size++;
    }
}

huffnode* remove()
{
    huffnode* temp;
    temp=nodearray[0];
    for(int i=0;i<size-1;i++)
    {
        nodearray[i]=nodearray[i+1];
    }
    size--;
    return temp;
}

huffnode* makehuff()
{
    while(size!=1)
    {
        huffnode* temp1;
        huffnode* temp2;
        temp1=remove();
        temp2=remove();
        huffnode* temp3= new huffnode(temp1,temp2);
        insert(temp3);
    }
    return nodearray[0];
}

huffnode** getarray()
{
    return nodearray;
}

};

int main()
{
int n;
cin>>n;
forest f(n);
string _f[n];
for(int i=0;i {
char it;
int weight;
cin>>it>>weight;
//huffnode tempnode(it,weight);
f.insert(new huffnode(it,weight));
_f[i]=it;
cout<<_f[i];
}

cout<<endl;

for(int i=0;i<n;i++)
{
    cout<<f.getarray()[i]->getit()<<f.getarray()[i]->getweight();

}

return 1;

}

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答