Dictionary with Hashing in C

[zorro]

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.

#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;
		}
	}
}

#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;
		}
	}
}

 

[ScottSalley]

"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.

 

[rcgldr]

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:

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 */

 

[jim mcnamara]

Or maybe think of it like this

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.

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.

 

[LudusRex]

The first piece of code uses a struct data type to create a hash table with linked lists. The "cword" and "mword" variables are pointers to char arrays, which means they are storing the memory address of the char arrays rather than the actual values. This can cause issues when trying to access or modify the values.

In the second piece of code, the "cword" and "mword" variables are declared as char arrays rather than pointers. This means that the actual values are being stored in the hash table rather than just the memory address. This can make it easier to access and modify the values.

Additionally, the first code has a bug in the "hash" function where the "new" variable is not being allocated enough memory for the "next" pointer. This can cause issues when trying to traverse the linked list. The second code fixes this bug by correctly allocating memory for the "next" pointer.

Overall, the second piece of code is more efficient and less prone to errors compared to the first one.