哈希表和 BST 实现
Hashtable & BST Implementation
我正在做一项作业,它可以接受来自键盘的命令,将人们插入到哈希表中table。将某人插入 hastable 后,他们可以 "friended" 与 table 中的另一个人。我必须存储谁和谁是二叉搜索树的朋友的方式。我要做的是对于 hashtable 节点的第一部分是这个人的名字,然后 next 是指向那个人的朋友的 bst 的指针,最后是指向 next 的指针发生碰撞时链接的节点。这是一个视觉示例...
我已经能够将人添加到我的 table 中,但我无法弄清楚的问题是如何访问 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] = '[=10=]';
// 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()
打印他们。但是,当我 运行 该函数时,什么也没有打印出来。有人知道我在哪里搞砸了吗?我已经更新了上面的代码。
您的 linkedList
存储 name
和一个 tree
指针。但是tree
的类型是linkedList
。将其更改为 struct bst *
。您必须重新排序声明,或插入前向声明。
执行搜索。您检查哈希桶是否为空,但您没有搜索匹配的名称。
一旦在存储桶中找到匹配的名称,同一节点就会包含上述 tree
指针。将朋友插入树中。根据您的逻辑,您可能想也可能不想在其他人的树中插入反向引用。 (如果Alice和Bob是好友,那么Bob会自动和Alice成为好友吗?还是等待确认?)
我正在做一项作业,它可以接受来自键盘的命令,将人们插入到哈希表中table。将某人插入 hastable 后,他们可以 "friended" 与 table 中的另一个人。我必须存储谁和谁是二叉搜索树的朋友的方式。我要做的是对于 hashtable 节点的第一部分是这个人的名字,然后 next 是指向那个人的朋友的 bst 的指针,最后是指向 next 的指针发生碰撞时链接的节点。这是一个视觉示例...
我已经能够将人添加到我的 table 中,但我无法弄清楚的问题是如何访问 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] = '[=10=]';
// 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()
打印他们。但是,当我 运行 该函数时,什么也没有打印出来。有人知道我在哪里搞砸了吗?我已经更新了上面的代码。
您的 linkedList
存储 name
和一个 tree
指针。但是tree
的类型是linkedList
。将其更改为 struct bst *
。您必须重新排序声明,或插入前向声明。
执行搜索。您检查哈希桶是否为空,但您没有搜索匹配的名称。
一旦在存储桶中找到匹配的名称,同一节点就会包含上述 tree
指针。将朋友插入树中。根据您的逻辑,您可能想也可能不想在其他人的树中插入反向引用。 (如果Alice和Bob是好友,那么Bob会自动和Alice成为好友吗?还是等待确认?)