how find a char most use in a stirng ?

[mail.zhf]

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

[osmium]

"mail.zhf" writes:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be some
obnoxious, convoluted way to do it with the STL too.

[Zara]

osmium wrote:

"mail.zhf" writes:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be

some obnoxious, convoluted way to do it with the STL too.


Yes. Look at this beutiful piece of code:
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef string::iterator s_iter;

// for counting chars
typedef map<char,size_t> charSet;
typedef charSet::iterator cs_iter;

// for ordering the results
typedef multimap<size_t,char,greater<size_t> > countSet;
typedef countSet::iterator cnt_iter;

// functor that counts chars
class countChar
{
private:
charSet& cs;
public:
countChar(charSet& chs):cs(chs) {}

void operator()(char c)
{
size_t count=1;
cs_iter csi=cs.find(c);
if (csi!=cs.end())
{
count=csi->second+1;
cs.erase(csi);
}
cs.insert(make_pair(c,count));
}
};

int main()
{
string str;
cout<<"Input your string: ";
cin>>str;

if (str.empty())
{
cout<<"This string is empty!!";
return -1;
}

charSet cs;
for_each (str.begin(),str.end(),countChar(cs));

countSet cnts;
for (cs_iter csi=cs.begin();csi!=cs.end();++csi)
{
cnts.insert(make_pair(csi->second,csi->first));
}

cout<<"The character(s) most used is/are:";

cnt_iter ci=cnts.begin();
size_t repetitions=ci->first;
for (;(ci!=cnts.end())&&(ci->first==repetitions);++ci)
{
cout<<' '<<ci->second;
}

}

Not much thought dedicated to it, I supose it shold be easy to obfuscate
it a lot more.

BTW, out is: s

[Gianni Mariani]

mail.zhf wrote:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Your question is a little ambiguous.

If you are asking for the most frequently used character in a string,
the answer should be 's'.

What should be the output for this string:

"abc"

and this one

"cba"

and this one

"..."

and this one

""

and this one

"Aabbc"

?

[akarl]

mail.zhf wrote:

if have two char use equality, out first.

???

[Dweia]

akarl wrote:

mail.zhf wrote:

if have two char use equality, out first.

???

He's saying, if there are ultiple characters with equal frequency, e.g.
aabbcc, it returns the one which occurs first in the string, in the
above case, a.

[mail.zhf]

the method is best but i don't use stl, i want use c

"Zara" <yo****@terra.es>
??????:8H***********************@telenews.teleline .es...

osmium wrote:

"mail.zhf" writes:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

Fill this array:

char cnt[26];

Then see which entry in the array has the largest value. There may be

some

obnoxious, convoluted way to do it with the STL too.

Yes. Look at this beutiful piece of code:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef string::iterator s_iter;

// for counting chars
typedef map<char,size_t> charSet;
typedef charSet::iterator cs_iter;

// for ordering the results
typedef multimap<size_t,char,greater<size_t> > countSet;
typedef countSet::iterator cnt_iter;

// functor that counts chars
class countChar
{
private:
charSet& cs;
public:
countChar(charSet& chs):cs(chs) {}

void operator()(char c)
{
size_t count=1;
cs_iter csi=cs.find(c);
if (csi!=cs.end())
{
count=csi->second+1;
cs.erase(csi);
}
cs.insert(make_pair(c,count));
}
};

int main()
{
string str;
cout<<"Input your string: ";
cin>>str;

if (str.empty())
{
cout<<"This string is empty!!";
return -1;
}

charSet cs;
for_each (str.begin(),str.end(),countChar(cs));

countSet cnts;
for (cs_iter csi=cs.begin();csi!=cs.end();++csi)
{
cnts.insert(make_pair(csi->second,csi->first));
}

cout<<"The character(s) most used is/are:";

cnt_iter ci=cnts.begin();
size_t repetitions=ci->first;
for (;(ci!=cnts.end())&&(ci->first==repetitions);++ci)
{
cout<<' '<<ci->second;
}

}

Not much thought dedicated to it, I supose it shold be easy to obfuscate
it a lot more.

BTW, out is: s

[Zara]

mail.zhf wrote:

the method is best but i don't use stl, i want use c

Then, why do you ask on comp.lang.c++? You should ask on comp.lang.c

