字典树 trie树 学习

/*
 字典树学习：
 
 输入n个单词  举出一个单词出现的次数。
 
 10
 
 apple
 ppppp
 hello
 hello
 need
 bee
 bee
 none
 you
 apple
 
 
 need
 ==1
 ==Program ended with exit code: 0
 
 */
//
//  main.cpp
//  CPlusDemo
//
//  Created by HF on 2018/5/15.
//  Copyright © 2018年 HF-Liqun. All rights reserved.
//

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using  namespace std;

#define MAX 26    //the total number of alphabet is 26, a...z

struct DicTrie{
    bool isTerminal;//是否是单词结束标志
    int  count;     //当前字符串出现次数
    struct DicTrie *next[MAX ]; //每个节点 最多 有 MAX 个孩子节点 结构体嵌套
}   ;

DicTrie *root = NULL; // 根节点是一个空节点 特此声明并赋值

int init()            //初始化链表,有对空间要求的 可选用该方法进行初始化
{
    root = new DicTrie;
    root->count = 0;
    for (int  i = 0; i < MAX; i ++) {
        root->next[i] = NULL; // 空节点
        root->isTerminal = false; //
    }
    return 0;
}

bool isFindTrie(char *targetString) //判断是否能在字典树中查到目标串
{
    int len = strlen(targetString);
    DicTrie *head = root;
    for (int i = 0; i < len; i ++) {
        int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
        if (head->next[res] == NULL) { //如果是空节点 则为否 结束查找
            return false;
        } else {//不为空 更新头指针 以便继续往下查找
            head = head->next[res];
        }
    }
    if (head->count > 0) {
        return true;
    }
    return false;
}

int findTrieCount(char *targetString) //判断是否能在字典树中查到目标串
{
    int len = strlen(targetString);
    DicTrie *head = root;
    for (int i = 0; i < len; i ++) {
        int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
        if (head->next[res] == NULL) { //如果是空节点 则为否 结束查找
            return false;
        } else {//不为空 更新头指针 以便继续往下查找
            head = head->next[res];
        }
    }
    return head->count;
}

int insertTrie(char *targetString)
{
    int len = strlen(targetString);
    DicTrie *head = root;
    for (int i = 0; i < len; i ++) {
        int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
        if (head->next[res] == NULL) { //如果是空节点
            head->next[res] = new DicTrie;//则插入新节点元素
            head = head->next[res]; //更新头指针 并初始化
            head->count = 0;        //
            for (int j = 0; j < MAX; j ++) {
                head->next[j] = NULL;
                head->isTerminal = false;
            }
        } else {
            head = head->next[res];
        }
    }
    head->count ++;//每次插入一个，响应计数都增加1
    head->isTerminal = true;
    return head->count;
}

int deleteTrie(char *targetString)
{
    int len = strlen(targetString);
    DicTrie *head = root;
    for (int i = 0; i < len; i ++) {
        int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
        if (head->next[res] == NULL) { //如果是空节点 表示删除的字符串不在字典中
            return 0;
        } else { //继续查找
            head = head->next[res];
        }
    }
    head->count --;//每次删除一个，响应计数都-1
    if (head->count <= 0) {
        head->count = 0;
        head->isTerminal = false;
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int n;
    char targetString[20];
    
    init();
    
    scanf("%d",&n); //n 组数据
    for (int i = 0; i < n; i ++) {
        scanf("%s",targetString);
        //字符串插入字典树
        insertTrie(targetString);//插入方法
    }
    scanf("%s",targetString);
    printf("==%d\n",findTrieCount(targetString));//查找方法
    
    return 0;
}