Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 370
  • Last Modified:

Collisions using Hashing

The following code is NEARLY working. My AddHashEntry()
function needs to chain, dynamically, new structures when there is a collision.
I've been using a file containing the reserved words in C
which, in this implementation, are a part of the first
collision occuring in the second location of the array of
structure pointers known as hash_tab, hash_tab[1].

ALL collisions should be handled in this manner so that
a report of C's reserved words will display each of the words
contained at their locations. I FULLY understand that
this makes for a much faster search, especially if an algorithm
to MINIMIZE collisions is applied.


HERE'S MOST OF THE CODE. . . . . .

/*class.h  */

#define HASHSIZE   20

typedef struct node {
        char    *linetext;   /* For variable length lines from any file */
      struct node *next_ptr;   /* For singly linked list. */
} NODE_ENTRY;

typedef NODE_ENTRY *NODE_PTR;

typedef NODE_PTR HASH_TAB[HASHSIZE];

/* Function prototypes. */

#define MAXARRAY   280

int hash(char *);
void InitHashTab(HASH_TAB);
void AddHashEntry(HASH_TAB, NODE_PTR);
void PrintHashEntries(HASH_TAB);
int FindHashEntry(HASH_TAB, char *);

NODE_PTR node_alloc(void);
NODE_PTR makenode(char*);

void process_input_file(char *, HASH_TAB);
char *strdup(char*);
void print_node_entry(NODE_PTR);
void getinputfile(char *);


This program was compiled using Turbo C/C++ 3.0 DOS using the large
memory model
and selecting adherence to ANSI C language compliance.


/* The following function, FindHashEntry(HASH_TAB hash_tab, char *key),
   as yet unfinished and amongst other things, calls the hash(char *key)
   function WITHIN the index brackets [] to create an index value for
   the reserved word PASSED to it. It then assigns the index as part
   of a pre-defined array to a POINTER TO THE ARRAY, as in:
            NODE_PTR node_ptr = hash_tab[hash(key)];
   It compares the value of node_ptr->linetext to the parameter, 'key'.
   So that: If entry exists return 1 else return 0.
*/


int FindHashEntry(HASH_TAB hash_tab, char *key)
  {

  NODE_PTR node_ptr = hash_tab[hash(key)];/*Get hash index from hash
function.*/
  NODE_PTR np = node_ptr;

        /* Traverse the linked list
           until you find it or hit the end of the linked list. */

       /* This cell in the table is already in use. See if the current string
          has already been inserted, and if so, increment its count.
       */

              for ( np = node_ptr; np != NULL; np = np->next_ptr)
       if ( strcmp(node_ptr->linetext,key ) == 0)
       {
       printf("key: %s and node_ptr->linetext: %s are equal. Call AddHash\n",
key, node_ptr->linetext);
       return 1;
       }
                               else
                               node_ptr = node_ptr->next_ptr;

                         /**********************/

return 0;   /* Not found! */
}    /* End FindHashEntry. */



/* The following function, process_input_file, is the "work horse" of
this
   program. It performs MANY duties. It checks to see that a valid
filename
   was passed to this program for processing, stopping execution of this
   program upon encountering an invalid/corrupt file. It uses
   fgets(file_buffer,MAXARRAY, infp) to get EACH line from the input
file.
   It then takes the string in file_buffer and REMOVES the <cr>
(carriage
   return). It then allocates a node, node_ptr (defined within this
function)
   through the use of a call to makenode(char *w) passing it the
modified string
   NOW contained in the variable, file_buffer, as in:
                  makenode(file_buffer);
   Next, it uses an if test to determine if a call to
   FindHashEntry(hash_tab, node_ptr->linetext). If it is FALSE,
   the function AddHashEntry is called passing to it the originally
   initialized hash table(hash_tab) and node_ptr. If it is TRUE,
   then a message stating that that particular string has already been
   entered is outputed.

  ->> Read the reserved words from the input file ( one word / line),
make a
      node for the linked list, add the node to the linked list if the
word
      has not been previously entered.
 */



void process_input_file(char *i_file_name, HASH_TAB hash_tab )
  {
       char file_buffer[MAXARRAY];

       FILE *infp; /* Pointer to input stream of type FILE. */

       NODE_PTR node_ptr;

       /* Open input file. Test for good file name. */

              if ((infp = fopen(i_file_name,"r")) == NULL) {
                          printf("Error in input file name : %s\n",i_file_name);
                          exit(-1); /* Stop processing. */
              }

       /* Read lines from input file, invoke hash function */

              while( fgets(file_buffer,MAXARRAY , infp) != NULL ) {
                          file_buffer[strlen(file_buffer) - 1] = '\0'; /* Replace cr with
null */
                          node_ptr = makenode (file_buffer);
                          /* printf("node_ptr->linetest is %s\n", node_ptr->linetext); */

                        /* If FALSE, call AddHashEntry() */

                        if ( !FindHashEntry(hash_tab, node_ptr->linetext )) {
                        AddHashEntry(hash_tab, node_ptr);
                                    node_ptr = node_ptr->next_ptr; /* Added 3/31/97 */
              }
                                    else
                                    printf("\"%s\" has already been entered into the hash table\n",
                                    node_ptr->linetext);


              } /* End while. */

} /* End process_input_file. */




