C-数据结构-retrieval搜索树

log

ant:a samll insect that lives in group
butterfly:a flying insect with a long thin body
cobra:a highly dangerous snake
monkey: a animal with short legs and long ears
1
2
3
4

trie.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define DESC_SIZE 256
#define KEY_SIZE  256
#define BUF_SIZE  512
#define FNAME 	  "log"	//当前路径的Log文件

struct node_st 
{
	struct node_st *ch[26];
	char desc[DESC_SIZE];
};

int get_word(FILE *fp,char *key,char *desc)
{
	char buf[BUF_SIZE];
	char *retp;
	int i,j;
	
	retp = fgets(buf,BUF_SIZE,fp);
	if(retp == NULL)
		return -1;
	
	for(i = 0;i < KEY_SIZE-1 && buf[i] != ':'; i++)
		key[i] = buf[i];
	key[i] = '\0';
	i++;
	for(j = 0 ;j < DESC_SIZE -1 && buf[i] !='\0';j++,i++)
		desc[j] = buf[i];
	desc[j] = '\0';
	return 0;
}

struct node_st *newnode()
{
	int i;
	struct node_st *node;
	node = malloc(sizeof(*node));
	if(node == NULL)
		return NULL;
	node->desc[0] = '\0';
	for(i =0;i<26;i++)
		node->ch[i] = NULL;
	return node;
}

int insert(struct node_st **root,char *key,char *desc)
{
	if(*root == NULL)
	{
		*root = newnode();
		if(*root == NULL)
			return -1;
	}
	if(*key == '\0')
	{
		strcpy((*root)->desc,desc);
		return 0;
	}
	return insert((*root)->ch + *key - 'a',key +1,desc);

}

char *find(struct node_st *root,char *key)
{
	if(root == NULL)
		return NULL;
	if(*key == '\0')
		return root->desc;
	return find(root->ch[*key-'a'],key +1);
}


int main()
{
	struct node_st *tree = NULL;
	int ret;
	FILE *fp;
	char desc[DESC_SIZE]={'\0'},key[KEY_SIZE]={'\0'};
	char *datap;
	
	fp = fopen(FNAME,"r");
	if(fp == NULL)
	{
		fprintf(stderr,"fopen:error!\n");
		exit(1);
	}
	
	while(1)
	{
		ret = get_word(fp,key,desc);
		if(ret == -1)
			break;
		//puts(key);
		//puts(desc);
		insert(&tree,key,des);
		
		
	}
	datap = find(tree,"monkey");
	if(datap == NULL)
		printf("can not find \n");
	else 
		puts(datap);


	fclose(fp);
	exit(0);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

补充说明

要理解 struct node_st *ch[26]; 的含义，我们可以逐步解析这个定义，并结合代码示例说明它是如何工作的。这里我们一步一步地解释。

逐步理解 struct node_st *ch[26];
指针数组：

ch 是一个数组，它包含 26 个元素。
数组的每个元素都是一个指向 struct node_st 类型的指针。
struct node_st 是一个结构体类型，表示前缀树的节点。
struct node_st 是一个包含指针数组 ch 和描述字符串 desc 的结构体。