个人原创，转载请注明出处，谢谢！

一、 目的

如示例：

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）；