#include<bits/stdc++.h>
#include<string>
using namespace std;
float AverageCodeLength = 0;
// structure of a node containing the input symbol and its corresponding probability
struct Node {
char symbol;
float probability;
struct Node *left, *right;
};
// structure of a minheap
struct MinHeap {
int size;
struct Node** array;
};
// function to create a newnode
struct Node* createNode(char symbol, float probability) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->left = temp->right = NULL;
temp->symbol = symbol;
temp->probability = probability;
return temp;
}
// function to check whether the provided input is valid or
bool performSanityCheck(char symbols[] ,float probabilities[] , int n){
//check if the total probabilities sum to 1
float sum = 0;
for (int i = 0 ; i < n ; i++){
sum += probabilities[i];
}
// cout << sum << "\n";
if (sum != 1) return true ;
//check if there are unique symbols being used
//first we will sort the symbols array
sort(symbols , symbols + n);
// printCharacterArray(symbols , n);
bool flg = false ;
for (int i = 0 ; i<n-1 ; i++){
if (symbols[i] == symbols[i+1]){
flg = true;
break;
}
}
return flg;
}
// function to swap two nodes
void swapNodes(struct Node** a, struct Node** b) {
struct Node* t = *a;
*a = *b;
*b = t;
}
// The standard Heapify function.
void Heapify(struct MinHeap* minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
int size = minHeap-> size;
float lprob = 0 ;
float rprob = 0 ;
float sprob = 0;
if (minHeap->array[left]){
lprob = minHeap->array[left]->probability;
}
if (minHeap->array[right]){
rprob = minHeap->array[right]->probability;
}
if (minHeap->array[smallest]){
lprob = minHeap->array[smallest]->probability;
}
cout << minHeap->array[left]-> probability << " " << minHeap->array[right]-> probability << " " << minHeap->array[smallest]->probability << endl;
if (left < size && minHeap->array[left]-> probability < minHeap->array[smallest]->probability)
smallest = left;
if (right < size && minHeap->array[right]-> probability < minHeap->array[smallest]->probability)
smallest = right;
if (smallest != idx) {
swapNodes(&minHeap->array[smallest], &minHeap->array[idx]);
Heapify(minHeap, smallest);
}
}
//function to extract minimum value from a heap
struct Node* extractMinValue(struct MinHeap* minHeap) {
struct Node* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
minHeap->size -= 1;
Heapify(minHeap, 0);
return temp;
}
// function to insert a new node in the minHeap
void insertMinHeap(struct MinHeap* minHeap, struct Node* Node) {
minHeap->size += 1;
int i = minHeap->size - 1;
float nprob = Node->probability;
while (i && nprob < minHeap->array[(i - 1) / 2]->probability) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = Node;
}
// function to build min heap of the given size
struct MinHeap* buildMinHeap(char symbol[], float probability[], int size) {
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = size;
minHeap->array = (struct Node**)malloc(size * sizeof(struct Node*));
for (int i = 0; i < size; ++i) {
minHeap->array[i] = createNode(symbol[i], probability[i]);
}
minHeap->size = size;
int n = size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
Heapify(minHeap, i);
return minHeap;
}
// function to print an array of integers
void printArr(int arr[], int n) {
int i;
for (i = 0; i < n; ++i)
cout<< arr[i];
cout<<"\n";
}
//function to print an array of decimal values , i.e , probabilities
void printFloatArray(float arr[] , int n){
for (int i = 0; i<n ; i++){
cout << arr[i] << " ";
}
cout << endl;
}
//function to print an array of character , i.e , symbols
void printCharacterArray(char arr[] , int n){
for (int i = 0; i<n ; i++){
cout << arr[i] << " ";
}
cout << endl;
}
// function to check if a node is leafnode or not
bool isLeaf(struct Node* root) {
return !(root->left) && !(root->right);
}
// function to build huffmantree with the given symbols and their corresponding probabilities
struct Node* buildHuffmanTree(char symbol[], float probability[], int size) {
struct Node *left, *right, *top;
struct MinHeap* minHeap = buildMinHeap(symbol, probability, size);
while (!(minHeap->size == 1)) {
// here we extract wo minimum values from our heap
left = extractMinValue(minHeap);
right = extractMinValue(minHeap);
// here $ represents a new node which is not an input symbol and represents an internal node while building our huffman tree
top = createNode('$', left->probability + right->probability);
top->left = left;
top->right = right;
// we insert the newly created intermediate node into the minheap
insertMinHeap(minHeap, top);
}
// after the tree is being built the minimum value is present at the root of the tree which is being returned here
return extractMinValue(minHeap);
}
// function for printing the huffman codes for corresponding symbols
void printHuffManCodes(struct Node* root, int arr[], int top) {
if (root->left) {
arr[top] = 1;
printHuffManCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 0;
printHuffManCodes(root->right, arr, top + 1);
}
if (isLeaf(root)) {
cout<< " " << root->symbol <<": ";
//cout << top << endl;
//cout << root->probability << endl;
::AverageCodeLength += top*root->probability;
printArr(arr, top);
}
}
int main() {
// taking user input
int n ; // variable for getting the number of unique symbols
char symbols[n];
float probabilities[n] ; //arrays for the symbols and their probablities
while (true) {
cout << " Enter the no. of unique symbols ";
cin >> n ;
cout << " Enter the symbols and their corresponding probabilities \n";
for (int i = 0 ; i<n ; i++){
cout << " Enter the " + to_string(i+1) + "th symbol ";
cin >> symbols[i] ;
cout << " Enter the " + to_string(i+1) + "th probability ";
cin >> probabilities[i];
}
bool flg = performSanityCheck(symbols,probabilities,n);
//cout << "flg" << flg;
//printFloatArray(probabilities,n);
//printCharacterArray(symbols,n);
if (!flg) break ;
else{
cout << " The values provided were not correct . Please make sure that all the entered symbols are unique and all the probabilities sum up to 1 \n";
}
}
// Construct Huffman Tree
struct Node* root = buildHuffmanTree(symbols, probabilities, n);
int arr[n], top = 0;
printHuffManCodes(root, arr, top);
cout << " AverageCodeLength: " << AverageCodeLength << endl;
return 0;
}
В этом коде я попытался построить дерево Хаффмана, используя minheaps. В функции Heapify, когда я пытаюсь использовать minHeap->array[left]->probability, сохраняя его значение в переменной с именем lprob, это не работает; но когда я использую его непосредственно в операторе if, он работает. Может ли кто-нибудь сказать мне, почему это происходит?
Когда я пытаюсь выполнить это, нет ошибки компиляции или чего-то подобного, но выполнение внезапно останавливается, когда я пытаюсь сохранить его в переменной.