Question

Write a program that takes a string of characters (including spaces) as input, computes the frequency of each character, sorts them by frequency, and outputs the Huffman code for each character.   When you are writing your program, you should first test it on a string of 7 characters, so you can check it. PLEASE NOTE: Your program must work for any text that has upper and lower case letters digits 0 - 9, commas, periods, and spaces. Please submit the source code (cpp) file in standard C++ as one file. Then upload a screenshot of the output as another file.Also submit the cpp source code as trxt attachment to email.
Make sure your program works. Note the deadline. It will be posted an additional 5 days, but points deducted for every day after deadline.   Please manually calcu;ate runtime. Write the function and the order. Please also calculate how many bits were saved by Huffman coding.

Answer 1

Here i am providing the answer. Hope it helps. please give me a like. it helps me a lot.

OUTPUT--

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define max_height_of_tree 400
struct Node
{
char val;
int freq;
struct Node *left;
struct Node *right;
};
struct MinHeap
{
int heapArraySize;
int size;

struct Node** minHeapArray;
};
void exchange(struct Node** a,struct Node** b)
{
struct Node* t ;
t= *a;
*a = *b;
*b = t;
}
struct Node* getnode(char val, int freq)
{
struct Node* newNode= (struct Node*)malloc(sizeof(struct Node));

newNode->freq = freq;
newNode->val = val;
newNode->left =NULL;
newNode->right=NULL;
return newNode;
}

void minHeapify(struct MinHeap* minHeap, int index)

{

int least,left,right;
least = index;
left = 2 * index + 1;
right = 2 * index + 2;

if (left < minHeap->size && minHeap->minHeapArray[left]->freq < minHeap->minHeapArray[least]->freq)
{
least = left;
}

if (right < minHeap->size && minHeap->minHeapArray[right]->freq < minHeap->minHeapArray[least]->freq)

{
least = right;
}

if (least != index)
{

exchange(&minHeap->minHeapArray[least],&minHeap->minHeapArray[index]);
minHeapify(minHeap, least);
}
}

struct MinHeap* createMinHeap(int heapArraySize)

{

struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;

minHeap->heapArraySize = heapArraySize;

minHeap->minHeapArray
= (struct Node**)malloc(minHeap->
heapArraySize * sizeof(struct Node*));
return minHeap;
}

struct Node* extractMin(struct MinHeap* minHeap)

{

struct Node* temp ;
temp= minHeap->minHeapArray[0];
minHeap->minHeapArray[0]= minHeap->minHeapArray[minHeap->size - 1];

--minHeap->size;
minHeapify(minHeap, 0);

return temp;
}
int isSizeOne(struct MinHeap* minHeap)
{

return (minHeap->size == 1);
}
void insert(struct MinHeap* minHeap,
struct Node* Node)

{

++minHeap->size;
int i = minHeap->size - 1;

while (i && Node->freq < minHeap->minHeapArray[(i - 1) / 2]->freq) {

minHeap->minHeapArray[i] = minHeap->minHeapArray[(i - 1) / 2];
i = (i - 1) / 2;
}

minHeap->minHeapArray[i] = Node;
}
void buildMinHeap(struct MinHeap* minHeap)

{

int n = minHeap->size - 1;
int i;

for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
{
cout<< arr[i];
}
cout<<"\n";
}
int lastNode(struct Node* node)

{
return ((!(node->left) )&&( !(node->right)));
}
struct MinHeap* cBuildheap(char val[], int freq[], int size)

{

struct MinHeap* minHeap = createMinHeap(size);

for (int i = 0; i < size; ++i)
minHeap->minHeapArray[i] = getnode(val[i], freq[i]);

minHeap->size = size;
buildMinHeap(minHeap);

return minHeap;
}

struct Node* buildTree(char val[], int freq[], int size)

{
struct Node *left, *right, *top;
struct MinHeap* minHeap = cBuildheap(val, freq, size);
while (!isSizeOne(minHeap)) {

left = extractMin(minHeap);
right = extractMin(minHeap);
top = getnode('$', left->freq + right->freq);

top->left = left;
top->right = right;

insert(minHeap, top);
}

return extractMin(minHeap);
}
void printOutputCode(struct Node* node, int arr[], int top)

{
if (node->left) {

arr[top] = 0;
printOutputCode(node->left, arr, top + 1);
}
if (node->right) {

arr[top] = 1;
printOutputCode(node->right, arr, top + 1);
}

if (lastNode(node)) {

cout<<"code for "<< node->val <<" => ";
printArr(arr, top);
}
}
void code(char val[], int freq[], int size)

{
struct Node* node
= buildTree(val, freq, size);

int arr[max_height_of_tree], top = 0;

printOutputCode(node, arr, top);
}

int main()
{
int i,j;
string str;
cout<<"Enter the string of characters"<<endl;
getline(cin,str);
int a[256]={0};
for(i=0;i<str.size();i++)
{
a[str[i]]++;
}
int n=0;
for(i=0;i<256;i++)
{

if(a[i]>0)
{
n=n+1;
}
}
j=0;
char arr[n];
int frequency[n];
for(i=0;i<256;i++)
{
if(a[i]>0)
{

arr[j]=char(i);
frequency[j]=a[i];
j++;
}
}
cout<<"characters and frequencies"<<endl;
for(i=0;i<n;i++)
{
cout<<arr[i]<<" "<<frequency[i]<<endl;
}
cout<<"charactes and huffman code"<<endl;
code(arr, frequency, n);
}

Thank you. please upvote.