九度OJ 1199：找位置 （计数）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：2083

解决：1010

题目描述：

对给定的一个字符串，找出有重复的字符，并给出其位置，如：abcaaAB12ab12
输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。

输入：

输入包括一个由字母和数字组成的字符串，其长度不超过100。

输出：

可能有多组测试数据，对于每组数据，
按照样例输出的格式将字符出现的位置标出。

样例输入：

abcaaAB12ab12

样例输出：

a:0,a:3,a:4,a:9
b:1,b:10
1:7,1:11
2:8,2:12

提示：

1、下标从0开始。
2、相同的字母在一行表示出其出现过的位置。

来源：

2005年华中科技大学计算机保研机试真题

代码：

找个数组或建个结构体计数。

代码：

#include <stdio.h>
#include <stdlib.h>
 
#define N 100
 
struct node {
    char c;
    int count;
    int index[N];
};
 
void print(struct node *p)
{
    int i;
    for (i=0; i<p->count-1; i++)
        printf("%c:%d,", p->c, p->index[i]);
    printf("%c:%d
", p->c, p->index[i]);
}
 
int cmp(const void *a, const void *b)
{
    struct node *c = (struct node *)a;
    struct node *d = (struct node *)b;
    return c->index[0] - d->index[0];
}
 
int main(void)
{
    int i;
    char s[N+1];
    struct node a[128];
 
    while (scanf("%s", s) != EOF)
    {
        for (i=0; i<128; i++)
        {
            a[i].c = i;
            a[i].count = 0;
            a[i].index[0] = -1;
        }
        for (i=0; s[i]; i++)
        {
            a[s[i]].index[a[s[i]].count] = i;
            a[s[i]].count ++;
        }
        qsort(a, 128, sizeof(a[0]), cmp);
        for (i=0; i<128; i++)
        {
            if (a[i].count > 1)
                print(&a[i]);
        }
    }
 
    return 0;
}
/**************************************************************
    Problem: 1199
    User: liangrx06
    Language: C
    Result: Accepted
    Time:30 ms
    Memory:912 kb
****************************************************************/