POJ 2418这个题目要求输入多个字符串，按
alphabetical（字母大小）顺序输出，并且统计每种字符串出现的百分比。其中重要的一点就是对字符串进行排序，这时我们考虑用BST（二叉搜索树）来存储数据，然后按中序输出，至于百分比在存储数据时附加上就行了。BST是一个很高效的算法，插入时的时间复杂度是线性的。 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 char a[31];
5 typedef struct nod{
6 char b[31];
7 int num;
8 struct nod *lchild,*rchild;
9 }node;
10 node *bt;
11 int count = 0;
12 void Insert();
13 void print(node *p);
14 int main()
15 {
16 bt = NULL;
17 while(strcmp(gets(a),"##")){
18 count++;
19 Insert();
20 }
21 print(bt);
22 system("pause");
23 return 0;
24 }
25 void Insert()
26 {
27 node *p = bt;
28 node *q = NULL;//q在这里有2个作用 ，太巧妙了
29 int flag = 0;
30 while(p != NULL){
31 if(!strcmp(a,p->b)){
32 p->num++;
33 return;
34 }
35 q = p;
36 p = strcmp(a,p->b) > 0?p->rchild:p->lchild;
37 flag = 1;
38 }
39 if(q == NULL){//q的第1个作用：判断是否为空树
40 bt = (node *)malloc(sizeof(struct nod));
41 strcpy(bt->b,a);
42 bt->num = 1;
43 bt->lchild = NULL;
44 bt->rchild = NULL;
45 }
46 else{
47 if(flag){
48 p = (node *)malloc(sizeof(struct nod));
49 strcpy(p->b,a);
50 p->num = 1;
51 p->lchild = NULL;
52 p->rchild = NULL;
53 }
54 if(strcmp(q->b,a) > 0){//q的第2个作用：记录p结点，以便能使插入的结点连接到树中
55 q->lchild = p;
56 }
57 else{
58 q->rchild = p;
59 }
60 }
61 }
62 void print(node *p)
63 {
64 if(p != NULL){
65 print(p->lchild);
66 printf("%s %.4f\n",p->b,100.0*p->num/count);//注意这里*100.0
67 print(p->rchild);
68 }
69 }
70