Thread: how to solve this question?

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    168

    how to solve this question?

    To analysing a string, then finding the char whose counts of appearing in string is max.
    how to solve this question?

    for example:
    Code:
    char *string = "ab---ebbbe";
    the appearing counts of char 'b'  is max. It is 4.
    I now think two method.
    one is :
    Code:
    sort(string);
    statisticalCountofChar(string);
    the other is
    Code:
    char *individualofChar;
    for ( string )
    {
          for ( *individualofChar )
          {
                caculateCountofChar();
          }
    }
    is there even more better method to solve this question?
    how to solve this question using HASHING TABLE? how to design hashing function ?

  2. #2
    Registered User
    Join Date
    Feb 2010
    Posts
    57

    Re: how to solve this question?

    In hash table you can solve this requirement easily.

    You can have some algorithm to convert the string key to some index value.

    And you can pass the strings to that algorithm.

    If you found that string you can increment the count of the characters as value of that index in hash array.

    Then finally your hash should be like this.
    Ex:
    If you have ab---bbbc
    hash[a] = 1
    hash[b]= 4
    hash[c]=1

    If you want b count you can just print the value of hash[b].

    Reference for HASH algorithm : http://www.burtleburtle.net/bob/hash/doobs.html
    Last edited by sganesh; 03-01-2010 at 03:38 AM. Reason: edit some more text

  3. #3
    Registered User
    Join Date
    Jan 2010
    Location
    Germany, Hannover
    Posts
    15
    safe&simple( should work for any non empty string :-) :
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char *argv[])
    {
      int count[256]={0},i=0;
      int max=0;
      char maxchar;
      char* pstr="abce";
         
      do {
        count[*pstr]+=1;
        if (count[*pstr]>max){
           maxchar=*pstr;
           max=count[*pstr];
          }
      } while (*++pstr);
      printf("maxchar %c , count %d \n",maxchar,max);
      system("PAUSE");	
      return 0;
    }

  4. #4
    Registered User
    Join Date
    Aug 2009
    Posts
    168
    Quote Originally Posted by sganesh View Post
    In hash table you can solve this requirement easily.

    You can have some algorithm to convert the string key to some index value.

    And you can pass the strings to that algorithm.

    If you found that string you can increment the count of the characters as value of that index in hash array.

    Then finally your hash should be like this.
    Ex:
    If you have ab---bbbc
    hash[a] = 1
    hash[b]= 4
    hash[c]=1

    If you want b count you can just print the value of hash[b].

    Reference for HASH algorithm : A Hash Function for Hash Table Lookup
    how to design hash function?

  5. #5
    Registered User
    Join Date
    Feb 2010
    Posts
    57

    Thumbs up Re: how to solve this question?

    Did you go through the link which I have given to you?
    Actually, that link has more hash functions.

    If that link is very hard to read try these URL's:

    http://www.cse.yorku.ca/~oz/hash.html
    How to write a hash function in C? - Stack Overflow
    Eternally Confuzzled - Hash Table Tutorial
    A Hash Function for Hash Table Lookup

    Try the sample Hash function from K&R C Book:

    Code:
    #define HASHSIZE 101
    unsigned hash(char *s)
    {
            unsigned hashval;
            for(hashval=0;*s!='\0';s++)
                    hashval=*s+31*hashval;
            return hashval%HASHSIZE;
    }
    You need keep some points while writing hash function,
    * It should not have the collision(same key for different strings). If it has it should have the solution.
    * And it should always return same key for the same inputs.

    You can also develop your own hash algorithm for hash function.

    I think After look on those URL's you will get a clear picture about it.
    Last edited by sganesh; 03-02-2010 at 12:24 AM.

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Why bother doing that? When the limits of char are well known? You'll only ever have CHAR_MAX + -CHAR_MIN + 1 possible values in a "char". You can create a perfect has for that.

    Code:
    zac@neux:code (0) $ gcc -funsigned-char hash.c -o hash
    zac@neux:code (0) $ ./hash 
    Accepting 256 possible values
    Test
    character 'T' at position 84
    character 'e' at position 101
    character 's' at position 115
    character 't' at position 116
    character '
    ' at position 10
    zac@neux:code (0) $ gcc -fsigned-char hash.c -o hash
    zac@neux:code (0) $ ./hash 
    Accepting 256 possible values
    Test
    character 'T' at position 84
    character 'e' at position 101
    character 's' at position 115
    character 't' at position 116
    character '
    ' at position 10
    zac@neux:code (0) $ cat hash.c 
    #include <limits.h>
    #include <stdio.h>
    
    int main(void)
    {
       int table[CHAR_MAX + -CHAR_MIN + 1];
       char example[32];
       char * ch = NULL;
       int pos = 0;
    
       printf("Accepting %lu possible values\n", sizeof(table) / sizeof(table[0]));
    
       fgets(example, sizeof example, stdin);
       for(ch = example; *ch; ch++)
       {
          pos = *ch;
          if(pos < 0)
             pos += -CHAR_MIN;
          printf("character '%c' at position %d\n", *ch, pos);
       }
    
       return 0;
    }
    Or something.
    Last edited by zacs7; 03-02-2010 at 12:59 AM.

  7. #7
    Registered User
    Join Date
    Aug 2009
    Posts
    168
    Quote Originally Posted by sganesh View Post
    Did you go through the link which I have given to you?
    Actually, that link has more hash functions.

    If that link is very hard to read try these URL's:

    http://www.cse.yorku.ca/~oz/hash.html
    How to write a hash function in C? - Stack Overflow
    Eternally Confuzzled - Hash Table Tutorial
    A Hash Function for Hash Table Lookup

    Try the sample Hash function from K&R C Book:

    Code:
    #define HASHSIZE 101
    unsigned hash(char *s)
    {
            unsigned hashval;
            for(hashval=0;*s!='\0';s++)
                    hashval=*s+31*hashval;
            return hashval%HASHSIZE;
    }
    You need keep some points while writing hash function,
    * It should not have the collision(same key for different strings). If it has it should have the solution.
    * And it should always return same key for the same inputs.

    You can also develop your own hash algorithm for hash function.

    I think After look on those URL's you will get a clear picture about it.

    I see !
    Thank you very much!

  8. #8
    Registered User
    Join Date
    Aug 2009
    Posts
    168
    Quote Originally Posted by zacs7 View Post
    Why bother doing that? When the limits of char are well known? You'll only ever have CHAR_MAX + -CHAR_MIN + 1 possible values in a "char". You can create a perfect has for that.

    Code:
    zac@neux:code (0) $ gcc -funsigned-char hash.c -o hash
    zac@neux:code (0) $ ./hash 
    Accepting 256 possible values
    Test
    character 'T' at position 84
    character 'e' at position 101
    character 's' at position 115
    character 't' at position 116
    character '
    ' at position 10
    zac@neux:code (0) $ gcc -fsigned-char hash.c -o hash
    zac@neux:code (0) $ ./hash 
    Accepting 256 possible values
    Test
    character 'T' at position 84
    character 'e' at position 101
    character 's' at position 115
    character 't' at position 116
    character '
    ' at position 10
    zac@neux:code (0) $ cat hash.c 
    #include <limits.h>
    #include <stdio.h>
    
    int main(void)
    {
       int table[CHAR_MAX + -CHAR_MIN + 1];
       char example[32];
       char * ch = NULL;
       int pos = 0;
    
       printf("Accepting %lu possible values\n", sizeof(table) / sizeof(table[0]));
    
       fgets(example, sizeof example, stdin);
       for(ch = example; *ch; ch++)
       {
          pos = *ch;
          if(pos < 0)
             pos += -CHAR_MIN;
          printf("character '%c' at position %d\n", *ch, pos);
       }
    
       return 0;
    }
    Or something.
    thanks for your answer! I do understand

  9. #9
    Registered User
    Join Date
    Aug 2009
    Posts
    168
    Quote Originally Posted by sganesh View Post
    Code:
    #define HASHSIZE 101
    unsigned hash(char *s)
    {
            unsigned hashval;
            for(hashval=0;*s!='\0';s++)
                    hashval=*s+31*hashval;
            return hashval%HASHSIZE;
    }
    how does "31" come?
    use "32" or "33", is it feasible ?

  10. #10
    Registered User
    Join Date
    Feb 2010
    Posts
    57

    Re how to solve this question?

    Actually, K&R used 31. Because it is an odd prime number. And in ASCII table up-to 31 characters are non-printable character.

    And it will give less no of collisions.

    And note that expression won't give result as 1-31 value for any character.

    And refer this URL it is very interesting,
    Why do hash functions use prime numbers? « Computing Life

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Newbie question, C #
    By mate222 in forum C# Programming
    Replies: 4
    Last Post: 12-01-2009, 06:24 AM
  2. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 12:14 PM
  3. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 04:22 AM
  4. Question type program for beginners
    By Kirdra in forum C++ Programming
    Replies: 7
    Last Post: 09-15-2002, 05:10 AM
  5. what does this warningmean???
    By kreyes in forum C Programming
    Replies: 5
    Last Post: 03-04-2002, 07:53 AM