//說明：使用有序鏈表實(shí)現(xiàn)，單詞插入的復(fù)雜度和查找的時間復(fù)雜度均為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字典的插入單詞，和查找類似單詞的實(shí)現(xiàn)
//說明：如果查詢的單詞長度小于等于當(dāng)前單詞，且strnicmp(兩個單詞，較短的長度)==0，則認(rèn)為是類似單詞
//用有序鏈表保存單詞,測試成功
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);
????}
}

總結(jié)

以上是生活随笔為你收集整理的AutoComplete的字典建立和单词查找算法实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。