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);
}
