c - バグのあるリンクリストを持つハッシュテーブル

Question

リンクされたリストを使用してハッシュテーブルを実装しようとしていますが、正しく機能しないことが 1 つあります。最初に、リンクされたリストのコードを作成し、それが想定どおりに機能することを確認したので、ハッシュテーブルの実装またはそれらの間の相互作用に何かが必要であることがわかりました。

何が起こるかというと、いくつかのオブジェクトを追加して、それらを問​​題なく再び見つけることができるということです。しかし、2 つ以上のオブジェクトが同じキーでハッシュされている場合、それらはリンク リストを作成するはずですが、何らかの理由で、リンク リストで最後に追加されたオブジェクトしか見つけることができません。

ただし、「lookup_string」関数で見つけることができないオブジェクトを正常に削除できるため、以前に追加したオブジェクトはそこにあります。そのため、オブジェクトがその場所に保存されていることがわかります。

したがって、関数「lookup_string」は、ハッシュテーブルで検索するオブジェクトを提供することになっており、「検索」関数は、リンクリストのみを実装したときに使用したものです。言及する価値があるのは、「検索」機能は削除プロセスで使用されますが、オブジェクトを見つけたいだけのプロセスでは使用されないということです。 「検索」機能のないオブジェクト。

これを簡単にするために、2 つのオブジェクトを保存します。

オブジェクト 1:

name(key) = bcd
telephone number = 123

オブジェクト 2:

name(key) = ace
telephone number = 910

これで、オブジェクト 1 と 2 の両方が同じハッシュ キー値を取得するため、それらはハッシュ テーブルの同じスロットに格納されます。それらはリンクされたリストを作成することになっていますが、オブジェクトを検索すると (メニューの選択番号 3)、最後に追加されたオブジェクト (オブジェクト 2) しか見つかりません。しかし、オブジェクト 1 を削除することはできます。オブジェクト 1 は正常に削除されました。

コード：

struct post
{   
    char name[30];          
    int tel;                
    struct post *next;      
};

typedef struct post Post;

Post *head = NULL;  
Post *current;  

struct hash_table
{
    Post **table;
    int size;
};

typedef struct hash_table Post_table;

unsigned int Hash(Post_table *hash_table, char tempname[30])
{
    int i;
    int sum;
    int key;
    for(i = 0; i < strlen(tempname); i++)
    {
        sum += (int)tempname[i];
    }

    key = sum % hash_table->size;
    return key;
}

Post_table *create_hash_table(int size)
{
    int i;
    Post_table *new_table;

    if (size < 1)
    {
        return NULL;
    }

    //attempt to allocate memory for the table structure
    if ((new_table = malloc(sizeof(Post_table))) == NULL)
    {
        return NULL;
    }

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

    //Initialize the elements of the table
    for(i = 0; i < size; i++)
    {
        new_table->table[i] = NULL;
        new_table->size = size;
    }
    return new_table;
}

Post *lookup_string(Post_table *hash_table, char tempname[30])
{
    Post *list;
    unsigned int hashkey = Hash(hash_table, tempname);

    for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
    {
        if (strcmp(tempname, list->name) == 0)
        {
            return list;
        }
    }
    return NULL;
}

int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
    Post *new_list;
    Post *current_list;
    unsigned int hashkey = Hash(hash_table, tempname);

    /* Attempt to allocate memory for list */
    if ((new_list = malloc(sizeof(Post))) == NULL)
    {
        return 1;
    }

    /* Does item already exist? */
    current_list = lookup_string(hash_table, tempname);
    /* item already exists, don't insert it again. */
    if (current_list != NULL)
    {
        return 2;
    }
    /* Insert into list */

    printf("\nHash-key: %d\n", hashkey); 
    hash_table->table[hashkey] = AddList(tempname, temptel);

    return 0;
}

Post* CreateList(char tempname[30], int temptel)
{   
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);    
    ptr->tel = temptel;
    ptr->next = NULL;

    printf("\n creating list with headnode as [%s]\n",tempname);

    head = current = ptr;
    return ptr;
}

Post* AddList(char tempname[30], int temptel)
{
    if (NULL == head)
    {
        return (CreateList(tempname, temptel));
    }

    printf("\n Adding node to end of list with value [%s]\n",tempname);
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);
    ptr->tel = temptel;
    ptr->next = NULL;

    current->next = ptr;
    current = ptr;
    return ptr;
}

