問題:
http://poj.org/problem?id=2418思路:
題意清晰明了，不難，用三種方法分別實現:
快速排序
動態生成節點的二叉查找樹
靜態分配節點的二叉查找樹
結果發現，原來對于快速排序與靜態分配節點都不是很熟悉，二維數組的快速排序分析見
http://www.shnenglu.com/Joe/archive/2010/10/29/131746.html，而動態生成節點則需要注意如果函數需要修改指針，那么必須傳遞指向指針的指針，因為C是值傳遞的
另外，我以為靜態分配節點應該比動態分配節點節約很多時間的，結果居然差不多...而快速排序在這題明顯是最耗時的
代碼(快排)
1 /* 35640K 1844MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 36
6 #define MAX_NUM 1000001
7 char species[MAX_NUM][MAX_LEN];
8
9 int
10 cmp(const void *arg1, const void *arg2)
11 {
12 return strcmp((char *)arg1, (char *)arg2);
13 }
14
15 int
16 main(int argc, char **argv)
17 {
18 int i, count, total = 0;
19 while(gets(species[total]) != NULL)
20 ++total;
21 qsort(species, total, sizeof(species[0]), cmp);
22 count = 1;
23 for(i=1; i<total; i++) {
24 if(strcmp(species[i], species[i-1]) == 0)
25 ++count;
26 else {
27 printf("%s %.4f\n", species[i-1], (count*100.0)/total);
28 count = 1;
29 }
30 }
31 printf("%s %.4f\n", species[total-1], (count*100.0)/total);
32 }
代碼(動態分配節點的BST，原本想實現下destroy函數的，結果怕麻煩就留給系統回收吧(*^__^*) 嘻嘻……)
1 /* binary search tree(dynamic allocation) */
2 /* 544K 1188MS */
3 #include<stdio.h>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<assert.h>
7 #define MAX_LEN 36
8 struct Node {
9 char spec[MAX_LEN];
10 int count;
11 struct Node *left, *right;
12 };
13 int total;
14
15 struct Node *
16 create_node(char *str)
17 {
18 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
19 assert(node != NULL);
20 strcpy(node->spec, str);
21 node->left = node->right = NULL;
22 node->count = 1;
23 return node;
24 }
25
26 void
27 insert(struct Node **root, char *str)
28 {
29 int ret;
30 struct Node *node;
31 if(*root==NULL) {
32 *root = create_node(str);
33 return;
34 }
35 ret = strcmp((*root)->spec, str);
36 if(ret == 0)
37 ++((*root)->count);
38 else if(ret < 0)
39 insert(&((*root)->right), str);
40 else
41 insert(&((*root)->left), str);
42 }
43
44 void
45 inorder(struct Node *root)
46 {
47 if(root == NULL)
48 return;
49 inorder(root->left);
50 printf("%s %.4f\n", root->spec, (root->count)*100.0/total);
51 inorder(root->right);
52 }
53
54 void
55 destroy(struct Node **root)
56 {
57 }
58
59 int
60 main(int argc, char **argv)
61 {
62 char str[MAX_LEN];
63 struct Node *bst = NULL;
64 total = 0;
65 while(gets(str) != NULL) {
66 ++total;
67 insert(&bst, str);
68 }
69 inorder(bst);
70 }
代碼(靜態分配節點的BST)
1 /* binary search tree(static allocation) */
2 /* 492K 1188MS */
3 #include<stdio.h>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<assert.h>
7 #define MAX_LEN 36
8 #define MAX_NUM 10007
9 #define ROOT 1
10 struct Node {
11 char spec[MAX_LEN];
12 int count;
13 int left, right;
14 }bst[MAX_NUM];
15 int cur_index, total;
16
17 int
18 find(int root, char *str)
19 {
20 int ret, parent, cur = root;
21 while(cur != 0) {
22 parent = cur;
23 ret = strcmp(bst[cur].spec, str);
24 if(ret == 0) {
25 ++bst[cur].count;
26 return 0;
27 } else if(ret < 0) {
28 cur = bst[cur].right;
29 } else {
30 cur = bst[cur].left;
31 }
32 }
33 return parent;
34 }
35
36 #define ADD(index, str) { \
37 strcpy(bst[index].spec, str); \
38 bst[index].left = bst[index].right = 0; \
39 bst[index].count = 1; \
40 ++index; }
41
42 void
43 insert(int parent, char *str)
44 {
45 int ret = strcmp(bst[parent].spec, str);
46 assert(ret != 0);
47 if(ret < 0)
48 bst[parent].right = cur_index;
49 else
50 bst[parent].left = cur_index;
51 ADD(cur_index, str);
52 }
53
54 void
55 inorder(int index)
56 {
57 if(index == 0)
58 return;
59 inorder(bst[index].left);
60 printf("%s %.4f\n", bst[index].spec, (bst[index].count*100.0)/total);
61 inorder(bst[index].right);
62 }
63
64 int
65 main(int argc, char **argv)
66 {
67 int parent;
68 char str[MAX_LEN];
69 total = 1;
70 cur_index = ROOT;
71 gets(str);
72 ADD(cur_index, str); /* create the root node first */
73 while(gets(str) != NULL) {
74 ++total;
75 if((parent=find(ROOT, str)) > 0)
76 insert(parent, str);
77 }
78 inorder(ROOT);
79 }