C++ Help

Discussion in 'OT Technology' started by SPACECATAZ, Mar 19, 2009.

  1. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    Hey guys, I'm trying to build a Huffman algorithm, but since my professor is senile and old. He changed the assignment on us half way through the due date about how we are supposed to read in the input.

    Originally, we were supposed to read in the frequency counts of a character from a text file.

    Original input file:

    a(character) 500(frequency count)
    b 250
    c 300
    d 340
    e 500

    And then store them into the priority queue.

    The way he illustrates it now, the input will be read this way from a text file:

    aabbccddeeffgg

    and everytime it sees a specific character, it will add one to the count for the specific character and then store it into the priority queue.

    So for example, it would read in:
    aabbccddeeffgg

    Then it would store each character with its frequency into the priority queue, this way:

    a 2

    b 2

    c 2

    d 2

    etc


    I'm not sure how to count it that way. I know we have to initialize the count to zero, but I don't know what to do with the loop after that to store it into the priority queue each time it sees something.

    Code:
    
    //Assignment 4
    
    #include <iostream>
    #include <fstream>
    #include "pqueue.h"
    #include "tree.h"
    using namespace std;
    
    
    
    
    
     /***************************************************************
     *                   huffInput                                  *
     ****************************************************************
     * huffInput() takes in an input file and stores the frequency  *
     *  of each specific character into an array                    *        
     ****************************************************************/
     
    void huffInput(PriorityQueue& q)
    {
        
        ifstream inFile;
        inFile.open("input.txt");
        char ch;
        int freq = 0;
    
    //New loop for counting each occurrence of a character and storing it into a priority queue.
        while(true)
        {
            inFile >> ch;
            if(inFile.eof()) break; 
            
    
        //This loop would've read it the original way and inputted it into the priority queue correctly.
        // while(true)
        // {
            // inFile >> ch;
            // if(inFile.eof()) break;
            // inFile >> freq;
            // insert(q, new Node(ch), freq);
        // }
        inFile.close();
    }
        
     /***************************************************************
     *                   huffBuild                                 *
     ****************************************************************
     * huffBuild() takes in a PriorityQueue of frequency counts     *
     * that is stored, then attempts to build  *
     *   a huffman tree and ends with the final tree in a priority 
    *    queue                                                *       
     ****************************************************************/
    
    void huffBuild(PriorityQueue& q)
    {
        Node* T1;
        Node* T2;
        int f1 = 0;
        int f2 = 0;
        while(true)
        {
            remove(q, T1, f1)
        if(isEmpty(q)) break;
            remove(q, T2, f2) 
            Tree* tree1= new Tree(T1, T2);
            insert(q, tree1, (f1+f2)); 
        }
        insert(q. T1, f1);
    }   
        
    int main()
    {
        
        PriorityQueue* q = new PriorityQueue;
        huffInput(q);
        huffBuild(q);
    }
    
     
    Last edited: Mar 19, 2009
  2. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    I'm thinking it would go something like this.

    Code:
    char ch;
    int freql
    while(true)
    {
            inFile >> ch;
            if(inFile.eof()) break;
            freq++;
            insert(q, new Node(ch), freq);
    }
    
    But that doesn't seem to take into account the specific characters, so an if statement might be better. Ugh, :hs:.
     
  3. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Use a 26 element array to keep count of each letter. No need for a bunch of if statements since you can use the character itself to calculate the array index.

    freq[ch - 'a']++;
     
  4. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    I figured it out.

    Code:
    void huffCount(int* count, PriorityQueue& q)
    {
        ifstream inFile;
        inFile.open("input.txt");
        char ch;
        for(int i = 0; i < 256; i++)
        {
            count[i] = NULL;
        }
        while(true)
        {
            inFile >> ch;
            if(inFile.eof()) break; 
            count[ch]++;
            insert(q, new Node(ch), count[ch]);
        }
        inFile.close();
    }
    
     
  5. DeathClock

    DeathClock Guest

    why are you using a for loop to initialize a contiguous block of memory?
    Use memset instead.

    Also, I don't understand why you are using a 256 element array to keep track of character counts when there are 26 letters in the alphabet, or does he want you to keep track of punctuation characters and digits as well?

    You should probably just use a 26 element array and index it with count[toupper(ch)-'A']
     
  6. DeathClock

    DeathClock Guest

    I am also inclined to believe that, based on your description, you are not adding things to the queue properly. It would seem like you were supposed to wait until you read a character that was different than the last character, so that if you get a "run" of two or more identical characters you add that entire set to the queue at once, which you aren't doing. Instead, if you had 5 'a's in a row for example you would have 5 entries into the queue each with a an increased number for count, like this:

    input: aaaabbccca
    output as you have it written:
    a 1
    a 2
    a 3
    a 4
    b 1
    b 2
    c 1
    c 2
    c 3
    a 5

    When I think it should be:
    a 4
    c 2
    b 3
    a 1

    To do this all you have you to do is "remember" the last character read and also count the number of identical characters in a row. As soon as you get a different character than the last one read you make an entry into the queue of the last character read and the in-a-row count (NOT the total character count)
     
  7. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    I'm not really sure why he wanted it that way. This is what my assignment page says for that particular array where you add the counts.

    Code:
    Write a function to get the character frequencies. 
    
    
    Create an array of 256 integers to store the frequency counts,  one for each possible character that can be stored in one byte.
    
    Initially, all of the counts are 0.  Now read each character of the file, adding 1 to its count. 
    
    You can open a file for reading using the <fstream> library. Write 
    
    [B]ifstream in(fname);[/B]
    
     to open file fname for reading.  
    
    Now use in just the way you would use cin.  When you are done,  
    
    [B] in.close();[/B]
    
     will close the file.   Do not skip over blanks.  If variable c has type int, then
    
    [B]  c = cin.get();
    
    [/B] stores the integer code of the next character into variable  c, regardless of what the next character is.  If there are no more characters in the file, then it sets c to EOF (which is defined to be -1).  So you would typically say [B] 
    
     c = cin.get();
    
    if(c != EOF) ...
    
    [/B] Be sure to make variable c have type int, not char. 
    
    
    
    I've never used the memset function before. I remember seeing it on google, when researching a better way to initialize the array to zero, but I didn't really understand how to use it.

    Your second output is correct, but it's supposed to be:

    a 5
    c 2
    b 3

    instead of:

    a 4
    c 2
    b 3
    a 1

    I'm supposed to count each occurrence of the character in the file and store that into the priorityqueue. I kinda understand what you're saying, but not really. I think I could create a local variable to "remember" the last character read like you said.

    Something like this?

    Code:
    void huffCount(int* count, PriorityQueue& q)
    {
        ifstream inFile;
        inFile.open("input.txt");
        char ch;
        char chbuffer;
        memset(count, 0, 256*sizeof (int));
        while(true)
        {
            inFile >> ch;
            chbuffer = ch;
            if(inFile.eof()) break; 
            if(ch == chbuffer)
            {
                count[ch]++;
                insert(q, new Node(ch), count[ch]);
             } else insert(q, new Node(ch), count[ch]);
        }
        inFile.close();
    }
    
     
  8. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Since you haven't shown us the implementation of the priority queue, we can only assume what the outcome will be when you insert a new node every time you increment a counter.

    For efficiency's sake, and to avoid the outcome where the same letter is entered in the queue with different priorities, your counting loop should simply count and not enter items into the queue. Once that loop is finished counting characters, you can use another loop to iterate through the count array and enter only the non-zero counts into the queue.
     
  9. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0

    This is my insert function, sorry. :o

    Code:
    void insert(PriorityQueue& q, tree item, int priority)
    {
        if(q.ptr == NULL || (priority < q.ptr->priority))
        {
            PQCell* buffer;
            
            if(q.ptr != NULL) buffer = q.ptr;
            else buffer = NULL;
            q.ptr = new PQCell(item, priority);
            q.ptr->next = buffer;
        }
        else insertCell(q.ptr, item, priority);
    }
    
     
  10. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    The insert function is really irrelevant. My point was that it's better to count first, then build the queue, calling insert just once per non-zero count, instead of calling insert everytime you count a character. This avoids the possible side-effect of building a queue like the one DeathClock pointed out.
     

Share This Page