void skrivMeny(void)
{
    printf("\n1: Register name and telephone number\n");
    printf("2: Remove name and telephone number\n");
    printf("3: Search for name\n");
    printf("5: Exit\n");
}

Post* Search(char tempname[30], Post **prev)
{
    Post *ptr = head;
    Post *tmp = NULL;
    int found = 0;
    char structname[sizeof(tempname)];

    printf("\n Searching the list for value [%s] \n",tempname);

    while(ptr != NULL)
    {   
        if (strcmp(ptr->name, tempname) == 0)
        {
            found = 1;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(found == 1)
    {
        if(prev)
        {
            *prev = tmp;
        }
        return ptr;
    }
    else
    {
        return NULL;
    }
}

void free_entry(Post_table *hash_table, char tempname[30])
{
    Post *del_list;
    Post *temp;
    int ret = 0;

    unsigned int hashkey = Hash(hash_table, tempname);
    del_list = lookup_string(hash_table, tempname);

    ret = Delete(tempname);

    if(ret != 0)
    {
        printf("\n delete [name = %s] failed, no such element found\n",tempname);
    }
    else
    {
        printf("\n delete [name = %s]  passed \n",tempname);
    }
}

int Delete(char tempname[30])
{
    Post *prev = NULL;
    Post *del = NULL;

    printf("\n Deleting value [%s] from list\n",tempname);
    del = Search(tempname,&prev);

    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
        {
            prev->next = del->next;
        }
        if(del == current && del != head)
        {
            current = prev;
        }
        else if(del == head)
        {
            head = del->next;
        }
    }

    free(del);
    del = NULL;
    return 0;
}


int main()
{
    printf("\nHej och välkommen till hashlistan\n\n");
    int menyval = 1;
    char tempname[30];
    int temptel;
    int key;

    Post * ptr;

    Post_table *hash_table;
    int table_size = 10;
    hash_table = create_hash_table(table_size);

while (menyval > 0 && menyval <= 5)
{
    skrivMeny();
    scanf("%d", &menyval);

        if (menyval == 1)
        {
            printf("[Name] [Number] = ");
            scanf("%s %d", &tempname[0], &temptel);//inmatning
            add_string(hash_table, tempname, temptel);
        }

        if (menyval == 2)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            free_entry(hash_table, tempname);
        }

        if (menyval == 3)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            ptr = lookup_string(hash_table, tempname);

            if(ptr == NULL)
            {
                printf("\n Search [name = %s] failed, no such element found\n",tempname);
            }
            else
            {
                printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
            }
        }
        if (menyval == 5)
        {
            break;
        }

    }
    return 0;
}

問題を解決するためのすべてのヘルプまたはヒントに感謝します!

編集:これが私のコードの現在の様子です。ファイルを2つのファイルに分割しました。cファイルにヘッダーファイルを含めたhash.cとlista.h。

lista.h:

struct post
{   
    char name[30];          
    int tel;                
    struct post *next;      
};
typedef struct post Post;

struct list
{
    Post *head = NULL;  
    Post *current;
};
typedef struct list List;

Post* CreateList(char tempname[30], int temptel)
{   
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);    
    ptr->tel = temptel;
    ptr->next = NULL;

    printf("\n creating list with headnode as [%s]\n",tempname);

    return ptr;
}

Post* AddList(char tempname[30], int temptel, int emptyElement)
{
    if (emptyElement == 1)
    {
        return (CreateList(tempname, temptel));
    }

    printf("\n Adding node to end of list with value [%s]\n",tempname);
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);
    ptr->tel = temptel;
    ptr->next = NULL;

    return ptr;
}

int Delete(Post_table *hash_table, char tempname[30])
{
    Post *prev = NULL;
    Post *del = NULL;

    printf("\n Deleting value [%s] from list\n",tempname);
    del = Search(tempname,&prev);

    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
        {
            prev->next = del->next;
        }
        if(del == hash_table->table[hashkey].current && del != hash_table->table[hashkey].head)
        {
            hash_table->table[hashkey].current = prev;
        }
        else if(del == hash_table->table[hashkey].head)
        {
            hash_table->table[hashkey].head = del->next;
        }
    }

    free(del);
    del = NULL;
    return 0;
}

hash.c:

struct hash_table
{
    List *table;
    int size;
};

typedef struct hash_table Post_table;

