Can someone edit the below code to read input from a text file and save the resu
ID: 3591696 • Letter: C
Question
Can someone edit the below code to read input from a text file and save the results to an output text file. Currently it is reading from two prefixed arrays.
#include <bits/stdc++.h>
using namespace std;
// A Huffman tree node
struct MinHeapNode
{
char data; // One of the input characters
unsigned freq; // Frequency of the character
MinHeapNode *left, *right; // Left and right child
MinHeapNode(char data, unsigned freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
// For comparison of two heap nodes (needed in min heap)
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
// Prints huffman codes from the root of Huffman Tree.
void printCodes(struct MinHeapNode* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << " ";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
// Create a min heap & inserts all characters of data[]
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(data[i], freq[i]));
// Iterate while size of heap doesn't become 1
while (minHeap.size() != 1)
{
// Extract the two minimum freq items from min heap
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
// Create a new internal node with frequency equal to the
// sum of the two nodes frequencies. Make the two extracted
// node as left and right children of this new node. Add
// this node to the min heap
// '$' is a special value for internal nodes, not used
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
// Print Huffman codes using the Huffman tree built above
printCodes(minHeap.top(), "");
}
// Driver program to test above functions
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; // This Part should be read from input.txt
int freq[] = { 5, 9, 12, 13, 16, 45 }; // This should also be read from input.txt
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Explanation / Answer
#include <bits/stdc++.h>
using namespace std;
// A Huffman tree node
struct MinHeapNode
{
char data; // One of the input characters
unsigned freq; // Frequency of the character
MinHeapNode *left, *right; // Left and right child
MinHeapNode(char data, unsigned freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
// For comparison of two heap nodes (needed in min heap)
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
// Prints huffman codes from the root of Huffman Tree.
void printCodes(struct MinHeapNode* root, string str, ofstream &outFile)
{
if (!root)
return;
if (root->data != '$')
outFile << root->data << ": " << str << " ";
//cout << root->data << ": " << str << " ";
printCodes(root->left, str + "0", outFile);
printCodes(root->right, str + "1", outFile);
}
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
// Create a min heap & inserts all characters of data[]
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(data[i], freq[i]));
// Iterate while size of heap doesn't become 1
while (minHeap.size() != 1)
{
// Extract the two minimum freq items from min heap
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
// Create a new internal node with frequency equal to the
// sum of the two nodes frequencies. Make the two extracted
// node as left and right children of this new node. Add
// this node to the min heap
// '$' is a special value for internal nodes, not used
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
ofstream outFile("output.txt");
if(!outFile.is_open()){
cout << "Unable to open file" << endl;
exit(1);
}
// Print Huffman codes using the Huffman tree built above
printCodes(minHeap.top(), "" , outFile);
outFile.close();
}
// Driver program to test above functions
int main()
{
//Declare an input file stream
ifstream inFile;
//We need to give path to the input file
inFile.open("input.txt");
if(!inFile){
cout << "Unable to open file" << endl;
exit(1);
}
int size,i;
inFile >> size;
char arr[size];
int freq[size];
for(i=0;i<size;i++)
inFile >> arr[i];
for(i=0;i<size;i++)
inFile >> freq[i];
inFile.close();
//char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; // This Part should be read from input.txt
//int freq[] = { 5, 9, 12, 13, 16, 45 }; // This should also be read from input.txt
//int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Suppose the contents of input.txt is following:
6 a b c d e f 5 9 12 13 16 45
Then contents of output.txt are following:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111