Hash Table outputting incorrect number

This is a discussion on Hash Table outputting incorrect number within the C Programming forums, part of the General Programming Boards category; Before we begin, I'll tell you this is for an assignment. I do not expect you to write it all ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    6

    Hash Table outputting incorrect number

    Before we begin, I'll tell you this is for an assignment. I do not expect you to write it all out for me, but to highlight where I have been going wrong.

    The program below is reading in an uncompressed .tga file (an example I have uploaded here: http://paul-skinner.com/stuff/uni/da...tures/lena.tga ).

    It is then turning the image in to greyscale, and finally putting the data in to a hash table with chaining as its collision detection.

    Once this is done, the hash table is printed out along with the total number of unique entries.

    This is where it's going wrong.

    Data is being inputted in to the hash table, however the amount of unique entries should be 204 (this is based on the tga file referenced to above and has been told to me beforehand by the lecturer).

    I cannot for the life of me see why it's outputting incorrectly as 59.


    You may want to put a system("pause") or getchar in to make it stop before exiting.

    To run the program you must give the full path to the .tga file (possibly in quote marks) as the first argument.

    Example:

    "C:\assignment.exe" "C:\lena.tga"


    Thank you in advanced for any advice.


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <cstdlib>
    #include <cstdio>
    
    #define HEADERSIZE  18
    
    #define W_LSB       12
    #define W_MSB       13
    #define H_LSB       14
    #define H_MSB       15
    
    #define HASHSIZE    211  //This is the first prime past 204
    #define N           230
    
    int T[HASHSIZE];
    
    struct node
    {
       int key;
       struct node *next;
    };
    
    node * ListStart = NULL;
    
    int storage_attempts = 0, retrieval_attempts = 0;
    
    int hash(unsigned char key, int startnum);
    void hashtable(unsigned char *I);
    int findData(int key);
    int hash(int key);
    void addToOverflow(int key);
    void printTable();
    void printOverflow();
    int openTGA(char *arg1);
    void loadTGA(int total, unsigned char *I, char *arg1);
    
    int main(int argc, char** argv)
    {
    
    
    
       int total = 0;
    
       total = openTGA(argv[1]); //return MxN
    
       unsigned char I[total];
    
       loadTGA(total, I, argv[1]);
    
       hashtable(I);
    
       //getchar();
    
    
    }
    
        //---------------------End Main---------------------//
    
    int openTGA(char *arg1)
    {
       int i; 
       unsigned char header[HEADERSIZE];
       FILE *fp;
    
       printf("Opening Input Image '%s' ... ", arg1);fflush(stdout);
       fp = fopen(arg1,"rb");
       if(!fp)
       {
          printf("\n\nARGH! File couldn't be opened.\n");fflush(stdout);
       }
       printf("Done.");fflush(stdout);
    
    
       printf("\n\nReading %d Byte Header ... ", HEADERSIZE);fflush(stdout);
       fread(header, HEADERSIZE, 1, fp);
       printf("Done.");fflush(stdout);
    
    
       printf("\n\nHeader Contents: ");fflush(stdout);
       for(i=1;i<HEADERSIZE;i++)
       {
          printf("|%d|", header[i]);fflush(stdout);
       }
    
       int m = (header[W_MSB]*256) + header[W_LSB];
       int n = (header[H_MSB]*256) + header[H_LSB];
    
       printf("\n\nDimensions Extracted: Width=%d, Height=%d.", m, n);
       fflush(stdout);
       fclose(fp);
    
       return (m*n);
    }
    void loadTGA(int total, unsigned char *I, char *arg1)
    {
    
       int x = 0;
       unsigned char header[HEADERSIZE];
       unsigned char Rt, Gt, Bt;
    
       FILE * fp;
    
       fp = fopen(arg1,"rb");
       if(!fp)
       {
          printf("\n\nARGH! File couldn't be opened.\n");fflush(stdout);
       }
       printf("Done.");fflush(stdout);
    
    
       printf("\n\nReading %d Byte Header ... ", HEADERSIZE);fflush(stdout);
       fread(header, HEADERSIZE, 1, fp);
       printf("Done.");fflush(stdout);
    
    
       printf("\n\nReading RGB Data & Calculating Greyscale ... ");fflush(stdout);
       for(x=0;x<total;x++)
       {
          fscanf(fp, "%c", &Rt);
          fscanf(fp, "%c", &Gt);
          fscanf(fp, "%c", &Bt);
    
          I[x] = (Rt+Gt+Bt)/3;
       }
       fclose(fp);
       printf("Done.");fflush(stdout);
    
       fclose(fp);
    }
    
    
    
    void hashtable(unsigned char *I)
    {
       int table_count = 0, overflow_count = 0, x=0, k = 0;
    
       for(x=0; x<N; x++)
       {
    
             k = I[x];
    
             if(T[hash(k)] == '\0')
             {
                // Empty Space, Insert New Item
                T[hash(k)] = k;
             }
             else if(T[hash(k)] != k)
             {
                // Collision, add item to overflow
                addToOverflow(k);
             }
       }
    
       // Print hash table
       printf("\nHASH TABLE\n\n");
       printTable();
    
    }
    
    
    
    int hash(int key)
    {
       int i;
    
       i = key % HASHSIZE;
    
       return i;
    }
    
    void addToOverflow(int key)
    {
       node * temp;
    
       temp = new node;
       temp->key = key;
       temp->next = NULL;
    
       if(ListStart == NULL)
       {
          ListStart = temp;
       }
       else
       {
          temp->next = ListStart;
    
          ListStart = temp;
       }
    }
    
    int findData(int key)
    {
       retrieval_attempts = 1;
    
       int i = key % HASHSIZE;
    
       if(T[i] == key)
       {
          // Hash location is correct, return data
          return T[i];
       }
       else
       {
          // Hash location is incorrect, search linked list
          node * current;
    
          current = ListStart;
    
          do
          {
             if(current->key == key)
             {
                retrieval_attempts++;
    
                return current->key;
             }
             else if(current->next != NULL)
             {
                retrieval_attempts++;
    
                current = current->next;
             }
             else
             {
                retrieval_attempts++;
    
                return -1;
             }
          } while(current != NULL);
       }
    }
    
    void printTable()
    {
       int temp = 0, counter = 0;
       for(int i=0; i<HASHSIZE; i++)
       {
          temp=T[i];
          printf("%7d", temp);
          if (temp!=0)
          {
             counter++;
          }
    
          if(i%10==0) printf("\n");
       }
       printf("\n\n=%d=\n\n", counter);
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm not quite sure I know what you're seeing and what you want to be seeing. Are things not hashing to the correct place? Are you miscounting how many elements are in your hash table? Something else?

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    6
    Quote Originally Posted by tabstop View Post
    I'm not quite sure I know what you're seeing and what you want to be seeing. Are things not hashing to the correct place? Are you miscounting how many elements are in your hash table? Something else?
    The wrong data is being hashed, though I cannot work out how.

    T[] is the greyscale intensities and this is what's being put in to the hash table.

    Currently, the hash table is showing that there are 59 unique intensities.
    This number should be 204 if it were hashing correctly.

    I'm pretty sure it's the hashing that is going wrong, and not the calculation of unique intensities.


    I hope that clarifies it.
    Last edited by Paul Skinner; 11-19-2008 at 02:48 PM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,824
    > fscanf(fp, "&#37;c", &Rt);
    Perhaps use fgetc() instead.
    Does this even work for a binary file, in particular something like a \0 ?

    In any event, checking the return result of your file reading functions would be a good idea as well.
    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.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    6
    Quote Originally Posted by Salem View Post
    > fscanf(fp, "%c", &Rt);
    Perhaps use fgetc() instead.
    Does this even work for a binary file, in particular something like a \0 ?

    In any event, checking the return result of your file reading functions would be a good idea as well.
    fscanf(fp, "%c", &Rt); works fine

    I found the answer in the end.

    #define N was set to too low a number.

    I forgot that N needed to be the total POSSIBLE collisions (512*512), not the number I knew it to be.

    I've removed N and passed total to hashtable() now, and it's working fine.

    Thanks for your help anyway.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Hash Table
    By siavoshkc in forum C++ Programming
    Replies: 4
    Last Post: 08-29-2006, 05:29 PM
  3. help with creating a hash table
    By newbie40 in forum C++ Programming
    Replies: 3
    Last Post: 08-15-2002, 08:31 PM
  4. Hash Table Problem
    By Unregistered in forum C Programming
    Replies: 14
    Last Post: 05-21-2002, 05:34 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-26-2001, 12:45 AM

Tags for this Thread


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