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

评论