Poj Solution 1002

http://poj.org/problem?id=1002

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

typedef struct BSTNode
{
    char phoneName[9];
    int times;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

int count;

void InsertBST(BSTree &t, char name[])//二叉排序树的插入,注意里面的BSTree &t
{
    BSTree p,f;
    p = t;//指向树根
    while(p)
    {
        if(strcmp(name,p->phoneName) == 0)//树中已有name值了,无需插入
        {
            p->times++;
            count=1;
            return;
        }
        f = p;// f保存当前查找的结点
        //若name < p->phoneName ,在左子树上查找,否则在右子树查找.
        p = (strcmp(name,p->phoneName)<0) ? p->lchild : p->rchild;
    }

    p = (BSTree)malloc(sizeof(BSTNode));
    strcpy(p->phoneName,name);
    p->lchild = p->rchild = NULL;
    p->times = 1;

    if(t == NULL) t = p;
    else if(strcmp(name,f->phoneName)<0)
            f->lchild = p;
    else f->rchild = p;    
}

void InOrderTraverse(BSTree t)//中序遍历
{
    if(t!=NULL)
    {
        InOrderTraverse(t->lchild);
        if(t->times > 1)
            printf("%s %dn",t->phoneName,t->times);
        InOrderTraverse(t->rchild);
    }
}

int main()
{
    int n,i,j;
    char str[20];
    char ch;
    BSTree t = NULL;

    scanf("%d",&n);
    ch = getchar();
    count = 0;
    for(i=0;i<n;i++)
    {
        j=0;
        while( (ch=getchar())!='n')
        {
            if(isdigit(ch))//判断是否为数字
               str[j++] = ch;
            else
                if(isupper(ch))//判断是否为大写字母
                {
                    switch(ch)
                    {
                    case'A':case'B':case'C': ch = '2';break;
                    case'D':case'E':case'F': ch = '3';break;
                    case'G':case'H':case'I': ch = '4';break;
                    case'J':case'K':case'L': ch = '5';break;
                    case'M':case'N':case'O': ch = '6';break;
                    case'P':case'R':case'S': ch = '7';break;
                    case'T':case'U':case'V': ch = '8';break;
                    case'W':case'X':case'Y': ch = '9';break;
                    }
                    str[j++] = ch;
                }
                else continue;
            if(j==3) str[j++] = '-';//在第四个位置补上一横;
        }
        str[j]='';

        InsertBST(t,str);
    }

    if(count) InOrderTraverse(t);
    else printf("No duplicates.n");

    return 0;
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *