Incorrect output shanno -fanno alogrithm

Viewed 22

I am having trouble getting the desired output using shanno- fanno compression algorithm. I am unsure where the problem is. My output is not matching the desired output. Where am I making the mistake and why is my output different from the desired output.

my output =

Symbol A, Code: 001

Symbol B, Code: 000

Symbol C, Code: 0101

Symbol D, Code: 0100

Symbol E, Code: 0111

desired output =

Symbol A, Code: 001

Symbol B, Code: 011

Symbol C, Code: 101

Symbol D, Code: 1100

Symbol E, Code: 11110

#include <cstdlib>
#include <bits/stdc++.h>
#include <iostream>
#include <istream>
#include <fstream>
#include <vector>  
#include <string>
#include <ctype.h>
#include <stdio.h>
#include <algorithm>
using namespace std;


      struct node {

// for storing symbol
char sym;

// for storing probability or frequency
float pro;
int arr[20];
int top;
} p[20];

typedef struct node node;

// function to find shannon code
void shannon(int l, int h, node p[])
{
float pack1 = 0, pack2 = 0, diff1 = 0, diff2 = 0;
int i, d, k, j;
if ((l + 1) == h || l == h || l > h) {
    if (l == h || l > h)
        return;
    p[h].arr[++(p[h].top)] = 0;
    p[l].arr[++(p[l].top)] = 1;
    return;
}
else {
    for (i = l; i <= h - 1; i++)
        pack1 = pack1 + p[i].pro;
    pack2 = pack2 + p[h].pro;
    diff1 = pack1 - pack2;
    if (diff1 < 0)
        diff1 = diff1 * -1;
    j = 2;
    while (j != h - l + 1) {
        k = h - j;
        pack1 = pack2 = 0;
        for (i = l; i <= k; i++)
            pack1 = pack1 + p[i].pro;
        for (i = h; i > k; i--)
            pack2 = pack2 + p[i].pro;
        diff2 = pack1 - pack2;
        if (diff2 < 0)
            diff2 = diff2 * -1;
        if (diff2 >= diff1)
            break;
        diff1 = diff2;
        j++;
    }
    k++;
    for (i = l; i <= k; i++)
        p[i].arr[++(p[i].top)] = 0;
    for (i = k + 1; i <= h; i++)
        p[i].arr[++(p[i].top)] = 1;

    // Invoke shannon function
    shannon(l, k, p);
    shannon(k + 1, h, p);
   }
   }
   void display(int n, node p[])
  {
    int i, j;
    for (i = 0 ; i < n; i++) {
    cout << endl <<"Symbol " << p[i].sym << "," << " " <<"Code: ";
    for (j = 0; j <= p[i].top; j++)
        cout << p[i].arr[j];
    }
}


    int main() {

// store symbols from standard input  pass by refrence to function //
 int size = 20;  
 char symbol[size]; 
 float integer[size];
 float tot = 0;
 node temp; 
 int n = 5;


for(int i = 0; i < n; i++){
   cin >> symbol[i];
   p[i].sym = symbol[i];
  cout << p[i].sym << endl;
  }
   
for(int i = 0; i < n ; i++) {
   cin >> integer[i]; 
   p[i].pro = integer[i];
   cout << p[i].pro << endl;
 }
  

// Find the shannon code
shannon(0, n, p);

// Display the codes
display(n, p);

return 0;

}

0 Answers
Related