ハフマン復号化アルゴリズムを作成しようとしています。私は反復的なアプローチを取ることにしました。私が抱えている主な問題は、ノードタイプ構造体に関係していると思います。DDD では、右の *child はありません。これがなぜなのかについての提案はありますか?あちこち検索しましたが、問題の解決策が見つかりませんでした。助言がありますか?
簡単にするために、残りのプログラムは省略しました。
#include <fstream>
#include <iostream>
#include <queue>
#include <iomanip>
#include <map>
#include <string>
#include <cassert>
#include <sstream>
using namespace std;
typedef unsigned int uint;
struct nodetype
{
// constructor
nodetype( char symbol, nodetype * left, nodetype * right) :
symbol( symbol ), left( left ), right( right )
{ }
char symbol;
nodetype* left;
nodetype* right;
};
void createDecodingTree( nodetype* root,
nodetype* &iter,
string &codeSubstring,
char leaf )
{
string code = codeSubstring;
nodetype* newLeaf = new nodetype( leaf, NULL, NULL );
uint index = 0;
uint codeLength = code.length();
iter = root;
//traverse through the code until the second to last bit
//for( uint i = 0; i <= code.length()-1; i++ );
while( codeLength - 1 > 0 )
{
if( code.at(index) == '0' )
{
if( iter->left == NULL )
{
nodetype* newLeft = new nodetype( '\0', NULL, NULL );
iter->left = newLeft;
iter = iter->left;
}
else{
iter = iter->left;
}
}
if( code.at(index) == '1' )
{
if( iter->right == NULL )
{
nodetype* newRight = new nodetype( '\0', NULL, NULL );
iter->right = newRight;
iter = iter->right;
}
else{
iter = iter->right;
}
}
codeLength--;
index++;
}
//now make a new leaf based on the last bit
if( code.at( code.length() - 1 ) == '0' )
iter->left = newLeaf;
else{
iter->right = newLeaf;
}
}
そして、これがルートを初期化する方法です。
nodetype* root = new nodetype( '\0', NULL, NULL );