?
Solved

Implementing a search and delete function into a Hash table

Posted on 2003-03-30
4
Medium Priority
?
440 Views
Last Modified: 2010-04-15
Can anyone give me some guidance as to how to add a search and delete function to my existing code?

Thank you for any help.  No rush.

/*This is a program to demonstrate Hashing-to-Lists Functions*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUMPOINTERS 5

 
/*  Structure Declaration */
typedef struct student STUDENTREC;
struct student
{
     char ss[10];
     struct student *next;
};
 

/*Function Declarations*/
STUDENTREC *insert(char ss[], STUDENTREC *student_body[], int hashval);
void traverse(STUDENTREC *student_body[]);
int hash(char ss[]);

int main()
{
     char ss[10];
     STUDENTREC *student_body[NUMPOINTERS] = {NULL};
     STUDENTREC *person;
     int hashval;
     
     while(printf("Enter Social Security Number: "), strcmp(gets(ss), "quit"))
     {
          hashval = hash(ss);
          person = insert(ss, student_body, hashval);
          if (person)
               printf("You have attempted to enter a duplicte record!\n");
     } /*end of while*/

     traverse(student_body);
     return 0;

} /*end of main() */

/*Hash Social Security number by summing the cubes of the ASCII value
of characters and then take the modulo of this sum.  Return reslt(hashval). */
int hash(char ss[])
{
     long hashval = 0;

     for(; *ss != '\0'; ss++)
          hashval += (*ss) * (*ss) * (*ss);
     return hashval % NUMPOINTERS;
} /*end of hash() */

/*Put hashed record in list indicated by hash value. */
STUDENTREC *insert(char ss[], STUDENTREC *student_body[], int hashval)
{
     STUDENTREC **mover;

     mover = &student_body[hashval];
     while (*mover)
     {
          if (strcmp(ss, (*mover)->ss) == 0)
               return (*mover);
          mover = &((*mover)->next);
     } /*end of while */

     if ((*mover = (STUDENTREC *) malloc(sizeof(STUDENTREC))) ==NULL)
     {
          printf("Malloc error in insert\n");
          exit(1);
     } /*end of if */

     strcpy((*mover)->ss, ss);
     (*mover)->next = NULL;
     printf("Person with ss number %s placed in list %d.\n", ss, hashval);
     return NULL;
} /*end of insert() */

/*searches the hash table for a social security number */
STUDENTREC *insert(char ss[], STUDENTREC *student_body[], int hashval)






/*Output contents of lists */
void traverse(STUDENTREC *student_body[])
{
     int i;
     STUDENTREC **mover;

     for (i = 0; i < NUMPOINTERS; i++)
     {
          printf("Contents of list %d:\n", i);
          printf("--------------------\n");
          for (mover = &student_body[i]; *mover; mover = &(*mover)->next)
               printf("%s\n", (*mover)->ss);
          printf("\n");
     } /*end of for */

} /* end of traverse() */
0
Comment
Question by:jpipitone
3 Comments
 
LVL 5

Accepted Solution

by:
burtdav earned 200 total points
ID: 8236150
The hash function could stand to be improved ("1234" hashes to the same value as "4321").
A notable omission is collision detection - what if 2 ss#s hash to the same value?
Also, the insert function should only be passed ss and student_body; it should calculate hash(ss) itself.
A "search" a hash table would just index it with the hash, and check if the ss matches:
/* start code */
STUDENTREC *get(char ss[], STUDENTREC *student_body[]){
  STUDENTREC *s = student_body[hash(ss)];
  if (strcmp(s->ss,ss)) {
    return NULL;
    /* actually here you'd find the correct entry however you would depending on your collision detection */
  }
  else {
    return s;
  }
}
/* end code */
To delete, student_body[hash(ss)] = NULL; instead of return s;
You'll probably want your entire hash table initialised to NULL initally, too...
I learnt about hash tables at sparknotes. Check out that tutorial. Good luck.
http://www.sparknotes.com/cs/searching/hashtables/section1.html
0
 
LVL 2

Expert Comment

by:bkrahmer
ID: 8243857
Hey look everybody!  It's 'theoriginalplan' still trying to get us to do his homework!  Please ignore this guy so he'll stop being a freeloader.

brian
0
 
LVL 20

Expert Comment

by:jmcg
ID: 10194637
Nothing has happened on this question in more than 9 months. It's time for cleanup!

My recommendation, which I will post in the Cleanup topic area, is to
accept answer by burtdav (or delete as homework).

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

jmcg
EE Cleanup Volunteer
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

621 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question