POJ 2418這個(gè)題目要求輸入多個(gè)字符串，按
alphabetical（字母大小）順序輸出，并且統(tǒng)計(jì)每種字符串出現(xiàn)的百分比。其中重要的一點(diǎn)就是對字符串進(jìn)行排序，這時(shí)我們考慮用BST（二叉搜索樹）來存儲(chǔ)數(shù)據(jù)，然后按中序輸出，至于百分比在存儲(chǔ)數(shù)據(jù)時(shí)附加上就行了。BST是一個(gè)很高效的算法，插入時(shí)的時(shí)間復(fù)雜度是線性的。 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個(gè)作用 ，太巧妙了
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個(gè)作用：判斷是否為空樹
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個(gè)作用：記錄p結(jié)點(diǎn)，以便能使插入的結(jié)點(diǎn)連接到樹中
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