나는 이상하게 행동하는 C 해싱 루틴을 가지고있다

Question

이 해싱 루틴에서 : 1.) 문자열을 추가 할 수있다. 2.) 추가 된 문자열을 볼 수 있습니다. 3.) 중복 문자열을 추가하려고하면 이미 존재한다는 오류가 발생합니다. 4.) 그러나 해시 테이블에 이미있는 동일한 문자열을 삭제하려고하면 lookup_routine이 해시 함수를 호출하여 인덱스를 가져옵니다. 이때 이미 추가 된 것과 다른 해쉬 인덱스를 던집니다. 따라서, 내 삭제 루틴이 실패입니까?

동일한 문자열에 대해 해시 함수가 매번 다른 인덱스를 계산하는 이유를 이해할 수 있습니다 (반면 동일한 논리가 뷰 해시 테이블 루틴에서 작동 함). 누군가 나를 도울 수 있습니까?

이

, 나는 출력 얻고있다 :

$ ./a 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :gaura 

enters in add_string 

DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 1 
hashval = 1 
enters in lookup_string 

str in lookup_string = gaura 
DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 1 
hashval = 1 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG1 : enters here 

hashval = 1 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :ayu 

enters in add_string 

DEBUG purpose in hash function: 

str passed = ayu 
Hashval returned in hash func= 1 
hashval = 1 
enters in lookup_string 

str in lookup_string = ayu 
DEBUG purpose in hash function: 

str passed = ayu 
Hashval returned in hash func= 1 
hashval = 1 

returns NULL in lookup_string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG2 : enters here 

hashval = 1 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :gaurava 

enters in add_string 

DEBUG purpose in hash function: 

str passed = gaurava 
Hashval returned in hash func= 7 
hashval = 7 
enters in lookup_string 

str in lookup_string = gaurava 
DEBUG purpose in hash function: 

str passed = gaurava 
Hashval returned in hash func= 7 
hashval = 7 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG1 : enters here 

hashval = 7 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 4 
Index : i = 1 String = gaura ayu 
Index : i = 7 String = gaurava 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 2 

Please enter the string you want to delete :gaura 

String entered = gaura 
enters in delete_string 

DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 0 
hashval = 0 
enters in lookup_string 

str in lookup_string = gaura 
DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 0 
hashval = 0 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

Item not present. So, cannot be deleted 

Item found in list: Deletion failed 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 
============================================================== 

내 루틴이 아래에 붙여 :

#include<stdio.h> 
#include<string.h> 

struct list 
{ 
char *string; 
struct list *next; 
}; 

struct hash_table 
{ 
int size;  /* the size of the table */ 
struct list **table; /* the table elements */ 
}; 

struct hash_table * hashtable = NULL; 

struct hash_table *create_hash_table(int size) 
{ 
    struct hash_table *new_table; 
    int i; 

    if (size<1) return NULL; /* invalid size for table */ 

    /* Attempt to allocate memory for the table structure */ 
    if ((new_table = malloc(sizeof(struct hash_table))) == NULL) { 
     return NULL; 
    } 

    /* Attempt to allocate memory for the table itself */ 
    if ((new_table->table = malloc(sizeof(struct list *) * size)) == NULL) { 
     return NULL; 
    } 

    /* Initialize the elements of the table */ 
    for(i=0; i<size; i++) 
    new_table->table[i] = '\0'; 

    /* Set the table's size */ 
    new_table->size = size; 

    return new_table; 
} 


unsigned int hash(struct hash_table *hashtable, char *str) 
{ 
    printf("\n DEBUG purpose in hash function:\n"); 
    printf("\n str passed = %s", str); 

    unsigned int hashval = 0; 
    int i = 0; 

    for(; *str != '\0'; str++) 
    { 
    hashval += str[i]; 
    i++; 
    } 
    hashval = hashval % 10; 
    printf("\n Hashval returned in hash func= %d", hashval); 
    return hashval; 
} 


