问个算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个算法题

问个算法题# JobHunting - 待字闺中

j*y2011-12-29 08:12

1 楼

一个pre-screen的问题，感觉一点思路都没有啊：
write a library function in C that takes a string and a “FILE *” as
parameters, assuming the string consists of words separated by a single
white space, and prints into the stream the words in descending order sorted
by the number of times they appear in the string.
For example an input string of “a b b” would generate the following output
into the FILE:
b : 2
a : 1
请帮帮忙，谢谢（最好能给出完整的程序或者程序的基本骨架）。

q*c2011-12-29 08:12

2 楼

If the string consists of white space separated letters, use bit map; if
they are words use hash table. But I suppose it's the former case because
for hashtable in C you would have to use some external library.

r*t2011-12-29 08:12

3 楼

建议改下标题，这个不是算法题，就是个 C 题

v*a2011-12-29 08:12

4 楼

很直白吧，统计个数
这就写一个，要马上交吗？

sorted
output

【在 j***y 的大作中提到】

: 一个pre-screen的问题，感觉一点思路都没有啊：
: write a library function in C that takes a string and a “FILE *” as
: parameters, assuming the string consists of words separated by a single
: white space, and prints into the stream the words in descending order sorted
: by the number of times they appear in the string.
: For example an input string of “a b b” would generate the following output
: into the FILE:
: b : 2
: a : 1
: 请帮帮忙，谢谢（最好能给出完整的程序或者程序的基本骨架）。

q*x2011-12-29 08:12

5 楼

id送人了？

sorted
output

【在 j***y 的大作中提到】

j*y2011-12-29 08:12

6 楼

是啊，等着交货呢。请帮帮忙，谢谢。

【在 v***a 的大作中提到】

: 很直白吧，统计个数
: 这就写一个，要马上交吗？
:
: sorted
: output

j*y2011-12-29 08:12

7 楼

没有啊，我一直用这个id的，有什么问题吗？

【在 q****x 的大作中提到】

: id送人了？
:
: sorted
: output

q*x2011-12-29 08:12

8 楼

印象中这个id算法很厉害。这题太简单。

【在 j***y 的大作中提到】

:
: 没有啊，我一直用这个id的，有什么问题吗？

j*y2011-12-29 08:12

9 楼

哈，我的算法和数据结构烂得一塌糊涂。这题简单吗？能否大概给个程序框架？我感觉
一点思路都没有啊。

【在 q****x 的大作中提到】

: 印象中这个id算法很厉害。这题太简单。

q*x2011-12-29 08:12

10 楼

那我记错了。
就是计数、排序、放到文件里。

【在 j***y 的大作中提到】

:
: 哈，我的算法和数据结构烂得一塌糊涂。这题简单吗？能否大概给个程序框架？我感觉
: 一点思路都没有啊。

v*a2011-12-29 08:12

11 楼

第一次写 c 程序，不保证正确，请自己 debug
程序假设单词是 a to z 组成
用的 bst counting, 然后导出来 qsort
#include
#include
struct _node;
typedef struct _node {
int cc;
char c;
struct _node * n[26];
struct _node * fa;
} node;
void addToTree(node * root, node * r, const char * p1, const char * p2) {
int t;
int i;
if (p1 == p2) {
if (r->cc == 0) root->cc++;
r->cc++;
return;
}
t = (*p1) - (int)'a';
if (r->n[t] == NULL) {
r->n[t] = (node *)malloc(sizeof(node));
r->n[t]->cc = 0;
r->n[t]->fa = r;
r->n[t]->c = (*p1);
for (i = 0; i < 26; i++) r->n[t]->n[i] = NULL;
}
addToTree(root, r->n[t], p1 + 1, p2);
};
void moveAll(node ** all, node * r, int * index) {
int i;
if (r->cc > 0) {
all[*index] = r;
(*index)++;
}
for (i = 0; i < 26; i++) if (r->n[i] != NULL)
moveAll(all, r->n[i], index);
};
int nodeCmp (const void * a, const void * b) {
return ( (*((node**)b))->cc - (*((node**)a))->cc );
}
void freeTree( node * r ) {
int i;
for (i = 0; i < 26; i++) if (r->n[i] != NULL) freeTree(r->n[i]);
free(r);
}
void counting(const char * str, FILE *fp) {
const char * p1 = str;
const char * p2;
int i, j, k;
int index;
char * tmpStr;
node * root;
node * t1;
node ** all;
if (fp == NULL) return;
root = (node*)malloc(sizeof(node));
root->cc = 0;
root->fa = NULL;
root->c = 0;
for (i = 0; i < 26; i++) root->n[i] = NULL;
while ((*p1) == ' ') p1++;
if (*p1 == '\0') { return; }
p2 = p1;
while (p2 != '\0') {
p2++;
if (*p2 == ' ' || *p2 == '\0') {
addToTree(root, root, p1, p2);
p1 = p2;
while ((*p1) == ' ') p1++;
if (*p1 == '\0') break;
p2 = p1;
}
}
all = (node **)malloc( (root->cc + 1) * sizeof(node) );
index = 0;
moveAll(all, root, &index);
qsort(all + 1, index - 1, sizeof(node *), nodeCmp);
for (i = 1; i < index; i++) {
j = 0;
t1 = all[i];
while (t1->fa != NULL) {
t1 = t1->fa;
j++;
}
tmpStr = (char *)malloc((j + 1) * sizeof(char));
tmpStr[j] = '\0';
t1 = all[i];
k = j - 1;
while (t1->fa != NULL) {
tmpStr[k--] = t1->c;
t1 = t1->fa;
}
fprintf(fp, "%s\t: %d\n", tmpStr, all[i]->cc);
free(tmpStr);
tmpStr = NULL;
}
free(all);
freeTree(root);
fprintf(fp, "End\n");
};
int main() {
const char * targetStr = "aa bb bb bc bc bc ad ad ad ad ad aaa";
FILE *fp;
fp = fopen("test.out", "w");
if (fp == NULL) {
fprintf(stderr, "File open error!\n");
exit(1);
};
counting(targetStr, fp);
fclose(fp);
return 0;
}

