Question

In: Computer Science

Create this C++ program using classes 1. Create a file text file with a string on...

Create this C++ program using classes

1. Create a file text file with a string on it

2. Check the frecuency of every letter, number and symbol (including caps)

3. Use heapsort to sort the frecuencys found

4. Use huffman code on the letters, symbols or numbers that have frecuencys

I created the file, and the frecuency part but i'm having trouble with the huffman and heapsort implementation.

Solutions

Expert Solution

Huffman Code implementation: (I have included the main() for your understanding)

#include <bits/stdc++.h> 
using namespace std;
struct minHeapNode { 
    char data; 
    int freq; 
    minHeapNode *left, *right; 
    minHeapNode(char data, int freq) 
    { 
        left = right = NULL; 
        this->data = data; 
        this->freq = freq; 
    } 
}; 
struct compare { 
  
    bool operator()(minHeapNode* l, minHeapNode* r) 
  
    { 
        return (l->freq > r->freq); 
    } 
}; 
 
void printHuffCodes(struct minHeapNode* root, string str) 
{ 
  
    if (!root) 
        return; 
  
    if (root->data != '$') 
        cout << root->data << ": " << str << "\n"; 
  
    printHuffCodes(root->left, str + "0"); 
    printHuffCodes(root->right, str + "1"); 
} 

void HuffmanCodes(char data[], int freq[], int size) 
{ 
    struct minHeapNode *left, *right, *top; 
    priority_queue<minHeapNode*, vector<minHeapNode*>, compare> minHeap; 
  
    for (int i = 0; i < size; ++i) 
        minHeap.push(new minHeapNode(data[i], freq[i])); 
    while (minHeap.size() != 1) { 
        left = minHeap.top(); 
        minHeap.pop(); 
  
        right = minHeap.top(); 
        minHeap.pop(); 
        top = new minHeapNode('$', left->freq + right->freq); 
  
        top->left = left; 
        top->right = right; 
  
        minHeap.push(top); 
    } 

    printHuffCodes(minHeap.top(), ""); 
} 
int main() 
{ 
  
    char arr[] = { 'a', 'b', 'c', 'd' }; 
    int freq[] = { 24, 27, 21, 15 }; 
  
    int size = sizeof(arr) / sizeof(arr[0]); 
  
    HuffmanCodes(arr, freq, size); 
  
    return 0; 
} 

Heapsort:

#include <bits/stdc++.h> 
using namespace std; 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int left = 2*i + 1; 
    int right = 2*i + 2;  
  
    if (left < n && arr[left] > arr[largest]) // If left child is larger than root
        largest = left; 
  
     
    if (right < n && arr[right] > arr[largest]) // If right child is larger than largest so far
        largest = right; 
  
    if (largest != i)   // If largest is not root 
    { 
        swap(arr[i], arr[largest]); 
        heapify(arr, n, largest); 
    } 
} 
  
void heapSort(int arr[], int n) 
{ 
    for (int i = n / 2 - 1; i >= 0; i--) //Building the heap
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>0; i--)   // extract an element from heap 
    { 
        swap(arr[0], arr[i]); // Moving the current root to end
        heapify(arr, i, 0);  // call max heapify on the reduced heap
    } 
} 
 
int main() 
{ 
    int arr[] = {38, 21, 25, 1, 8, 49}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is: "; 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
} 

Related Solutions

Write a C++ program that reads a string from a text file and determines if the...
Write a C++ program that reads a string from a text file and determines if the string is a palindrome or not using stacks and queue
Write a C++ program to create a text file. Your file should contain the following text:...
Write a C++ program to create a text file. Your file should contain the following text: Batch files are text files created by programmer. The file is written in notepad. Creating a text file and writing to it by using fstream: to write to a file, you need to open thew file as write mode. To do so, include a header filr to your program. Create an object of type fsrteam. Open the file as write mode. Reading from a...
Write a C program that can search for a string within a text file, replace it...
Write a C program that can search for a string within a text file, replace it with another string and put results in a new file.
Using C++, write a code that this program always stores text file output into a text...
Using C++, write a code that this program always stores text file output into a text file named "clean.txt". -The program should read one character at a time from "someNumbers.txt", and do the following. -If it is a letter, print that letter to the screen, AND also store it in the text file. All letters should be converted to lowercase beforehand. -If it is a number, print that number to screen, but do NOT store it in the text file....
Using a minimum of 2 classes create a java program that writes data to a file...
Using a minimum of 2 classes create a java program that writes data to a file when stopped and reads data from a file when started. The data should be in a readable format and the program should work in a way that stopping and starting is irrelevant (e.g. all data doesn't have to save just the important elements.) Program should be unique and semi-complex in some way.
WRITE A C++ PROGRAM TO IMPLEMENT THE CONCEPT OF INDEX (Create index in text file)
WRITE A C++ PROGRAM TO IMPLEMENT THE CONCEPT OF INDEX (Create index in text file)
Write a C++ program using produces Huffman code for a string of text entered by the...
Write a C++ program using produces Huffman code for a string of text entered by the user. Must accept all ASCII characters.
Write a C++ program using produces Huffman code for a string of text entered by the...
Write a C++ program using produces Huffman code for a string of text entered by the user. The string given by the user can be either 1 word or 1000 words. Must accept all ASCII characters. Please do not copy from the internet. This is my 3rd time posting the same question and I have not received a correct answer.
Create a c++ program with this requirements: Create an input file using notepad ( .txt )...
Create a c++ program with this requirements: Create an input file using notepad ( .txt ) . When testing your program using different input files, you must change the filename inside your program otherwise there will be syntax errors. There are a finite number of lines to be read from the data file. But we can’t assume to know how many before the program executes; so, the standard tactic is to keep reading until you find the “End of File”...
C++ Code You will write a program to process the lines in a text file using...
C++ Code You will write a program to process the lines in a text file using a linked list and shared pointers. You will create a class “Node” with the following private data attributes: • Line – line from a file (string) • Next (shared pointer to a Node) Put your class definition in a header file and the implementation of the methods in a .cpp file. The header file will be included in your project. If you follow the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT