?
Solved

Implementing a search and delete function into a Hash table

Posted on 2003-03-30
4
Medium Priority
?
431 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 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

Technology Partners: 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!

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Suggested Courses

770 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