Data Structures

Answer:

Algorithm for Huffman:
Input:
Characters : [C 1 ,C 2 ,…………C n ]
Weight : [W 1 ,W 2 ,………W n ]
where W i is the weight of C i
Step 1 :
One-node binary tree list is initiated.
Step 2 :
Repeat the process for n-1 times:
• search for the lowest weight in the list W' and W''and draw two trees T' and T''
• the trees are replaced with binary tree which contains the root value as W' + W''
• the subtree pointers are labeled as 0 and 1 respectively
Step 3 :
The character's code can be obtained by label in the path from root to the current node
Given:
Huffman code developed in "Exercise-7":
Consider the Message: "feed a deaf aged hag":
The Huffman code for the value "f" is as follows:
The Huffman code for the value "e" is as follows:
The Huffman code for the value "e" is as follows:
The Huffman code for the value "d" is as follows:
The Huffman code for the value "a" is as follows:
The Huffman code for the value "d" is as follows:
The Huffman code for the value "e" is as follows:
The Huffman code for the value "a" is as follows:
The Huffman code for the value "f" is as follows:
The Huffman code for the value "a" is as follows:
The Huffman code for the value "g" is as follows:
The Huffman code for the value "e" is as follows:
The Huffman code for the value "d" is as follows:
The Huffman code for the value "h" is as follows:
The Huffman code for the value "a" is as follows:
The Huffman code for the value "g" is as follows:
Thus the encoded message is as follows:

Answer:

Algorithm for Huffman:
Input:
Characters : [C 1 ,C 2 ,…………C n ]
Weight : [W 1 ,W 2 ,………W n ]
where W i is the weight of C i
Step 1 :
One-node binary tree list is initiated.
Step 2 :
Repeat the process for n-1 times:
• Search for the lowest weight in the list W' and W'' and draw two trees T' and T''
• The trees are replaced with binary tree which contains the root value as W' + W''
• The subtree pointers are labeled as 0 and 1 respectively
Step 3 :
The character's code can be obtained by label in the path from root to the current node
Given:
Use the given table to construct the Huffman code:
As per the Huffman's algorithm, a list of one-node binary tree is constructed in order of increasing order of their weight.
The two trees are selected that has the smallest weights; thus it results
.
From the list, select two of minimal weights "
".
From the list of 3 binary trees, select two of minimal weights "
".
From the list, select two of minimal weights "
":
From the list, select two of minimal weights "
".
Combine the two binary trees to get single resulting Huffman tree:
Complete Huffman tree.
Thus the Huffman code obtained from the tree:

Answer:

Problem plan:
• Include the required header files into the program.
• Use "struct" for tree node
• Allocate new tree to a node
• Define a function "encoding ()" to encode the string.
o check if the root node is null
o check if the leaf node is found
o call the function "encoding ()" to append 0
o call the function "encoding ()" to append 1
• Define a function "huff_tree ()" to generate huffman code
o Use map tp count the frequency
o store live nodes
o create leaf node and push the elements
o perform until more than 1 node in the tree
o pointer is stored to the root of the Huffman
o traverse and store the huffman codes
o print the huffman codes
• Define "main()" to demonstrate huffman technique
o Declare variables
o get input from user
o call the function "huff_tree()" to generate huffman code
Program:
/ ***********************************************************Run the code in c++ 11 compiler *
*Program to construct Huffman code and the encode a *
*message entered by the user *
********************************************************** /
/ / include header files
#include
#include
#include
#include
using namespace std;
/ / struct for tree node
struct Node
{
int f;
char ch;
Node *l, *r;
};
/ / allocation of new tree to a node
Node* g_N(char ch, int f, Node* l, Node* r)
{
Node* node = new Node();
/ / assign the node elements
node- ch = ch;
node- f = f;
node- l = l;
node- r = r;
/ / return after all the process has been done
return node;
}
/ / object for comparison
struct comp
{
bool operator()(Node* l, Node* r)
{
/ / the item with highest priority has lowest / / frequency
return l- f r- f;
}
};
/ / traverse and store in an huffman map
void encoding(Node* root, string tx, map huffmanCode)
{
/ / check if the root node is null
if (root == NULL)
return;
/ / if the leaf node is found
if (!root- l !root- r)
huffmanCode[root- ch] = tx;
/ / cal the function to append 0
encoding(root- l, tx + "0", huffmanCode);
/ / call the function to append 1
encoding(root- r, tx + "1", huffmanCode);
}
/ / / build tree and decode
void huff_tree(string inp)
{
/ / to count the frequency
map f;
for (char ch : inp)
f[ch]++;
/ / store live nodes
priority_queue , comp pq;
/ / create leaf node and push the elements
for (auto it : f)
pq.push(g_N(it.first, it.second, NULL, NULL));
/ / perform until more than 1 node in the tree
while (pq.size() != 1)
{
/ / remove nodes with highest priotity
Node *l = pq.top(); pq.pop();
Node *r = pq.top(); pq.pop();
/ / internal node is created and then a new node / / is added
int sum = l- f + r- f;
pq.push(g_N('\0', sum, l, r));
}
/ / pointer is stored to the root of the huffman tree
Node* root = pq.top();
/ / traverse and store the huffman codes
map huffmanCode;
encoding(root, "", huffmanCode);
/ / print the huffman codes
cout "Huffman Code :\n" endl;
for (auto it : huffmanCode)
cout it.first " " it.second endl;
/ / actual string
cout "\n actual string was :\n";
cout inp endl;
/ / print encoded string
string tx = "";
for (char ch : inp)
tx += huffmanCode[ch];
cout "\n encoded string is :\n" tx endl;
}
/ / main function to perform huffman encoding
int main()
{
/ / variable declaration
string inp;
cout "enter the string you want to decode:";
/ / get input from user
cin inp;
/ / call the fuction to generate huffman code
huff_tree(inp);
return 0;
}
Sample Output:
enter the string you want to decode:goodmorning
Huffman Code :
d 1100
g 00
i 1101
m 011
n 111
o 10
r 010
actual string was :
goodmorning
encoded string is :
001010110001110010111110111100