Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dictionary with Hashing in C

  1. Apr 7, 2013 #1
    Can some one explain me the difference between the following two pieces of code ?
    First one doesn't work. I debugged it and made it to work but I am unable to understand how.
    The lines with changes have been made red bold.


    Code (Text):
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define SIZE 100

    int hash_func(char k[]);
    void hash(int key,char k1[],char k2[]);
    char *search(int key,char k[]);


    struct hash_table{

    [B] [COLOR="Red"]char *cword;
        char *mword;[/COLOR][/B]
        struct hash_table *next;
       
    };

    struct hash_table *arr[SIZE];

    int main() {
        char k1[100];
        char k2[100];
        char buf[200];
        char test[100];
        char *word;
        int key;
        int i;
        int choice1;
        int choice2;
        FILE *fp1;
        FILE *fp2;

        fp1=fopen("spell.txt","r");
        if(fp1==0){
            printf("Could not open dictionary file");
            exit(0);
        }
        for(i=0;i<SIZE;i++){
            arr[i]=NULL;
        }
       
                while(fscanf(fp1,"%s",k1)!=EOF){
                            fscanf(fp1,"%s",k2);
                            key=hash_func(k1);
                            hash(key,k1,k2);
                       
                    printf("%d %s %s\n",key,arr[key]->cword,arr[key]->mword);
                    }
                printf("%s\n",arr[56]->mword);
                printf("Enter 0 for auto spell check and 1 for manual check\n");
                scanf("%d",&choice1);
                for(i=0;i<100;i++){
                    if(arr[i]!=NULL)
                    printf("%d >>%s\n",i,arr[i]->cword);
                }
                while(fscanf(fp2,"%s",k1)!=EOF){
                    key=hash_func(k1);
                    word=search(key,k1);
                    if(choice1==0){
                        //fprintf(fp2,"%s",k2);
                        printf("--%s--",word);
                    }
                    else{
                        printf("Misspelled Word : %s  Correct Word : %s\n",k1,k2);
                        printf("Enter 0 to modify the word in file\n");
                        scanf("%d",&choice2);
                        if(choice2==0)
                            fprintf(fp2,"%s",k2);
                    }              
                               
                }
           
       
    }

    int hash_func(char k[]){

        int n;
        int sum=0;
        n=strlen(k);
        while(n--){
            sum=sum+*k++;
        }
        printf("key %d\n",sum%100);
        return sum%100;
    }

    void hash(int key,char k1[],char k2[]){

        struct hash_table *temp,*new;
        temp=arr[key];
           
        if(temp==NULL){
            arr[key]=(struct hash_table *)malloc(sizeof(struct hash_table));
           
            [B][COLOR="Red"]arr[key]->cword=k2;    
            arr[key]->mword=k1;[/COLOR][/B]
            arr[key]->next=NULL;
           
        }

        else{
            while(temp->next!=NULL)
                temp=temp->next;
            new=(struct hash_table *)malloc(sizeof(struct hash_table));
                [B][COLOR="Red"]new->mword=k1;
                new->cword=k2;[/COLOR][/B]
                new->next=NULL;
            temp->next=new;
        }
    }
           


    char * search(int key,char k[]){

        struct hash_table *temp;
        if(arr[key]==NULL){
            printf("*1*");
            return k;
        }

        else{
            temp=arr[key];
            while(temp->next!=NULL){
                if(strcmp(k,temp->mword)==0){
                    printf("*2*");
                    return temp->cword;
                }
                temp=temp->next;
            }
        }
    }      


    Code (Text):
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    int hash_func(char k[]);
    void hash(int key,char k1[],char k2[]);
    char *search(int key,char k[]);


    struct hash_table{

    [B] [COLOR="Red"]char cword[20];
        char mword[20];[/COLOR][/B]
        struct hash_table *next;
       
    };

    struct hash_table *arr[100];

    int main() {
        char k1[100];
        char k2[100];
        char buf[200];
        char test[100];
        char *word;
        int key;
        int i;
        int choice1;
        int choice2;
        FILE *fp1;
        FILE *fp2;

        fp1=fopen("spell.txt","r");
        if(fp1==0){
            printf("Could not open dictionary file");
            exit(0);
        }
        for(i=0;i<100;i++){
            arr[i]=NULL;
        }
       
                while(fscanf(fp1,"%s",k1)!=EOF){
                            fscanf(fp1,"%s",k2);
                            key=hash_func(k1);
                            hash(key,k1,k2);
                       
                    printf("%d %s %s\n",key,arr[key]->cword,arr[key]->mword);
                     
                    }
                printf("%s\n",arr[56]->mword);
                printf("Enter 0 for auto spell check and 1 for manual check\n");
                scanf("%d",&choice1);
                for(i=0;i<100;i++){
                    if(arr[i]!=NULL)
                    printf("%d >>%s\n",i,arr[i]->cword);
                }
                while(fscanf(fp2,"%s",k1)!=EOF){
                    key=hash_func(k1);
                    word=search(key,k1);
                    if(choice1==0){
                        //fprintf(fp2,"%s",k2);
                        printf("--%s--",word);
                    }
                    else{
                        printf("Misspelled Word : %s  Correct Word : %s\n",k1,k2);
                        printf("Enter 0 to modify the word in file\n");
                        scanf("%d",&choice2);
                        if(choice2==0)
                            fprintf(fp2,"%s",k2);
                    }              
                               
                }
           
       
    }

    int hash_func(char k[]){

        int n;
        int sum=0;
        n=strlen(k);
        while(n--){
            sum=sum+*k++;
        }
        printf("key %d\n",sum%100);
        return sum%100;
    }

    void hash(int key,char k1[],char k2[]){

        struct hash_table *temp,*new;
        temp=arr[key];
       
        if(temp==NULL){
            arr[key]=(struct hash_table *)(malloc(sizeof(struct hash_table)));
        [B] [COLOR="Red"]strcpy(arr[key]->cword,k2);       
            strcpy(arr[key]->mword,k1);[/COLOR][/B]
            arr[key]->next=NULL;
           
        }

        else{
            while(temp->next!=NULL)
                temp=temp->next;
            new=(struct hash_table *)malloc(sizeof(struct hash_table));
       [B]      [COLOR="Red"]strcpy(new->mword,k1);
                strcpy(new->cword,k2);[/COLOR][/B]
                new->next=NULL;
            temp->next=new;
        }
    }
           


    char * search(int key,char k[]){

        struct hash_table *temp;
        if(arr[key]==NULL){
            printf("*1*");
            return k;
        }

        else{
            temp=arr[key];
            while(temp->next!=NULL){
                if(strcmp(k,temp->mword)==0){
                    printf("*2*");
                    return temp->cword;
                }
                temp=temp->next;
            }
        }
    }      
     
     
  2. jcsd
  3. Apr 7, 2013 #2
    "char *cword" means cword is a pointer to a character (which may be an array of characters). 'cword' may be assigned to so that you can point to different characters. Just defining 'cword' did not create a character or array of characters.

    "char cword[200]" means cword is a pointer to an array of 200 characters that has been allocated by the compiler. You cannot assign a new value to 'cword' to point to a different array of characters.

    I suggest getting a good book on C -- but I can't recommend any because I taught myself almost two decades ago.
     
  4. Apr 7, 2013 #3

    rcgldr

    User Avatar
    Homework Helper

    As posted, "char * cword" declares cword to be a pointer to a single character, which may be the first character of an array of characters. Somewhat different than what was posted, "char cword[20]" declares cword to be an array of 20 characters, and although it can be used similar to a pointer, it's not a pointer. If you examine the size, such as sizeof(cword), in the first case you'll get the size of a pointer, probably 4 or 8 bytes depending if the computer is running in 32 bit or 64 bit mode. In the second case, sizeof(cword) will return the size of the array, which is 20.

    In the first case, you'll need to assign a pointer to cword each time you declare an instance of the hash_table structure. This can be an array name, as in your first example, or you can allocate (malloc) an array of characters (you'll need to free them as well).

    Also you can use typedefs for structures in C:

    Code (Text):

    typedef struct_hash_table{ /* prefix of _ commonly used for struct name */
        char cword[20];
        char mword[20];
        struct _hash_table *next;
    }hash_table, *phash_table; /* typedefs for hash table and ptr to hash table */

    /* ... */

    phash_table arr[100] /* declare an array of 100 pointers to hash_table */
     
     
    Last edited: Apr 8, 2013
  5. Apr 8, 2013 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    Or maybe think of it like this

    Code (Text):

    char *cword;
     
    requires you to create and maintain memory storage for this variable. It is super flexible. You can use it to refeence almost any size string object. But it has a lot more "programmer responsibility" overhead. If you allocate memory [ malloc() or strdup() ] to it then you have to clean up [ free() ] later. If you "forget" to clean up then you can literally leak memory out of the program into a place where you cannot use it anymore.. If you merely decide to "aim it" at an existing place in memory, that place cannot change.

    Code (Text):

    char cword[20];
     
    Is less flexible. You have basically one option: [ strcpy() or memcpy() ] to load data into it. It will last, it does not need tending. It cannot handle anything larger than 19 character strings -- C requires an extra trailing nul (ASCII 0 character on every string. If you copy 2 characters into it, it still uses up 20 character total.

    So the latter choice will work well for any language that has no word longer than 20 characters. The former choice is much better for huge dictionaries where consuming memory space wisely is important.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Dictionary with Hashing in C
  1. Hash Functions (Replies: 4)

Loading...