1929.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1929 on 2005-09-26 at 22:28:22 */ 
#include <cstdio>
#include <cstring>
#define  MAX  10000

class BSTreeNode {
public:
	char content[32];
	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 leftRootRight(const long total) {
		double percent = (double)number * 100 / total;
		if(left != NULL) {
			left->leftRootRight(total);
		}
		printf("%s %.4lf\n", content, percent);
		if(right != NULL) {
			right->leftRootRight(total);
		}
	}
};

int main()
{
	BSTreeNode *Node[MAX+1], *root;
	char name[32];
	long spe;
	int nodeNum, i, j = 0;
	bool searched;
	
	for(i = 0; i < MAX+1; i++) {
		Node[i] = new BSTreeNode;
	}
	while(true) {
		if(j != 0) {
			putchar('\n');
		}
		root = NULL;
		nodeNum = 0;
		for(spe = 0; true; spe++) {
			if(gets(name) == NULL) {
				if(root != NULL) {
					root->leftRootRight(spe);
				}
				return 0;
			} else {
				if(strlen(name) == 0) {
					break;
				} else {
					Node[nodeNum]->init(name);
					if(root == NULL) {
						root = Node[nodeNum++];
					} else {
						searched = root->add(Node[nodeNum]);
						if(!searched) {
							nodeNum++;
						}
					}
				}
			}
		}
		if(root != NULL) {
			root->leftRootRight(spe);
		}
		j++;
	}
	
	return 0;
}