据说字典树可以做,我当时也没多想直接敲了个AVL出来,也不知道用了多少时间AC的(早上考xx,考试那系统不给看时间)
貌似我把windows里面的src拿到ubuntu的FF里面去着色会发生悲剧(回车变成俩回车,怀疑是某人依然没处理好\r\n根\r)
也不知道能用Hash不。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <functional>
#include <cstring>
#include <utility>
#include <string>
using namespace std;
struct carrot_t {
carrot_t *parent;
carrot_t *left;
carrot_t *right;
char data[31];
int count;
int bf;
};
carrot_t* root;
int carrot_count;
inline
bool
comp(const char * str1, const char * str2) {
return strcmp(str1, str2) > 0;
}
void
rotate_left(carrot_t* n) {
carrot_t *r(n->right), *p(n->parent);
r->parent = n->parent;
n->parent = r;
n->right = r->left;
if (r->left) {
r->left->parent = n;
}
r->left = n;
if (p) {
(comp(p->data, n->data) ? p->left : p->right) = r;
} else {
root = r;
}
++n->bf;
n->bf -= (r->bf < 0 ? r->bf : 0);
++r->bf;
r->bf += (n->bf > 0 ? n->bf : 0);
return;
}
void
rotate_right(carrot_t* n) {
carrot_t *l(n->left), *p(n->parent);
l->parent = n->parent;
n->parent = l;
n->left = l->right;
if (l->right) {
l->right->parent = n;
}
l->right = n;
if (p) {
(comp(p->data, n->data) ? p->left : p->right) = l;
} else {
root = l;
}
--n->bf;
n->bf += (l->bf > 0 ? l->bf : 0);
--l->bf;
l->bf -= (n->bf < 0 ? n->bf : 0);
return;
}
void
balance_left(carrot_t *n) {
if (n->right->bf == 1) {
rotate_right(n->right);
}
rotate_left(n);
return;
}
void
balance_right(carrot_t *n) {
if (n->left->bf == -1) {
rotate_left(n->left);
}
rotate_right(n);
return;
}
inline
carrot_t *
allocate_node(const char * object) {
carrot_t* nd;
nd = new carrot_t;
nd->parent = nd->left = nd->right = 0;
strcpy(nd->data, object);
nd->bf = 0;
nd->count = 1;
return nd;
}
void
insert_node(const char * object) {
carrot_t* n(root), *p;
++carrot_count;
if (!root) {
root = allocate_node(object);
return;
}
while (n) {
p = n;
if (!strcmp(n->data, object)) {
++n->count;
return;
}
if (comp(n->data, object)) {
n = n->left;
} else {
n = n->right;
}
}
if (comp(p->data, object)) {
p->left = allocate_node(object);
} else {
p->right = allocate_node(object);
}
// balance
while (n) {
n->bf += comp(n->data, object);
if (n->bf == 2) {
balance_right(n);
} else if (n->bf == -2) {
balance_left(n);
}
if (!n->bf) {
break;
}
}
return;
}
void
display_result(carrot_t *r)
{
if (r->left) {
display_result(r->left);
}
printf("%s %.4f\n", r->data, (double)r->count / carrot_count * 100);
if (r->right) {
display_result(r->right);
}
return;
}
inline
int
get_line(char * p)
{
//.....
int c;
c = getchar();
while (c != '\n' && c != '\r' && c != EOF) {
*p = c;
c = getchar();
++p;
}
*p = 0;
return c;
}
int main()
{
char buffer[60];
root = 0;
carrot_count = 0;
//freopen("test.txt", "r", stdin);
while (get_line(buffer) != EOF) {
insert_node(buffer);
}
display_result(root);
return 0;
}