[Gernot Frisch]

"mail.zhf" <ma******@163.com> schrieb im Newsbeitrag
news:df***********@mail.cn99.com...

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

[msalters]

Gernot Frisch schreef:

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

How is counts['a'] initialized? Is it default-constructed or set to
int(0)?

HTH,
Michiel Salters

[Maxim Yegorushkin]

mail.zhf wrote:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

There are 3 f's and 4 s's in the string. Shouldn't it output s?

char most_used(char const* s)
{
unsigned freq[0x100] = {};
char c = 0;
for(; *s; ++s)
if(++freq[static_cast<unsigned>(*s)] >
freq[static_cast<unsigned>(c)])
c = *s;
return c;
}

If you change > to >= it will output the last found most used
charecter.

[Marc Mutz]

Gernot Frisch wrote:
<snip>

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC]*++;
}
return**counts.front().first;*//*or*back??
}

<snip>

Yeah, right :)

Try
return counts.empty()
? '\0'
: min_element(counts.begin(),counts.end())->first;
instead.

Marc

[Karl Heinz Buchegger]

Marc Mutz wrote:

Gernot Frisch wrote:
<snip>

char MostUsed(const char* pC)
{
std::map<char, int> counts;
while(*pC!='\0')
{
counts[*pC] ++;
}
return *counts.front().first; // or back??
}

<snip>

Yeah, right :)

Try
return counts.empty()
? '\0'
: min_element(counts.begin(),counts.end())->first;
instead.

I don't think this will work.
This will return the map element with the minimum *key*,
not with the minimum count.

You will need to use max_element (as the name MostUsed implies)
and have to use the predicate version of it, to search for the
maximum in the counts.

--
Karl Heinz Buchegger
kb******@gascad.at

[akarl]

mail.zhf wrote:

if have two char use equality, out first.
example:

char str[] = "gbdfssdffss";

out is: f.

I'm feeling generous today, so here's a solution in C:

#define SIZE 256 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

static int counts[SIZE]; /* counts[c + OFFSET] is the frequency of
char c */

/* most_common(s) returns the first character in the string s with
the highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(char s[])
{
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
k++;
}
result = s[0];
k = 0;
while (s[k] != '\0') {
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = (char) s[k];
}
k++;
}
return result;
}
August

[akarl]

akarl wrote:

#define SIZE 256 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

static int counts[SIZE]; /* counts[c + OFFSET] is the frequency of
char c */

/* most_common(s) returns the first character in the string s with
the highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(char s[])
{
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
k++;
}
result = s[0];
k = 0;
while (s[k] != '\0') {
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = (char) s[k];
....and of course, this cast should be removed.
}
k++;
}
return result;
}
August

[Maxim Yegorushkin]

akarl wrote:

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

[akarl]

Maxim Yegorushkin wrote:

akarl wrote:

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower). Can you think of any sensible
return value for an empty string?

Here is the modified version:

#include <assert.h>

#define SIZE 0x100 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

/* most_common(s) returns the first character in the string s with the
highest frequency.

Precondition: s[0] != '\0'

Example: most_common("Alibaba") returns 'b'.
*/

char most_common(const char s[])
{
int counts[SIZE]; /* counts[c + OFFSET] is the frequency of char c */
int k;
char result;

assert(s[0] != '\0');
for (k = 0; k < SIZE; k++) { counts[k] = 0; }
result = s[0];
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = s[k];
}
k++;
}
return result;
}
August

[Maxim Yegorushkin]

akarl wrote:

Maxim Yegorushkin wrote:

akarl wrote:

I'm feeling generous today, so here's a solution in C:

There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

Mine is not.
Can you think of any sensible return value for an empty string?

An empty c-string contains a single character '\0', which is the most
used character in this case.

[akarl]

Maxim Yegorushkin wrote:

akarl wrote:

Maxim Yegorushkin wrote:

akarl wrote:

I'm feeling generous today, so here's a solution in C:
There is a number of problems in the solution:

1) The function is not reentrant.
2) It uses 2 loops instead of 1.
3) It operates on char[] rather than char const[] and does not handle
empty strings.
Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

The allocation of the array on the stack requires some extra instructions.
Mine is not.

Can you think of any sensible return value for an empty string?

An empty c-string contains a single character '\0', which is the most
used character in this case.

