单链表有关问题：输入一串字符，要求分别统计出各个字符出现的次数

单链表问题：输入一串字符，要求分别统计出各个字符出现的次数
该如何实现这个问题啊，我知道用单链表能够解决，但是还有没有最优的方法，求各个指点指点
[解决办法]
为啥要用链表？

如果只是ASCII字符的话，开一个256大的数组统计就OK了
[解决办法]
要么用可变长度数组？关键是长度不定
[解决办法]
1#说得好
[解决办法]
学习来的
[解决办法]
难道你想用map?
[解决办法]
用哈希表嘛，干嘛要用链表
开一个127个元素的数组，每个字符转换成整型值就哈希成数组元素的位置，然后每扫描一个字符，就去该字母在数组中对应位置加1，最后，遍历一遍数组就知道了噻

[解决办法]
用map表，以字符本身为索引，节点为出现的次数，

typedef std::map<char,int> CharMap;
CharMap g_map;
void Countchar(char ch)
{
CharMap::iterator iter=  g_map.find(ch);
if(iter==g_map.end())
g_map[ch]=1;
else
iter->second+=1;
}

void OutCount()
{
CharMap::iterator iterbeg=  g_map.begin();
CharMap::iterator iterend=  g_map.end();
CharMap::iterator iter=  g_map.begin();
for(iter=iterbeg;iter!=iterend;iter++)
{
TRACE("字符%c出现%d次\r\n",iter->first,iter->second);
}
}

void Test()
{
char *ptest="1111111aaadddddddddffff";
int len=strlen(ptest);
for(int i=0;i<len;i++)
{
//遍历统计每个字符
Countchar(ptest[i]);
}
//输出统计结果
OutCount();
}

运行结果：
字符1出现7次
字符a出现3次
字符d出现9次
字符f出现4次
[解决办法]

引用:

用哈希表嘛，干嘛要用链表
开一个127个元素的数组，每个字符转换成整型值就哈希成数组元素的位置，然后每扫描一个字符，就去该字母在数组中对应位置加1，最后，遍历一遍数组就知道了噻

为什么127？256不最好么，空间又不大。省得查找了。
[解决办法]
字符最大的ASCLL码是127
[解决办法]
能用数组还是用数组吧，链表需要扫描复杂度是O(n)，n=字母个数,数组复杂度是O(1)。而且链表还要消耗指针存储空间
[解决办法]
127大小的数组不是很大的，这点空间算啥啊。
[解决办法]

引用:

为啥要用链表？

如果只是ASCII字符的话，开一个256大的数组统计就OK了

++

引用:

一楼的：oo(为了名副其实，努力学习oo技术)
说的用数组实现，能够解决。开辟的空间上有点不太确定，我用单链表实现就是考虑到数组空间的问题
我的想法是，每次接收一个字符时，从链表的头部检查看看是否有相应的字符出现过，如果有的话对应的计数器就加1，没有的话，把该元素加入到链表中
7楼的：dahuaixiaohuai
提到map,看来不错，以前没用过，学习啦，

LZ没明白1L的意思

如果没有中文字符,那么256个int类型的空间就可以实现高效算法,绝对比链表快

#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
        //charNum[0]~charNum[255]分别对应ASCII码中各字符出现的次数 在输入字符串之前都是0
int charNum[256] = {0};
char *str = "babshasgfsfdjkfghfkldhh234gkrthggh4y682378462tej";
char *c = str;
while(*(c++))charNum[*c]++;//*c做下标是亮点 这样可以快速定位 绝对比链表快

        //打印结果
for(int i = 0; i<256; i++)if(0!=charNum[i])printf("%c %d\n", i, charNum[i]); 
 
return 0;
}

这就是常说的位图法 而256个ASCII字符用不了多少空间 换取的时间却不少 绝对值

[解决办法]
我是观看的
[解决办法]
人家就是想要用链表做，怎么有那么多其他的建议呢？？？？？？？？
[解决办法]
数组就可以实现。无需怀疑长度[code=C/C#include] <iostream>

using namespace std;

int main()
{
// 统计ASCII字符出现次数
int count[257 = {0};

char ch;
//从键盘不断输入，直到回车
while ( (ch = getchar()) != '\n')
{
count[ch - 0]++;
}

for (int i = 0; i < 257; i++)
{
if( count[i] )
cout << (char)i << ":" << count[i] << endl;
}
return 0;
}[/code]
[解决办法]

#include <iostream> 
using namespace std; 
int main() 
{ 
// 统计ASCII字符出现次数 
int count[257 = {0}; 

char ch; 
//从键盘不断输入，直到回车 
while ( (ch = getchar()) != '\n') 
{ 
count[ch - 0]++; 
} 

for (int i = 0; i < 257; i++) 
{ 
if( count[i] ) 
cout < < (char)i < < ":" < < count[i] < < endl; 
} 
return 0; 
}

查看更多 下一篇