1880.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1880 on 2005-10-01 at 15:17:42 */ 
#include <cstdio>
#include <cstring>
#define  MAX  10000

class BSTreeNode {
public:
	char content[64];
	long number;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s) {
		left = NULL;
		right = NULL;
		number = 1;
		strcpy(content, s);
	}
	bool add(BSTreeNode *node) {
		BSTreeNode *p = this;
		int i;
        while(true) {
            i = strcmp(node->content, p->content);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                    return false;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
                    return false;
                }
            } else {
                p->number++;
				return true;
            }
        }
	}
	void search(const long n, int *i) {
		if(left != NULL) {
			left->search(n, i);
		}
		if(n == number) {
			printf("%s\n", content);
			(*i)++;
		}
		if(right != NULL) {
			right->search(n, i);
		}
	}
};

char* slwr(char *);

int main()
{
	BSTreeNode *Node[MAX], *root;
	int i, n, p, wn, nodeN, q = 0;
	char word[64], ch;
	bool begin, find;
	
	for(i = 0; i < MAX; i++) {
		Node[i] = new BSTreeNode;
	}
	while(scanf("%d", &n) == 1) {
		if(q != 0) {
			putchar('\n');
		}
		q++;
		nodeN = 0;
		root = NULL;
		while(true) {
			wn = 0;
			begin = false;
			while(true) {
				ch = getchar();
				if(ch <= 'z' && ch >= 'A') {
					begin = true;
					word[wn++] = ch;
				} else {
					if(begin) {
						word[wn] = 0;
						break;
					}
				}
			}
			if(wn == 0) {
				continue;
			}
			if(strcmp(word, "EndOfText")) {
				slwr(word);
				Node[nodeN]->init(word);
				if(root == NULL) {
					root = Node[nodeN];
					nodeN++;
				} else {
					find = root->add(Node[nodeN]);
					if(!find) {
						nodeN++;
					}
				}
			} else {
				p = 0;
				root->search(n, &p);
				if(p == 0) {
					printf("There is no such word.\n");
				}
				break;
			}
		}
	}
	
	return 0;
}

char* slwr(char *s)
{
	int i;
	for(i = 0; ; i++) {
		if(s[i] >= 'A' && s[i] <= 'Z') {
			s[i] = s[i] - 'A' + 'a';
		} else if(s[i] == 0) {
			break;
		}
	}
	
	return s;
}