变位词实现

### 问题描述 （来源于**《编程珠玑》第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 #include #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;cntarr[i]){ temp=arr[i]; j=i-1; do{ arr[j+1]=arr[j]; j–; }while(j>=left && arr[j] #include