电话号码问题

phonenumber.c

// 电话号码问题
// 商业单位需要容易记忆的电话号码，有一些方法可以让电话号码变得更容易记忆。譬如，可以把电话号码写成单词或短语，如 MON-GLOP
// 可以代表滑铁卢大学的电话。有时仅仅是把号码的一部分写成单词，如打 310-GINO 便可向 GINO
// 比萨饼店定购比萨。另一种让电话号码容易记忆的方法是将数字用一种容易记的方式组合起来，譬如 3-10-10-10 也可以代表 GINO
// 比萨饼店。

// 电话号码的标准形式是七位十进制数字，在它的第三位和第四位之间用连字符连接(例如：666-1200)。电话的键盘提供了字符与数字之间的映
// 射关系，如下所示：

// 2 A、B和C  3 D、E和F  4 G、H和I  5 J、K和L  6 M、N和O  7 P、R和S  8 T、U和V  9
// W、X和Y  Q 和 Z 没有映射到键盘，而连字符不需要被拨打并且可以根据需要添加和删除。MON-GLOP 的标准形式是
// 666-4567，310-GINO 的标准形式是310-4466，3-10-10-10的标准形式也是 310-1010。

// 如果两个电话号码有相同的标准形式，那么这两个电话号码是相同的。

// 你所在的公司正在编辑一本当地商业单位的电话簿，作为质量控制流程的一部分，你需要确认在该电话簿中有没有错误的电话号码，以及有没有两个(或
// 两个以上的)商业单位使用相同的电话号码。由于当地只使用了 3 和 6 两个区段，因此电话号码的第一个数字应当永远是 3 或者
// 6，如果出现了其它数字，就表示这个电话号码错了。此外，如果电话号码中出现了 Q 和 Z，也说明这个电话错了。

// 输入 一次输入为一个样例。每个号码一行，每行的字符不会超过 20 个。每次输入的数据可能会非常大，譬如超过 1,000,000
// 个电话号码。

// 你可以假设输入中可能会出现重复的电话号码不超过 1,500 个，每个号码重复的次数不超过 1000 次。

// 输出 输出包括两个部分，第一个部分是错误的电话号码，对于这些号码应当按照输入的顺序以原始的形式输出。在输出错误电话号码前输出“Erro
// r:”，随后输出这些号码，如果没有错误的电话号码，则输出“Not found.”。

// 第二部分是重复的电话号码，对每一个在电话簿中以任何形式出现一次以上的电话号码，生成一行输出。这一行应以标准形式给出电话号码，其后跟随一
// 个空格，空格后跟随电话号码在电话簿中出现的次数。所有重复的电话号码输出行应以号码的升序排列（小号码在前）。在输出重复电话号码前输出“D
// uplication”，随后按照上述格式输出号码，如果在输入中没有重复的电话号码，则输出：“Not found.”。

// 注意 你所编写的程序以后可能会在一种特殊的嵌入式设备上运行，为了降低成本，这种设备使用的 CPU 不是很快、可用的 RAM 为
// 288K（跟 GBA 一样）且它没有磁盘设备因此不能使用文件作为数据的临时存储。

// 提示 请参考《编程珠玑》第一部分，若程序不能在规定的内存中运行，则不得分。

/*
// sample input
4873279
ITS-EASY
666-4567
3-10-10-10
666-GLOP
MON-GLOP
367-11-11
310-GINO
F101010
666-1200
-4-8-7-3-2-7-9
487-3279

// sample output
Error:
4873279
ITS-EASY
-4-8-7-3-2-7-9
487-3279

Duplication:
310-1010 2
666-4567 3
*/

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

char bits[250001];
char phone[21];
char stand[10];

struct phonenumber {
    char stand[10];
    int count;
    int num;
} stands[1501];

struct phonenumber tmp;
int alphabet2digit(char c)
{
    int d = -1;
    switch (c) {
    case 'A':
    case 'B':
    case 'C':
        d = 2;
        break;
    case 'D':
    case 'E':
    case 'F':
        d = 3;
        break;
    case 'G':
    case 'H':
    case 'I':
        d = 4;
        break;
    case 'J':
    case 'K':
    case 'L':
        d = 5;
        break;
    case 'M':
    case 'N':
    case 'O':
        d = 6;
        break;
    case 'P':
    case 'R':
    case 'S':
        d = 7;
        break;
    case 'T':
    case 'U':
    case 'V':
        d = 8;
        break;
    case 'W':
    case 'X':
    case 'Y':
        d = 9;
        break;
    }
    if (isdigit(c)) {
        d = c - '0';
    }
    return d;
}

void covert2stand(char phone[], char stand[])
{
    int len = strlen(phone);
    int m = 0;
    int error = 0;
    for (int i = 0; i < len; ++i) {
        char c = phone[i];
        if ((isalpha(c) && (c != 'Q' && c != 'Z')) || isdigit(c)) {
            //printf("%d", alphabet2digit(c));
            stand[m] = '0' + alphabet2digit(c);
            m++;
        } else if (c == '-') {
            // skip
        } else {
            // error
            error = 1; //mark as error
            break;
        }
        if (m == 3) {
            stand[m] = '-';
            m++;
        }
    }
    // if (len>0&&phone[0]=='-'){
    // 	error = 1;
    // }
    if (error) {
        stand[0] = '0';
    }
    if (m > 9) {
        m = 9;
    }
    stand[m] = '\0';
    return;
}

int stand2number(char stand[])
{
    int r = 0;
    for (int i = 0, count = strlen(stand); i < count; ++i) {
        if (stand[i] != '-') {
            r = r * 10 + stand[i] - '0';
        }
    }
    return r;
}
int main()
{
    //freopen("data_16.txt","r",stdin);
    int n = 0, m, r;
    int error = 0;
    int duplication = 0;
    printf("Error:\n");

    while (scanf("%s", phone) != EOF && strlen(phone) > 0) {
        covert2stand(phone, stand);
        if (strlen(stand) == 8 && (stand[0] == '3' || stand[0] == '6')) {
            // valid
            m = stand2number(stand);
            r = m;
            //printf("stand2number: %d\n",r);
            if (stand[0] == '3') {
                r -= 3000000;
            }
            if (stand[0] == '6') {
                r -= 5000000;
            }
            int position = r / 8;
            int bit = r % 8;
            if (bits[position] & (1 << bit)) {
                duplication++;
                int find = 0;
                for (int i = 0; i < n; ++i) {
                    if (strcmp(stands[i].stand, stand) == 0) {
                        stands[i].count++;
                        find = 1;
                    }
                }
                if (find == 0) {
                    strcpy(stands[n].stand, stand);
                    stands[n].num = m;
                    stands[n].count = 2;
                    n++;
                }
            } else {
                bits[position] |= (1 << bit);
            }
            //printf("stand2number: %d %d %d\n",r,r/8,r%8);
        } else {
            error++;
            printf("%s\n", phone);
        }
    }

    if (error == 0) {
        printf("Not found.\n");
    }
    printf("\n");

    printf("Duplication:\n");

    if (duplication == 0) {
        printf("Not found.\n");
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (stands[j].num > stands[j + 1].num) {
                    tmp = stands[j];
                    stands[j] = stands[j + 1];
                    stands[j + 1] = tmp;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            printf("%s %d\n", stands[i].stand, stands[i].count);
        }
    }
    return 0;
}

test_data

4873279
ITS-EASY
666-4567
3-10-10-10
666-GLOP
MON-GLOP
367-11-11
310-GINO
F101010
666-1200
-4-8-7-3-2-7-9
487-3279