1347.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1347 on 2005-11-09 at 19:55:19 */ 
#include <cstdio>
#include <cstring>

const int L_MAX = 16;
const int MAX = 102400;

class BSTree {
private:
	BSTree *left;
	BSTree *right;
	char number[L_MAX];
	int n;
public:
	static bool print;
	void init(char*);
	bool insert(BSTree*);
	void travel();
};
bool BSTree::print = false;
void BSTree::init(char *s) {
	strcpy(number, s);
	n = 1;
	left = right = NULL;
}
bool BSTree::insert(BSTree *node) {
	BSTree *p = this;
	while(true) {
		int i = strcmp(p->number, node->number);
		if(i > 0) {
			if(p->left != NULL) {
				p = p->left;
			} else {
				p->left = node;
				return true;
			}
		} else if(i < 0) {
			if(p->right != NULL) {
				p = p->right;
			} else {
				p->right = node;
				return true;
			}
		} else {
			p->n++;
			return false;
		}
	}
}
void BSTree::travel() {
	if(left != NULL) {
		left->travel();
	}
	if(n > 1) {
		printf("%s %d\n", number, n);
		print = true;
	}
	if(right != NULL) {
		right->travel();
	}
}

BSTree *root, node[MAX];

char phoneNumber(char);

int main()
{
	char line[128], num[L_MAX];
	int T, t, i, j;
	int n, l, pn;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		if(t != 0) {
			putchar('\n');
		}
		scanf("%d", &n);
		root = NULL;
		getchar();
		pn = 0;
		for(i = 0; i < n; i++) {
			gets(line);
			for(j = 0, l = 0; line[j] != 0; j++) {
				if(line[j] != '-') {
					num[l++] = phoneNumber(line[j]);
					if(l == 3) {
						num[l++] = '-';
					}
				}
			}
			num[l] = '\0';
			node[pn].init(num);
			if(root == NULL) {
				root = &node[pn++];
			} else if(root->insert(&node[pn])) {
				pn++;
			}
		}
		BSTree::print = false;
		if(root != NULL) {
			root->travel();
		}
		if(!BSTree::print) {
			printf("No duplicates.\n");
		}
	}
	
	return 0;
}

char phoneNumber(char c)
{
	switch(c) {
	case 'A': case 'B': case 'C':
		return '2';
	case 'D': case 'E': case 'F':
		return '3';
	case 'G': case 'H': case 'I':
		return '4';
	case 'J': case 'K': case 'L':
		return '5';
	case 'M': case 'N': case 'O':
		return '6';
	case 'P': case 'R': case 'S':
		return '7';
	case 'T': case 'U': case 'V':
		return '8';
	case 'W': case 'X': case 'Y':
		return '9';
	default:
		return c;
	}
}