### 问题描述 （来源于**《编程珠玑》第2版**的第2章第11页问题 C） Given a dictionary of english words,find all sets of anagrams,For instance, “posts”,”stop”and ”tops” are all anagrams of one another because each can be formed by permuting the letters of the others.[译] 给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。 ### 方案一 按照书上给出的解法，先对每一个单词生成相应的“签名”（“signature”），即把单词中的字母按照字母表的顺序重新排列，例如stop 重新排列成opst , 然后把有相同signature的单词归为一组输出。基本过程如下：  其中sign()函数用于生成每一个单词的”签名“，如何生成呢？由于每个单词的长度一般都很短（不超过10个字母）于是可选择用**直接插入排序法**。其他的数据结构和函数很简单，直接看代码吧！ ### 代码： ~~~ #include<stdio.h> #include<string.h> #define MAX_WORD 100 /* the max length of a word */ #define MAX_NUM 100 /* the max number of words in a dictionary */ struct Word{ char ch[MAX_WORD];/*a word*/ char sig[MAX_WORD];/*signature*/ int flag;/*has been print or not*/ }; struct Word dic[MAX_NUM]; /*put in*/ int putin(); void putout(int count); /*generate a word’s signature */ void sign(int count); void insertSort(char * arr,int left,int right); /* main() */ int main(void){ int count; int i; count=putin(); sign(count); putout(count); return 0; } int putin() { int c=0; while(scanf(“%s”,dic[c].ch)!=EOF) { strcpy(dic[c].sig,dic[c].ch); dic[c].flag=0; c++; } return c; } void sign(int count) { int cnt,i,len; for(cnt=0;cnt<count;cnt++) { len=strlen(dic[cnt].ch); insertSort(dic[cnt].sig,0,len); dic[cnt].sig[len]=‘\0′; } } void insertSort (char * arr,int left,int right){ int i,j; char temp; for(i=left+1;i<right;i++){ if(arr[i-1]>arr[i]){ temp=arr[i]; j=i-1; do{ arr[j+1]=arr[j]; j–; }while(j>=left && arr[j]<temp); arr[j+1]=temp; } } }/* insertSort */ void putout(int cnt) { int i,j; for(i=0;i<cnt;i++){ if(dic[i].flag==0){ printf(“———-%s———-\n“,dic[i].sig); printf(“%s\n“,dic[i].ch); dic[i].flag=1; for(j=0;j<cnt;j++){ if(strcmp(dic[i].sig,dic[j].sig)==0&&dic[j].flag==0){ dic[j].flag=1; printf(“%s\n“,dic[j].ch); } } } } } ~~~ ### 方案二 我们获得的”啊哈！灵机一动“就是标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后，将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题：选择标识和集中具有相同标识的单词。 对第一个问题，我们可以使用基于排序的标识：将单词中的字母按照字母表顺序排列。要解决第二个问题，我们将所有的单词按照其标识的顺序排列。 ### 代码： ~~~ #include <iostream> #include <map> #include <string> #include <fstream> using namespace std; int compare_string(const void *a,const void *b){ return *((char*)(a)) - *((char*)(b)); } void FindAnagram(char *file_name){ ifstream in_file(file_name); string word_sort; string word; multimap<string,string> word_map; while(in_file>>word){ word_sort = word; qsort(word_sort.begin(),word_sort.length(),sizeof(char),compare_string); word_map.insert(make_pair(word_sort,word)); } multimap<string,string>::const_iterator iter = word_map.begin(); multimap<string,string>::const_iterator iter_end = word_map.end(); while(iter_end != iter){ cout<<iter->first<<":"<<iter->second<<endl; ++iter; } } int main(){ FindAnagram("f://data.txt"); return 0; } ~~~ **转载请注明出处：**[http://blog.csdn.net/utimes/article/details/8760350](http://blog.csdn.net/utimes/article/details/8760350)