Pagini recente » Cod sursa (job #1244100) | Cod sursa (job #1935278) | Cod sursa (job #308399) | Cod sursa (job #2875352) | Cod sursa (job #1216767)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("huffman.in");
ofstream out("huffman.out");
class Node {
public:
Node(unsigned _symId, unsigned _occrs) :
symId(_symId),
occrs(_occrs),
parent(nullptr),
isOne(false)
{
childs[0] = nullptr;
childs[1] = nullptr;
}
Node(Node* child0, Node* child1) :
symId(0),
occrs(child0->occrs + child1->occrs),
isOne(false)
{
childs[0] = child0;
child0->parent = this;
childs[1] = child1;
child1->parent = this;
child1->isOne = true;
symId = 0;
}
friend ostream& operator<<(ostream& os, const Node &node) {
os << node.symId << ':' << node.occrs << ':' << node.isOne;
return os;
}
bool getCode() const {
return isOne;
}
Node* getParent() const {
return parent;
}
unsigned getOccrs() const {
return occrs;
}
private:
unsigned symId;
unsigned occrs;
Node* parent;
bool isOne;
Node* childs[2];
};
struct Code {
unsigned long long code;
unsigned lvl;
};
Code getCode(const Node* nd, unsigned lvl) {
if(nd->getParent()) {
Code c = getCode(nd->getParent(),lvl+1);
c.code += nd->getCode()*(1ull<<lvl);
return c;
}
else {
return {0,lvl};
}
}
bool comp(const Node* a, const Node* b) {
return a->getOccrs() > b->getOccrs();
}
queue<Node*> symQueue;
queue<Node*> midQueue;
Node* getNext() {
if(symQueue.empty()) {
Node* ret = midQueue.front();
midQueue.pop();
return ret;
}
if(midQueue.empty()) {
Node* ret = symQueue.front();
symQueue.pop();
return ret;
}
if(symQueue.front()->getOccrs() < midQueue.front()->getOccrs()) {
Node* ret = symQueue.front();
symQueue.pop();
return ret;
}
else {
Node* ret = midQueue.front();
midQueue.pop();
return ret;
}
}
int main() {
size_t nrSyms;
in >> nrSyms;
vector<Node*> syms(nrSyms+1, nullptr);
for(size_t i = 1; i <= nrSyms; ++i) {
unsigned nrOccrs;
in >> nrOccrs;
syms[i] = new Node(i,nrOccrs);
symQueue.push(syms[i]);
}
Node *child0, *child1;
while(symQueue.size() + midQueue.size() > 2) {
child0 = getNext();
child1 = getNext();
midQueue.push(new Node(child0,child1));
}
child0 = getNext();
child1 = getNext();
Node* parent = new Node(child0,child1);
vector<Code> codes(nrSyms+1);
unsigned long long len = 0;
for(size_t i = 1; i <= nrSyms; ++i) {
codes[i] = getCode(syms[i],0);
len += codes[i].lvl*syms[i]->getOccrs();
}
out << len << '\n';
for(size_t i = 1; i <= nrSyms; ++i) {
out << codes[i].lvl << ' ' << codes[i].code << '\n';
}
}