在一个文本词库里查找相似单词,就是输入一个单词,在词库里找与这个单词相似的单词,由相似度大到小,用最小编辑距离实现C++
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct
{
char english[20];
char chinese[30];
char word_class[10];
} Word;
Word words[8000]; //将词典数组设置成全局的结构体数组
int wordsNum=0; //词典中的词条数目
typedef struct
{
int length;
char english[20];
}st;
st sth[8000];
int N=0;
void readDictionary()
{
FILE *fp;
//将文件中的数据读入到对象数组中
fp = fopen("G:\毕业设计\dictionary.txt","r"); //以输入的方式打开文件
if(fp==NULL) //测试是否成功打开
{
printf("dictionary open error!\n");
exit(1);
}
while (!feof(fp))
{
fscanf(fp, "%s%s%s", words[wordsNum].english, words[wordsNum].chinese,words[wordsNum].word_class);
++wordsNum;
}
fclose(fp);
}
char s1[1000],s2[1000];
int min(int a,int b,int c)
{
int t = a < b ? a : b;
return t < c ? t : c;
}
int editDistance(int len1,int len2)
{
int ** d=new int *[len1+1];
for (int k=0;k<=len1;k++)
{
d[k]=new int [len2+1];
}
int i,j;
for (i = 0;i <= len1;i++)
{
d[i][0] = i;
}
for (j = 0;j <= len2;j++)
{
d[0][j] = j;
}
for (i = 1;i <= len1;i++)
{
for (j = 1;j <= len2;j++)
{
int cost = s1[i] == s2[j] ? 0 : 1;
int deletion = d[i-1][j] + 1;
int insertion = d[i][j-1] + 1;
int substitution = d[i-1][j-1] + cost;
d[i][j] = min(deletion,insertion,substitution);
}
}
return d[len1][len2];
for (int s=0;i<=len1;s++)
{
delete[] d[s];
}
delete[] d;
}
void bubble(int a[],int size) //冒泡排序
{
int i,temp;
for(int pass=1; pass
for(i=0; i
if(a[i]>a[i+1]){
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
void main()
{
//int n;
char key1[20];
char key2[20];
// key1=new char [20];
// key2=new char [20];
readDictionary();
printf("请输入待查找的单词:\n");
scanf("%s",&key1);
for(int num=0;num<wordsNum;num++)
{
int len1,len2;
// readDictionary();
printf("1\n");
//key2=words[num].english;
strcpy(key2,words[num].english);
printf("2\n");
len1=strlen(key1);
len2=strlen(key2);
printf("3\n");
sth[num].length = editDistance(len1,len2);
printf("4\n");
}
printf("输出结果:\n");
bubble(sth[wordsNum].length,wordsNum);
for(int k;k<wordsNum;k++)
{
strcpy(words[k].english,sth[k].english);
}
for(int i=0;i<wordsNum;i++)
{
if(sth[i].length>0&&sth[i].length<4)
printf("%s ---> %s \t %s\n",words[i].english , words[i].word_class, words[i].chinese);
}
}