STL实现哈夫曼算法

1. 云栖社区>
2. 博客>
3. 正文

## STL实现哈夫曼算法

class hNode

public:
friend bool operator > (hNode n1,hNode n2);　//定义了大于符号，供优先队列排列使用
hNode(string d="",int i=0,hNode* l = NULL,hNode* r =NULL):left(l),right(r),data(d),value(i){}
hNode* left;
hNode* right;
string data; //储存的字符串
int value; //字符串出现的次数
};

bool operator >(hNode n1,hNode n2)

return n1.value > n2.value;

while(...)

std::priority_queue<hNode> q;
.....
hNode h1 = q.top();
q.pop();
hNode h2 = q.top();
q.pop();
hNode r;
r.left = h1;
r.right = h2;
r.value = h1.value + h2.value;
q.push(r);

struct phNodeComp

bool operator () (const hNode*& left,const hNode*& right) const

return left->value > right->value;
}

}

priority_queue<hNode*,vector<hNode*>,phNodeComp > pq;

posted on 2004-03-19 19:47 Justin Shen 评论(6) 编辑 收藏

# re: 用C++ std::priority_queue　实现哈夫曼算法
earthharp

Posted @ 2004-03-20 01:06
# re: 用C++ std::priority_queue　实现哈夫曼算法
Justin Shen

vector<int> v;
void DoPrint(hNode* r)

if (r->left ==NULL && r->right == NULL)

cout << r->data <<": ";
for (int i = 0;i<v.size();++i)
cout << v;
cout << endl;
v.pop_back();
delete r;
return ;
}

if (r->left)

v.push_back(0);
DoPrint(r->left);
}

if (r->right)

v.push_back(1);
DoPrint(r->right);
}

v.pop_back();
}