北大ACM题库1002,实在想不出为什么是WRONG ANSWER - C语言论坛

已结贴√ 问题点数：20 回复次数：3

北大ACM题库1002,实在想不出为什么是WRONG ANSWER

用排序二叉树过了，就是时间有点长。把字符串转化为unsigned int数据类型，然后快排，竟然错了。郁闷！
请大家看看哪里的问题，谢谢！
/*
    Name:
    Copyright:
    Author:
    Date: 31/12/14 08:38
    Description:
    北大ACM题库1002
题目
Description

企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。
有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Gino's订一份pizza。让电话号码容易被记住的另一个办法是
以一种好记的方式对号码的数字进行分组。通过拨打必胜客的"三个十"号码3-10-10-10，你可以从他们那里订pizza。

电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9

Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。 TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。

如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）

你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。
Input

输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。
每个电话号码中只会刚好有7个数字或者字母。
Output

对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。
如果输入数据中没有重复的号码，输出一行：
No duplicates.
Sample Input

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
Sample Output

310-1010 2
487-3279 4
888-4567 3
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 100010

unsigned int TelNum[MAX] = {0};

void PrintTelNum(int n);//输出电话号码
int Change(const char *s, int top);//插入新结点，并返回数组长度
int Cmp(const void *a , const void *b);

int main(void)
{
    char str[100];
    int i, len = 0, n;

    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        scanf("%s", str);
        len = Change(str, len);//插入新结点，并返回数组长度
    }

    qsort(TelNum, len, sizeof(TelNum[0]), Cmp);
    PrintTelNum(len);//输出电话号码

    return 0;
}

int Cmp(const void *a , const void *b)
{ return *(unsigned int *)a - *(unsigned int *)b; }

int Change(const char *s, int top)//转换为标准电话号码
{
    int i;

    for (TelNum[top]=i=0; s[i] != '\0'; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')//数字，直接存储
        {
            TelNum[top] = TelNum[top] * 10 + s[i] - '0';
        }
        else if (s[i] >= 'A' && s[i] <= 'Y')//大写字母，转换后存储
        {
            if (s[i] > 'Q') //跳过字母Q
                TelNum[top] = TelNum[top] * 10 + (s[i] - 60) / 3;
            else
                TelNum[top] = TelNum[top] * 10 + (s[i] - 59) / 3;
        }
    }
    return top + 1;
}

void PrintTelNum(int n)//输出电话号码
{
    int i, s = 0, flag = 0;

    for (i=1; i<n; i++)
    {
        if (TelNum[i] == TelNum[i-1])
        {
            s++;
        }
        else if (s > 0)
        {
            printf("%03d-%04d %d\n", TelNum[i-1]/10000, TelNum[i-1]%10000, s+1);
            flag = 1;
            s = 0;
        }
        else
        {
            s = 0;
        }
    }
    if (flag == 0)
        puts("No duplicates.");
}

第 2 楼

得分:0

使用排序二叉树过了：
13760960    QiaoRuoZhuo    1002    Accepted    3488K    641MS    C    2138B    2015-01-04 19:38:19

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

#define MAX 50 //电话号码最大长度

typedef struct node{
    char telNum[9];//电话号码
    int num;//相同号码数量
    struct node *lc, *rc; //二叉排序树的左右孩子
}  BiTreeNode, *BiTree;

void Change(char *dest, const char *s);//转换为标准电话号码
void Insert(BiTree *b, char *s);//插入新结点
BiTree NewBiTree(char *key);//生成一个新结点
void InOrderPrint(BiTree p, int *flag);//按号码的字典升序输出

int main(void)
{
    char str[MAX], dest[9];
    BiTree b = NULL;
    int i, n, flag = 0;

    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        scanf("%s", str);
        Change(dest, str);
        Insert(&b, dest);//插入新结点
    }

    InOrderPrint(b, &flag);
    if (flag == 0)
        puts("No duplicates.");

    return 0;
}

void InOrderPrint(BiTree p, int *flag)
{
    if (p != NULL)
    {
        InOrderPrint(p->lc, flag); //遍历左子树
        if (p->num > 1)
        {
            printf("%s %d\n", p->telNum, p->num);//输出该结点
            *flag = 1;
        }
        InOrderPrint(p->rc, flag); //遍历右子树
    }
}

void Change(char *dest, const char *s)//转换为标准电话号码
{
    int i, top;

    for (top=i=0; s[i] != '\0'; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')//数字，直接存储
        {
            dest[top++] = s[i];
        }
        else if (s[i] >= 'A' && s[i] <= 'Y')//大写字母，转换后存储
        {
            if (s[i] > 'Q') //跳过字母Q
                dest[top++] = (s[i] - 60) / 3 + '0';
            else
                dest[top++] = (s[i] - 59) / 3 + '0';
        }
        if (top == 3)
        {
            dest[top++] = '-';
        }
    }
    dest[top] = '\0';
}

void Insert(BiTree *b, char *s)//插入新结点
{
    if (*b == NULL)
        *b = NewBiTree(s);
    else if (strcmp(s, (*b)->telNum) == 0)//不做任何插入操作
        (*b)->num++;
    else if (strcmp(s, (*b)->telNum) < 0)//把s所指结点插入到左子树中
        Insert(&(*b)->lc, s);
    else               //把s所指结点插入到右子树中
        Insert(&(*b)->rc, s);
}

BiTree NewBiTree(char *key)//生成一个新结点
{
    BiTree s = (BiTree)malloc(sizeof(BiTreeNode));

    if (!s)
    {
        printf("Out of space!");
        exit (1);
    }
    strcpy(s->telNum, key);
    s->num = 1;
    s->lc = s->rc = NULL;

    return s;
}

第 3 楼

得分:0

使用折半插入法，超时了

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

#define MAX 100000

struct Node{
    char telNum[9];//电话号码
    int num;//相同号码数量
}  Tel[MAX];

void PrintTelNum(int n);//输出电话号码
int Insert(char *str, int n);//折半插入新结点
void Change(char *dest, const char *s);//转换为标准电话号码

int main(void)
{
    char str[50], dest[9];
    int i, len = 0, n, pos;

    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        scanf("%s", str);
        Change(dest, str);
        len = Insert(dest, len);//插入新结点，并返回数组长度
    }

    PrintTelNum(len);//输出电话号码

    return 0;
}

void Change(char *dest, const char *s)//转换为标准电话号码
{
    int i, top;

    for (top=i=0; s[i] != '\0'; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')//数字，直接存储
        {
            dest[top++] = s[i];
        }
        else if (s[i] >= 'A' && s[i] <= 'Y')//大写字母，转换后存储
        {
            if (s[i] > 'Q') //跳过字母Q
                dest[top++] = (s[i] - 60) / 3 + '0';
            else
                dest[top++] = (s[i] - 59) / 3 + '0';
        }
        if (top == 3)
        {
            dest[top++] = '-';
        }
    }
    dest[top] = '\0';
}

void PrintTelNum(int n)//输出电话号码
{
    int i, flag = 0;

    for (i=0; i<n; i++)
    {
        if (Tel[i].num > 1)
        {
            printf("%s %d\n", Tel[i].telNum, Tel[i].num);//输出该结点
            flag = 1;
        }
    }
    if (flag == 0)
        puts("No duplicates.");
}

int Insert(char *str, int n)//折半插入新结点
{
    int i, flag = 1;//标记是否为已有号码结点
    int mid, low = 0, high = n - 1;

    if (n == 0)
    {
        strcpy(Tel[0].telNum, str);
        Tel[0].num = 1;
        return 1;
    }

    while (low <= high)//折半查找插入位置
    {
        mid = (low + high)/2;
        flag = strcmp(str, Tel[mid].telNum); //比较字符串大小
        if (flag == 0) //已有号码结点
            break;
        else if (flag < 0)
            high = mid - 1;
        else
            low = mid + 1;
    }

    if (flag == 0) //增加已有号码数量
        Tel[mid].num++;
    else //插入新结点
    {
        for (i=n; i>low; i--)
            Tel[i] = Tel[i-1];

        strcpy(Tel[low].telNum, str);
        Tel[low].num = 1;
        n++;
    }

    return n; //返回新的数组长度
}

[ 本帖最后由巧若拙于 2015-1-5 06:50 编辑 ]

第 4 楼

得分:0

现在查出输出函数有点问题，修改了，但还是不能过，请大神指导
void PrintTelNum(int n)//输出电话号码
{
    int i, s = 0, flag = 0;

    for (i=1; i<n; i++)
    {
        if (TelNum[i] == TelNum[i-1])
        {
            s++;
        }
        else if (s > 0)
        {
            printf("%03d-%04d %d\n", TelNum[i-1]/10000, TelNum[i-1]%10000, s+1);
            flag = 1;
            s = 0;
        }
    }
    if (s > 0)
    {
        printf("%03d-%04d %d\n", TelNum[i-1]/10000, TelNum[i-1]%10000, s+1);
        flag = 1;
    }

    if (flag == 0)
        puts("No duplicates.");
}