### 問題描述 （來源于**《編程珠璣》第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)