ハッシュテーブル＆BST実装

Question

ハッシュテーブルに人を挿入するためのキーボードからのコマンドを受け入れることができる割り当てに取り組んでいます。誰かがhastableに挿入された後、彼らはテーブルの中の他の人と "友好的になる"ことができます。バイナリ検索ツリーを誰と友人なのかを保存する方法。私がしなければならないのは、ハッシュテーブルのために、ノードの最初の部分は人の名前であり、次に次はその人の友人のためのbstへのポインタであり、最後に、衝突です。ここに視覚的な例があります... 私はテーブルに人を挿入することができましたが、私が理解できない問題は、BSTにアクセスしてその人の友達を追加する方法です。ここに私のコードは...

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

// Structures 
struct linkedList{ 
    char *name; 
    struct linkedList *next; 
    struct linkedList *tree; 
}; 

typedef struct linkedList list; 

struct hashTable{ 
    int size; 
    list **table; 
}; 

typedef struct hashTable hash; 

struct bst{ 
    char *val; 
    struct bst *l; 
    struct bst *r; 
}; 

int main(){ 
char input[50]; 
char *ch, cmd_str[50], name[30]; 

// Make hash table for names 
hash *profiles; 
profiles = createHashTable(1001); 

while(1){ 
    // Get keyboard input 
    fgets(input, 50, stdin); 
    input[strlen(input)-1] = '\0'; 

    // parse the input 
    ch = strtok(input, " "); 
    strcpy(cmd_str,ch); 



    if(strcmp("CREATE", cmd_str) == 0){ 
     ch = strtok(NULL, " \n"); 
     insertPerson(profiles, ch); 
    } 
    else if(strcmp("FRIEND", cmd_str) == 0){ 
     ch = strtok(NULL, " \n"); 
     strcpy(name, ch); 
     ch = strtok(NULL, " \n"); 
     friendPerson(profiles, name, ch); 
    } 
    else if(strcmp("UNFRIEND", cmd_str) == 0){ 
     ch = strtok(NULL, " \n"); 

    } 
    else if(strcmp("LIST", cmd_str) == 0){ 
     ch = strtok(NULL, " \n"); 
     printFriends(profiles, ch); 
    } 
    else if(strcmp("QUERY", cmd_str) == 0){ 

    } 
    else if(strcmp("BIGGEST-FRIEND-CIRCLE", cmd_str) == 0){ 

    } 
    else if(strcmp("INFLUENTIAL-FRIEND", cmd_str) == 0){ 

    } 
    else if(strcmp("EXIT", cmd_str) == 0){ 
     printf("\nExiting...\n"); 
     return 0; 
    } 
    else{ 
     printf("\nBad Command.\n"); 
    } 
} 
} 

// Creates Hash Table 
hash *createHashTable(int size){ 
int i; 
hash *new_table; 

if((new_table = malloc(sizeof(hash))) == NULL) 
    return NULL; 

if((new_table->table = malloc(sizeof(list *) * size)) == NULL) 
    return NULL; 

for(i=0; i < size; i++) 
    new_table->table[i] = NULL; 

new_table->size = size; 

return new_table; 
} 

// hashing function 
int keyHash(char *name){ 
    int c; 
    unsigned long key; 

    while(c = *name++) 
     key = ((key<<5) + key) + c; 

    return key%1000; 
} 

// insert a person into the hash table 
void insertPerson(hash *profiles, char *name){ 
    struct linkedList *item = (struct linkedList*)malloc(sizeof(struct linkedList)); 
    int hash_val = keyHash(name); 

    item->name = name; 
    item->next = NULL; 
    item->tree = new_tree; 

    // Collision case 
    if(profiles->table[hash_val] != NULL){ 
     while(profiles->table[hash_val]->next != NULL){ 
      profiles->table[hash_val] = profiles->table[hash_val]->next; 
     } 
     profiles->table[hash_val]->next = item; 
    } 
    // Empty cell 
    else{ 
     profiles->table[hash_val] = item; 
    } 

} 

// friend two people inside the hash table 
void friendPerson(hash *profiles, char *name, char *_friend){ 
    int hash1 = keyHash(name); 
    int hash2 = keyHash(_friend); 

    // check if the names are already in system 
    if(!profiles->table[hash1]){ 
     printf("%s is not yet in the system", name); 
     return; 
    } 
    if(!profiles->table[hash2]){ 
     printf("%s is not yet in the system", _friend); 
     return; 
    } 

    // add first friend 
    if(strcmp(profiles->table[hash1]->name, name) == 0){ 
     insertBST(profiles->table[hash1]->tree, _friend); 
    } 
    else{ 
     while(profiles->table[hash1]->next != NULL){ 
      if(strcmp(profiles->table[hash1]->name, name) == 0)){ 
       break; 
      } 
      profiles->table[hash1] = profiles->table[hash1]->next; 
     } 
     insertBST(profiles->table[hash1]->tree, _friend); 
    } 

    // add second friend 
    if(strcmp(profiles->table[hash2]->name, _friend) == 0){ 
     insertBST(profiles->table[hash2]->tree, name); 
    } 
    else{ 
     while(profiles->table[hash2]->next != NULL){ 
      if(strcmp(profiles->table[hash2]->name, name) == 0)){ 
       break; 
      } 
      profiles->table[hash2] = profiles->table[hash1]->next; 
     } 
     insertBST(profiles->table[hash2]->tree, name); 
    } 
} 

// creates a new bst node 
struct bst *newBSTNode(char *name){ 
    struct bst *temp = (struct bst*)malloc(sizeof(struct bst)); 
    temp->val = strdup(name); 
    strcpy(temp->val, name); 
    temp->l = temp->r = NULL; 
    return temp; 
} 

// Inserts the a friend into a BST 
struct bst *insertBST(struct bst *node, char *name){ 
    if(!node) 
     return newBSTNode(name); 
    else{ 
     if(strcmp(name, node->val) < 0){ 
      node->l = insertBST(node->l, name); 
     } 
     else if(strcmp(name, node->val) > 0){ 
      node->r = insertBST(node->r, name); 
     } 
    } 

    return node; 
} 

// Inorder print of names 
void inorder(struct bst *root){ 
    if(!root){ 
     inorder(root->l); 
     printf("%s ", root->val); 
     inorder(root->r); 
    } 
} 

// Sends to function to print names 
void printFriends(hash *profiles, char *name){ 
    int hash_val = keyHash(name); 
    inorder(profiles->table[hash_val]->tree); 
} 

私はその人のBSTにどのようにアクセスできますか？ struct bst *tree = profiles->table[hash1]->tree;は私の以前の試みでしたが、暗闇の中でより多くのショットでした。前もって感謝します！

更新：さて、私は友人を追加することができました（私は思う）、今はvoid printFriends()でそれらを印刷しようとしています。しかし、私が関数を実行すると何も出力されません。誰かが私がそれを台無しにしているか知っていますか？上記のコードを更新しました。

Answer 1

linkedListには、nameとtreeポインタが格納されています。しかしtreeのタイプはlinkedListです。これをstruct bst *に変更します。宣言の順序を変更するか、前方宣言を挿入する必要があります。

検索を実装します。ハッシュバケットが空であるが、一致する名前を検索しないかどうかをチェックします。

バケット内で一致する名前が見つかると、同じノードに前述のtreeポインタが含まれます。友人をツリーに挿入します。あなたのロジックに応じて、他人のツリーに逆参照を挿入したい場合としない場合があります。 （もしAliceがBobと友達だったら、BobがAliceと自動的に連絡を取るのですか？あるいは確認を待つのですか？）