快捷導(dǎo)航

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

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

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

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

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

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

那么"abcdef"這個字符串到底有多少個連續(xù)子片段呢？我們按照子片段的長度挨個找規(guī)律，按長度由大到小進(jìn)行：長度為6的就只有"abcdef"這1個；長度為5的有2個："abcde"和"bcdef"；長度為4的有3個："abcd"、"bcde"和"cdef"；長度為3的有4個；長度為2的有5個；長度為1的有6個。所以一共有1+2+3+4+5+6=21個。想必看到這里大家已經(jīng)找到了規(guī)律：若關(guān)鍵詞的長度為n，則該關(guān)鍵詞的連續(xù)子字符串的個數(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的長度 N2為str連續(xù)子串的個數(shù)
 int N1=0,N2=0;
 N1=strlen(str);
 /*計算連續(xù)子串的個數(shù)*/
 for(i=1;i<=N1;i++)
  N2+=i;
  /*計算連續(xù)子串的個數(shù)*/
  //i控制子字符串的長度
  //j控制賦值
  //k控制新的線性結(jié)構(gòu)b的下標(biāo)
  //l控制子數(shù)組的首項在原數(shù)組中的位置
  //m控制即將用作賦值的str的下標(biāo)
  Element *b=malloc(sizeof(Element)*N2);
  for(i=1;i<=N1;i++)
  {
    l=0;
    /*while循環(huán)內(nèi)為給一個子字符串?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;
      }
  }
  //挨個比對
  for(i=0;i<N2;i++)
    if(strcmp(key,b[i].son)==0)
    {
      f=1;
      break;
    }
  free(b);
  return f;
}

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

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

//按學(xué)號查找界面的<查找>
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));
}

最后給大家看一下實驗結(jié)果：