个人原创，转载请注明出处，谢谢！
一、 目的
如示例：
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）；
评论