个人原创,转载请注明出处,谢谢!
一、 目的
如示例:
input: 单词文件
output: 同位词归类文件
constrain: 归类所有为同位词的单词
何为同位词:单词字母相同,但字母的顺序不同:
pans 和snap是同位词
pots 、stop和tops是同位词,还有这些:
二、算法原理
如果我们输入如下单词序列,并期望对该序列进行同位词归类:
第一步:对每个单词进行签名。如这些单词:
我们使用每个单词的字母序列(按字母顺序进行排列)作为它的个人签名,如pans的签名是 anps,这样我们可以得到上图右侧的签名序列。
第二步:对签名序列进行排序。如下图:
通过对签名序列进行排序后,大家可以发现同位词聚在了一起,我们只需要将具有相同签名的单词合并在一起即可。
第三步:对排序后的签名序列进行挤压:
这样我们通过三步即完成了同位词的查找过程,实现代码其实很简单,但其算法思想给人眼前一亮的感觉。
三、代码
Sign.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100
int charcomp (char *x, char *y)
{ return *x - *y;
}
int main()
{ char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) != EOF) {
strcpy(sig, word);
qsort(sig, strlen(sig), sizeof(char), charcomp);
printf("%s %s\n", sig, word);
}
return 0;
}
Squash.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100
int main()
{ char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];
int linenum = 0;
strcpy(oldsig, "");
while (scanf("%s %s", sig, word) != EOF) {
if (strcmp(oldsig, sig) != 0 && linenum > 0)
printf("\n");
strcpy(oldsig, sig);
linenum++;
printf("%s ", word);
}
printf("\n");
return 0;
}
四、代码注解
Sign.c :
/*签名文件的源程序*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100
/*qsort的字符排序函数*/
int charcomp (char *x, char *y)
{ return *x - *y;
}
int main()
{ char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) != EOF) {
strcpy(sig, word);
/*对每个单词的字母按字母顺序排序,以作为其签名*/
qsort(sig, strlen(sig), sizeof(char), charcomp);
/*形成: 签名 单词字符串输出,如 anps pans*/
printf("%s %s\n", sig, word);
}
return 0;
}
Squash.c:
/*本程序将签名相同的单词序列进行挤压,从而使同位词在一行上*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100
int main()
{ char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];
int linenum = 0;
strcpy(oldsig, "");
while (scanf("%s %s", sig, word) != EOF) {
/*如果签名不同则说明该单词与之前的单词不是同位词,故换行开如进行下一组同位词的归类,如上例中的anps签名的同位词完成后,开始进行另一组opt的归类*/
if (strcmp(oldsig, sig) != 0 && linenum > 0)
printf("\n");
strcpy(oldsig, sig);
linenum++;
printf("%s ", word); /*将同位词串起来,让它们在一行上*/
}
printf("\n");
return 0;
}
五、代码执行方法
Sign < dictionary.txt | sort | squash > result.txt
说明:
l 将单词文件dictionary.txt输入到sign中(Sign < dictionary.txt);
l 使用系统工具sort完成排序工作(| sort);
l 将排序后的结果,作为squash的输入进行挤压,挤压后的结果输出到result.txt中(| squash > result.txt);
评论