1 #include<stdio.h>
2 #include<math.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include<memory.h>
6 #include<float.h>
7 #define NULL 0
8 #define LEN sizeof(struct trie)
9
10 struct trie
11 {
12 int count;
13 struct trie *next[26];
14 };
15
16 trie *root, *p1, *p2;
17
18 void init(trie *node)
19 {
20 int i;
21 for (i=0; i<26; i++)
22 node->next[i] = NULL;
23 }
24
25 void add()
26 {
27 int n, len, i, k, j;
28 char s[15];
29 printf("\n请输入要加入的单词的个数:");
30 scanf("%d", &n);
31 printf("请输入要加入的小写字母单词,每个单词以回车结束:\n");
32 while(n--)
33 {
34 scanf("%s", &s);
35 len = strlen(s);
36 p1 = p2 = root;
37 for (i=0; i<len; i++)
38 {
39 k = s[i] - 'a';
40 if (root == NULL)
41 {
42 root = (trie *) malloc(LEN);
43 init(root);
44 p1 = root;
45 p1->count = 1;
46 }
47 if (p1->next[k] == NULL)
48 {
49 p2 = (trie *) malloc(LEN);
50 init(p2);
51 p2->count = 1;
52 p1->next[k] = p2;
53 p1 = p1->next[k];
54 }
55 else
56 p1 = p1->next[k];
57 }
58 p1->count = -1;
59 }
60 printf("输入的单词已经录入完成!\n");
61 }
62
63 void print(trie *point)
64 {
65 int i;
66 printf("%d ", point->count);
67 if (point->count == -1)
68 printf("\n");
69 for (i=0; i<26; i++)
70 {
71 if(point->next[i] != NULL)
72 print(point->next[i]);
73 }
74 }
75
76 void deleting()
77 {
78
79 }
80
81 void search()
82 {
83 int len, i, k;
84 char s[15];
85 printf("\n请输入要搜索的单词:");
86 scanf("%s", &s);
87 len = strlen(s);
88 p1 = root;
89 for (i=0; i<len; i++)
90 {
91 k = s[i] - 'a';
92 p1 = p1->next[k];
93 if (p1 == NULL)
94 {
95 printf("没有该单词!\n");
96 return;
97 }
98 }
99 if (p1->count == -1)
100 printf("存在该单词!\n");
101 else
102 printf("没有该单词!\n");
103 }
104
105 int main()
106 {
107 int a;
108 root = NULL;
109 printf("这里是字典树单词管理系统!!\n\n");
110 printf("请输入需要进行的操作:\n1 为添加, 2 为打印, 3 为删除, 4 为搜索, 0 为退出:");
111 while(scanf("%d", &a) && a!=0)
112 {
113 switch(a)
114 {
115 case 1: add(); break;
116 case 2: print(root); break;
117 case 3: deleting(); break;
118 case 4: search(); break;
119 default: printf("输入的操作无效,请重新输入。\n\n");
120 }
121 printf("\n请输入需要进行的操作:\n1 为添加, 2 为打印, 3 为删除, 4 为查找, 0 为退出:");
122 }
123 }