Hardwood Species_专业打酱油_百度空间
据说字典树可以做,我当时也没多想直接敲了个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;
}



郑重声明:资讯 【Hardwood Species_专业打酱油_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——