快捷導(dǎo)航

使用C語(yǔ)言實(shí)現(xiàn)模糊搜索功能

更新時(shí)間：2018年08月14日 14:33:17 投稿：mrr

本文所提到的模糊搜索是指輸入不完整的關(guān)鍵詞即可查詢(xún)到對(duì)應(yīng)的全部準(zhǔn)確結(jié)果。下面小編通過(guò)實(shí)例代碼給大家分享使用C語(yǔ)言實(shí)現(xiàn)模糊搜索功能，感興趣的朋友一起看看吧

例如：輸入“天”即可將所有姓名中帶有“天”字的人搜索出來(lái)；輸入“0809”即可將所有ID中帶有“0809”片段的人搜索出來(lái)。

這種搜索技術(shù)被廣泛應(yīng)用于各大有查詢(xún)功能的軟件，為用戶提供了極大的方便。在眾多的QQ/微信好友中，輸入想要查找的聯(lián)系人的姓名的一部分即可查找到該聯(lián)系人，是不是很方便呢？在excel中，即使只記住了查詢(xún)對(duì)象的幾個(gè)字，也能夠通過(guò)這種查找方式查詢(xún)到對(duì)應(yīng)的對(duì)象，是不是彌補(bǔ)了你的健忘癥呢？

實(shí)現(xiàn)模糊搜索算法的思路：輸入的關(guān)鍵詞即為一個(gè)字符數(shù)組（字符串），本文將以"abcdef"這個(gè)字符串為例。要想完成對(duì)片段的查詢(xún)，不能僅僅從前往后比對(duì)，也不能僅僅從后往前比對(duì)，而是要將所有的片段都進(jìn)行一遍比對(duì)。這就要求要將字符串的所有連續(xù)子片段都找出來(lái)存放到一個(gè)新的線性結(jié)構(gòu)中，通過(guò)對(duì)新線性結(jié)構(gòu)的遍歷并使用字符串比較函數(shù)strcmp進(jìn)行模糊搜索。

那么"abcdef"這個(gè)字符串到底有多少個(gè)連續(xù)子片段呢？我們按照子片段的長(zhǎng)度挨個(gè)找規(guī)律，按長(zhǎng)度由大到小進(jìn)行：長(zhǎng)度為6的就只有"abcdef"這1個(gè)；長(zhǎng)度為5的有2個(gè)："abcde"和"bcdef"；長(zhǎng)度為4的有3個(gè)："abcd"、"bcde"和"cdef"；長(zhǎng)度為3的有4個(gè)；長(zhǎng)度為2的有5個(gè)；長(zhǎng)度為1的有6個(gè)。所以一共有1+2+3+4+5+6=21個(gè)。想必看到這里大家已經(jīng)找到了規(guī)律：若關(guān)鍵詞的長(zhǎng)度為n，則該關(guān)鍵詞的連續(xù)子字符串的個(gè)數(shù)就為1+2+3+...+n。

以下函數(shù)用作判斷是否符合篩選條件，其中key為關(guān)鍵詞。

//模糊搜索判斷是否符合篩選條件
int result_mohu(const gchar* key,char* str)
{
  typedef struct
  {
    char son[11];
  }Element;
  int i,j,k=0,l=0,m=0;
  //f=1為符合篩選條件
  int f=0;
 //N1為str的長(zhǎng)度 N2為str連續(xù)子串的個(gè)數(shù)
 int N1=0,N2=0;
 N1=strlen(str);
 /*計(jì)算連續(xù)子串的個(gè)數(shù)*/
 for(i=1;i<=N1;i++)
  N2+=i;
  /*計(jì)算連續(xù)子串的個(gè)數(shù)*/
  //i控制子字符串的長(zhǎng)度
  //j控制賦值
  //k控制新的線性結(jié)構(gòu)b的下標(biāo)
  //l控制子數(shù)組的首項(xiàng)在原數(shù)組中的位置
  //m控制即將用作賦值的str的下標(biāo)
  Element *b=malloc(sizeof(Element)*N2);
  for(i=1;i<=N1;i++)
  {
    l=0;
    /*while循環(huán)內(nèi)為給一個(gè)子字符串?dāng)?shù)組賦值*/
    while(1)
      {
      m=l;
      for(j=0;j<i;j++)
      {
        b[k].son[j]=str[m];
        m++;
      }
      l++;
      k++;
      if(m==N1)
        break;
      }
  }
  //挨個(gè)比對(duì)
  for(i=0;i<N2;i++)
    if(strcmp(key,b[i].son)==0)
    {
      f=1;
      break;
    }
  free(b);
  return f;
}

若返回值f=1則表示符合篩選條件，即查詢(xún)對(duì)象含有包含關(guān)鍵詞的片段。最為關(guān)鍵的循環(huán)就是按照子字符串的長(zhǎng)度從1到N1(查詢(xún)對(duì)象字符串的長(zhǎng)度)。

以下片段為遍歷代碼，可看可不看，核心算法都在上面。注：博主實(shí)現(xiàn)模糊搜索的環(huán)境是linux系統(tǒng)下的gtk開(kāi)發(fā)。

//按學(xué)號(hào)查找界面的<查找>
void on_button_idsearch_clicked(GtkObject* widget,gpointer user_data)
{
 int i;
 int f=0;
 GtkTreeIter iter;
 //獲取搜索關(guān)鍵字
 const gchar* keywords = gtk_entry_get_text(entry_search_id);
 gtk_list_store_clear(liststore2);
 for(i=0;i<size1;i++)
  if(result_mohu(keywords,stu1[i].id)==1)
   {    
    gtk_list_store_append(liststore2,&iter);
    gtk_list_store_set(liststore2,&iter,0,stu1[i].no,-1);
    gtk_list_store_set(liststore2,&iter,1,stu1[i].id,-1);
    gtk_list_store_set(liststore2,&iter,2,stu1[i].name,-1);
    gtk_list_store_set(liststore2,&iter,3,stu1[i].math,-1);
    gtk_list_store_set(liststore2,&iter,4,stu1[i].c_language,-1);
    gtk_list_store_set(liststore2,&iter,5,stu1[i].daolun,-1);
    gtk_list_store_set(liststore2,&iter,6,stu1[i].english,-1);
    gtk_list_store_set(liststore2,&iter,7,stu1[i].pe,-1);
    gtk_list_store_set(liststore2,&iter,8,stu1[i].history,-1);
    gtk_list_store_set(liststore2,&iter,9,stu1[i].daoyuan,-1);
    gtk_list_store_set(liststore2,&iter,10,stu1[i].banzhuren,-1);
    gtk_list_store_set(liststore2,&iter,11,stu1[i].score_classmate,-1);
    gtk_list_store_set(liststore2,&iter,12,stu1[i].sum,-1);
    f=1;
   }
 if(f==0)
  gtk_widget_show(GTK_WIDGET(window_noresult));
}

最后給大家看一下實(shí)驗(yàn)結(jié)果：