I just learned about hash tables today and I tried to make one in C. I get a segmentation fault at line 90. It seems to store the data and retrieve the data fine. It's just when I try to use strcpy to copy the value in the data to a string in the calling function that I get a segmentation fault. I'm not really sure why this is happening since the data is printing out fine.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define size 100
//creates the lsit where the hash table will be stored
float round(int conver){
conver = conver*10.0f;
conver = (conver > (floor(conver) 0.5f)) ? ceil(conver) : floor(conver);
conver = conver/10.0f;
//If you're using C99 or better, rather than ANSI C/C89/C90, the following will also work.
//conver = roundf(conver*10.0f)/10.0f;
return conver;
}
int hash(char input[]){
//decides where a string should be stored
float number = 0;
for(int i = 0; i < strlen(input); i ){
int toAdd = input[i];
printf("to add: %d", toAdd);
number = number toAdd;
printf("number: %f", number);
}
printf("number again: %f", number);
number /= strlen(input);
number = round(number);
printf("number divided: %f \n", number);
return number;
}
struct Node{
//blueprint for linked list node
struct Node *Next;
char data[];
};
struct Node *hashTable[];
struct Node *createNode(char *data){
//utility function to create a node in the linked list
struct Node *newNode = malloc(sizeof(struct Node));
newNode->Next = NULL;
strcpy(newNode->data, data);
return newNode;
};
void createHashTable(){
//creates the hash table before anything can be inserted
for(int i = 0; i < size; i ){
hashTable[i] = NULL;
}
}
void addToHashTable(char *input){
//adds to the hash table
int hashed = hash(input);
if(hashTable[hashed] == NULL){
hashTable[hashed] = createNode(input);
}
else{
struct Node *newNode = createNode(input);
newNode->Next = hashTable[hashed];
hashTable[hashed] = newNode;
}
}
char *search(char input[], char *writeTo){
//searches the hash table for a value
int hashed = hash(input);
printf("\nhashed: %d", hashed);
printf("\ndata: %s", hashTable[hashed]->data);
if(hashTable[hashed] == NULL){
strcpy(writeTo, "not found");
return;
}
else if(hashTable[hashed]->Next == NULL){
printf("\nit is: %s", hashTable[hashed]->data);
strcpy(writeTo, hashTable[hashed]->data);
return;
}
else{
struct Node *newNode = hashTable[hashed];
while(newNode != NULL){
if(newNode->data == input){
strcpy(writeTo, hashTable[hashed]->data);
return;
}
newNode = newNode->Next;
}
}
}
int main()
{
//main function
createHashTable();
addToHashTable("124");
char *writeTo;
search("124", writeTo);
printf("%s", writeTo);
return 0;
}
CodePudding user response：
First of all, when I run your code I don't get a segfault. Did you remove the use case where the segfault occured? If not, it could be a difference in our environments.
More importantly, your code seems to be riddled in small problems. If you get to fixing those one by one, then the important logical errors will have nowhere to hide.
Here is a (n unordered and incomplete) list of such problems:
In your round function, you are using floor and ceil, but you never include the math library.
In your search function, you are not returning a char*, you are returning nothing. The function header should reflect that.
In your search function, in the final else statement, in the while loop, the condition of the if statement compares two char* values, whereas I assume you mean to compare two strings.
In some of your print statements, you are not printing a new line or any other whitespace, making the results hard to read.
CodePudding user response：
There were some bugs in it.
This code should work. I tried to change your code as minimal as possible.
Dont forget that you have to free() pointerstructures.
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#define size 100
int _round(float conver){
conver = (conver > (floorf(conver) 0.5f)) ? ceilf(conver) : floorf(conver);
return (int) conver;
}
int hash(char input[]){
float number = 0;
for(int i = 0; i < strlen(input); i )
{
int toAdd = (int) input[i];
number = number toAdd;
}
number /= strlen(input);
number = _round(number);
return number;
}
struct Node{
struct Node *Prev;
struct Node *Next;
char *data;
};
struct Node *hashTable[size];
struct Node *createNode(char data[]){
struct Node *newNode = malloc(sizeof(struct Node));
newNode->Prev = NULL;
newNode->Next = NULL;
newNode->data = malloc( sizeof(char) * (strlen(data)));
strcpy(newNode->data, &data[0]);
return newNode;
};
void createHashTable(){
for(int i = 0; i < size; i ){
hashTable[i] = NULL;
}
}
void addToHashTable(char input[]){
int hashed = hash(input);
if(hashTable[hashed] == NULL){
hashTable[hashed] = createNode(input);
}
else{
struct Node *newNode = createNode(input);
newNode->Next = hashTable[hashed];
hashTable[hashed]->Prev = newNode;
hashTable[hashed] = newNode;
}
}
char *search(char input[]){
int hashed = hash(input);
printf("hashed: %d\n", hashed );
if(hashTable[hashed] == NULL){
char *writeTo = malloc( sizeof( char ) * 9);
strcpy(writeTo, "not found");
return writeTo;
}
else if(hashTable[hashed]->Next == NULL){
char *writeTo = malloc( sizeof(char) * (strlen(input)));
strcpy(writeTo, hashTable[hashed]->data);
return writeTo;
}
else{
struct Node *newNode = hashTable[hashed];
char *data = malloc( sizeof( char) * (strlen(input)));
strcpy( data, &input[0] );
data[strlen(input)] = '\0';
while(newNode != NULL){
if(strcmp(newNode->data, data) == 0 ){
char *writeTo = malloc( sizeof(char) * (strlen(input)));
strcpy(writeTo, newNode->data);
return writeTo;
}
newNode = newNode->Next;
}
free( data );
}
char *writeTo = malloc( sizeof( char ) * 9);
strcpy(writeTo, "not found");
return writeTo;
}
void freeHashTable()
{
struct Node * node;
for( int i = 0; i < size; i )
{
node = hashTable[i];
if( node != NULL )
{
while( node->Next != NULL )
{
node = node->Next;
}
while( node->Prev != NULL )
{
node = node->Prev;
free( (void*) node->Next->data );
free( (void*) node->Next );
}
free( (void*) node->data );
free( (void*) node );
}
}
}
int main()
{
createHashTable();
addToHashTable("142");
addToHashTable("124");
char *writeTo;
writeTo= search("142");
printf("%s\n", writeTo );
free( (void*) writeTo);
writeTo = search( "124" );
printf("%s\n", writeTo);
free( (void*) writeTo);
freeHashTable();
return 0;
}