# Thread: how to solve this question?

1. ## 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. ## 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

3. 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. Originally Posted by sganesh
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. ## 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.

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.

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

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

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. Originally Posted by zacs7
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.

9. Originally Posted by sganesh
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. ## 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