k*t2011-12-29 08:12

12 楼

也来凑个热闹。主要是练练trie。
花了些时间才调通:( 谁帮忙给Review一下？谢了。
运行结果：
ad: 5
bc: 3
bb: 2
aaa: 1
aa: 1
源码：
#include
#include
using namespace std;
struct Node {
int cnt;
char c;
struct Node *n[26];
char *p; // to the 1st occurrence in the original input string
};
#define idx(x) (x-'a')
void add2trie (Node *r, char *p1, char *p2) {
char *p; Node *cur=r; Node *n;
p=p1;
cur=r;
while (p!=p2 && cur->n[idx(*p)]) {cur=cur->n[idx(*p)]; ++p;}
if (p==p2) { cur->cnt++; return; }
while (p!=p2) {
Node *n = (Node *)malloc(sizeof(Node));
n->c = *p; n->cnt=0; cur->n[idx(*p)]=n;
for (int i=0;i<26;i++) n->n[i]=NULL;
p++; cur=n;
}
cur->cnt++; cur->p=p1;
}
void add2vec (vector &v, Node *n) {
if (n->cnt!=0) v.push_back(n);
for (int i=0;i<26;i++) {
if (!n->n[i]) continue;
add2vec(v, n->n[i]);
}
}
bool cntcmp (Node * x, Node * y) {
return (x->cnt >= y->cnt);
}
void counting (char *a) {
char *p1, *p2;
vector v;
Node *r=NULL;
if (!a || !*a) return;
// init the trie
r = (Node *)malloc(sizeof(Node));
r->c=0; r->cnt=0; r->p=NULL;
for (int i=0;i<26;i++) r->n[i]=NULL;
// find words in the input string and add to the trie
p1 = a-1;
while(*(++p1)) {
if (*p1==' ') continue;
p2=p1+1;
while(*p2!=' ' && *p2!='\0') p2++;
add2trie(r, p1, p2);
if (!*p2) break;
p1=p2;
}
// push strings to a vector for sorting, and sort it
add2vec(v, r);
sort(v.begin(), v.end(), cntcmp);
// print out
for (unsigned int i=0; iNode *n = v[i]; char *p;
p=n->p;
while(*p!=' ' && *p!='\0') printf("%c", *(p++));
printf(": %d\n", v[i]->cnt);
}
}
int main() {
char targetStr[100] = "aa bb bb bc bc bc ad ad ad ad ad aaa";
counting(targetStr);
return 0;
}

sorted
output

【在 j***y 的大作中提到】

j*y2011-12-29 08:12

13 楼

什么是bitmap啊？没听过这样的数据结构？可否稍微详细介绍一些？
我的想法是如果是单个letter的case，打算用类似下面的方法解决：
int c[26] = {0};
char *pIn = strIn;
while (*pIn != 0 && *pIn != ' ') {
++c[*pIn];
++pIn;
}
/* how to sort the array c[26] and remember the original index? */
排序之后怎样知道某个整数对应的是哪个character的count呢？这个还没有想好。请指
教。
如果不是单个letter的case，准备用map解决，可行吗？

【在 q********c 的大作中提到】

: If the string consists of white space separated letters, use bit map; if
: they are words use hash table. But I suppose it's the former case because
: for hashtable in C you would have to use some external library.
:

b*c2011-12-29 08:12

14 楼

bitmap??
用map
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
map