# 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.