typedef struct search_tree_node {				//定義搜索樹(shù)節(jié)點(diǎn)
	struct search_tree_node* ch[CHAR_SIZE];		//分類(lèi)
	char desc[DESC_SIZE];						//描述
}STNode;

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define CHAR_SIZE	26				//字母大小（26小寫(xiě)）
#define KEY_SIZE	256				//關(guān)鍵字大小
#define DESC_SIZE	256				//描述區(qū)大小
#define BUFF_SIZE	512				//緩沖區(qū)大小
#define FILE_NAME	"test.txt"		//文件路徑

typedef struct search_tree_node {				//定義搜索樹(shù)節(jié)點(diǎn)
	struct search_tree_node* ch[CHAR_SIZE];		//分類(lèi)
	char desc[DESC_SIZE];						//描述
}STNode;


int get_word(FILE* fp, char* key, char* desc);					//分離文本信息
STNode* new_node();												//新建節(jié)點(diǎn)
int insert_st_tree(STNode** st_tree, char* key, char* desc);	//插入信息
char* find(STNode* st_tree, char* key);							//查找分類(lèi)


int main() {
	char key[KEY_SIZE];
	char desc[DESC_SIZE];
	STNode* st_tree = NULL;
	char* data;

	FILE* fp = fopen(FILE_NAME, "r");
	if (fp == NULL) {
		fprintf(stderr, "fopen error!\n");
		return -1;
	}

	while (1) {
		int res = get_word(fp, key, desc);
		if (res != -1) {
			printf("%s\n", key);
			printf("%s\n", desc);
		}
		else {
			break;
		}
		insert_st_tree(&st_tree, key, desc);
	}

	data = find(st_tree, (char*)"ant");
	if (data != NULL) {
		printf("\nFind description: %s", data);
	}
	else {
		printf("\nCan not find!\n");
	}

	fclose(fp);
	return 0;
}


/*****************************************************************************
* @data  : 2020/4/19
* @brief : 讀取文件，分離關(guān)鍵字和描述信息
* @input :
*   fp	: 文件指針
*	key	: 關(guān)鍵字（返回）
*	desc: 描述信息（返回）
* @output:
*   -1	: 失敗
*	0	: 成功
*****************************************************************************/
int get_word(FILE* fp, char* key, char* desc) {
	int i, j;
	char buff[BUFF_SIZE];
	char* res = fgets(buff, BUFF_SIZE, fp);		//逐行讀?。ò〒Q行符）
	if (res == NULL) {
		return -1;
	}
	for (i = 0; i < KEY_SIZE - 1 && buff[i] != ':'; i++) {	//預(yù)留結(jié)束符，分割標(biāo)志
		key[i] = buff[i];
	}
	key[i] = '\0';
	i++;
	for (j = 0; j < DESC_SIZE - 1 && buff[i] != '\0'; j++, i++) {	//預(yù)留結(jié)束符，結(jié)束標(biāo)志
		desc[j] = buff[i];
	}
	desc[j] = '\0';
	return 0;
}

/*****************************************************************************
* @data  : 2020/4/19
* @brief : 創(chuàng)建新搜索樹(shù)結(jié)點(diǎn)
* @input :
*   none : none
* @output:
*   node : 初始化的新結(jié)點(diǎn)
*****************************************************************************/
STNode* new_node() {
	STNode* node;
	node = (STNode*)malloc(sizeof(STNode));		//分配一個(gè)空間
	if (node == NULL) {
		return NULL;
	}
	for (int i = 0; i < CHAR_SIZE; i++) {		//初始化
		node->ch[i] = NULL;
	}
	node->desc[0] = '\0';
	return node;
}

/*****************************************************************************
* @data  : 2020/4/19
* @brief : 創(chuàng)建搜索樹(shù)
* @input :
*   st_tree	: 二級(jí)指針創(chuàng)建搜索樹(shù)
*	key		: 關(guān)鍵字
*	desc	: 描述信息
* @output:
*   -1		: 失敗
*	0		: 成功
*****************************************************************************/
int insert_st_tree(STNode** st_tree, char* key, char* desc) {
	if (*st_tree == NULL) {
		*st_tree = new_node();
		if (*st_tree == NULL) {
			return -1;
		}
	}
	if (*key == '\0') {
		strcpy((*st_tree)->desc, desc);
		return 0;
	}
	//遞歸創(chuàng)建，因?yàn)橐孕?xiě)英文字母為例（26），ASCII碼減去'a'，得到指針相對(duì)地址（或數(shù)組下標(biāo)）
	return insert_st_tree((*st_tree)->ch + *key - 'a', key + 1, desc);
}

/*****************************************************************************
* @data  : 2020/4/19
* @brief : 使用搜索樹(shù)查詢(xún)關(guān)鍵字描述（有返回，無(wú)）
* @input :
*   st_tree	: 搜索樹(shù)
*	key		: 關(guān)鍵字
* @output:
*   desc	: 描述信息
*	NULL	: 空
*****************************************************************************/
char* find(STNode* st_tree, char* key) {
	if (st_tree == NULL) {	//為空，返回 NULL
		return NULL;
	}
	if (*key == '\0') {		//完全匹配，返回描述信息
		if (st_tree->desc[0] == '\0') {
			return NULL;
		}
		return st_tree->desc;
	}
	return find(st_tree->ch[*key - 'a'], key + 1);	//遞歸查找
}