/* The following function, AddHashEntry, requires that each of the
reserved
   words be entered into their proper place in the hash table. This
needs to
   be accomplished in this fashion:
            1) Go to a cell in the hash table
            2) check to see if anything is there
                  if not, ( if NULL ) then
                        a) add the reserved word to that part of new node
                        b) assign the ADDRESS of the new node to the cell
                           where the node is created.
            3) If there IS a node or there are multiple nodes then
                        a) check to insure that the string is not already
                           there. If it is, insert the NEW node FIRST in the list.
                           This is to defeat duplication of entries.

So,
->> Add an entry to the hash table, if an entry already exists at that
cell,
            then insert the new node first in the list since all reserved words in
            the input file are unique.
*/
/* As of 4/05/97, it is yet unfinished. */



void AddHashEntry(HASH_TAB hash_tab, NODE_PTR node_ptr)
  {
        /* As the name suggests this function adds an entry into the chained
hash
            table.
        Work is needed here to store entries and handle collisions, etc.
        */

       int value = 0;
       NODE_PTR np;
       np = node_ptr;
       value = hash(np->linetext);

       /* NULL means that this cell hasn't been used yet. Space
          needs to be allocated for it and the data put there.
       */
              /* printf("word '%s' has a hash value of %d\n", np->linetext,
value); */


        hash_tab[value] = node_ptr;

               if ( (hash_tab[value]->linetext != NULL ) )

              {
                 hash_tab[value]->linetext = np->linetext;
                 /*printf("linetext = '%s'\n", np->linetext); */

                 np->next_ptr = makenode(hash_tab[value]->linetext);



                 /* printf("index %d contains '%s'\n", value,np->linetext); */
                 np = np->next_ptr;
              }

                 /*else
                 {
                  for ( np = node_ptr; np->linetext != NULL; np = np->next_ptr);

                 } */



  } /* End AddHashEntry. */
0
jnowlin
Asked:
jnowlin
1 Solution
 
jnowlinAuthor Commented:
Edited text of question
0
 
jnowlinAuthor Commented:
Why is this so straightforward and yet so f*!#% ing difficult?!
0
 
julio011597Commented:
Couldn't it be a problem of good rating your questions?

Cheers, julio
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
dominusCommented:
Probably nobody wants to help you because
 1. You didn't state clearly what you wanted.
 2. It looks like you're a student trying to cheat on a homework      assignment.
 3. 15 points is not enough to tempt someone to spen their time       debugging your program.

Of course, there might be some other reason, too.
0
 
jnowlinAuthor Commented:
1. Why doesn't the function AddHashEntry() work, as written?
    ( A QUESTION )

2. This WAS a homework assignment handed in incomplete some
   3 weeks ago. I was told by management that questions asked
   in Experts Exchange are NOT limited to people poking
   around with a computing problem because it was Tuesday,
   and it was raining that day. Therefore, academically related
   questions are "Okie dokie".

3. I was wrong in the number of points I offered. Let's see if I
   can get jos or someone else in the top 15 experts 'tempted'.
   50

4. I don't know what "some other reason" means or implies.

0
 
prcCommented:
Well, I'll have a go, although I do so with some trepidation ;-)

It looks to me like (among other things) you have a problem with what you consider to be an empty cell in the hash table.  The obvious thing to do, which you suggest in some of the code is to treat a NULL in the hash table itself as meaning empty.  In AddHashEntry, though, you seem to be assuming that the pointer in hashtab will point to a valid NODE_ENTRY, and are checking whether the linetext is set.  It's not obvious to me how you could ever get a node with linetext = NULL.  There are also various lines in AddHashEntry which make no sense at all, like assigning the hashtab[value] as soon as you get in there - what is going to happen to any existing nodes?

You haven't posted the code for 'makenode'.  I hope it calls strdup, or all your nodes will point to your (temporary) file_buffer which gets overwritten each time.

Can I make a cruel-but-kind suggestion?  Scrap all this and sit down with some pictures of the structure you want, then, as you have started to do, code up each operation you can imagine into a separate function.  Keep in mind all the time what the _meaning_ of a NULL pointer is in each situation, and don't forget that pointers don't copy the data they point to.  I know this sounds a bit condescending, but even experienced programmers make these mistakes.  I can't design a data structure without a picture of it.

I hope this helps.

Cheers

Paul
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now