You are suggested to use the teaching servers burrow.soic.indiana.edu or hulk.soic.indiana.edu or tank.soic.indiana.edu for practicing C programs.
The Huffman algorithm is given below:
HUFFMAN(C: list of characters with frequency) n = length(C) PriorityQueue PQ = C for i = 1 to n-1 create a new node z z.left = x = EXTRACT_MIN(PQ) z.right = y = EXTRACT_MIN(PQ) z.freq = x.freq + y.freq INSERT(PQ, z) return EXTRACT_MIN(PQ) // return the root of the tree
typedef struct node_struct { char symbol; int freq; struct node_struct *left; struct node_struct *right; } Node;
#include <stdio.h> #include <queue> using namespace std; typedef struct node_struct { char symbol; int freq; struct node_struct *left; struct node_struct *right; } Node; struct NodeCompare { bool operator()(const Node &n1, const Node &n2) const { return n1.freq > n2.freq; } }; int main() { int n = 6; Node nodeList[6] = { {'a', 45, NULL, NULL}, {'b', 13, NULL, NULL}, {'c', 12, NULL, NULL}, {'d', 16, NULL, NULL}, {'e', 9, NULL, NULL}, {'f', 5, NULL, NULL} }; std::priority_queue<Node, vector<Node>, NodeCompare> PQ; for(int i = 0; i < n; ++i) PQ.push(nodeList[i]); for(int i = 0; i < n; ++i) { Node t; t = PQ.top(); // Getting the min item, the item still stays in the Queue PQ.pop(); // Popping out this item printf("%c %d\n", t.symbol, t.freq); } return 0; }
// Our created new Node, we could also use malloc() to create this Node *x = new Node; Node t; t = PQ.top(); // Getting the min item, the item still stays in the Queue PQ.pop(); // Popping out this item // Copying t value into our created x node, we will not work anymore with t after this point x->symbol = t.symbol; x->freq = t.freq; x->left = t.left; x->right = t.right;
CALL printTree(Root, 0); global character array codeword printTree(T, depth) { if (T.symbol is not 0) { print "Codeword for <T.symbol> is <codeword>" Return } codeword[depth] := "0" printTree(Left of T, depth+1) codeword[depth] := "1" printTree(Right of T, depth+1) }