c - 我有一个行为奇怪的 C 哈希例程

Question

在此哈希例程中:1.) 我能够添加字符串。2.) 我可以查看我添加的字符串。3.) 当我尝试添加重复的字符串时，它会抛出一个错误，指出该字符串已存在。4.)但是，当我尝试删除哈希表中已存在的相同字符串时， 然后lookup_routine调用哈希函数来获取索引。此时，它会抛出一个与已添加的哈希索引不同的哈希索引。因此，我的删除例程失败了？

我能够理解为什么对于相同的字符串，哈希函数每次计算不同的索引(而相同的逻辑在 View 哈希表例程中起作用)？有人可以帮助我吗？

这是输出，我得到:

$ ./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;

}