struct list *lookup_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in lookup_string \n"); 
    printf("\n str in lookup_string = %s",str); 

    struct list * new_list; 
    unsigned int hashval = hash(hashtable, str); 

    printf("\n hashval = %d \n", hashval); 

    if(hashtable->table[hashval] == NULL) 
    { 
     printf("\n DEBUG ERROR :element not found in lookup string \n"); 
     return NULL; 
    } 

    /* Go to the correct list based on the hash value and see if str is 
    * in the list. If it is, return return a pointer to the list element. 
    * If it isn't, the item isn't in the table, so return NULL. 
    */ 


    for(new_list = hashtable->table[hashval]; new_list != NULL;new_list = new_list->next) 
    { 
     if (strcmp(str, new_list->string) == 0) 
      return new_list; 
    } 
    printf("\n returns NULL in lookup_string \n"); 
    return NULL; 
} 


int add_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in add_string \n"); 

    struct list *new_list; 
    struct list *current_list; 
    unsigned int hashval = hash(hashtable, str); 
    printf("\n hashval = %d", hashval); 

    /* Attempt to allocate memory for list */ 
    if ((new_list = malloc(sizeof(struct list))) == NULL) 
    { 
    printf("\n enters here \n"); 
    return 1; 
    } 

    /* Does item already exist? */ 
    current_list = lookup_string(hashtable, str); 

    if (current_list == NULL) 
    { 
    printf("\n DEBUG Purpose \n"); 
    printf("\n NULL \n"); 
    } 

    /* item already exists, don't insert it again. */ 
    if (current_list != NULL) 
    { 
    printf("\n Item already present...\n"); 
    return 2; 
    } 

    /* Insert into list */ 
    printf("\n Inserting...\n"); 

    new_list->string = strdup(str); 
    new_list->next = NULL; 
    //new_list->next = hashtable->table[hashval]; 
    if(hashtable->table[hashval] == NULL) 
    { 
     printf("\n DEBUG1 : enters here \n"); 
     printf("\n hashval = %d", hashval); 
     hashtable->table[hashval] = new_list; 
    } 
    else 
    { 
     printf("\n DEBUG2 : enters here \n"); 
     printf("\n hashval = %d", hashval); 
     struct list * temp_list = hashtable->table[hashval]; 
     while(temp_list->next!=NULL) 
     temp_list = temp_list->next; 

     temp_list->next = new_list; 
     // hashtable->table[hashval] = new_list; 
    } 

    return 0; 
} 

int delete_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in delete_string \n"); 

    struct list *new_list; 
    struct list *current_list; 
    unsigned int hashval = hash(hashtable, str); 
    printf("\n hashval = %d", hashval); 

    /* Does item already exist? */ 
    current_list = lookup_string(hashtable, str); 

    if (current_list == NULL) 
    { 
    printf("\n DEBUG Purpose \n"); 
    printf("\n Item not present. So, cannot be deleted \n"); 
    return 1; 
    } 

    /* item exists, delete it. */ 
    if (current_list != NULL) 
    { 
    struct list * temp = hashtable->table[hashval]; 
    if(strcmp(temp->string,str) == 0) 
    { 
     if(temp->next == NULL) 
     { 
     hashtable->table[hashval] = NULL; 
     free(temp); 
     } 
     else 
     { 
     hashtable->table[hashval] = temp->next; 
     free(temp); 
     } 
    } 
    else 
    { 
     struct list * temp1; 
     while(temp->next != NULL) 
     { 
     temp1 = temp; 

     if(strcmp(temp->string, str) == 0) 
     { 
      break; 
     } 
     else 
     { 
      temp = temp->next; 
     } 
     } 
     if(temp->next == NULL) 
     { 
     temp1->next = NULL; 
     free(temp); 
     } 
     else 
     { 
     temp1->next = temp->next; 
     free(temp); 
     } 
    } 
    } 
    return 0; 
} 