You may argue whether '\0' is really a *part* of the string or a string
delimiter, but as the behavior of strchr when given an empty string is
to return a pointer to the '\0' character I tend to agree with you.

Here is the final version:

#define SIZE 0x100 /* number of values a char can assume */
#define OFFSET (SIZE / 2)

/*
* most_common(s) returns the first character in the string s with the
* highest frequency.
*
* Example: most_common("Alibaba") returns 'b'.
*/

char most_common(const char s[])
{
int counts[SIZE]; /* counts[c + OFFSET] is the frequency of char c */
int k;
char result;

for (k = 0; k < SIZE; k++) { counts[k] = 0; }
result = s[0];
k = 0;
while (s[k] != '\0') {
counts[(int) s[k] + OFFSET]++;
if (counts[(int) s[k] + OFFSET] > counts[(int) result + OFFSET]) {
result = s[k];
}
k++;
}
return result;
}
August

[Maxim Yegorushkin]

akarl wrote:

Maxim Yegorushkin wrote:

[]

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

The allocation of the array on the stack requires some extra instructions.

Yes, this instruction on x86 is add esp, 0x100.

[akarl]

Maxim Yegorushkin wrote:

akarl wrote:

Maxim Yegorushkin wrote:

[]

Thanks for your comments. Code reviewing is indispensable. Whether the
function should be thread-safe or not depends on the requirements (the
thread safe version is slightly slower).

The allocation of the array on the stack requires some extra instructions.

Yes, this instruction on x86 is add esp, 0x100.

So you see no disadvantages with large local variables?

August

[Maxim Yegorushkin]

akarl wrote:

Maxim Yegorushkin wrote:

akarl wrote:

Maxim Yegorushkin wrote:

[]

>Thanks for your comments. Code reviewing is indispensable. Whether the
>function should be thread-safe or not depends on the requirements (the
>thread safe version is slightly slower).

The allocation of the array on the stack requires some extra instructions.

Yes, this instruction on x86 is add esp, 0x100.

My mistake, it's sub esp, 0x100, because the stack grows down.
So you see no disadvantages with large local variables?

Stack allocation is convenient. The problem with large arrays on stack
is that if you are not careful enough you can exhaust it and get a
SIGSEGV.

#include <cstdlib>
#include <iostream>
using namespace std;

char SortStr(char* pstr);
template<typename T> void Sort(T* p, int len, bool bType);

int main(int argc, char *argv[])
{
char pstr[] = "aeebbcf";

//Sort(pstr, strlen(pstr), true);

//cout<<endl;
cout<<SortStr(pstr)<<endl;
//cout<<pstr<<endl;
cout<<"Origin string is:"<<pstr<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

char SortStr(char* pstr)
{
assert(pstr);
const int len = strlen(pstr);
char ch = ' ';
char str[len + 1];
memset(str, ' ', sizeof(str));
bool bExist = false;
int iPos[len];
int iPosTmp[len];
int i=0, j=0;

for(i=0; i<len; i++)
{
iPos[i] = iPosTmp[i] = 1;
}

for(i=0; i<len; i++)
{
ch = pstr[i];
for(j=0; j<len; j++)
{
if(ch == str[j])
{
bExist = true;
iPos[i]++;
}
}
if( !bExist )
{
str[i] = ch;
}

bExist = false;
}

cout<<"filtrate string is:"<<str<<endl;
for(i=0; i<len; i++)
{
iPosTmp[i] = iPos[i];
}

Sort(iPos, len, false);

int pos = iPos[0];

cout<<"max number is:"<<pos<<endl;

for(i=0; i<len; i++)
{
if(pos == iPosTmp[i])
{
pos = i;
break;
}
}

return str[pos-1];
}

template<typename T> void Sort(T* p, int len, bool bType)
{
T tmp;

for(int i=0; i<len; i++)
{
for(int j=i+1; j<len; j++)
{
if( bType ) //ture is min to max
{ /*
if(p[i] > p[j])
{
tmp = p[i];
p[i] = p[j];
p[j] = tmp;
}
*/
if(*(p+i) > *(p+j))
{
tmp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = tmp;
}

}
else
{
if(*(p+i) < *(p+j))
{
tmp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = tmp;
}
}
}
}
}