unsigned int Hash(Post_table *hash_table, char tempname[30])
{
    int i;
    int sum;
    int key;
    for(i = 0; i < strlen(tempname); i++)
    {
        sum += (int)tempname[i];
    }

    key = sum % hash_table->size;
    return key;
}

Post_table *create_hash_table(int size)
{
    int i;
    Post_table *new_table;

    if (size < 1)
    {
        return NULL;
    }

    //attempt to allocate memory for the table structure
    if ((new_table = malloc(sizeof(Post_table))) == NULL)
    {
        return NULL;
    }

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

    //Initialize the elements of the table
    for(i = 0; i < size; i++)
    {
        new_table->table[i] = NULL;
        new_table->size = size;
    }
    return new_table;
}

Post *lookup_string(Post_table *hash_table, char tempname[30])
{
    Post *list;
    unsigned int hashkey = Hash(hash_table, tempname);

    for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
    {
        if (strcmp(tempname, list->name) == 0)
        {
            return list;
        }
    }
    return NULL;
}

int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
    int emptyElement = 0;        
    Post *new_list;
    Post *current_list;
    unsigned int hashkey = Hash(hash_table, tempname);

    /* Attempt to allocate memory for list */
    if ((new_list = malloc(sizeof(Post))) == NULL)
    {
        return 1;
    }

    /* Does item already exist? */
    current_list = lookup_string(hash_table, tempname);
    /* item already exists, don't insert it again. */
    if (current_list != NULL)
    {
        return 2;
    }
    /* Insert into list */
    if (hash_table->table[hashkey] == NULL)
    {
        emptyElement = 1;
    }

    printf("\nHash-key: %d\n", hashkey); 
    hash_table->table[hashkey] = AddList(tempname, temptel);

    if (emptyElement == 1)
    {
            hash_table->table[hashkey].head = hash_table->table[hashkey];
            hash_table->table[hashkey].current = hash_table->table[hashkey];
    }

    if (emptyElement == 0)
    {
            hash_table->table[hashkey].current = hash_table->table[hashkey];
    }

    return 0;
}

void free_entry(Post_table *hash_table, char tempname[30])
{
    Post *del_list;
    Post *temp;
    int ret = 0;

    unsigned int hashkey = Hash(hash_table, tempname);
    del_list = lookup_string(hash_table, tempname);

    ret = Delete(tempname);

    if(ret != 0)
    {
        printf("\n delete [name = %s] failed, no such element found\n",tempname);
    }
    else
    {
        printf("\n delete [name = %s]  passed \n",tempname);
    }
}

void skrivMeny(void)
{
    printf("\n1: Register name and telephone number\n");
    printf("2: Remove name and telephone number\n");
    printf("3: Search for name\n");
    printf("5: Exit\n");
}

Post* Search(char tempname[30], Post **prev)
{
    Post *ptr = head;
    Post *tmp = NULL;
    int found = 0;
    char structname[sizeof(tempname)];

    printf("\n Searching the list for value [%s] \n",tempname);

    while(ptr != NULL)
    {   
        if (strcmp(ptr->name, tempname) == 0)
        {
            found = 1;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(found == 1)
    {
        if(prev)
        {
            *prev = tmp;
        }
        return ptr;
    }
    else
    {
        return NULL;
    }
}

int main()
{
    printf("\nHej och välkommen till hashlistan\n\n");
    int menyval = 1;
    char tempname[30];
    int temptel;
    int key;

    Post * ptr;

    Post_table *hash_table;
    int table_size = 10;
    hash_table = create_hash_table(table_size);

while (menyval > 0 && menyval <= 5)
{
    skrivMeny();
    scanf("%d", &menyval);

        if (menyval == 1)
        {
            printf("[Name] [Number] = ");
            scanf("%s %d", &tempname[0], &temptel);//inmatning
            add_string(hash_table, tempname, temptel);
        }

        if (menyval == 2)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            free_entry(hash_table, tempname);
        }

        if (menyval == 3)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            ptr = lookup_string(hash_table, tempname);

            if(ptr == NULL)
            {
                printf("\n Search [name = %s] failed, no such element found\n",tempname);
            }
            else
            {
                printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
            }
        }
        if (menyval == 5)
        {
            break;
        }

    }
    return 0;
}

しかし、私が言ったように、この部分には何か問題があるようです:

struct list
{
    Post *head = NULL;  
    Post *current;
};

