Array of pointer to the linked list

Question

I'm working of my assignment, in C, which to store 500 string into strings of 5 char by the mean of hash table with chaining method to fix the collision.

Hashing algorithm : to add up the ASCII value and apply the modulus operator to the result.

The hash table store the hash key generated and a pointer which points to a linked list. Each linked list has more than one element if there are more than one 5-char string that gives the same hash key.

So far this is my code. I compiled it (Codeblock) and it appears that there is no error. However the program crashed.

Please give some inputs on where did i do wrong.

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

#define SLEN 500
#define WLEN 5
#define MPRIME 73

struct Node {
    char s[WLEN+1];      // array to hold the 5-letter word
    int sindex;          // starting index of the word
    struct Node * next;  // a pointer to the next word in the list
};

int searchword(char *);
int hashfunc(char *);
void build_hashtbl();

struct Node * hashtable[MPRIME] = {NULL};

char string[SLEN+1] = "thenamewasfamiliartomeonseverallevelslookingbackitwasfatethatifoundhimihadcometopeppervillebeachtocloseonasmallhousethathadbeeninourfamilyforyearsonmywaybacktotheairportistoppedforcoffeetherewasafieldacrossthestreetwherekidsinpurpletshirtswerepitchingandhittingihadtimeiwanderedoverasistoodatthebackstopmyfingercurledinthechainlinkfenceanoldmanmaneuveredalawnmoweroverthegrasshewastannedandwrinkledwithahalfcigarinhismouthheshutthemowerwhenhesawmeandaskedifihadakidoutthereisaidnoheaskedwhatiwasdoing";

int main(void) {
    int index;
    char query[WLEN+1];
    build_hashtbl();      // prepare the hash table
    printf("Enter a 5-letter word to search: ");
    scanf("%s", query);
    index = searchword(query);
    if (index != -1)
        printf("The word %s starts at index %d.\n", query, index);
    else
        printf("The word %s is not found.\n", query);
    return 0;
}

int searchword(char * word) {
    int hashval;
    struct Node * lhead;
    hashval = hashfunc(word);
    lhead = hashtable[hashval];
    while (lhead) {
        if (strcmp(lhead->s,word) == 0)
            return lhead->sindex;
        lhead = lhead->next;
    }
    return -1;
}

int hashfunc(char *){
    int hashval = 0;
    int i = 0;
    for (i = 0; i < WLEN; i++){
        hashval += (int) string[i];
    }
    return (int) (hashval % MPRIME);
}

void build_hashtbl(){
    struct Node *hashtable[MPRIME]; //already declared. put here for ease
    struct Node * head = NULL;
    struct Node * last = NULL;

    int i = 0;
    int k = 0;
    int key = 0;
    char sElement[WLEN+1] = {0};

    for (i = 0; i <SLEN; i = i+WLEN){ //for every 5 char, find they hashtable index key
        key = hashfunc(*string[i]);

        for (k = 0; k <WLEN; k++){ //create a new string, sElement from the 5 letter word
        sElement[k] = string[i+k];
        }



    if (hashtable[key] != (NULL)){  //if the hashtable element at that index is empty, STORE it in a node
        hashtable[key] = head;
        struct Node *new_node;
        new_node = (struct Node *) malloc ( sizeof (struct Node) );
        strcpy(new_node->s, sElement); //put the new 5 letter word string into the node
        new_node->sindex = i; //put the starting index of this word
        new_node->next = NULL; //the next pointer is set to NULL
        head->next = new_node; //finally set the head node to point to this new node
        last = new_node; //set the new node as the last node
    }
    else { //if there is already a node in the array
        struct Node *new_node;
        new_node = (struct Node *) malloc ( sizeof (struct Node) );
        strcpy(new_node->s, sElement); //put the new 5 letter word string into the node
        new_node->sindex = i; //put the starting index of this word
        new_node->next = NULL; //the next pointer is set to NULL
        head->next = new_node; //finally set the head node to point to this new node
        last->next = new_node; //set the last node to point to thew new created node
        last = new_node; //set the new node as the last node
    }

    }
}

Where did it crash? Use gdb or printfs to determine which line causes the crash — Dan
– Dan, Commented Jan 4, 2012 at 23:46
Did you try running this in the debugger? That would tell you which line caused the crash. — Oliver Charlesworth
– Oliver Charlesworth, Commented Jan 4, 2012 at 23:47
Who is giving something like this as a C++ assignment? There are neat container classes which do the various bits. Sure, you can practice implementing e.g. a hash container but at least use a std::list (or a std::slist). Judging from the use of <stdio.h> I'd suspect this question is wrongly tagged C++: it looks more like C. — Dietmar Kühl
– Dietmar Kühl, Commented Jan 4, 2012 at 23:51
struct Node *hashtable[MPRIME]; //already declared. put here for ease is called a shadowed variable. — wildplasser
– wildplasser, Commented Jan 4, 2012 at 23:52

Eugen Rieck · Accepted Answer · 2012-01-05 00:32:34Z

1

Your used last and head uninitialized, so head->next and friends would segfault. In fact you don't need them at all and you don't need your if branches - just replace hashtable[key] by new_node after setting new_node->next to hashtable[key]

void build_hashtbl(){

    int i = 0;
    int k = 0;
    int key = 0;

    char sElement[WLEN+1] = {0};

    for (i = 0; i <SLEN; i = i+WLEN){ //for every 5 char, find they hashtable index key
        key = hashfunc(string+i);

        for (k = 0; k <WLEN; k++){ //create a new string, sElement from the 5 letter word
            sElement[k] = string[i+k];
        }

        struct Node *new_node;
        new_node = (struct Node *) malloc ( sizeof (struct Node) );
        strcpy(new_node->s, sElement); //put the new 5 letter word string into the node
        new_node->next=hashtable[key];
        new_node->sindex=i;
        hashtable[key]=new_node;

    }
}

Works for me.

Edit: Also needs #include <stdlib.h> (at least here)

answered Jan 5, 2012 at 0:32

Eugen Rieck

65.6k10 gold badges75 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

wildplasser Over a year ago

sElement is not nul terminated (in the OP, it was not terminated either)

Eugen Rieck Over a year ago

It is: char sElement[WLEN+1] = {0} fills it up with nulls, and later only WLEN chars are overwritten. I checked this one first.

wildplasser Over a year ago

My bad, you're right, I got confused by the strange way of doing things (what's wrong with memcpy(sElement,string+i,5); sElement[5] = 0;, instead of the silly loop ?)

Raf Over a year ago

@EugenRieck thanks. I feel so silly about checking the existence of the nodes like i did before... however, your idea this part still get me confused. I thought of it the new_node.next pointer points back to the pointer in the array. Why? new_node->next=hashtable[key]; wildplasser that is one useful way of writing it. Man, thanks a lot.

Eugen Rieck Over a year ago

new_node.next pointer points back to the pointer that WAS in the array, now new_node IS in the array. We PREPEND the new element instead of APPENDing it, as this doesn't need the check, if a node is already there: We can prepend to a null-node, but we can't append to a null-node

|

Collectives™ on Stack Overflow

Array of pointer to the linked list

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related