前些日子做了一个输入法,用到键树研究了一下,此树又叫字典树。
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<windows.h>
#include<fstream>
using namespace std;
//数据结构:
//以键树为数据结构,采用孩子兄弟链表存储
typedef struct Node
{
    char ch;                 //存拼音字母
    int Count;                 //存以ch为前缀的拼音数
    int Index;                 //存第一个以ch为前缀的索引
    struct Node* pChild;          //子结点
    struct Node* pBrother;          //兄弟结点
}PinYin, *pPinYin;

typedef PinYin const* cpPinYin;

//拼音森林,每个开头的字母为一棵树
PinYin PinYinTree[26];

//初始化每棵树的根
void Init()
{
    int i;
    for(i = 0; i < 26; ++i){
        PinYinTree[i].ch = 'a'+i;
        PinYinTree[i].Count=1;
        PinYinTree[i].Index=-1;
        PinYinTree[i].pChild=NULL;
        PinYinTree[i].pBrother=NULL;
    }
}

//算法
//pCur为当前结点指针,pTemp为临时结点指针,idCur表示当前字符在字符串中的下标,i表示字符串的索引
//1.根据第一个字母定位于第j个森林:若当前索引为－1,Index=i; Count++,idCur++,pCur=&PinYinTree[j];
//2.从第二个字母开始,判断pCur->pChild是否为空;
//3.根据第2步,若pCur->pChild不为空,则置pCur=p->pChild找pCur的兄弟结点的ch是否与idCur相同;
//若找pTemp到则置pCur=pTemp,pTemp->Count++,idCur++;
//否则新建结点pNew,pNew->Count=1,pNew->ch=idCur,pNew->index=i,pCur->pBrother=pNew,pCur=pNew;
//4.根据第2步,若pCur为空则新建结点pNew,pNew->Count=0,pNew->ch=idCur
//pNew->index=i,pCur->pChild=pNew,pCur=pNew;
//5.依次处理2-4,直到字符串尾
//6.依次处理1-5,直到处理完所有字符串

void CreateTree(const vector<string>& vecString)
{
    int i, size, sizeTemp;
    int idTemp, idCur;
    pPinYin pCur, pTemp, pNew;
    size = vecString.size();
    Init();
    for(i = 0; i < size; ++i){
        sizeTemp = vecString[i].size();
          //确定第一个字符在森林中的位置
        idTemp = vecString[i][0]-'a';
          //存储第一个以第一个字符为前缀的字符串索引
        if(PinYinTree[idTemp].Index==-1)
            PinYinTree[idTemp].Index=i;
 
        idCur=1;
          //以第一个字符为前缀的字符串数增加
        PinYinTree[idTemp].Count++;
          //当前指针置第i棵树根
        pCur = &PinYinTree[idTemp];
 
        while(idCur != sizeTemp){
               //若当前指针的子树不为空,进入子树查找当前字符是否在子树中出现过
            if(pCur->pChild != NULL){
                pCur = pCur->pChild;
                pTemp = pCur;
                    //循环当前层查找
                while(pTemp != NULL){
                    if(pTemp->ch == vecString[i][idCur])
                        break;
                    pCur = pTemp;
                    pTemp = pTemp->pBrother;
   
                }
                    //当前字符已经出现过
                if(pTemp != NULL){
                    pCur = pTemp;
                    pCur->Count++;
                    idCur++;
                }
                    //当前字符未曾出现过,则新建兄弟结点
                else{
                    pNew = new PinYin();
                    pNew->ch = vecString[i][idCur];
                    idCur++;
                    pNew->Count = 1;
                    pNew->Index = i;
                    pNew->pChild = NULL;
                    pNew->pBrother = NULL;
                    pCur->pBrother = pNew;
                    pCur = pNew;
                }
            }
               //它的子树为空,新建子结点
            else{
                pNew = new PinYin();
                pNew->ch = vecString[i][idCur];
                idCur++;
                pNew->Count = 1;
                pNew->Index = i;
                pNew->pBrother = NULL;
                pNew->pChild = NULL;
                pCur->pChild = pNew;
                pCur = pNew;
            }
        }
    }
}

//删除子树
//采用后序遍历
void DeleteChildTree(pPinYin pChildTree)
{
    //当前指针空返回
    if(pChildTree == NULL) return;
    //子树不为空删除
    if(pChildTree->pChild != NULL){
        DeleteChildTree(pChildTree->pChild);
        pChildTree->pChild = NULL;
    }
    //兄弟树不为空删除
    if(pChildTree->pBrother != NULL){
        DeleteChildTree(pChildTree->pBrother);
        pChildTree->pBrother = NULL;
    }
    delete pChildTree;
}
void DeleteTree()
{
    int i;
    for(i = 0; i < 26; ++i){
      //若第i棵树不为空删除
        if(PinYinTree[i].pChild != NULL){
            DeleteChildTree(PinYinTree[i].pChild);
            PinYinTree[i].pChild = NULL;
        }
    }
}

//字符串比较函数,用来排序字符串
bool str_cmp(const string& first, const string& second)
{
    return first.compare(second) < 0 ? true: false;
}


//算法:采用先序遍历
//1.由当前的宽度和深度画出当前结点
//2.子结点的宽度不变,深度增加2
//3.兄弟结点的深度不变,宽度变成最大宽度加2