これは正しくないため、他のいくつかのエラーが発生するため、最初にこの部分の何が問題なのかを確認しようとしています.

Answer 1

ここにあなたのコードのいくつかの改善点があります: 私はタグ「レオ」でそれらをマークしました

list.c で:

struct post                 // structure of node
{   
    char name[30];          // stored data
    int tel;                // stored data
    struct post *next;      // reference to next node
};

typedef struct post Post;   // Post = struct post

struct list
{
    Post *head;         
    Post *current;              
};

typedef struct list List;

struct hash_table
{
    List *table;
    int size;
};

typedef struct hash_table Post_table;

Post* CreateList(char tempname[30], int temptel);
Post* AddList(char tempname[30], int temptel, int emptyElement, Post *current);
void skrivMeny(void);
void PrintList(void);
int Delete(Post_table *hash_table, char tempname[30], unsigned int hashkey);
Post* Search(Post_table *hash_table, unsigned int hashkey, char tempname[30], Post **prev);

Post* CreateList(char tempname[30], int temptel)
{   
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);    
    ptr->tel = temptel;
    ptr->next = NULL;

    printf("\n creating list with headnode as [%s]\n",tempname);

    return ptr;
}

// Leo: emptyElement isn't neccessary, we use current==null 
Post* AddList(char tempname[30], int temptel, Post *current)
{
    if( current == null )
    {
        return (CreateList(tempname, temptel));
    }

    printf("\n Adding node to end of list with value [%s]\n",tempname);
    Post *ptr = (Post*)malloc(sizeof(Post));

    strcpy(ptr->name, tempname);
    ptr->tel = temptel;
    ptr->next = NULL;

    // Leo: we must append the new element to current
    current->next = ptr;

    return ptr;
}

そしてhash.cで

unsigned int Hash(Post_table *hash_table, char tempname[30])
{
    int i;
    int sum;
    int key;
    for(i = 0; i < strlen(tempname); i++)
    {
        sum += (int)tempname[i];
    }

    key = sum % hash_table->size;
    return key;
}

Post_table *create_hash_table(int size)
{
    int i;
    Post_table *new_table;

    if (size < 1)
    {
        return NULL;
    }

    //attempt to allocate memory for the table structure
    if ((new_table = malloc(sizeof(Post_table))) == NULL)
    {
        return NULL;
    }

    //attempt to allocate memory for the table itself
    // Leo: replaced malloc() by calloc() so all head and current are initialized with NULL
    if ((new_table->table = calloc(size, sizeof(List *) )) == NULL)
    {
        return NULL;
    }

    //Initialize the elements of the table
    /* Leo: What's that loop for ?
    for(i = 0; i < size; i++)
    {
        new_table->table[i];        // Leo: that line doen't do anything
        new_table->size = size;     // Leo: once is enough, let's have it otside the loop
    }
    */
    new_table->size = size;       // Leo: once is enough, let's have it otside the loop
    return new_table;
}

Post *lookup_string(Post_table *hash_table, char tempname[30])
{
    Post *list;
    unsigned int hashkey = Hash(hash_table, tempname);

    /* 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.
    */
    // Leo: we must start with head instead of current
    for(list = hash_table->table[hashkey].head; list != NULL; list = list->next)
    {
        if (strcmp(tempname, list->name) == 0)
        {
            return list;
        }
    }
    return NULL;
}

int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
    //Leo: emptyElement is not used any more (see AddList()
    //int emptyElement = 0;
    //Leo: new_list is never used
    //Post *new_list;
    Post *current_list;
    unsigned int hashkey = Hash(hash_table, tempname);

    /* Attempt to allocate memory for list */
    /* Leo: new_list is never used
    if ((new_list = malloc(sizeof(Post))) == NULL)
    {
        return 1;
    }
    */

    /* Does item already exist? */
    current_list = lookup_string(hash_table, tempname);
    /* item already exists, don't insert it again. */
    if (current_list != NULL)
    {
        return 2;
    }
    /* Insert into list */
    /* Leo: emptyElement isn't used any more 
    if (hash_table->table[hashkey].head == NULL)
    {
        emptyElement = 1;
    }
    */

    printf("\nHash-key: %d\n", hashkey);
    //This line of code under used to store my element in the hash-table but gives now an error 
    //  hash_table->table[hashkey] = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);

    /* Leo: in case of emptyElement == 1 you have called AddList() twice and so created two new list elemens, we replace all of this by the code below
    if (emptyElement == 1)
    {
        hash_table->table[hashkey].head = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
        hash_table->table[hashkey].current = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
    }

    if (emptyElement == 0)
    {
        hash_table->table[hashkey].current = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
    }
    */

    // Leo: Note: if the list for hashKey has not been created yet then both head and current are NULL, otherwise both are != NULL
    hash_table->table[hashkey].current = AddList(tempname, temptel, hash_table->table[hashkey].current);
    // Leo: if the list has been created just now, then both head and current must point to the only list element
    if( hash_table->table[hashkey].head == NULL )
         hash_table->table[hashkey].head = hash_table->table[hashkey].current;

    return 0;
}

