huffman coding

This is a discussion on huffman coding within the C++ Programming forums, part of the General Programming Boards category; this is my huffman code but it is not giving the correct result as it should i mean i am ...

  1. #1
    Registered User
    Join Date
    Jan 2010
    Posts
    11

    huffman coding

    this is my huffman code but it is not giving the correct result as it should i mean i am not getting the whole right subtree from root

    for eg:

    if a text file contains

    space:3
    a:8
    e:6
    w:2
    r:2
    t:2
    d:1
    q:2

    den i not getting sub tree containing r,t,a,sapce

    whereas left sub tree is coming all correct
    to get a clear view just see the attachment[

    code is below

    to execute it first make a text file and write letter shown above and no's adjacent to them r dere respective occurrences in a file

    Code:
    #include <fstream.h> 
    #include<conio.h> 
    #include<iostream.h> 
    #include<stdio.h> 
    struct node 
    { int weight; 
    char data; 
    int freq; 
    struct node *left,*right,*prev,*next; 
    }; 
    char ch; 
    int min,min2,min3,m,min4; 
    node *root,*ptr,*last,*temp2,*add,*temp,*back,*r; 
    node *del(node *ptr,int min); 
    int minsecond(node *ptr); 
    node *insert(node *ptr,int min3) ; 
    int minfirst(node *ptr); 
    int main() 
    { 
    clrscr(); 
    char filename[89]; 
    int a; 
    int arr[256]; 
    for(int i=0;i<256;i++) 
    { 
    arr[i]=0; 
    } 
    cout<<"enter filename"; 
    cout<<"\n"; 
    cin.get(filename,89); 
    fstream file_op(filename,ios::in); 
    if(!file_op) 
    { 
    cout<<"file does not exist"; 
    return 0; 
    } 
    while(!file_op.eof()) 
    { 
    file_op.get(ch); 
    a=ch; 
    arr[a]=arr[a]+1; 
    } 
    file_op.close(); 
    root =new node; 
    ptr=root; 
    root->next=NULL; 
    root->prev=NULL; 
    root->right=NULL; 
    root->left=NULL; 
    for(i=0;i<256;i++) 
    { 
    if(arr[i]>0) 
    { 
    root->right=new node; 
    root=root->right; 
    root->right=NULL; 
    root->left=root; 
    root->data=i; 
    root->freq=arr[i]; 
    root->next=NULL; 
    root->prev=NULL; 
    } 
    } 
    while(ptr->right->right!=NULL) 
    { 
    min=minfirst(ptr); 
    ptr=del(ptr,min); 
    min2=minr(ptr); 
    min3=min+min2; 
    ptr=del(ptr,min2); 
    ptr=insert(ptr,min3); 
    } 
    node *r; 
    r=ptr->right; 
    cout<<r->data<<r->freq; 
    cout<<endl; 
    while(r->next!=NULL) 
    { r=r->next; 
    cout<<r->weight<<","<<r->freq<<","<<r->data<<"\n"; 
    } 
    getch(); 
    } 
    node *insert(node *ptr,int min3) 
    { 
    add=new node; 
    add->freq=min3; 
    add->data=NULL; 
    if(ptr->right==NULL) 
    add->right=NULL; 
    else 
    add->right=ptr->right; 
    add->left=ptr; 
    ptr->right=add; 
    add->next=temp2; 
    temp2->weight=1; 
    add->prev=last; 
    last->weight=0; 
    return(ptr); 
    } 
    node *del(node *ptr,int m) 
    { 
    back=ptr; 
    temp=ptr->right; 
    while(temp!=NULL) 
    { 
    if(temp->freq==m) 
    { 
    if(temp->right!=NULL) 
    { 
    back->right=temp->right; 
    temp->right=NULL; 
    temp->left=NULL; 
    } 
    else 
    back->right=NULL; 
    return(ptr); 
    } 
    back=temp; 
    temp=temp->right; 
    } 
    } 
    int minsecond(node *ptr) 
    { ptr=ptr->right; 
    min4=ptr->freq; 
    while(ptr!=NULL) 
    { 
    if(ptr->freq<min4) 
    { 
    min4=ptr->freq; 
    if(ptr->next!=NULL) 
    { 
    temp2=new node; 
    temp2->freq=min4; 
    temp2=ptr; 
    temp2->weight=1; 
    temp->data=NULL; 
    } 
    else 
    { 
    temp2=new node; 
    temp2->next=NULL; 
    temp2->prev=NULL; 
    temp2->data=ptr->data; 
    temp2->weight=1; 
    temp2->freq=min4; 
    } 
    } 
    else 
    { 
    ptr=ptr->right; 
    } 
    } 
    return(min4); 
    } 
    int minfirst(node *ptr) 
    { 
    ptr=ptr->right; 
    min4=ptr->freq; 
    while(ptr!=NULL) 
    { 
    if(ptr->freq<min4) 
    { 
    min4=ptr->freq; 
    if(ptr->next!=NULL) 
    { 
    last=new node; 
    last->freq=min4; 
    last=ptr; 
    last->weight=0; 
    last->data=NULL; 
    } 
    else 
    { 
    last=new node; 
    last->next=NULL; 
    last->prev=NULL; 
    last->data=ptr->data; 
    last->weight=0; 
    last->freq=min4; 
    } 
    } 
    else 
    { 
    ptr=ptr->right; 
    } 
    } 
    return(min4); 
    }
    Attached Files Attached Files

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,243
    Looking at that set of frequencies, I do not think that any valid Huffman subtree would contain those symbols. What is the complete tree that you DO get?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    hey see the attachment along with dis post

    there is a tree for these freq.

  4. #4
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    hey did u see that attachment?

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,243
    Quote Originally Posted by ratikag View Post
    hey did u see that attachment?
    I am unable to open a .doc file.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #6
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    Quote Originally Posted by brewbuck View Post
    I am unable to open a .doc file.
    wht's the problem?

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,243
    Quote Originally Posted by ratikag View Post
    wht's the problem?
    Uh, I have no software that understands that?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    u don't hv MS-word with u?

  9. #9
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    if u hv notepad or wordpad with u den u can also open dis file in it

  10. #10
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    r u still unable to open it?

  11. #11
    Registered User
    Join Date
    Jan 2010
    Posts
    11
    hey is dere nyone who can help me out?

  12. #12
    Registered User QuestionKing's Avatar
    Join Date
    Jan 2009
    Posts
    68
    I looked, your posted doc.doc was empty :/
    Asking a question you already know the answer to might teach you something you did not know...

  13. #13
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    I gave up looking when I saw
    - unindented code (a lot of it),
    - non-portable and malware abusable file formats (.doc) and
    - kiddie "cn u rd ths" SMS speak.

    How To Ask Questions The Smart Way
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 03-20-2009, 05:22 PM
  2. Huffman coding
    By misplaced in forum C++ Programming
    Replies: 2
    Last Post: 04-21-2005, 01:14 PM
  3. Huffman coding
    By fatinez in forum C Programming
    Replies: 4
    Last Post: 11-04-2003, 04:03 PM
  4. yet another huffman tree problem
    By ygfperson in forum C++ Programming
    Replies: 2
    Last Post: 04-18-2002, 01:20 AM
  5. Coding Contest....
    By Koshare in forum A Brief History of Cprogramming.com
    Replies: 46
    Last Post: 10-14-2001, 04:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21