字典树
#ifndef TIRE_H_INCLUDED
#define TIRE_H_INCLUDED
/*
** 字典树
*/
#define MAX 26
typedef struct Node
{
int num;
struct Node* next[MAX];
}Tire;
/*
** 创建一个节点
*/
Tire* create(void);
/*
** 插入一个字符串
*/
Tire* insert(char str[], Tire* head);
/*
** 搜索字符串
*/
int search(char str[], Tire* head);
#endif // TIRE_H_INCLUDED
/*---------------------------------------------------------------------------------- * Project: Tire.cpp * Name: zwp * Date: 2014/5 *---------------------------------------------------------------------------------*/ #include#include #include #include "Tire.h" #include /* ** 创建一个节点 */ Tire* create(void) { int i; Tire* node = (Tire*)malloc(sizeof(Tire)); if(node == NULL) printf("Out of space...\n"); /* 初始化 */ for(i = 0; i < MAX; ++ i) node->next[i] = NULL; node->num = 0; return node; } /* ** 插入一个字符串 */ Tire* insert(char str[], Tire* head) { int i, len = strlen(str); Tire *node, *ptr = head; for(i = 1; i < len; ++ i) { int count = str[i] - 'a'; /* 若不存在该字符串 */ if(ptr->next[count] == NULL) { node = create(); ptr->next[count] = node; ptr->num++; ptr = ptr->next[count]; } /* 若存在该字符串 */ else { ptr = ptr->next[count]; } } } /* ** 搜索字符串,返回该字符串出现的次数 */ int search(char str[], Tire* head) { Tire* ptr = head; int len = strlen(str); int i, count = 0; for(i = 0; i < len; ++ i) { int cou = str[i] - 'a'; if(ptr->next[cou] == NULL) { printf("不存在该字符串\n"); count = 0; return 0; } else { ptr = ptr->next[cou]; count = ptr->num; } } return count; }
/*------------------------------------------------------------------------------ * Project: Main.cpp * Name: zwp * Date: 20145/ *------------------------------------------------------------------------------*/ #include "Tire.h" #include#include #include int main(int argc, char* argv[]) { Tire* node = create(); char str[10]; while(scanf("%s\n", str) ) { if(strcmp(str, "quit") == 0) break; insert(str, node); } int count = search("a", node); printf("%d\n", count); system("pause"); return 0; }