void free_entry(Post_table *hash_table, char tempname[30])
{
    Post *del_list;
    Post *temp;
    int ret = 0;

    unsigned int hashkey = Hash(hash_table, tempname);
    del_list = lookup_string(hash_table, tempname);

    ret = Delete(hash_table, tempname, hashkey);

    if(ret != 0)
    {
        printf("\n delete [name = %s] failed, no such element found\n",tempname);
    }
    else
    {
        printf("\n delete [name = %s]  passed \n",tempname);
    }
}

void skrivMeny(void)
{
    printf("\n1: Register name and telephone number\n");
    printf("2: Remove name and telephone number\n");
    printf("3: Search for name\n");
    printf("5: Exit\n");
}

Post* Search(Post_table *hash_table, unsigned int hashkey, char tempname[30], Post **prev)
{
    Post *ptr = hash_table->table[hashkey].head;
    Post *tmp = NULL;
    int found = 0;
    char structname[sizeof(tempname)];

    printf("\n Searching the list for value [%s] \n",tempname);

    while(ptr != NULL)
    {   
        if (strcmp(ptr->name, tempname) == 0)
        {
            found = 1;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(found == 1)
    {
        if(prev)
        {
            *prev = tmp;
        }
    return ptr;
    }
    else
    {
        return NULL;
    }
}


int main()
{
    printf("\nHej och välkommen till hashlistan\n\n");
    int menyval = 1;
    char tempname[30];
    int temptel;
    int key;

    Post * ptr;

    Post_table *hash_table;
    int table_size = 10;
    hash_table = create_hash_table(table_size);

    while (menyval > 0 && menyval <= 5)
    {
        skrivMeny();
        scanf("%d", &menyval);

        if (menyval == 1)
        {
            printf("[Name] [Number] = ");
            scanf("%s %d", &tempname[0], &temptel);//inmatning
            add_string(hash_table, tempname, temptel);
        }

        if (menyval == 2)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            free_entry(hash_table, tempname);
        }

        if (menyval == 3)
        {
            printf("[Name] = ");
            scanf("%s", &tempname[0]);
            ptr = lookup_string(hash_table, tempname);

            if(ptr == NULL)
            {
                printf("\n Search [name = %s] failed, no such element found\n",tempname);
            }
            else
            {
                printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
            }
        }

        if (menyval == 5)
        {
            break;
        }

    }
    return 0;
}


int Delete(Post_table *hash_table, char tempname[30], unsigned int hashkey)
{
    Post *prev = NULL;
    Post *del = NULL;

    printf("\n Deleting value [%s] from list\n",tempname);
    del = Search(hash_table, hashkey, tempname, &prev);

    if(del == NULL)
    {
        return -1;
    }

    else
    {
        if(prev != NULL)
        {
            prev->next = del->next;
        }

        if(del == hash_table->table[hashkey].current && del != hash_table->table[hashkey].head)
        {
            hash_table->table[hashkey].current = prev;
        }

        else if(del == hash_table->table[hashkey].head)
        {
            hash_table->table[hashkey].head = del->next;
        }
    }

    free(del);
    del = NULL;
    return 0;
}

私はそれをコンパイルしていないので、構文エラーがあるかもしれませんが、全体がどのように機能するかが明確になることを願っています. 他にご不明な点がございましたら、お気軽にお問い合わせください。

Answer 2

間違っていたら申し訳ありませんが、lookup_string() 関数がハッシュ テーブルの最後の要素 (最近追加された要素) にトラバースすることがわかります。逆にたどってみるか、双方向リンクリストを使用してください。

PS: ちょっとしたカスタマイズで検索機能を使っていませんか? Y ルックアップと検索のこの冗長性は?

ハッピーコーディング！