//树的最大深度
int MaxDegree;
//树的最大宽度
int MaxWidth;
void DrawChildTree(pPinYin pChildTree, COORD point, HANDLE& hCout)
{
    COORD pt;
    //将指针移到当前坐标点,并打印字符
    SetConsoleCursorPosition(hCout, point);
    cout<<pChildTree->ch;

    //记录最大深度和最大宽度
    if(MaxDegree < point.Y)
        MaxDegree = point.Y;
    if(MaxWidth < point.X)
        MaxWidth = point.X;
    //若树的深度不超过屏幕一页的高度且子树不为空
    if(pChildTree->pChild != NULL && MaxDegree < 205){
        pt = point;
        pt.Y++;
          //子树和父母新结点通过'|'连结
        SetConsoleCursorPosition(hCout, pt);
        cout<<'|';
        pt.Y++;
        DrawChildTree(pChildTree->pChild, pt, hCout);
    }

    //树的宽度不超过屏幕的宽度且兄弟不为空
    if(pChildTree->pBrother != NULL && MaxWidth < 78){
        pt = point;
          //兄弟之间通过'-'连结
        for(pt.X += 1; pt.X <= MaxWidth+2; pt.X++)
        {
            SetConsoleCursorPosition(hCout, pt);
            cout<<'-';
        }
        DrawChildTree(pChildTree->pBrother, pt, hCout);
    }
}
void DrawTree()
{
    HANDLE hCout;
    COORD pt;
    hCout = GetStdHandle(STD_OUTPUT_HANDLE);

    int i;
    MaxDegree = -4;
    for(i = 0; i < 26; ++i){
        i = 0;
        if(PinYinTree[i].pChild != NULL){
               //画出第i个树的根
            MaxWidth = 0;
            pt.Y = MaxDegree+4;
            pt.X = 0;
            SetConsoleCursorPosition(hCout, pt);
            cout<<PinYinTree[i].ch;
            pt.Y++;
            SetConsoleCursorPosition(hCout, pt);
            cout<<'|';
            pt.Y++;
            DrawChildTree(PinYinTree[i].pChild, pt, hCout);
        }
    }
    pt.Y = MaxDegree+2;
    pt.X = 0;
    SetConsoleCursorPosition(hCout, pt);
}


//在键树中查找特定字符串
cpPinYin Search(const string& str)
{
    int idCur, size;
    pPinYin pCur;

    size = str.size();
    idCur = str[0]-'a';
    pCur = &PinYinTree[idCur];
    idCur = 0;
    while(pCur != NULL){
          //已经找到第idCur字符进入子树,否则继续在兄弟结点找
        if(pCur->ch == str[idCur]){
            idCur++;
               //已经到字符串尾退出
            if(idCur == size)
                break;
               //进入子树
            pCur = pCur->pChild;
            continue;
        }
          //继续在兄弟结点找
        pCur = pCur->pBrother;
    }
    return pCur;
}
int main(int argv, char* argc[])
{
    char str[100];
    int i, size;
    double d;
    vector<string> vString;
    LARGE_INTEGER t1,t2,feq;
    cpPinYin pPtr;
   
    //打印读写文件的时间
    QueryPerformanceFrequency(&feq);        //每秒跳动次数
    QueryPerformanceCounter(&t1);        //测前跳动次数
    while(cin>>str){
        if(strcmp(str, "a") == 0) break;
        vString.push_back(str);
    }
    QueryPerformanceCounter(&t2);        //测后跳动次数
    d=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒
    // cout<<"读文件总用时:"<<d<<endl;

    size = vString.size();
    // cout<<size<<endl;

    //打印排序的时间
    QueryPerformanceFrequency(&feq);        //每秒跳动次数
    QueryPerformanceCounter(&t1)        ;//测前跳动次数
    sort(vString.begin(), vString.end(), str_cmp);
    QueryPerformanceCounter(&t2);        //测后跳动次数
    d=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒
    // cout<<"排序总用时:"<<d<<endl;

    int ct=0;
    for(i = 0; i < 200; ++i){
        if(vString[i][1] == 'b')
            ct++;
    }
    // cout<<ct<<endl;
   
    //打印创建键树的时间
    QueryPerformanceFrequency(&feq);        //每秒跳动次数
    QueryPerformanceCounter(&t1);        //测前跳动次数
    CreateTree(vString);
    QueryPerformanceCounter(&t2);        //测后跳动次数
    d=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒
    // cout<<"创建字母树用时:"<<d<<endl;

    //以图形方式输出树
    DrawTree();

    //在键树中搜索
    while(cin>>str){
        if(strcmp(str, "0") == 0)
            break;
        pPtr = Search(str);
    }
   
    //打印删除森林的时间
    QueryPerformanceFrequency(&feq);        //每秒跳动次数
    QueryPerformanceCounter(&t1);        //测前跳动次数
    //DeleteTree();
    QueryPerformanceCounter(&t2);        //测后跳动次数
    d=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒
    // cout<<"删除字母树用时:"<<d<<endl;
    return 0;
}

输入测试数据后的效果:
http://sz.photo.store.qq.com/rurl2=a5ce32e0a040d5e34002a81be4d80be006330b3f488ed96137f7e1904a635a91a118c601943542559524bbc046e3b22673bf7d65479efd26719f3f74d56e40063dc0b00d8aeeab678494459889a352e2ce96c2aa

评论