void free_table(struct hash_table *hashtable) 
{ 
    int i; 
    struct list *new_list, *temp_list; 

    if (hashtable==NULL) return; 

    /* Free the memory for every item in the table, including the 
    * strings themselves. 
    */ 
    for(i=0; i<hashtable->size; i++) { 
     new_list = hashtable->table[i]; 
     while(new_list!=NULL) { 
      temp_list = new_list; 
      new_list = new_list->next; 
      free(temp_list->string); 
      free(temp_list); 
     } 
    } 

    /* Free the table itself */ 
    free(hashtable->table); 
    free(hashtable); 
} 

void view_hashtable(struct hash_table * hashtable) 
{ 
    int i = 0; 
    if(hashtable == NULL) 
    return; 

    for(i =0; i < hashtable->size; i++) 
    { 
     if((hashtable->table[i] == 0) || (strcmp(hashtable->table[i]->string, "*") == 0)) 
     { 
      continue; 
     } 
     printf(" Index : i = %d\t String = %s",i, hashtable->table[i]->string); 
     struct list * temp = hashtable->table[i]->next; 
     while(temp != NULL) 
     { 
      printf("\t %s",temp->string); 
      temp = temp->next; 
     } 

     printf("\n"); 
    } 
} 



int main() 
{ 
    hashtable = create_hash_table(10); 
    if(hashtable == NULL) 
    { 
    printf("\n Memory allocation failure during creation of hash table \n"); 
    return 0; 
    } 

    int flag = 1; 

    while(flag) 
    { 
     int choice; 

     printf("\n Press 1 to add an element to the hashtable\n"); 
     printf("\n Press 2 to delete an element from the hashtable\n"); 
     printf("\n Press 3 to search the hashtable\n");   printf("\n Press 4 to view the hashtable\n");    printf("\n Press 5 to exit \n"); 
     printf("\n Please enter your choice: "); 

     scanf("%d",&choice); 

     if(choice == 5) 
     flag = 0; 

     else if(choice == 1) 
     { 
      char str[20]; 
      printf("\n Please enter the string :"); 
      scanf("%s",&str); 
      int i; 
      i = add_string(hashtable,str); 

      if(i == 1) 
      { 
       printf("\n Memory allocation failure:Choice 1 \n"); 
       return 0; 
      } 
      else if(i == 2) 
      { 
       printf("\n String already prsent in hash table : Couldnot add it again\n"); 
       return 0; 
      } 
      else 
      { 
       printf("\n String added successfully \n"); 

      } 
     } 


     else if(choice == 2) 
     { 
      int i; 
      struct list * temp_list; 
      char str[20]; 
      printf("\n Please enter the string you want to delete :"); 
      scanf("%s",&str); 

      printf("\n String entered = %s", str); 

      i = delete_string(hashtable,str); 

      if(i == 0) 
      { 
       printf("\n Item found in list: Deletion success \n"); 
      } 
      else 
       printf("\n Item found in list: Deletion failed \n"); 
     } 


     else if(choice == 3) 
     { 
      struct list * temp_list; 
      char str[20]; 
      printf("\n Please enter the string :"); 
      scanf("%s",&str); 
      temp_list = lookup_string(hashtable,str); 

      if(!temp_list) 
      { 
       printf("\n Item not found in list: Deletion failed \n"); 
       return 0; 
      } 
      printf("\n Item found: Present in Hash Table \n"); 
     } 


     else if(choice == 4) 
     { 
      view_hashtable(hashtable); 
     } 
     else if(choice == 5) 
     { 
      printf("\n Exiting ...."); 
      return 0; 
     } 
     else 
     printf("\n Invalid choice:"); 
    }; 

    free_table(hashtable); 
    return 0; 
} 

Answer 1

귀하의 해시 함수를 그냥 예를 들어, 수행, 문자열의 끝을지나 실행

for(; *str != '\0'; str++) 
{ 
hashval += *str; 

}