前些日子做了一个输入法,用到键树研究了一下,此树又叫字典树。#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

评论