Autocomplete的字典建立和单词查找算法实现.

//说明：使用有序链表实现，单词插入的复杂度和查找的时间复杂度均为O(n)，
#include <windows.h>
#include <math.h>
#include <iostream>
#include <list>
#include <string>

#define ASSERT(x) if(!(x)){throw 0;}
void TRACE(const char *szFormat,

)
{
    va_list l;
    char s[1000];

    va_start(l,szFormat);
    vsprintf(s,szFormat,l);
    OutputDebugString(s);
}

using namespace std;

typedef list<string> STRLIST;

//MS笔试题：AutoComplete字典的插入单词，和查找类似单词的实现
//说明：如果查询的单词长度小于等于当前单词，且strnicmp(两个单词，较短的长度)==0，则认为是类似单词
//用有序链表保存单词,测试成功
namespace Dictionary2
{
    struct LISTNODE
    {
        char data[100];
        LISTNODE *next;
    };

    BOOL InsertWord(LISTNODE *&root,const char *word)
    {
        int n=strlen(word);
        ASSERT(n>0 && n<100);

        if(!root)
        {
            root=new LISTNODE;
            strcpy(root->data,word);
            root->next=0;
            return TRUE;
        }

        LISTNODE *p=root;
        LISTNODE *p1=0; //前一个指针
        while (p)
        {
            //cout<<(DWORD)p<<endl;
            int n2=strlen(p->data);
            int nm=min(n,n2);
            int icmp=strnicmp(word,p->data,nm);

            if(icmp<0 || (icmp==0 && n<n2))
            {
                break;
            }
            else if(icmp==0 && n==n2)
            {
                return FALSE;
            }

            p1=p;
            p=p->next;
        }

        LISTNODE *p2=new LISTNODE;
        strcpy(p2->data,word);

        if (p1)
        {
            TRACE("插入到%s之后",p1->data);

            p2->next = p1->next;
            p1->next=p2;
        }
        else
        {
            //插入到跟指针出
            p2->next=root;
            root=p2;
        }

        return TRUE;
    }

    void Traverse(LISTNODE *root)
    {
        while (root)
        {
            cout<<root->data<<endl;
            root = root->next;
        }
    }

    void/*STRLIST*/ FindWord(LISTNODE *root,const char *word)
    {
        //STRLIST sl;
        if (root)
        {
            int n=strlen(word);

            LISTNODE *p=root;
            LISTNODE *p1=0;
            int step=0;
            while (p)
            {
                int n2=strlen(p->data);
                int nm=min(n,n2);
                int icmp=strnicmp(word,p->data,nm);

                if (icmp==0 && n<=n2)
                {
                    //sl.push_back(p->data);
                    cout <<p->data <<endl;
                }
                else if(icmp<0)
                    break;

                p1=p;
                p=p->next;
            }
        }
    }
    void Test()
    {
        LISTNODE *root=0;

        InsertWord(root,"abc");
        InsertWord(root,"abcd");
        InsertWord(root,"abcc");
        InsertWord(root,"zxabc");
        InsertWord(root,"a");
        InsertWord(root,"ab");
        InsertWord(root,"ac");
        InsertWord(root,"cb");
        InsertWord(root,"bc");
        InsertWord(root,"bxs");
        InsertWord(root,"ba");
        InsertWord(root,"baa");
        InsertWord(root,"bsxa");

        Traverse(root);

        char word[100];

        strcpy(word,"ab");
        cout<<"查找单词"<<word <<endl;
        FindWord(root,word);

        strcpy(word,"b");
        cout<<"查找单词"<<word <<endl;
        FindWord(root,word);
    }
}

Published on Nov 08, 2007 in categories