I have a problem with hash

This is a discussion on I have a problem with hash within the C Programming forums, part of the General Programming Boards category; I'm programming a hash with alphabetics, use as a dictionary, but I i have his problem: When I add a ...

  1. #1
    Registered User vddking2's Avatar
    Join Date
    Nov 2006
    Location
    Vietnam
    Posts
    12

    Post I have a problem with hash

    I'm programming a hash with alphabetics, use as a dictionary, but I i have his problem:

    When I add a new word after I had a hash with some word, old hash is deleted and it's creat a new hash, but I don't want so, I want it has the same hash because i want to save it:

    And, this is my code:

    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #include <stdlib.h>
    #define B 26
    #define maxlegth 30
     typedef char datatype;
     typedef struct Node
     {
    	 datatype Tu[maxlegth];
    	 datatype Nghia[maxlegth];
    	 Node*Next;
     };
     typedef Node*Position;
     typedef Position Dictionary[B];
     //Thiet ke ham bam
     int H(datatype X[maxlegth])
     {
         int chudau;
         char*s;
         s=strlwr(X);
         chudau=int(s[0])-97;
         return chudau%B;
     }
     //Tao bang bam rong;
     void MakenullSet(Dictionary*D)
     {
          for(int i=0;i<B;i++)
          (*D)[i]=NULL;
     }
     //Kiem tra thanh vien trong bang bam;
     int MemberSet(datatype X[maxlegth],Dictionary D)
     {
         Position P;
         P=D[H(X)];
         int Found=0;
         while((P!=NULL) && (Found!=1))
    				{
    				  //so sanh chuoi
    				if(strcmp(P->Tu,X)==0)
    				  Found=1;
    				else P=P->Next;
    				}
         return Found;
     }
     //Them phan tu vao bang bam
     void InsertSet(datatype X[maxlegth],datatype Y[maxlegth],Dictionary *D)
     {
          int Bucket;
          Position P;
    			  Bucket=H(X);
    			  P=(*D)[Bucket];
    			  (*D)[Bucket]=(Node*)malloc(sizeof(Node));
    
    			   //Khoi tao chuoi
    			   memset((*D)[Bucket]->Tu,'\0',maxlegth);
    			   memset((*D)[Bucket]->Nghia,'\0',maxlegth);
    			   //Chep chuoi
    			   strcpy((*D)[Bucket]->Tu,X);
    			   strcpy((*D)[Bucket]->Nghia,Y);
    
    			  (*D)[Bucket]->Next=P;
     }
     //Nhap du lieu cho bang bam tu ban phim
     void ReadSet(Dictionary*D)
     {
    			   int i;
    			   int n;
    			   datatype X[maxlegth];
    			   datatype Y[maxlegth];
    			   MakenullSet(D);
    			   printf("\n--------------------------- Number of word to add < Number only>: ");
    			   scanf("%d",&n);
    			   for(i=1;i<=n;i++)
    			   {
    				  flushall();
    				 // Nhap chuoi ham gets
    				  printf("\nWord number %d: ",i); gets(X);
    				  printf("\nMeaning: "); gets(Y);
    				  InsertSet(X,Y,D);
    			   }
     }
     //In du lieu ra man hinh
     void PrintSet(Dictionary D)
     {
    			  Position P;
    			  for(int i=0;i<B;i++)
    			  {
    				  P=D[i];
    				  printf("Bucket %c: ",char(i+65));
    				  while(P!=NULL)
    				  {
    						printf("%s",P->Tu);
    						printf(" - ");
    						printf("%s",P->Nghia);
    						P=P->Next;
    				  }
    				  printf("\n");
    			  }    printf("\n");
     }
     void FindSet(datatype F[maxlegth],Dictionary D)
     {
    			Position P;
    			F=strlwr(F);
    			int Found=0;
    			for(int i=0;i<B;i++)
    			  {
    
    				  P=D[i];
    				  while(P!=NULL && Found==0)
    				  {
    						if(strcmp(F,P->Tu)==0)
    						{
    							printf("Meaning: %s",P->Nghia);
    							Found=1;
    						}
    						else
    						{
    							P=P->Next;
    						}
    				  }
    			  }
    			  if(Found==0)
    			  {
    				printf("\nWe don't see this word.");
    			  }
    			  printf("\n");
     }
     void showmenu()
    {
     printf("\n\t-------------------- COMPUTER DICTIONARY -------------------");
     printf("\n[1].	Add WORDS.");
     printf("\n[2].	Find a word.");
     printf("\n[3].	Display all.");
     printf("\n[4]. Save and Close.");
     printf("\n\nEnter Choice: ");
    }
    void prog()
    {
     clrscr();
          int menuchoice;
          Dictionary D;
          datatype X[maxlegth];
          datatype F[maxlegth];
      while(1)
     {
      clrscr();
      showmenu();
      scanf("%d",&menuchoice);
      switch(menuchoice)
      {
       case 1:printf("\n\nAdd content of hash with %d Bucket: \n",B);
    	  ReadSet(&D);
    	  break;
       case 2:flushall();
    	  printf("\nAdd word which you want to find: ");
    	  gets(F);
    	  FindSet(F,D);
    	  getch();
    	  break;
       case 3:printf("\n\nDictionary: \n");
    	  PrintSet(D);
    	  getch();
    	  break;
       case 4:exit(1);
    	  break;
       default:printf("Enter Again");
    	   prog();
    	   break;
      }
     }
    }
     int main()
     {
         clrscr();
         showmenu();
         prog();
         return 0;
     }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What do you mean it deletes the old hash? It's supposed to generate a different hash for each word. That's the whole point of hashing. Oh, and get rid of malloc.h. malloc is included in stdlib.h, as are its related functions.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User vddking2's Avatar
    Join Date
    Nov 2006
    Location
    Vietnam
    Posts
    12
    So, what should I do to have a same hash?

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why do you think you should have the same hash? Give an example. The only time you should end up with the same hash is if you're trying to hash the same value. Or, in the case of a collision, which you generally seek to avoid.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User vddking2's Avatar
    Join Date
    Nov 2006
    Location
    Vietnam
    Posts
    12
    hi, now I knows how I have this problem. I used MakenullSet(D) in ReadSet function, so it deleted my hash ^_^

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    It's supposed to generate a different hash for each word.
    I thought it is something like map with unique key.
    Hash table, otherwise, can has several entries with the same hash value. The point here is to search the specific velue not through the whole array, but only through the part having the same hash value.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you would have read my second post, you'd have seen that your post has already been addressed, even before you posted it.

    The main problem here, is that by "hash", the OP actually meant that their entire hash table was being erased. I assumed they meant that they were trying to get the hash of a word, and then tried to get the hash for a second word, and couldn't figure out why the two were different.
    When I add a new word after I had a hash with some word, old hash is deleted and it's creat a new hash, but I don't want so, I want it has the same hash because i want to save it
    See? That doesn't say anything about the entire table getting nuked. You'd only guess that after reading their final post, where they've already figured out what they're doing wrong.

    As to hash tables having several entries with the same hash value, I already covered that in my second post. But that's not what they were talking about anyway, apparently.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Code:
     //Thiet ke ham bam
     int H(datatype X[maxlegth])
     {
         int chudau;
         char*s;
         s=strlwr(X);
         chudau=int(s[0])-97;
         return chudau%B;
     }
    Not a very good hash function there, is it.



    Looks like a strange dialect of C. Didn't know you could write Vietnamese in the Roman alphabet.
    Last edited by jafet; 11-21-2006 at 07:27 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  9. #9
    Registered User vddking2's Avatar
    Join Date
    Nov 2006
    Location
    Vietnam
    Posts
    12
    I could write Vienamese with Roman Alphabet but I order them with English, so, must use 26 character.

    About you, what's hash function do you think best?

  10. #10
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Letting the entire hash depend on only the first character will cause problems. Say I input "ada", "abc" and "algol". You would hash all of them to the same value.

    You could try en.wikipedia.org/wiki/Hash_table for better types of functions (maybe they have one in Vietnamese too). But if this is for some homework assignment or something where you're not supposed to care, I guess it doesn't really matter.

    More importantly, get rid of all that nonstandard junk in your code. Replace getc() with getchar(), remove <malloc.h>, use fflush instead of flushall(), etc.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  2. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  3. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 09:37 AM
  4. Problem with Hash Table Linear Probing
    By kirby1024 in forum C Programming
    Replies: 5
    Last Post: 10-23-2002, 07:03 AM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21